1/*
2 * Copyright (C) 2010 Google Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1.  Redistributions of source code must retain the above copyright
9 *     notice, this list of conditions and the following disclaimer.
10 * 2.  Redistributions in binary form must reproduce the above copyright
11 *     notice, this list of conditions and the following disclaimer in the
12 *     documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26// Tests for the interval tree class.
27
28#include "config.h"
29#include "platform/PODIntervalTree.h"
30
31#include "platform/Logging.h"
32#include "platform/testing/TreeTestHelpers.h"
33#include "wtf/Vector.h"
34#include "wtf/text/WTFString.h"
35
36#include <gtest/gtest.h>
37
38namespace blink {
39
40using TreeTestHelpers::initRandom;
41using TreeTestHelpers::nextRandom;
42
43#ifndef NDEBUG
44template<>
45struct ValueToString<float> {
46    static String string(const float& value) { return String::number(value); }
47};
48
49template<>
50struct ValueToString<void*> {
51    static String string(void* const& value)
52    {
53        return String::format("0x%p", value);
54    }
55};
56#endif
57
58TEST(PODIntervalTreeTest, TestInsertion)
59{
60    PODIntervalTree<float> tree;
61    tree.add(PODInterval<float>(2, 4));
62    ASSERT_TRUE(tree.checkInvariants());
63}
64
65TEST(PODIntervalTreeTest, TestInsertionAndQuery)
66{
67    PODIntervalTree<float> tree;
68    tree.add(PODInterval<float>(2, 4));
69    ASSERT_TRUE(tree.checkInvariants());
70    Vector<PODInterval<float> > result = tree.allOverlaps(PODInterval<float>(1, 3));
71    EXPECT_EQ(1U, result.size());
72    EXPECT_EQ(2, result[0].low());
73    EXPECT_EQ(4, result[0].high());
74}
75
76TEST(PODIntervalTreeTest, TestQueryAgainstZeroSizeInterval)
77{
78    PODIntervalTree<float> tree;
79    tree.add(PODInterval<float>(1, 2.5));
80    tree.add(PODInterval<float>(3.5, 5));
81    tree.add(PODInterval<float>(2, 4));
82    ASSERT_TRUE(tree.checkInvariants());
83    Vector<PODInterval<float> > result = tree.allOverlaps(PODInterval<float>(3, 3));
84    EXPECT_EQ(1U, result.size());
85    EXPECT_EQ(2, result[0].low());
86    EXPECT_EQ(4, result[0].high());
87}
88
89#ifndef NDEBUG
90template<>
91struct ValueToString<int*> {
92    static String string(int* const& value)
93    {
94        return String::format("0x%p", value);
95    }
96};
97#endif
98
99TEST(PODIntervalTreeTest, TestDuplicateElementInsertion)
100{
101    PODIntervalTree<float, int*> tree;
102    int tmp1 = 1;
103    int tmp2 = 2;
104    typedef PODIntervalTree<float, int*>::IntervalType IntervalType;
105    IntervalType interval1(1, 3, &tmp1);
106    IntervalType interval2(1, 3, &tmp2);
107    tree.add(interval1);
108    tree.add(interval2);
109    ASSERT_TRUE(tree.checkInvariants());
110    EXPECT_TRUE(tree.contains(interval1));
111    EXPECT_TRUE(tree.contains(interval2));
112    EXPECT_TRUE(tree.remove(interval1));
113    EXPECT_TRUE(tree.contains(interval2));
114    EXPECT_FALSE(tree.contains(interval1));
115    EXPECT_TRUE(tree.remove(interval2));
116    EXPECT_EQ(0, tree.size());
117}
118
119namespace {
120
121struct UserData1 {
122public:
123    UserData1()
124        : a(0), b(1) { }
125
126    float a;
127    int b;
128};
129
130} // anonymous namespace
131
132#ifndef NDEBUG
133template<>
134struct ValueToString<UserData1> {
135    static String string(const UserData1& value)
136    {
137        return String("[UserData1 a=") + String::number(value.a) + " b=" + String::number(value.b) + "]";
138    }
139};
140#endif
141
142TEST(PODIntervalTreeTest, TestInsertionOfComplexUserData)
143{
144    PODIntervalTree<float, UserData1> tree;
145    UserData1 data1;
146    data1.a = 5;
147    data1.b = 6;
148    tree.add(tree.createInterval(2, 4, data1));
149    ASSERT_TRUE(tree.checkInvariants());
150}
151
152TEST(PODIntervalTreeTest, TestQueryingOfComplexUserData)
153{
154    PODIntervalTree<float, UserData1> tree;
155    UserData1 data1;
156    data1.a = 5;
157    data1.b = 6;
158    tree.add(tree.createInterval(2, 4, data1));
159    ASSERT_TRUE(tree.checkInvariants());
160    Vector<PODInterval<float, UserData1> > overlaps = tree.allOverlaps(tree.createInterval(3, 5, data1));
161    EXPECT_EQ(1U, overlaps.size());
162    EXPECT_EQ(5, overlaps[0].data().a);
163    EXPECT_EQ(6, overlaps[0].data().b);
164}
165
166namespace {
167
168class EndpointType1 {
169public:
170    explicit EndpointType1(int value)
171        : m_value(value) { }
172
173    int value() const { return m_value; }
174
175    bool operator<(const EndpointType1& other) const { return m_value < other.m_value; }
176    bool operator==(const EndpointType1& other) const { return m_value == other.m_value; }
177
178private:
179    int m_value;
180    // These operators should not be called by the interval tree.
181    bool operator>(const EndpointType1& other);
182    bool operator<=(const EndpointType1& other);
183    bool operator>=(const EndpointType1& other);
184    bool operator!=(const EndpointType1& other);
185};
186
187} // anonymous namespace
188
189#ifndef NDEBUG
190template<>
191struct ValueToString<EndpointType1> {
192    static String string(const EndpointType1& value)
193    {
194        return String("[EndpointType1 value=") + String::number(value.value()) + "]";
195    }
196};
197#endif
198
199TEST(PODIntervalTreeTest, TestTreeDoesNotRequireMostOperators)
200{
201    PODIntervalTree<EndpointType1> tree;
202    tree.add(tree.createInterval(EndpointType1(1), EndpointType1(2)));
203    ASSERT_TRUE(tree.checkInvariants());
204}
205
206// Uncomment to debug a failure of the insertion and deletion test. Won't work
207// in release builds.
208// #define DEBUG_INSERTION_AND_DELETION_TEST
209
210#ifndef NDEBUG
211template<>
212struct ValueToString<int> {
213    static String string(const int& value) { return String::number(value); }
214};
215#endif
216
217namespace {
218
219void InsertionAndDeletionTest(int32_t seed, int treeSize)
220{
221    initRandom(seed);
222    int maximumValue = treeSize;
223    // Build the tree
224    PODIntervalTree<int> tree;
225    Vector<PODInterval<int> > addedElements;
226    Vector<PODInterval<int> > removedElements;
227    for (int i = 0; i < treeSize; i++) {
228        int left = nextRandom(maximumValue);
229        int length = nextRandom(maximumValue);
230        PODInterval<int> interval(left, left + length);
231        tree.add(interval);
232#ifdef DEBUG_INSERTION_AND_DELETION_TEST
233        WTF_LOG_ERROR("*** Adding element %s", ValueToString<PODInterval<int> >::string(interval).ascii().data());
234#endif
235        addedElements.append(interval);
236    }
237    // Churn the tree's contents.
238    // First remove half of the elements in random order.
239    for (int i = 0; i < treeSize / 2; i++) {
240        int index = nextRandom(addedElements.size());
241#ifdef DEBUG_INSERTION_AND_DELETION_TEST
242        WTF_LOG_ERROR("*** Removing element %s", ValueToString<PODInterval<int> >::string(addedElements[index]).ascii().data());
243#endif
244        ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " << seed;
245        tree.remove(addedElements[index]);
246        removedElements.append(addedElements[index]);
247        addedElements.remove(index);
248        ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
249    }
250    // Now randomly add or remove elements.
251    for (int i = 0; i < 2 * treeSize; i++) {
252        bool add = false;
253        if (!addedElements.size())
254            add = true;
255        else if (!removedElements.size())
256            add = false;
257        else
258            add = (nextRandom(2) == 1);
259        if (add) {
260            int index = nextRandom(removedElements.size());
261#ifdef DEBUG_INSERTION_AND_DELETION_TEST
262            WTF_LOG_ERROR("*** Adding element %s", ValueToString<PODInterval<int> >::string(removedElements[index]).ascii().data());
263#endif
264            tree.add(removedElements[index]);
265            addedElements.append(removedElements[index]);
266            removedElements.remove(index);
267        } else {
268            int index = nextRandom(addedElements.size());
269#ifdef DEBUG_INSERTION_AND_DELETION_TEST
270            WTF_LOG_ERROR("*** Removing element %s", ValueToString<PODInterval<int> >::string(addedElements[index]).ascii().data());
271#endif
272            ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " << seed;
273            ASSERT_TRUE(tree.remove(addedElements[index])) << "Test failed for seed " << seed;
274            removedElements.append(addedElements[index]);
275            addedElements.remove(index);
276        }
277        ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
278    }
279}
280
281} // anonymous namespace
282
283TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest1)
284{
285    InsertionAndDeletionTest(13972, 100);
286}
287
288TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest2)
289{
290    InsertionAndDeletionTest(1283382113, 10);
291}
292
293TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest3)
294{
295    // This is the sequence of insertions and deletions that triggered
296    // the failure in RandomDeletionAndInsertionRegressionTest2.
297    PODIntervalTree<int> tree;
298    tree.add(tree.createInterval(0, 5));
299    ASSERT_TRUE(tree.checkInvariants());
300    tree.add(tree.createInterval(4, 5));
301    ASSERT_TRUE(tree.checkInvariants());
302    tree.add(tree.createInterval(8, 9));
303    ASSERT_TRUE(tree.checkInvariants());
304    tree.add(tree.createInterval(1, 4));
305    ASSERT_TRUE(tree.checkInvariants());
306    tree.add(tree.createInterval(3, 5));
307    ASSERT_TRUE(tree.checkInvariants());
308    tree.add(tree.createInterval(4, 12));
309    ASSERT_TRUE(tree.checkInvariants());
310    tree.add(tree.createInterval(0, 2));
311    ASSERT_TRUE(tree.checkInvariants());
312    tree.add(tree.createInterval(0, 2));
313    ASSERT_TRUE(tree.checkInvariants());
314    tree.add(tree.createInterval(9, 13));
315    ASSERT_TRUE(tree.checkInvariants());
316    tree.add(tree.createInterval(0, 1));
317    ASSERT_TRUE(tree.checkInvariants());
318    tree.remove(tree.createInterval(0, 2));
319    ASSERT_TRUE(tree.checkInvariants());
320    tree.remove(tree.createInterval(9, 13));
321    ASSERT_TRUE(tree.checkInvariants());
322    tree.remove(tree.createInterval(0, 2));
323    ASSERT_TRUE(tree.checkInvariants());
324    tree.remove(tree.createInterval(0, 1));
325    ASSERT_TRUE(tree.checkInvariants());
326    tree.remove(tree.createInterval(4, 5));
327    ASSERT_TRUE(tree.checkInvariants());
328    tree.remove(tree.createInterval(4, 12));
329    ASSERT_TRUE(tree.checkInvariants());
330}
331
332TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest4)
333{
334    // Even further reduced test case for RandomDeletionAndInsertionRegressionTest3.
335    PODIntervalTree<int> tree;
336    tree.add(tree.createInterval(0, 5));
337    ASSERT_TRUE(tree.checkInvariants());
338    tree.add(tree.createInterval(8, 9));
339    ASSERT_TRUE(tree.checkInvariants());
340    tree.add(tree.createInterval(1, 4));
341    ASSERT_TRUE(tree.checkInvariants());
342    tree.add(tree.createInterval(3, 5));
343    ASSERT_TRUE(tree.checkInvariants());
344    tree.add(tree.createInterval(4, 12));
345    ASSERT_TRUE(tree.checkInvariants());
346    tree.remove(tree.createInterval(4, 12));
347    ASSERT_TRUE(tree.checkInvariants());
348}
349
350} // namespace blink
351