1	//===---- ADT/IntervalTreeTest.cpp - IntervalTree unit tests --------------===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8
9	#include "llvm/ADT/IntervalTree.h"
10	#include "gtest/gtest.h"
11
12	// The test cases for the IntervalTree implementation, follow the below steps:
13	// a) Insert a series of intervals with their associated mapped value.
14	// b) Create the interval tree.
15	// c) Query for specific interval point, covering points inside and outside
16	// of any given intervals.
17	// d) Traversal for specific interval point, using the iterators.
18	//
19	// When querying for a set of intervals containing a given value, the query is
20	// done three times, by calling:
21	// 1) Intervals = getContaining(...).
22	// 2) Intervals = getContaining(...).
23	// sortIntervals(Intervals, Sorting=Ascending).
24	// 3) Intervals = getContaining(...).
25	// sortIntervals(Intervals, Sorting=Ascending).
26	//
27	// The returned intervals are:
28	// 1) In their location order within the tree.
29	// 2) Smaller intervals first.
30	// 3) Bigger intervals first.
31
32	using namespace llvm;
33
34	namespace {
35
36	// Helper function to test a specific item or iterator.
37	template <typename TPoint, typename TItem, typename TValue>
38	void checkItem(TPoint Point, TItem Item, TPoint Left, TPoint Right,
39	TValue Value) {
40	EXPECT_TRUE(Item->contains(Point));
41	EXPECT_EQ(Item->left(), Left);
42	EXPECT_EQ(Item->right(), Right);
43	EXPECT_EQ(Item->value(), Value);
44	}
45
46	// User class tree tests.
47	TEST(IntervalTreeTest, UserClass) {
48	using UUPoint = unsigned;
49	using UUValue = double;
50	class MyData : public IntervalData<UUPoint, UUValue> {
51	using UUData = IntervalData<UUPoint, UUValue>;
52
53	public:
54	// Inherit Base's constructors.
55	using UUData::UUData;
56	PointType left() const { return UUData::left(); }
57	PointType right() const { return UUData::right(); }
58	ValueType value() const { return UUData::value(); }
59
60	bool left(const PointType &Point) const { return UUData::left(Point); }
61	bool right(const PointType &Point) const { return UUData::right(Point); }
62	bool contains(const PointType &Point) const {
63	return UUData::contains(Point);
64	}
65	};
66
67	using UUTree = IntervalTree<UUPoint, UUValue, MyData>;
68	using UUReferences = UUTree::IntervalReferences;
69	using UUData = UUTree::DataType;
70	using UUAlloc = UUTree::Allocator;
71
72	auto CheckData = [](UUPoint Point, const UUData *Data, UUPoint Left,
73	UUPoint Right, UUValue Value) {
74	checkItem<UUPoint, const UUData *, UUValue>(Point, Item: Data, Left, Right,
75	Value);
76	};
77
78	UUAlloc Allocator;
79	UUTree Tree(Allocator);
80	UUReferences Intervals;
81	UUPoint Point;
82
83	EXPECT_TRUE(Tree.empty());
84	Tree.clear();
85	EXPECT_TRUE(Tree.empty());
86
87	// [10, 20] <- (10.20)
88	// [30, 40] <- (30.40)
89	//
90	// [10...20] [30...40]
91	Tree.insert(Left: 10, Right: 20, Value: 10.20);
92	Tree.insert(Left: 30, Right: 40, Value: 30.40);
93	Tree.create();
94
95	// Invalid interval values: x < [10
96	Point = 5;
97	Intervals = Tree.getContaining(Point);
98	EXPECT_TRUE(Intervals.empty());
99
100	// Valid interval values: [10...20]
101	Point = 10;
102	Intervals = Tree.getContaining(Point);
103	ASSERT_EQ(Intervals.size(), 1u);
104	CheckData(Point, Intervals[0], 10, 20, 10.20);
105
106	Point = 15;
107	Intervals = Tree.getContaining(Point);
108	ASSERT_EQ(Intervals.size(), 1u);
109	CheckData(Point, Intervals[0], 10, 20, 10.20);
110
111	Point = 20;
112	Intervals = Tree.getContaining(Point);
113	ASSERT_EQ(Intervals.size(), 1u);
114	CheckData(Point, Intervals[0], 10, 20, 10.20);
115
116	// Invalid interval values: 20] < x < [30
117	Point = 25;
118	Intervals = Tree.getContaining(Point);
119	EXPECT_TRUE(Intervals.empty());
120
121	// Valid interval values: [30...40]
122	Point = 30;
123	Intervals = Tree.getContaining(Point);
124	ASSERT_EQ(Intervals.size(), 1u);
125	CheckData(Point, Intervals[0], 30, 40, 30.40);
126
127	Point = 35;
128	Intervals = Tree.getContaining(Point);
129	ASSERT_EQ(Intervals.size(), 1u);
130	CheckData(Point, Intervals[0], 30, 40, 30.40);
131
132	Point = 40;
133	Intervals = Tree.getContaining(Point);
134	ASSERT_EQ(Intervals.size(), 1u);
135	CheckData(Point, Intervals[0], 30, 40, 30.40);
136
137	// Invalid interval values: 40] < x
138	Point = 45;
139	Intervals = Tree.getContaining(Point);
140	EXPECT_TRUE(Intervals.empty());
141	}
142
143	using UUPoint = unsigned; // Interval endpoint type.
144	using UUValue = unsigned; // Mapped value type.
145
146	using UUTree = IntervalTree<UUPoint, UUValue>;
147	using UUReferences = UUTree::IntervalReferences;
148	using UUData = UUTree::DataType;
149	using UUSorting = UUTree::Sorting;
150	using UUPoint = UUTree::PointType;
151	using UUValue = UUTree::ValueType;
152	using UUIter = UUTree::find_iterator;
153	using UUAlloc = UUTree::Allocator;
154
155	void checkData(UUPoint Point, const UUData *Data, UUPoint Left, UUPoint Right,
156	UUValue Value) {
157	checkItem<UUPoint, const UUData *, UUValue>(Point, Item: Data, Left, Right, Value);
158	}
159
160	void checkData(UUPoint Point, UUIter Iter, UUPoint Left, UUPoint Right,
161	UUValue Value) {
162	checkItem<UUPoint, UUIter, UUValue>(Point, Item: Iter, Left, Right, Value);
163	}
164
165	// Empty tree tests.
166	TEST(IntervalTreeTest, NoIntervals) {
167	UUAlloc Allocator;
168	UUTree Tree(Allocator);
169	EXPECT_TRUE(Tree.empty());
170	Tree.clear();
171	EXPECT_TRUE(Tree.empty());
172
173	// Create the tree and switch to query mode.
174	Tree.create();
175	EXPECT_TRUE(Tree.empty());
176	EXPECT_EQ(Tree.find(1), Tree.find_end());
177	}
178
179	// One item tree tests.
180	TEST(IntervalTreeTest, OneInterval) {
181	UUAlloc Allocator;
182	UUTree Tree(Allocator);
183	UUReferences Intervals;
184	UUPoint Point;
185
186	// [10, 20] <- (1020)
187	//
188	// [10...20]
189	Tree.insert(Left: 10, Right: 20, Value: 1020);
190
191	EXPECT_TRUE(Tree.empty());
192	Tree.create();
193	EXPECT_FALSE(Tree.empty());
194
195	// Invalid interval values: x < [10.
196	Point = 5;
197	Intervals = Tree.getContaining(Point);
198	EXPECT_TRUE(Intervals.empty());
199
200	// Valid interval values: [10...20].
201	Point = 10;
202	Intervals = Tree.getContaining(Point);
203	ASSERT_EQ(Intervals.size(), 1u);
204	checkData(Point, Data: Intervals[0], Left: 10, Right: 20, Value: 1020);
205
206	Point = 15;
207	Intervals = Tree.getContaining(Point);
208	ASSERT_EQ(Intervals.size(), 1u);
209	checkData(Point, Data: Intervals[0], Left: 10, Right: 20, Value: 1020);
210
211	Point = 20;
212	Intervals = Tree.getContaining(Point);
213	ASSERT_EQ(Intervals.size(), 1u);
214	checkData(Point, Data: Intervals[0], Left: 10, Right: 20, Value: 1020);
215
216	// Invalid interval values: 20] < x
217	Point = 25;
218	Intervals = Tree.getContaining(Point);
219	EXPECT_TRUE(Intervals.empty());
220	}
221
222	// Two items tree tests. No overlapping.
223	TEST(IntervalTreeTest, TwoIntervals) {
224	UUAlloc Allocator;
225	UUTree Tree(Allocator);
226	UUReferences Intervals;
227	UUPoint Point;
228
229	// [10, 20] <- (1020)
230	// [30, 40] <- (3040)
231	//
232	// [10...20] [30...40]
233	Tree.insert(Left: 10, Right: 20, Value: 1020);
234	Tree.insert(Left: 30, Right: 40, Value: 3040);
235	Tree.create();
236
237	// Invalid interval values: x < [10
238	Point = 5;
239	Intervals = Tree.getContaining(Point);
240	EXPECT_TRUE(Intervals.empty());
241
242	// Valid interval values: [10...20]
243	Point = 10;
244	Intervals = Tree.getContaining(Point);
245	ASSERT_EQ(Intervals.size(), 1u);
246	checkData(Point, Data: Intervals[0], Left: 10, Right: 20, Value: 1020);
247
248	Point = 15;
249	Intervals = Tree.getContaining(Point);
250	ASSERT_EQ(Intervals.size(), 1u);
251	checkData(Point, Data: Intervals[0], Left: 10, Right: 20, Value: 1020);
252
253	Point = 20;
254	Intervals = Tree.getContaining(Point);
255	ASSERT_EQ(Intervals.size(), 1u);
256	checkData(Point, Data: Intervals[0], Left: 10, Right: 20, Value: 1020);
257
258	// Invalid interval values: 20] < x < [30
259	Point = 25;
260	Intervals = Tree.getContaining(Point);
261	EXPECT_TRUE(Intervals.empty());
262
263	// Valid interval values: [30...40]
264	Point = 30;
265	Intervals = Tree.getContaining(Point);
266	ASSERT_EQ(Intervals.size(), 1u);
267	checkData(Point, Data: Intervals[0], Left: 30, Right: 40, Value: 3040);
268
269	Point = 35;
270	Intervals = Tree.getContaining(Point);
271	ASSERT_EQ(Intervals.size(), 1u);
272	checkData(Point, Data: Intervals[0], Left: 30, Right: 40, Value: 3040);
273
274	Point = 40;
275	Intervals = Tree.getContaining(Point);
276	ASSERT_EQ(Intervals.size(), 1u);
277	checkData(Point, Data: Intervals[0], Left: 30, Right: 40, Value: 3040);
278
279	// Invalid interval values: 40] < x
280	Point = 45;
281	Intervals = Tree.getContaining(Point);
282	EXPECT_TRUE(Intervals.empty());
283	}
284
285	// Three items tree tests. No overlapping.
286	TEST(IntervalTreeTest, ThreeIntervals) {
287	UUAlloc Allocator;
288	UUTree Tree(Allocator);
289	UUReferences Intervals;
290	UUPoint Point;
291
292	// [10, 20] <- (1020)
293	// [30, 40] <- (3040)
294	// [50, 60] <- (5060)
295	//
296	// [10...20] [30...40] [50...60]
297	Tree.insert(Left: 10, Right: 20, Value: 1020);
298	Tree.insert(Left: 30, Right: 40, Value: 3040);
299	Tree.insert(Left: 50, Right: 60, Value: 5060);
300	Tree.create();
301
302	// Invalid interval values: x < [10
303	Point = 5;
304	Intervals = Tree.getContaining(Point);
305	EXPECT_TRUE(Intervals.empty());
306
307	// Valid interval values: [10...20]
308	Point = 10;
309	Intervals = Tree.getContaining(Point);
310	ASSERT_EQ(Intervals.size(), 1u);
311	checkData(Point, Data: Intervals[0], Left: 10, Right: 20, Value: 1020);
312
313	Point = 15;
314	Intervals = Tree.getContaining(Point);
315	ASSERT_EQ(Intervals.size(), 1u);
316	checkData(Point, Data: Intervals[0], Left: 10, Right: 20, Value: 1020);
317
318	Point = 20;
319	Intervals = Tree.getContaining(Point);
320	ASSERT_EQ(Intervals.size(), 1u);
321	checkData(Point, Data: Intervals[0], Left: 10, Right: 20, Value: 1020);
322
323	// Invalid interval values: 20] < x < [30
324	Point = 25;
325	Intervals = Tree.getContaining(Point);
326	EXPECT_TRUE(Intervals.empty());
327
328	// Valid interval values: [30...40]
329	Point = 30;
330	Intervals = Tree.getContaining(Point);
331	ASSERT_EQ(Intervals.size(), 1u);
332	checkData(Point, Data: Intervals[0], Left: 30, Right: 40, Value: 3040);
333
334	Point = 35;
335	Intervals = Tree.getContaining(Point);
336	ASSERT_EQ(Intervals.size(), 1u);
337	checkData(Point, Data: Intervals[0], Left: 30, Right: 40, Value: 3040);
338
339	Point = 40;
340	Intervals = Tree.getContaining(Point);
341	ASSERT_EQ(Intervals.size(), 1u);
342	checkData(Point, Data: Intervals[0], Left: 30, Right: 40, Value: 3040);
343
344	// Invalid interval values: 40] < x < [50
345	Point = 45;
346	Intervals = Tree.getContaining(Point);
347	EXPECT_TRUE(Intervals.empty());
348
349	// Valid interval values: [50...60]
350	Point = 50;
351	Intervals = Tree.getContaining(Point);
352	ASSERT_EQ(Intervals.size(), 1u);
353	checkData(Point, Data: Intervals[0], Left: 50, Right: 60, Value: 5060);
354
355	Point = 55;
356	Intervals = Tree.getContaining(Point);
357	ASSERT_EQ(Intervals.size(), 1u);
358	checkData(Point, Data: Intervals[0], Left: 50, Right: 60, Value: 5060);
359
360	Point = 60;
361	Intervals = Tree.getContaining(Point);
362	ASSERT_EQ(Intervals.size(), 1u);
363	checkData(Point, Data: Intervals[0], Left: 50, Right: 60, Value: 5060);
364
365	// Invalid interval values: 60] < x
366	Point = 65;
367	Intervals = Tree.getContaining(Point);
368	EXPECT_TRUE(Intervals.empty());
369	}
370
371	// One item tree tests.
372	TEST(IntervalTreeTest, EmptyIntervals) {
373	UUAlloc Allocator;
374	UUTree Tree(Allocator);
375	UUReferences Intervals;
376	UUPoint Point;
377
378	// [40, 60] <- (4060)
379	// [50, 50] <- (5050)
380	// [10, 10] <- (1010)
381	// [70, 70] <- (7070)
382	//
383	// [40...............60]
384	// [50...50]
385	// [10...10]
386	// [70...70]
387	Tree.insert(Left: 40, Right: 60, Value: 4060);
388	Tree.insert(Left: 50, Right: 50, Value: 5050);
389	Tree.insert(Left: 10, Right: 10, Value: 1010);
390	Tree.insert(Left: 70, Right: 70, Value: 7070);
391
392	EXPECT_TRUE(Tree.empty());
393	Tree.create();
394	EXPECT_FALSE(Tree.empty());
395
396	// Invalid interval values: x < [10.
397	Point = 5;
398	Intervals = Tree.getContaining(Point);
399	EXPECT_TRUE(Intervals.empty());
400
401	// Valid interval values: [10...10].
402	Point = 10;
403	Intervals = Tree.getContaining(Point);
404	ASSERT_EQ(Intervals.size(), 1u);
405	checkData(Point, Data: Intervals[0], Left: 10, Right: 10, Value: 1010);
406
407	// Invalid interval values: 10] < x
408	Point = 15;
409	Intervals = Tree.getContaining(Point);
410	EXPECT_TRUE(Intervals.empty());
411
412	// Invalid interval values: x < [50.
413	Point = 45;
414	Intervals = Tree.getContaining(Point);
415	ASSERT_EQ(Intervals.size(), 1u);
416	checkData(Point, Data: Intervals[0], Left: 40, Right: 60, Value: 4060);
417
418	// Valid interval values: [50...50].
419	Point = 50;
420	Intervals = Tree.getContaining(Point);
421	ASSERT_EQ(Intervals.size(), 2u);
422	checkData(Point, Data: Intervals[0], Left: 40, Right: 60, Value: 4060);
423	checkData(Point, Data: Intervals[1], Left: 50, Right: 50, Value: 5050);
424
425	// Invalid interval values: 50] < x
426	Point = 55;
427	Intervals = Tree.getContaining(Point);
428	ASSERT_EQ(Intervals.size(), 1u);
429	checkData(Point, Data: Intervals[0], Left: 40, Right: 60, Value: 4060);
430
431	// Invalid interval values: x < [70.
432	Point = 65;
433	Intervals = Tree.getContaining(Point);
434	EXPECT_TRUE(Intervals.empty());
435
436	// Valid interval values: [70...70].
437	Point = 70;
438	Intervals = Tree.getContaining(Point);
439	ASSERT_EQ(Intervals.size(), 1u);
440	checkData(Point, Data: Intervals[0], Left: 70, Right: 70, Value: 7070);
441
442	// Invalid interval values: 70] < x
443	Point = 75;
444	Intervals = Tree.getContaining(Point);
445	EXPECT_TRUE(Intervals.empty());
446	}
447
448	// Simple overlapping tests.
449	TEST(IntervalTreeTest, SimpleIntervalsOverlapping) {
450	UUAlloc Allocator;
451	UUTree Tree(Allocator);
452	UUReferences Intervals;
453	UUPoint Point;
454
455	// [40, 60] <- (4060)
456	// [30, 70] <- (3070)
457	// [20, 80] <- (2080)
458	// [10, 90] <- (1090)
459	//
460	// [40...60]
461	// [30...............70]
462	// [20...........................80]
463	// [10.......................................90]
464	Tree.insert(Left: 40, Right: 60, Value: 4060);
465	Tree.insert(Left: 30, Right: 70, Value: 3070);
466	Tree.insert(Left: 20, Right: 80, Value: 2080);
467	Tree.insert(Left: 10, Right: 90, Value: 1090);
468	Tree.create();
469
470	// Invalid interval values: x < [10
471	Point = 5;
472	Intervals = Tree.getContaining(Point);
473	EXPECT_TRUE(Intervals.empty());
474
475	// Valid interval values:
476	Point = 10;
477	Intervals = Tree.getContaining(Point);
478	ASSERT_EQ(Intervals.size(), 1u);
479	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
480
481	Point = 15;
482	Intervals = Tree.getContaining(Point);
483	ASSERT_EQ(Intervals.size(), 1u);
484	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
485
486	Point = 20;
487	Intervals = Tree.getContaining(Point);
488	ASSERT_EQ(Intervals.size(), 2u);
489	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
490	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
491	Intervals = Tree.getContaining(Point);
492	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
493	ASSERT_EQ(Intervals.size(), 2u);
494	checkData(Point, Data: Intervals[0], Left: 20, Right: 80, Value: 2080);
495	checkData(Point, Data: Intervals[1], Left: 10, Right: 90, Value: 1090);
496	Intervals = Tree.getContaining(Point);
497	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
498	ASSERT_EQ(Intervals.size(), 2u);
499	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
500	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
501
502	Point = 25;
503	Intervals = Tree.getContaining(Point);
504	ASSERT_EQ(Intervals.size(), 2u);
505	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
506	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
507	Intervals = Tree.getContaining(Point);
508	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
509	ASSERT_EQ(Intervals.size(), 2u);
510	checkData(Point, Data: Intervals[0], Left: 20, Right: 80, Value: 2080);
511	checkData(Point, Data: Intervals[1], Left: 10, Right: 90, Value: 1090);
512	Intervals = Tree.getContaining(Point);
513	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
514	ASSERT_EQ(Intervals.size(), 2u);
515	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
516	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
517
518	Point = 30;
519	Intervals = Tree.getContaining(Point);
520	ASSERT_EQ(Intervals.size(), 3u);
521	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
522	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
523	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
524	Intervals = Tree.getContaining(Point);
525	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
526	ASSERT_EQ(Intervals.size(), 3u);
527	checkData(Point, Data: Intervals[0], Left: 30, Right: 70, Value: 3070);
528	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
529	checkData(Point, Data: Intervals[2], Left: 10, Right: 90, Value: 1090);
530	Intervals = Tree.getContaining(Point);
531	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
532	ASSERT_EQ(Intervals.size(), 3u);
533	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
534	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
535	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
536
537	Point = 35;
538	Intervals = Tree.getContaining(Point);
539	ASSERT_EQ(Intervals.size(), 3u);
540	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
541	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
542	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
543	Intervals = Tree.getContaining(Point);
544	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
545	ASSERT_EQ(Intervals.size(), 3u);
546	checkData(Point, Data: Intervals[0], Left: 30, Right: 70, Value: 3070);
547	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
548	checkData(Point, Data: Intervals[2], Left: 10, Right: 90, Value: 1090);
549	Intervals = Tree.getContaining(Point);
550	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
551	ASSERT_EQ(Intervals.size(), 3u);
552	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
553	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
554	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
555
556	Point = 40;
557	Intervals = Tree.getContaining(Point);
558	ASSERT_EQ(Intervals.size(), 4u);
559	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
560	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
561	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
562	checkData(Point, Data: Intervals[3], Left: 40, Right: 60, Value: 4060);
563	Intervals = Tree.getContaining(Point);
564	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
565	ASSERT_EQ(Intervals.size(), 4u);
566	checkData(Point, Data: Intervals[0], Left: 40, Right: 60, Value: 4060);
567	checkData(Point, Data: Intervals[1], Left: 30, Right: 70, Value: 3070);
568	checkData(Point, Data: Intervals[2], Left: 20, Right: 80, Value: 2080);
569	checkData(Point, Data: Intervals[3], Left: 10, Right: 90, Value: 1090);
570	Intervals = Tree.getContaining(Point);
571	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
572	ASSERT_EQ(Intervals.size(), 4u);
573	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
574	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
575	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
576	checkData(Point, Data: Intervals[3], Left: 40, Right: 60, Value: 4060);
577
578	Point = 50;
579	Intervals = Tree.getContaining(Point);
580	ASSERT_EQ(Intervals.size(), 4u);
581	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
582	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
583	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
584	checkData(Point, Data: Intervals[3], Left: 40, Right: 60, Value: 4060);
585	Intervals = Tree.getContaining(Point);
586	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
587	ASSERT_EQ(Intervals.size(), 4u);
588	checkData(Point, Data: Intervals[0], Left: 40, Right: 60, Value: 4060);
589	checkData(Point, Data: Intervals[1], Left: 30, Right: 70, Value: 3070);
590	checkData(Point, Data: Intervals[2], Left: 20, Right: 80, Value: 2080);
591	checkData(Point, Data: Intervals[3], Left: 10, Right: 90, Value: 1090);
592	Intervals = Tree.getContaining(Point);
593	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
594	ASSERT_EQ(Intervals.size(), 4u);
595	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
596	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
597	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
598	checkData(Point, Data: Intervals[3], Left: 40, Right: 60, Value: 4060);
599
600	Point = 60;
601	Intervals = Tree.getContaining(Point);
602	ASSERT_EQ(Intervals.size(), 4u);
603	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
604	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
605	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
606	checkData(Point, Data: Intervals[3], Left: 40, Right: 60, Value: 4060);
607	Intervals = Tree.getContaining(Point);
608	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
609	ASSERT_EQ(Intervals.size(), 4u);
610	checkData(Point, Data: Intervals[0], Left: 40, Right: 60, Value: 4060);
611	checkData(Point, Data: Intervals[1], Left: 30, Right: 70, Value: 3070);
612	checkData(Point, Data: Intervals[2], Left: 20, Right: 80, Value: 2080);
613	checkData(Point, Data: Intervals[3], Left: 10, Right: 90, Value: 1090);
614	Intervals = Tree.getContaining(Point);
615	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
616	ASSERT_EQ(Intervals.size(), 4u);
617	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
618	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
619	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
620	checkData(Point, Data: Intervals[3], Left: 40, Right: 60, Value: 4060);
621
622	Point = 65;
623	Intervals = Tree.getContaining(Point);
624	ASSERT_EQ(Intervals.size(), 3u);
625	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
626	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
627	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
628	Intervals = Tree.getContaining(Point);
629	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
630	ASSERT_EQ(Intervals.size(), 3u);
631	checkData(Point, Data: Intervals[0], Left: 30, Right: 70, Value: 3070);
632	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
633	checkData(Point, Data: Intervals[2], Left: 10, Right: 90, Value: 1090);
634	Intervals = Tree.getContaining(Point);
635	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
636	ASSERT_EQ(Intervals.size(), 3u);
637	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
638	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
639	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
640
641	Point = 70;
642	Intervals = Tree.getContaining(Point);
643	ASSERT_EQ(Intervals.size(), 3u);
644	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
645	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
646	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
647	Intervals = Tree.getContaining(Point);
648	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
649	ASSERT_EQ(Intervals.size(), 3u);
650	checkData(Point, Data: Intervals[0], Left: 30, Right: 70, Value: 3070);
651	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
652	checkData(Point, Data: Intervals[2], Left: 10, Right: 90, Value: 1090);
653	Intervals = Tree.getContaining(Point);
654	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
655	ASSERT_EQ(Intervals.size(), 3u);
656	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
657	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
658	checkData(Point, Data: Intervals[2], Left: 30, Right: 70, Value: 3070);
659
660	Point = 75;
661	Intervals = Tree.getContaining(Point);
662	ASSERT_EQ(Intervals.size(), 2u);
663	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
664	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
665	Intervals = Tree.getContaining(Point);
666	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
667	ASSERT_EQ(Intervals.size(), 2u);
668	checkData(Point, Data: Intervals[0], Left: 20, Right: 80, Value: 2080);
669	checkData(Point, Data: Intervals[1], Left: 10, Right: 90, Value: 1090);
670	Intervals = Tree.getContaining(Point);
671	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
672	ASSERT_EQ(Intervals.size(), 2u);
673	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
674	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
675
676	Point = 80;
677	Intervals = Tree.getContaining(Point);
678	ASSERT_EQ(Intervals.size(), 2u);
679	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
680	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
681	Intervals = Tree.getContaining(Point);
682	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
683	ASSERT_EQ(Intervals.size(), 2u);
684	checkData(Point, Data: Intervals[0], Left: 20, Right: 80, Value: 2080);
685	checkData(Point, Data: Intervals[1], Left: 10, Right: 90, Value: 1090);
686	Intervals = Tree.getContaining(Point);
687	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
688	ASSERT_EQ(Intervals.size(), 2u);
689	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
690	checkData(Point, Data: Intervals[1], Left: 20, Right: 80, Value: 2080);
691
692	Point = 85;
693	Intervals = Tree.getContaining(Point);
694	ASSERT_EQ(Intervals.size(), 1u);
695	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
696
697	Point = 90;
698	Intervals = Tree.getContaining(Point);
699	ASSERT_EQ(Intervals.size(), 1u);
700	checkData(Point, Data: Intervals[0], Left: 10, Right: 90, Value: 1090);
701
702	// Invalid interval values: 90] < x
703	Point = 95;
704	Intervals = Tree.getContaining(Point);
705	EXPECT_TRUE(Intervals.empty());
706	}
707
708	// Complex Overlapping.
709	TEST(IntervalTreeTest, ComplexIntervalsOverlapping) {
710	UUAlloc Allocator;
711	UUTree Tree(Allocator);
712	UUReferences Intervals;
713	UUPoint Point;
714
715	// [30, 35] <- (3035)
716	// [39, 50] <- (3950)
717	// [55, 61] <- (5561)
718	// [31, 56] <- (3156)
719	// [12, 21] <- (1221)
720	// [25, 41] <- (2541)
721	// [49, 65] <- (4965)
722	// [71, 79] <- (7179)
723	// [11, 16] <- (1116)
724	// [20, 30] <- (2030)
725	// [36, 54] <- (3654)
726	// [60, 70] <- (6070)
727	// [74, 80] <- (7480)
728	// [15, 40] <- (1540)
729	// [43, 45] <- (4345)
730	// [50, 75] <- (5075)
731	// [10, 85] <- (1085)
732
733	// 30--35 39------------50 55----61
734	// 31------------------------56
735	// 12--------21 25------------41 49-------------65 71-----79
736	// 11----16 20-----30 36----------------54 60------70 74---- 80
737	// 15---------------------40 43--45 50--------------------75
738	// 10----------------------------------------------------------------------85
739
740	Tree.insert(Left: 30, Right: 35, Value: 3035);
741	Tree.insert(Left: 39, Right: 50, Value: 3950);
742	Tree.insert(Left: 55, Right: 61, Value: 5561);
743	Tree.insert(Left: 31, Right: 56, Value: 3156);
744	Tree.insert(Left: 12, Right: 21, Value: 1221);
745	Tree.insert(Left: 25, Right: 41, Value: 2541);
746	Tree.insert(Left: 49, Right: 65, Value: 4965);
747	Tree.insert(Left: 71, Right: 79, Value: 7179);
748	Tree.insert(Left: 11, Right: 16, Value: 1116);
749	Tree.insert(Left: 20, Right: 30, Value: 2030);
750	Tree.insert(Left: 36, Right: 54, Value: 3654);
751	Tree.insert(Left: 60, Right: 70, Value: 6070);
752	Tree.insert(Left: 74, Right: 80, Value: 7480);
753	Tree.insert(Left: 15, Right: 40, Value: 1540);
754	Tree.insert(Left: 43, Right: 45, Value: 4345);
755	Tree.insert(Left: 50, Right: 75, Value: 5075);
756	Tree.insert(Left: 10, Right: 85, Value: 1085);
757	Tree.create();
758
759	// Find valid interval values.
760	Point = 30;
761	Intervals = Tree.getContaining(Point);
762	ASSERT_EQ(Intervals.size(), 5u);
763	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
764	checkData(Point, Data: Intervals[1], Left: 25, Right: 41, Value: 2541);
765	checkData(Point, Data: Intervals[2], Left: 15, Right: 40, Value: 1540);
766	checkData(Point, Data: Intervals[3], Left: 20, Right: 30, Value: 2030);
767	checkData(Point, Data: Intervals[4], Left: 30, Right: 35, Value: 3035);
768	Intervals = Tree.getContaining(Point);
769	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
770	ASSERT_EQ(Intervals.size(), 5u);
771	checkData(Point, Data: Intervals[0], Left: 30, Right: 35, Value: 3035);
772	checkData(Point, Data: Intervals[1], Left: 20, Right: 30, Value: 2030);
773	checkData(Point, Data: Intervals[2], Left: 25, Right: 41, Value: 2541);
774	checkData(Point, Data: Intervals[3], Left: 15, Right: 40, Value: 1540);
775	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
776	Intervals = Tree.getContaining(Point);
777	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
778	ASSERT_EQ(Intervals.size(), 5u);
779	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
780	checkData(Point, Data: Intervals[1], Left: 15, Right: 40, Value: 1540);
781	checkData(Point, Data: Intervals[2], Left: 25, Right: 41, Value: 2541);
782	checkData(Point, Data: Intervals[3], Left: 20, Right: 30, Value: 2030);
783	checkData(Point, Data: Intervals[4], Left: 30, Right: 35, Value: 3035);
784
785	Point = 35;
786	Intervals = Tree.getContaining(Point);
787	ASSERT_EQ(Intervals.size(), 5u);
788	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
789	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
790	checkData(Point, Data: Intervals[2], Left: 25, Right: 41, Value: 2541);
791	checkData(Point, Data: Intervals[3], Left: 15, Right: 40, Value: 1540);
792	checkData(Point, Data: Intervals[4], Left: 30, Right: 35, Value: 3035);
793	Intervals = Tree.getContaining(Point);
794	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
795	ASSERT_EQ(Intervals.size(), 5u);
796	checkData(Point, Data: Intervals[0], Left: 30, Right: 35, Value: 3035);
797	checkData(Point, Data: Intervals[1], Left: 25, Right: 41, Value: 2541);
798	checkData(Point, Data: Intervals[2], Left: 31, Right: 56, Value: 3156);
799	checkData(Point, Data: Intervals[3], Left: 15, Right: 40, Value: 1540);
800	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
801	Intervals = Tree.getContaining(Point);
802	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
803	ASSERT_EQ(Intervals.size(), 5u);
804	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
805	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
806	checkData(Point, Data: Intervals[2], Left: 15, Right: 40, Value: 1540);
807	checkData(Point, Data: Intervals[3], Left: 25, Right: 41, Value: 2541);
808	checkData(Point, Data: Intervals[4], Left: 30, Right: 35, Value: 3035);
809
810	Point = 39;
811	Intervals = Tree.getContaining(Point);
812	ASSERT_EQ(Intervals.size(), 6u);
813	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
814	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
815	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
816	checkData(Point, Data: Intervals[3], Left: 39, Right: 50, Value: 3950);
817	checkData(Point, Data: Intervals[4], Left: 25, Right: 41, Value: 2541);
818	checkData(Point, Data: Intervals[5], Left: 15, Right: 40, Value: 1540);
819	Intervals = Tree.getContaining(Point);
820	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
821	ASSERT_EQ(Intervals.size(), 6u);
822	checkData(Point, Data: Intervals[0], Left: 39, Right: 50, Value: 3950);
823	checkData(Point, Data: Intervals[1], Left: 25, Right: 41, Value: 2541);
824	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
825	checkData(Point, Data: Intervals[3], Left: 31, Right: 56, Value: 3156);
826	checkData(Point, Data: Intervals[4], Left: 15, Right: 40, Value: 1540);
827	checkData(Point, Data: Intervals[5], Left: 10, Right: 85, Value: 1085);
828	Intervals = Tree.getContaining(Point);
829	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
830	ASSERT_EQ(Intervals.size(), 6u);
831	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
832	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
833	checkData(Point, Data: Intervals[2], Left: 15, Right: 40, Value: 1540);
834	checkData(Point, Data: Intervals[3], Left: 36, Right: 54, Value: 3654);
835	checkData(Point, Data: Intervals[4], Left: 25, Right: 41, Value: 2541);
836	checkData(Point, Data: Intervals[5], Left: 39, Right: 50, Value: 3950);
837
838	Point = 50;
839	Intervals = Tree.getContaining(Point);
840	ASSERT_EQ(Intervals.size(), 6u);
841	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
842	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
843	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
844	checkData(Point, Data: Intervals[3], Left: 39, Right: 50, Value: 3950);
845	checkData(Point, Data: Intervals[4], Left: 49, Right: 65, Value: 4965);
846	checkData(Point, Data: Intervals[5], Left: 50, Right: 75, Value: 5075);
847	Intervals = Tree.getContaining(Point);
848	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
849	ASSERT_EQ(Intervals.size(), 6u);
850	checkData(Point, Data: Intervals[0], Left: 39, Right: 50, Value: 3950);
851	checkData(Point, Data: Intervals[1], Left: 49, Right: 65, Value: 4965);
852	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
853	checkData(Point, Data: Intervals[3], Left: 31, Right: 56, Value: 3156);
854	checkData(Point, Data: Intervals[4], Left: 50, Right: 75, Value: 5075);
855	checkData(Point, Data: Intervals[5], Left: 10, Right: 85, Value: 1085);
856	Intervals = Tree.getContaining(Point);
857	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
858	ASSERT_EQ(Intervals.size(), 6u);
859	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
860	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
861	checkData(Point, Data: Intervals[2], Left: 50, Right: 75, Value: 5075);
862	checkData(Point, Data: Intervals[3], Left: 36, Right: 54, Value: 3654);
863	checkData(Point, Data: Intervals[4], Left: 49, Right: 65, Value: 4965);
864	checkData(Point, Data: Intervals[5], Left: 39, Right: 50, Value: 3950);
865
866	Point = 55;
867	Intervals = Tree.getContaining(Point);
868	ASSERT_EQ(Intervals.size(), 5u);
869	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
870	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
871	checkData(Point, Data: Intervals[2], Left: 49, Right: 65, Value: 4965);
872	checkData(Point, Data: Intervals[3], Left: 50, Right: 75, Value: 5075);
873	checkData(Point, Data: Intervals[4], Left: 55, Right: 61, Value: 5561);
874	Intervals = Tree.getContaining(Point);
875	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
876	ASSERT_EQ(Intervals.size(), 5u);
877	checkData(Point, Data: Intervals[0], Left: 55, Right: 61, Value: 5561);
878	checkData(Point, Data: Intervals[1], Left: 49, Right: 65, Value: 4965);
879	checkData(Point, Data: Intervals[2], Left: 31, Right: 56, Value: 3156);
880	checkData(Point, Data: Intervals[3], Left: 50, Right: 75, Value: 5075);
881	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
882	Intervals = Tree.getContaining(Point);
883	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
884	ASSERT_EQ(Intervals.size(), 5u);
885	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
886	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
887	checkData(Point, Data: Intervals[2], Left: 50, Right: 75, Value: 5075);
888	checkData(Point, Data: Intervals[3], Left: 49, Right: 65, Value: 4965);
889	checkData(Point, Data: Intervals[4], Left: 55, Right: 61, Value: 5561);
890
891	Point = 61;
892	Intervals = Tree.getContaining(Point);
893	ASSERT_EQ(Intervals.size(), 5u);
894	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
895	checkData(Point, Data: Intervals[1], Left: 49, Right: 65, Value: 4965);
896	checkData(Point, Data: Intervals[2], Left: 50, Right: 75, Value: 5075);
897	checkData(Point, Data: Intervals[3], Left: 55, Right: 61, Value: 5561);
898	checkData(Point, Data: Intervals[4], Left: 60, Right: 70, Value: 6070);
899	Intervals = Tree.getContaining(Point);
900	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
901	ASSERT_EQ(Intervals.size(), 5u);
902	checkData(Point, Data: Intervals[0], Left: 55, Right: 61, Value: 5561);
903	checkData(Point, Data: Intervals[1], Left: 60, Right: 70, Value: 6070);
904	checkData(Point, Data: Intervals[2], Left: 49, Right: 65, Value: 4965);
905	checkData(Point, Data: Intervals[3], Left: 50, Right: 75, Value: 5075);
906	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
907	Intervals = Tree.getContaining(Point);
908	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
909	ASSERT_EQ(Intervals.size(), 5u);
910	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
911	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
912	checkData(Point, Data: Intervals[2], Left: 49, Right: 65, Value: 4965);
913	checkData(Point, Data: Intervals[3], Left: 60, Right: 70, Value: 6070);
914	checkData(Point, Data: Intervals[4], Left: 55, Right: 61, Value: 5561);
915
916	Point = 31;
917	Intervals = Tree.getContaining(Point);
918	ASSERT_EQ(Intervals.size(), 5u);
919	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
920	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
921	checkData(Point, Data: Intervals[2], Left: 25, Right: 41, Value: 2541);
922	checkData(Point, Data: Intervals[3], Left: 15, Right: 40, Value: 1540);
923	checkData(Point, Data: Intervals[4], Left: 30, Right: 35, Value: 3035);
924	Intervals = Tree.getContaining(Point);
925	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
926	ASSERT_EQ(Intervals.size(), 5u);
927	checkData(Point, Data: Intervals[0], Left: 30, Right: 35, Value: 3035);
928	checkData(Point, Data: Intervals[1], Left: 25, Right: 41, Value: 2541);
929	checkData(Point, Data: Intervals[2], Left: 31, Right: 56, Value: 3156);
930	checkData(Point, Data: Intervals[3], Left: 15, Right: 40, Value: 1540);
931	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
932	Intervals = Tree.getContaining(Point);
933	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
934	ASSERT_EQ(Intervals.size(), 5u);
935	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
936	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
937	checkData(Point, Data: Intervals[2], Left: 15, Right: 40, Value: 1540);
938	checkData(Point, Data: Intervals[3], Left: 25, Right: 41, Value: 2541);
939	checkData(Point, Data: Intervals[4], Left: 30, Right: 35, Value: 3035);
940
941	Point = 56;
942	Intervals = Tree.getContaining(Point);
943	ASSERT_EQ(Intervals.size(), 5u);
944	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
945	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
946	checkData(Point, Data: Intervals[2], Left: 49, Right: 65, Value: 4965);
947	checkData(Point, Data: Intervals[3], Left: 50, Right: 75, Value: 5075);
948	checkData(Point, Data: Intervals[4], Left: 55, Right: 61, Value: 5561);
949	Intervals = Tree.getContaining(Point);
950	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
951	ASSERT_EQ(Intervals.size(), 5u);
952	checkData(Point, Data: Intervals[0], Left: 55, Right: 61, Value: 5561);
953	checkData(Point, Data: Intervals[1], Left: 49, Right: 65, Value: 4965);
954	checkData(Point, Data: Intervals[2], Left: 31, Right: 56, Value: 3156);
955	checkData(Point, Data: Intervals[3], Left: 50, Right: 75, Value: 5075);
956	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
957	Intervals = Tree.getContaining(Point);
958	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
959	ASSERT_EQ(Intervals.size(), 5u);
960	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
961	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
962	checkData(Point, Data: Intervals[2], Left: 50, Right: 75, Value: 5075);
963	checkData(Point, Data: Intervals[3], Left: 49, Right: 65, Value: 4965);
964	checkData(Point, Data: Intervals[4], Left: 55, Right: 61, Value: 5561);
965
966	Point = 12;
967	Intervals = Tree.getContaining(Point);
968	ASSERT_EQ(Intervals.size(), 3u);
969	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
970	checkData(Point, Data: Intervals[1], Left: 11, Right: 16, Value: 1116);
971	checkData(Point, Data: Intervals[2], Left: 12, Right: 21, Value: 1221);
972	Intervals = Tree.getContaining(Point);
973	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
974	ASSERT_EQ(Intervals.size(), 3u);
975	checkData(Point, Data: Intervals[0], Left: 11, Right: 16, Value: 1116);
976	checkData(Point, Data: Intervals[1], Left: 12, Right: 21, Value: 1221);
977	checkData(Point, Data: Intervals[2], Left: 10, Right: 85, Value: 1085);
978	Intervals = Tree.getContaining(Point);
979	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
980	ASSERT_EQ(Intervals.size(), 3u);
981	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
982	checkData(Point, Data: Intervals[1], Left: 12, Right: 21, Value: 1221);
983	checkData(Point, Data: Intervals[2], Left: 11, Right: 16, Value: 1116);
984
985	Point = 21;
986	Intervals = Tree.getContaining(Point);
987	ASSERT_EQ(Intervals.size(), 4u);
988	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
989	checkData(Point, Data: Intervals[1], Left: 15, Right: 40, Value: 1540);
990	checkData(Point, Data: Intervals[2], Left: 20, Right: 30, Value: 2030);
991	checkData(Point, Data: Intervals[3], Left: 12, Right: 21, Value: 1221);
992	Intervals = Tree.getContaining(Point);
993	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
994	ASSERT_EQ(Intervals.size(), 4u);
995	checkData(Point, Data: Intervals[0], Left: 12, Right: 21, Value: 1221);
996	checkData(Point, Data: Intervals[1], Left: 20, Right: 30, Value: 2030);
997	checkData(Point, Data: Intervals[2], Left: 15, Right: 40, Value: 1540);
998	checkData(Point, Data: Intervals[3], Left: 10, Right: 85, Value: 1085);
999	Intervals = Tree.getContaining(Point);
1000	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1001	ASSERT_EQ(Intervals.size(), 4u);
1002	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1003	checkData(Point, Data: Intervals[1], Left: 15, Right: 40, Value: 1540);
1004	checkData(Point, Data: Intervals[2], Left: 20, Right: 30, Value: 2030);
1005	checkData(Point, Data: Intervals[3], Left: 12, Right: 21, Value: 1221);
1006
1007	Point = 25;
1008	Intervals = Tree.getContaining(Point);
1009	ASSERT_EQ(Intervals.size(), 4u);
1010	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1011	checkData(Point, Data: Intervals[1], Left: 15, Right: 40, Value: 1540);
1012	checkData(Point, Data: Intervals[2], Left: 20, Right: 30, Value: 2030);
1013	checkData(Point, Data: Intervals[3], Left: 25, Right: 41, Value: 2541);
1014	Intervals = Tree.getContaining(Point);
1015	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1016	ASSERT_EQ(Intervals.size(), 4u);
1017	checkData(Point, Data: Intervals[0], Left: 20, Right: 30, Value: 2030);
1018	checkData(Point, Data: Intervals[1], Left: 25, Right: 41, Value: 2541);
1019	checkData(Point, Data: Intervals[2], Left: 15, Right: 40, Value: 1540);
1020	checkData(Point, Data: Intervals[3], Left: 10, Right: 85, Value: 1085);
1021	Intervals = Tree.getContaining(Point);
1022	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1023	ASSERT_EQ(Intervals.size(), 4u);
1024	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1025	checkData(Point, Data: Intervals[1], Left: 15, Right: 40, Value: 1540);
1026	checkData(Point, Data: Intervals[2], Left: 25, Right: 41, Value: 2541);
1027	checkData(Point, Data: Intervals[3], Left: 20, Right: 30, Value: 2030);
1028
1029	Point = 41;
1030	Intervals = Tree.getContaining(Point);
1031	ASSERT_EQ(Intervals.size(), 5u);
1032	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1033	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1034	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1035	checkData(Point, Data: Intervals[3], Left: 39, Right: 50, Value: 3950);
1036	checkData(Point, Data: Intervals[4], Left: 25, Right: 41, Value: 2541);
1037	Intervals = Tree.getContaining(Point);
1038	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1039	ASSERT_EQ(Intervals.size(), 5u);
1040	checkData(Point, Data: Intervals[0], Left: 39, Right: 50, Value: 3950);
1041	checkData(Point, Data: Intervals[1], Left: 25, Right: 41, Value: 2541);
1042	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1043	checkData(Point, Data: Intervals[3], Left: 31, Right: 56, Value: 3156);
1044	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
1045	Intervals = Tree.getContaining(Point);
1046	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1047	ASSERT_EQ(Intervals.size(), 5u);
1048	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1049	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1050	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1051	checkData(Point, Data: Intervals[3], Left: 25, Right: 41, Value: 2541);
1052	checkData(Point, Data: Intervals[4], Left: 39, Right: 50, Value: 3950);
1053
1054	Point = 49;
1055	Intervals = Tree.getContaining(Point);
1056	ASSERT_EQ(Intervals.size(), 5u);
1057	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1058	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1059	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1060	checkData(Point, Data: Intervals[3], Left: 39, Right: 50, Value: 3950);
1061	checkData(Point, Data: Intervals[4], Left: 49, Right: 65, Value: 4965);
1062	Intervals = Tree.getContaining(Point);
1063	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1064	ASSERT_EQ(Intervals.size(), 5u);
1065	checkData(Point, Data: Intervals[0], Left: 39, Right: 50, Value: 3950);
1066	checkData(Point, Data: Intervals[1], Left: 49, Right: 65, Value: 4965);
1067	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1068	checkData(Point, Data: Intervals[3], Left: 31, Right: 56, Value: 3156);
1069	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
1070	Intervals = Tree.getContaining(Point);
1071	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1072	ASSERT_EQ(Intervals.size(), 5u);
1073	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1074	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1075	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1076	checkData(Point, Data: Intervals[3], Left: 49, Right: 65, Value: 4965);
1077	checkData(Point, Data: Intervals[4], Left: 39, Right: 50, Value: 3950);
1078
1079	Point = 65;
1080	Intervals = Tree.getContaining(Point);
1081	ASSERT_EQ(Intervals.size(), 4u);
1082	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1083	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1084	checkData(Point, Data: Intervals[2], Left: 60, Right: 70, Value: 6070);
1085	checkData(Point, Data: Intervals[3], Left: 49, Right: 65, Value: 4965);
1086	Intervals = Tree.getContaining(Point);
1087	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1088	ASSERT_EQ(Intervals.size(), 4u);
1089	checkData(Point, Data: Intervals[0], Left: 60, Right: 70, Value: 6070);
1090	checkData(Point, Data: Intervals[1], Left: 49, Right: 65, Value: 4965);
1091	checkData(Point, Data: Intervals[2], Left: 50, Right: 75, Value: 5075);
1092	checkData(Point, Data: Intervals[3], Left: 10, Right: 85, Value: 1085);
1093	Intervals = Tree.getContaining(Point);
1094	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1095	ASSERT_EQ(Intervals.size(), 4u);
1096	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1097	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1098	checkData(Point, Data: Intervals[2], Left: 49, Right: 65, Value: 4965);
1099	checkData(Point, Data: Intervals[3], Left: 60, Right: 70, Value: 6070);
1100
1101	Point = 71;
1102	Intervals = Tree.getContaining(Point);
1103	ASSERT_EQ(Intervals.size(), 3u);
1104	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1105	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1106	checkData(Point, Data: Intervals[2], Left: 71, Right: 79, Value: 7179);
1107	Intervals = Tree.getContaining(Point);
1108	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1109	ASSERT_EQ(Intervals.size(), 3u);
1110	checkData(Point, Data: Intervals[0], Left: 71, Right: 79, Value: 7179);
1111	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1112	checkData(Point, Data: Intervals[2], Left: 10, Right: 85, Value: 1085);
1113	Intervals = Tree.getContaining(Point);
1114	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1115	ASSERT_EQ(Intervals.size(), 3u);
1116	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1117	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1118	checkData(Point, Data: Intervals[2], Left: 71, Right: 79, Value: 7179);
1119
1120	Point = 79;
1121	Intervals = Tree.getContaining(Point);
1122	ASSERT_EQ(Intervals.size(), 3u);
1123	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1124	checkData(Point, Data: Intervals[1], Left: 74, Right: 80, Value: 7480);
1125	checkData(Point, Data: Intervals[2], Left: 71, Right: 79, Value: 7179);
1126	Intervals = Tree.getContaining(Point);
1127	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1128	ASSERT_EQ(Intervals.size(), 3u);
1129	checkData(Point, Data: Intervals[0], Left: 74, Right: 80, Value: 7480);
1130	checkData(Point, Data: Intervals[1], Left: 71, Right: 79, Value: 7179);
1131	checkData(Point, Data: Intervals[2], Left: 10, Right: 85, Value: 1085);
1132	Intervals = Tree.getContaining(Point);
1133	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1134	ASSERT_EQ(Intervals.size(), 3u);
1135	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1136	checkData(Point, Data: Intervals[1], Left: 71, Right: 79, Value: 7179);
1137	checkData(Point, Data: Intervals[2], Left: 74, Right: 80, Value: 7480);
1138
1139	Point = 11;
1140	Intervals = Tree.getContaining(Point);
1141	ASSERT_EQ(Intervals.size(), 2u);
1142	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1143	checkData(Point, Data: Intervals[1], Left: 11, Right: 16, Value: 1116);
1144	Intervals = Tree.getContaining(Point);
1145	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1146	ASSERT_EQ(Intervals.size(), 2u);
1147	checkData(Point, Data: Intervals[0], Left: 11, Right: 16, Value: 1116);
1148	checkData(Point, Data: Intervals[1], Left: 10, Right: 85, Value: 1085);
1149	Intervals = Tree.getContaining(Point);
1150	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1151	ASSERT_EQ(Intervals.size(), 2u);
1152	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1153	checkData(Point, Data: Intervals[1], Left: 11, Right: 16, Value: 1116);
1154
1155	Point = 16;
1156	Intervals = Tree.getContaining(Point);
1157	ASSERT_EQ(Intervals.size(), 4u);
1158	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1159	checkData(Point, Data: Intervals[1], Left: 15, Right: 40, Value: 1540);
1160	checkData(Point, Data: Intervals[2], Left: 12, Right: 21, Value: 1221);
1161	checkData(Point, Data: Intervals[3], Left: 11, Right: 16, Value: 1116);
1162	Intervals = Tree.getContaining(Point);
1163	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1164	ASSERT_EQ(Intervals.size(), 4u);
1165	checkData(Point, Data: Intervals[0], Left: 11, Right: 16, Value: 1116);
1166	checkData(Point, Data: Intervals[1], Left: 12, Right: 21, Value: 1221);
1167	checkData(Point, Data: Intervals[2], Left: 15, Right: 40, Value: 1540);
1168	checkData(Point, Data: Intervals[3], Left: 10, Right: 85, Value: 1085);
1169	Intervals = Tree.getContaining(Point);
1170	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1171	ASSERT_EQ(Intervals.size(), 4u);
1172	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1173	checkData(Point, Data: Intervals[1], Left: 15, Right: 40, Value: 1540);
1174	checkData(Point, Data: Intervals[2], Left: 12, Right: 21, Value: 1221);
1175	checkData(Point, Data: Intervals[3], Left: 11, Right: 16, Value: 1116);
1176
1177	Point = 20;
1178	Intervals = Tree.getContaining(Point);
1179	ASSERT_EQ(Intervals.size(), 4u);
1180	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1181	checkData(Point, Data: Intervals[1], Left: 15, Right: 40, Value: 1540);
1182	checkData(Point, Data: Intervals[2], Left: 20, Right: 30, Value: 2030);
1183	checkData(Point, Data: Intervals[3], Left: 12, Right: 21, Value: 1221);
1184	Intervals = Tree.getContaining(Point);
1185	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1186	ASSERT_EQ(Intervals.size(), 4u);
1187	checkData(Point, Data: Intervals[0], Left: 12, Right: 21, Value: 1221);
1188	checkData(Point, Data: Intervals[1], Left: 20, Right: 30, Value: 2030);
1189	checkData(Point, Data: Intervals[2], Left: 15, Right: 40, Value: 1540);
1190	checkData(Point, Data: Intervals[3], Left: 10, Right: 85, Value: 1085);
1191	Intervals = Tree.getContaining(Point);
1192	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1193	ASSERT_EQ(Intervals.size(), 4u);
1194	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1195	checkData(Point, Data: Intervals[1], Left: 15, Right: 40, Value: 1540);
1196	checkData(Point, Data: Intervals[2], Left: 20, Right: 30, Value: 2030);
1197	checkData(Point, Data: Intervals[3], Left: 12, Right: 21, Value: 1221);
1198
1199	Point = 30;
1200	Intervals = Tree.getContaining(Point);
1201	ASSERT_EQ(Intervals.size(), 5u);
1202	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1203	checkData(Point, Data: Intervals[1], Left: 25, Right: 41, Value: 2541);
1204	checkData(Point, Data: Intervals[2], Left: 15, Right: 40, Value: 1540);
1205	checkData(Point, Data: Intervals[3], Left: 20, Right: 30, Value: 2030);
1206	checkData(Point, Data: Intervals[4], Left: 30, Right: 35, Value: 3035);
1207	Intervals = Tree.getContaining(Point);
1208	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1209	ASSERT_EQ(Intervals.size(), 5u);
1210	checkData(Point, Data: Intervals[0], Left: 30, Right: 35, Value: 3035);
1211	checkData(Point, Data: Intervals[1], Left: 20, Right: 30, Value: 2030);
1212	checkData(Point, Data: Intervals[2], Left: 25, Right: 41, Value: 2541);
1213	checkData(Point, Data: Intervals[3], Left: 15, Right: 40, Value: 1540);
1214	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
1215	Intervals = Tree.getContaining(Point);
1216	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1217	ASSERT_EQ(Intervals.size(), 5u);
1218	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1219	checkData(Point, Data: Intervals[1], Left: 15, Right: 40, Value: 1540);
1220	checkData(Point, Data: Intervals[2], Left: 25, Right: 41, Value: 2541);
1221	checkData(Point, Data: Intervals[3], Left: 20, Right: 30, Value: 2030);
1222	checkData(Point, Data: Intervals[4], Left: 30, Right: 35, Value: 3035);
1223
1224	Point = 36;
1225	Intervals = Tree.getContaining(Point);
1226	ASSERT_EQ(Intervals.size(), 5u);
1227	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1228	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1229	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1230	checkData(Point, Data: Intervals[3], Left: 25, Right: 41, Value: 2541);
1231	checkData(Point, Data: Intervals[4], Left: 15, Right: 40, Value: 1540);
1232	Intervals = Tree.getContaining(Point);
1233	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1234	ASSERT_EQ(Intervals.size(), 5u);
1235	checkData(Point, Data: Intervals[0], Left: 25, Right: 41, Value: 2541);
1236	checkData(Point, Data: Intervals[1], Left: 36, Right: 54, Value: 3654);
1237	checkData(Point, Data: Intervals[2], Left: 31, Right: 56, Value: 3156);
1238	checkData(Point, Data: Intervals[3], Left: 15, Right: 40, Value: 1540);
1239	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
1240	Intervals = Tree.getContaining(Point);
1241	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1242	ASSERT_EQ(Intervals.size(), 5u);
1243	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1244	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1245	checkData(Point, Data: Intervals[2], Left: 15, Right: 40, Value: 1540);
1246	checkData(Point, Data: Intervals[3], Left: 36, Right: 54, Value: 3654);
1247	checkData(Point, Data: Intervals[4], Left: 25, Right: 41, Value: 2541);
1248
1249	Point = 54;
1250	Intervals = Tree.getContaining(Point);
1251	ASSERT_EQ(Intervals.size(), 5u);
1252	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1253	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1254	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1255	checkData(Point, Data: Intervals[3], Left: 49, Right: 65, Value: 4965);
1256	checkData(Point, Data: Intervals[4], Left: 50, Right: 75, Value: 5075);
1257	Intervals = Tree.getContaining(Point);
1258	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1259	ASSERT_EQ(Intervals.size(), 5u);
1260	checkData(Point, Data: Intervals[0], Left: 49, Right: 65, Value: 4965);
1261	checkData(Point, Data: Intervals[1], Left: 36, Right: 54, Value: 3654);
1262	checkData(Point, Data: Intervals[2], Left: 31, Right: 56, Value: 3156);
1263	checkData(Point, Data: Intervals[3], Left: 50, Right: 75, Value: 5075);
1264	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
1265	Intervals = Tree.getContaining(Point);
1266	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1267	ASSERT_EQ(Intervals.size(), 5u);
1268	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1269	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1270	checkData(Point, Data: Intervals[2], Left: 50, Right: 75, Value: 5075);
1271	checkData(Point, Data: Intervals[3], Left: 36, Right: 54, Value: 3654);
1272	checkData(Point, Data: Intervals[4], Left: 49, Right: 65, Value: 4965);
1273
1274	Point = 60;
1275	Intervals = Tree.getContaining(Point);
1276	ASSERT_EQ(Intervals.size(), 5u);
1277	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1278	checkData(Point, Data: Intervals[1], Left: 49, Right: 65, Value: 4965);
1279	checkData(Point, Data: Intervals[2], Left: 50, Right: 75, Value: 5075);
1280	checkData(Point, Data: Intervals[3], Left: 55, Right: 61, Value: 5561);
1281	checkData(Point, Data: Intervals[4], Left: 60, Right: 70, Value: 6070);
1282	Intervals = Tree.getContaining(Point);
1283	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1284	ASSERT_EQ(Intervals.size(), 5u);
1285	checkData(Point, Data: Intervals[0], Left: 55, Right: 61, Value: 5561);
1286	checkData(Point, Data: Intervals[1], Left: 60, Right: 70, Value: 6070);
1287	checkData(Point, Data: Intervals[2], Left: 49, Right: 65, Value: 4965);
1288	checkData(Point, Data: Intervals[3], Left: 50, Right: 75, Value: 5075);
1289	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
1290	Intervals = Tree.getContaining(Point);
1291	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1292	ASSERT_EQ(Intervals.size(), 5u);
1293	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1294	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1295	checkData(Point, Data: Intervals[2], Left: 49, Right: 65, Value: 4965);
1296	checkData(Point, Data: Intervals[3], Left: 60, Right: 70, Value: 6070);
1297	checkData(Point, Data: Intervals[4], Left: 55, Right: 61, Value: 5561);
1298
1299	Point = 70;
1300	Intervals = Tree.getContaining(Point);
1301	ASSERT_EQ(Intervals.size(), 3u);
1302	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1303	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1304	checkData(Point, Data: Intervals[2], Left: 60, Right: 70, Value: 6070);
1305	Intervals = Tree.getContaining(Point);
1306	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1307	ASSERT_EQ(Intervals.size(), 3u);
1308	checkData(Point, Data: Intervals[0], Left: 60, Right: 70, Value: 6070);
1309	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1310	checkData(Point, Data: Intervals[2], Left: 10, Right: 85, Value: 1085);
1311	Intervals = Tree.getContaining(Point);
1312	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1313	ASSERT_EQ(Intervals.size(), 3u);
1314	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1315	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1316	checkData(Point, Data: Intervals[2], Left: 60, Right: 70, Value: 6070);
1317
1318	Point = 74;
1319	Intervals = Tree.getContaining(Point);
1320	ASSERT_EQ(Intervals.size(), 4u);
1321	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1322	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1323	checkData(Point, Data: Intervals[2], Left: 71, Right: 79, Value: 7179);
1324	checkData(Point, Data: Intervals[3], Left: 74, Right: 80, Value: 7480);
1325	Intervals = Tree.getContaining(Point);
1326	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1327	ASSERT_EQ(Intervals.size(), 4u);
1328	checkData(Point, Data: Intervals[0], Left: 74, Right: 80, Value: 7480);
1329	checkData(Point, Data: Intervals[1], Left: 71, Right: 79, Value: 7179);
1330	checkData(Point, Data: Intervals[2], Left: 50, Right: 75, Value: 5075);
1331	checkData(Point, Data: Intervals[3], Left: 10, Right: 85, Value: 1085);
1332	Intervals = Tree.getContaining(Point);
1333	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1334	ASSERT_EQ(Intervals.size(), 4u);
1335	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1336	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1337	checkData(Point, Data: Intervals[2], Left: 71, Right: 79, Value: 7179);
1338	checkData(Point, Data: Intervals[3], Left: 74, Right: 80, Value: 7480);
1339
1340	Point = 80;
1341	Intervals = Tree.getContaining(Point);
1342	ASSERT_EQ(Intervals.size(), 2u);
1343	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1344	checkData(Point, Data: Intervals[1], Left: 74, Right: 80, Value: 7480);
1345	Intervals = Tree.getContaining(Point);
1346	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1347	ASSERT_EQ(Intervals.size(), 2u);
1348	checkData(Point, Data: Intervals[0], Left: 74, Right: 80, Value: 7480);
1349	checkData(Point, Data: Intervals[1], Left: 10, Right: 85, Value: 1085);
1350	Intervals = Tree.getContaining(Point);
1351	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1352	ASSERT_EQ(Intervals.size(), 2u);
1353	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1354	checkData(Point, Data: Intervals[1], Left: 74, Right: 80, Value: 7480);
1355
1356	Point = 15;
1357	Intervals = Tree.getContaining(Point);
1358	ASSERT_EQ(Intervals.size(), 4u);
1359	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1360	checkData(Point, Data: Intervals[1], Left: 15, Right: 40, Value: 1540);
1361	checkData(Point, Data: Intervals[2], Left: 11, Right: 16, Value: 1116);
1362	checkData(Point, Data: Intervals[3], Left: 12, Right: 21, Value: 1221);
1363	Intervals = Tree.getContaining(Point);
1364	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1365	ASSERT_EQ(Intervals.size(), 4u);
1366	checkData(Point, Data: Intervals[0], Left: 11, Right: 16, Value: 1116);
1367	checkData(Point, Data: Intervals[1], Left: 12, Right: 21, Value: 1221);
1368	checkData(Point, Data: Intervals[2], Left: 15, Right: 40, Value: 1540);
1369	checkData(Point, Data: Intervals[3], Left: 10, Right: 85, Value: 1085);
1370	Intervals = Tree.getContaining(Point);
1371	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1372	ASSERT_EQ(Intervals.size(), 4u);
1373	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1374	checkData(Point, Data: Intervals[1], Left: 15, Right: 40, Value: 1540);
1375	checkData(Point, Data: Intervals[2], Left: 12, Right: 21, Value: 1221);
1376	checkData(Point, Data: Intervals[3], Left: 11, Right: 16, Value: 1116);
1377
1378	Point = 40;
1379	Intervals = Tree.getContaining(Point);
1380	ASSERT_EQ(Intervals.size(), 6u);
1381	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1382	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1383	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1384	checkData(Point, Data: Intervals[3], Left: 39, Right: 50, Value: 3950);
1385	checkData(Point, Data: Intervals[4], Left: 25, Right: 41, Value: 2541);
1386	checkData(Point, Data: Intervals[5], Left: 15, Right: 40, Value: 1540);
1387	Intervals = Tree.getContaining(Point);
1388	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1389	ASSERT_EQ(Intervals.size(), 6u);
1390	checkData(Point, Data: Intervals[0], Left: 39, Right: 50, Value: 3950);
1391	checkData(Point, Data: Intervals[1], Left: 25, Right: 41, Value: 2541);
1392	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1393	checkData(Point, Data: Intervals[3], Left: 31, Right: 56, Value: 3156);
1394	checkData(Point, Data: Intervals[4], Left: 15, Right: 40, Value: 1540);
1395	checkData(Point, Data: Intervals[5], Left: 10, Right: 85, Value: 1085);
1396	Intervals = Tree.getContaining(Point);
1397	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1398	ASSERT_EQ(Intervals.size(), 6u);
1399	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1400	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1401	checkData(Point, Data: Intervals[2], Left: 15, Right: 40, Value: 1540);
1402	checkData(Point, Data: Intervals[3], Left: 36, Right: 54, Value: 3654);
1403	checkData(Point, Data: Intervals[4], Left: 25, Right: 41, Value: 2541);
1404	checkData(Point, Data: Intervals[5], Left: 39, Right: 50, Value: 3950);
1405
1406	Point = 43;
1407	Intervals = Tree.getContaining(Point);
1408	ASSERT_EQ(Intervals.size(), 5u);
1409	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1410	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1411	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1412	checkData(Point, Data: Intervals[3], Left: 39, Right: 50, Value: 3950);
1413	checkData(Point, Data: Intervals[4], Left: 43, Right: 45, Value: 4345);
1414	Intervals = Tree.getContaining(Point);
1415	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1416	ASSERT_EQ(Intervals.size(), 5u);
1417	checkData(Point, Data: Intervals[0], Left: 43, Right: 45, Value: 4345);
1418	checkData(Point, Data: Intervals[1], Left: 39, Right: 50, Value: 3950);
1419	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1420	checkData(Point, Data: Intervals[3], Left: 31, Right: 56, Value: 3156);
1421	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
1422	Intervals = Tree.getContaining(Point);
1423	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1424	ASSERT_EQ(Intervals.size(), 5u);
1425	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1426	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1427	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1428	checkData(Point, Data: Intervals[3], Left: 39, Right: 50, Value: 3950);
1429	checkData(Point, Data: Intervals[4], Left: 43, Right: 45, Value: 4345);
1430
1431	Point = 45;
1432	Intervals = Tree.getContaining(Point);
1433	ASSERT_EQ(Intervals.size(), 5u);
1434	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1435	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1436	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1437	checkData(Point, Data: Intervals[3], Left: 39, Right: 50, Value: 3950);
1438	checkData(Point, Data: Intervals[4], Left: 43, Right: 45, Value: 4345);
1439	Intervals = Tree.getContaining(Point);
1440	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1441	ASSERT_EQ(Intervals.size(), 5u);
1442	checkData(Point, Data: Intervals[0], Left: 43, Right: 45, Value: 4345);
1443	checkData(Point, Data: Intervals[1], Left: 39, Right: 50, Value: 3950);
1444	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1445	checkData(Point, Data: Intervals[3], Left: 31, Right: 56, Value: 3156);
1446	checkData(Point, Data: Intervals[4], Left: 10, Right: 85, Value: 1085);
1447	Intervals = Tree.getContaining(Point);
1448	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1449	ASSERT_EQ(Intervals.size(), 5u);
1450	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1451	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1452	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1453	checkData(Point, Data: Intervals[3], Left: 39, Right: 50, Value: 3950);
1454	checkData(Point, Data: Intervals[4], Left: 43, Right: 45, Value: 4345);
1455
1456	Point = 50;
1457	Intervals = Tree.getContaining(Point);
1458	ASSERT_EQ(Intervals.size(), 6u);
1459	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1460	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1461	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1462	checkData(Point, Data: Intervals[3], Left: 39, Right: 50, Value: 3950);
1463	checkData(Point, Data: Intervals[4], Left: 49, Right: 65, Value: 4965);
1464	checkData(Point, Data: Intervals[5], Left: 50, Right: 75, Value: 5075);
1465	Intervals = Tree.getContaining(Point);
1466	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1467	ASSERT_EQ(Intervals.size(), 6u);
1468	checkData(Point, Data: Intervals[0], Left: 39, Right: 50, Value: 3950);
1469	checkData(Point, Data: Intervals[1], Left: 49, Right: 65, Value: 4965);
1470	checkData(Point, Data: Intervals[2], Left: 36, Right: 54, Value: 3654);
1471	checkData(Point, Data: Intervals[3], Left: 31, Right: 56, Value: 3156);
1472	checkData(Point, Data: Intervals[4], Left: 50, Right: 75, Value: 5075);
1473	checkData(Point, Data: Intervals[5], Left: 10, Right: 85, Value: 1085);
1474	Intervals = Tree.getContaining(Point);
1475	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1476	ASSERT_EQ(Intervals.size(), 6u);
1477	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1478	checkData(Point, Data: Intervals[1], Left: 31, Right: 56, Value: 3156);
1479	checkData(Point, Data: Intervals[2], Left: 50, Right: 75, Value: 5075);
1480	checkData(Point, Data: Intervals[3], Left: 36, Right: 54, Value: 3654);
1481	checkData(Point, Data: Intervals[4], Left: 49, Right: 65, Value: 4965);
1482	checkData(Point, Data: Intervals[5], Left: 39, Right: 50, Value: 3950);
1483
1484	Point = 75;
1485	Intervals = Tree.getContaining(Point);
1486	ASSERT_EQ(Intervals.size(), 4u);
1487	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1488	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1489	checkData(Point, Data: Intervals[2], Left: 74, Right: 80, Value: 7480);
1490	checkData(Point, Data: Intervals[3], Left: 71, Right: 79, Value: 7179);
1491	Intervals = Tree.getContaining(Point);
1492	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Ascending);
1493	ASSERT_EQ(Intervals.size(), 4u);
1494	checkData(Point, Data: Intervals[0], Left: 74, Right: 80, Value: 7480);
1495	checkData(Point, Data: Intervals[1], Left: 71, Right: 79, Value: 7179);
1496	checkData(Point, Data: Intervals[2], Left: 50, Right: 75, Value: 5075);
1497	checkData(Point, Data: Intervals[3], Left: 10, Right: 85, Value: 1085);
1498	Intervals = Tree.getContaining(Point);
1499	Tree.sortIntervals(IntervalSet&: Intervals, Sort: UUSorting::Descending);
1500	ASSERT_EQ(Intervals.size(), 4u);
1501	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1502	checkData(Point, Data: Intervals[1], Left: 50, Right: 75, Value: 5075);
1503	checkData(Point, Data: Intervals[2], Left: 71, Right: 79, Value: 7179);
1504	checkData(Point, Data: Intervals[3], Left: 74, Right: 80, Value: 7480);
1505
1506	Point = 10;
1507	Intervals = Tree.getContaining(Point);
1508	ASSERT_EQ(Intervals.size(), 1u);
1509	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1510
1511	Point = 85;
1512	Intervals = Tree.getContaining(Point);
1513	ASSERT_EQ(Intervals.size(), 1u);
1514	checkData(Point, Data: Intervals[0], Left: 10, Right: 85, Value: 1085);
1515
1516	// Invalid interval values.
1517	Point = 5;
1518	Intervals = Tree.getContaining(Point);
1519	EXPECT_TRUE(Intervals.empty());
1520	Point = 90;
1521	Intervals = Tree.getContaining(Point);
1522	EXPECT_TRUE(Intervals.empty());
1523	}
1524
1525	// Four items tree tests. Overlapping. Check mapped values and iterators.
1526	TEST(IntervalTreeTest, MappedValuesIteratorsTree) {
1527	UUAlloc Allocator;
1528	UUTree Tree(Allocator);
1529	UUPoint Point;
1530
1531	// [10, 20] <- (1020)
1532	// [15, 25] <- (1525)
1533	// [50, 60] <- (5060)
1534	// [55, 65] <- (5565)
1535	//
1536	// [10.........20]
1537	// [15.........25]
1538	// [50.........60]
1539	// [55.........65]
1540	Tree.insert(Left: 10, Right: 20, Value: 1020);
1541	Tree.insert(Left: 15, Right: 25, Value: 1525);
1542	Tree.insert(Left: 50, Right: 60, Value: 5060);
1543	Tree.insert(Left: 55, Right: 65, Value: 5565);
1544	Tree.create();
1545
1546	// Iterators.
1547	{
1548	// Start searching for '10'.
1549	Point = 10;
1550	UUIter Iter = Tree.find(Point);
1551	EXPECT_NE(Iter, Tree.find_end());
1552	checkData(Point, Iter, Left: 10, Right: 20, Value: 1020);
1553	++Iter;
1554	EXPECT_EQ(Iter, Tree.find_end());
1555	}
1556	{
1557	// Start searching for '15'.
1558	Point = 15;
1559	UUIter Iter = Tree.find(Point);
1560	ASSERT_TRUE(Iter != Tree.find_end());
1561	checkData(Point, Iter, Left: 15, Right: 25, Value: 1525);
1562	++Iter;
1563	ASSERT_TRUE(Iter != Tree.find_end());
1564	checkData(Point, Iter, Left: 10, Right: 20, Value: 1020);
1565	++Iter;
1566	EXPECT_EQ(Iter, Tree.find_end());
1567	}
1568	{
1569	// Start searching for '20'.
1570	Point = 20;
1571	UUIter Iter = Tree.find(Point);
1572	ASSERT_TRUE(Iter != Tree.find_end());
1573	checkData(Point, Iter, Left: 15, Right: 25, Value: 1525);
1574	++Iter;
1575	ASSERT_TRUE(Iter != Tree.find_end());
1576	checkData(Point, Iter, Left: 10, Right: 20, Value: 1020);
1577	++Iter;
1578	EXPECT_EQ(Iter, Tree.find_end());
1579	}
1580	{
1581	// Start searching for '25'.
1582	Point = 25;
1583	UUIter Iter = Tree.find(Point);
1584	ASSERT_TRUE(Iter != Tree.find_end());
1585	checkData(Point, Iter, Left: 15, Right: 25, Value: 1525);
1586	++Iter;
1587	EXPECT_EQ(Iter, Tree.find_end());
1588	}
1589	// Invalid interval values.
1590	{
1591	Point = 5;
1592	UUIter Iter = Tree.find(Point);
1593	EXPECT_EQ(Iter, Tree.find_end());
1594	}
1595	{
1596	Point = 45;
1597	UUIter Iter = Tree.find(Point);
1598	EXPECT_EQ(Iter, Tree.find_end());
1599	}
1600	{
1601	Point = 70;
1602	UUIter Iter = Tree.find(Point);
1603	EXPECT_EQ(Iter, Tree.find_end());
1604	}
1605	}
1606
1607	} // namespace
1608