1 /*
2   ==============================================================================
3 
4    This file is part of the JUCE library.
5    Copyright (c) 2020 - Raw Material Software Limited
6 
7    JUCE is an open source library subject to commercial or open-source
8    licensing.
9 
10    The code included in this file is provided under the terms of the ISC license
11    http://www.isc.org/downloads/software-support-policy/isc-license. Permission
12    To use, copy, modify, and/or distribute this software for any purpose with or
13    without fee is hereby granted provided that the above copyright notice and
14    this permission notice appear in all copies.
15 
16    JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
17    EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
18    DISCLAIMED.
19 
20   ==============================================================================
21 */
22 
23 namespace juce
24 {
25 
26 #if JUCE_UNIT_TESTS
27 
28 class SparseSetTests  : public UnitTest
29 {
30 public:
SparseSetTests()31     SparseSetTests()
32         : UnitTest ("SparseSet class", UnitTestCategories::containers)
33     {}
34 
runTest()35     void runTest() override
36     {
37         beginTest ("basic operations");
38         {
39             SparseSet<int> set;
40 
41             expect (set.isEmpty());
42             expectEquals (set.size(), 0);
43             expectEquals (set.getNumRanges(), 0);
44             expect (set.getTotalRange().isEmpty());
45 
46             set.addRange ({0, 10});
47             expect (! set.isEmpty());
48             expectEquals (set.size(), 10);
49             expectEquals (set.getNumRanges(), 1);
50             expect (! set.getTotalRange().isEmpty());
51             expect (set.getRange (0) == Range<int> (0, 10));
52 
53             expectEquals (set[0], 0);
54             expectEquals (set[5], 5);
55             expectEquals (set[9], 9);
56             // Index out of range yields a default value for a type
57             expectEquals (set[10], 0);
58             expect (set.contains (0));
59             expect (set.contains (9));
60             expect (! set.contains (10));
61         }
62 
63         beginTest ("adding ranges");
64         {
65             SparseSet<int> set;
66 
67             // Adding same range twice should yield just a single range
68             set.addRange ({0, 10});
69             set.addRange ({0, 10});
70             expectEquals (set.getNumRanges(), 1);
71             expect (set.getRange (0) == Range<int> (0, 10));
72 
73             // Adding already included range does not increase num ranges
74             set.addRange ({0, 2});
75             expectEquals (set.getNumRanges(), 1);
76             set.addRange ({8, 10});
77             expectEquals (set.getNumRanges(), 1);
78             set.addRange ({2, 5});
79             expectEquals (set.getNumRanges(), 1);
80 
81             // Adding non adjacent range includes total number of ranges
82             set.addRange ({-10, -5});
83             expectEquals (set.getNumRanges(), 2);
84             expect (set.getRange (0) == Range<int> (-10, -5));
85             expect (set.getRange (1) == Range<int> (0, 10));
86             expect (set.getTotalRange() == Range<int> (-10, 10));
87 
88             set.addRange ({15, 20});
89             expectEquals (set.getNumRanges(), 3);
90             expect (set.getRange (0) == Range<int> (-10, -5));
91             expect (set.getRange (1) == Range<int> (0, 10));
92             expect (set.getRange (2) == Range<int> (15, 20));
93             expect (set.getTotalRange() == Range<int> (-10, 20));
94 
95             // Adding adjacent ranges merges them.
96             set.addRange ({-5, -3});
97             expectEquals (set.getNumRanges(), 3);
98             expect (set.getRange (0) == Range<int> (-10, -3));
99             expect (set.getRange (1) == Range<int> (0, 10));
100             expect (set.getRange (2) == Range<int> (15, 20));
101             expect (set.getTotalRange() == Range<int> (-10, 20));
102 
103             set.addRange ({20, 25});
104             expectEquals (set.getNumRanges(), 3);
105             expect (set.getRange (0) == Range<int> (-10, -3));
106             expect (set.getRange (1) == Range<int> (0, 10));
107             expect (set.getRange (2) == Range<int> (15, 25));
108             expect (set.getTotalRange() == Range<int> (-10, 25));
109 
110             // Adding range containing other ranges merges them
111             set.addRange ({-50, 50});
112             expectEquals (set.getNumRanges(), 1);
113             expect (set.getRange (0) == Range<int> (-50, 50));
114             expect (set.getTotalRange() == Range<int> (-50, 50));
115         }
116 
117         beginTest ("removing ranges");
118         {
119             SparseSet<int> set;
120 
121             set.addRange ({-20, -10});
122             set.addRange ({0, 10});
123             set.addRange ({20, 30});
124             expectEquals (set.getNumRanges(), 3);
125 
126             // Removing ranges not included in the set has no effect
127             set.removeRange ({-5, 5});
128             expectEquals (set.getNumRanges(), 3);
129 
130             // Removing partially overlapping range
131             set.removeRange ({-15, 5});
132             expectEquals (set.getNumRanges(), 3);
133             expect (set.getRange (0) == Range<int> (-20, -15));
134             expect (set.getRange (1) == Range<int> (5, 10));
135             expect (set.getRange (2) == Range<int> (20, 30));
136 
137             // Removing subrange of existing range
138             set.removeRange ({20, 22});
139             expectEquals (set.getNumRanges(), 3);
140             expect (set.getRange (2) == Range<int> (22, 30));
141 
142             set.removeRange ({28, 30});
143             expectEquals (set.getNumRanges(), 3);
144             expect (set.getRange (2) == Range<int> (22, 28));
145 
146             set.removeRange ({24, 26});
147             expectEquals (set.getNumRanges(), 4);
148             expect (set.getRange (0) == Range<int> (-20, -15));
149             expect (set.getRange (1) == Range<int> (5, 10));
150             expect (set.getRange (2) == Range<int> (22, 24));
151             expect (set.getRange (3) == Range<int> (26, 28));
152         }
153 
154         beginTest ("XORing ranges");
155         {
156             SparseSet<int> set;
157             set.addRange ({0, 10});
158 
159             set.invertRange ({0, 10});
160             expectEquals (set.getNumRanges(), 0);
161             set.invertRange ({0, 10});
162             expectEquals (set.getNumRanges(), 1);
163 
164             set.invertRange ({4, 6});
165             expectEquals (set.getNumRanges(), 2);
166             expect (set.getRange (0) == Range<int> (0, 4));
167             expect (set.getRange (1) == Range<int> (6, 10));
168 
169             set.invertRange ({-2, 2});
170             expectEquals (set.getNumRanges(), 3);
171             expect (set.getRange (0) == Range<int> (-2, 0));
172             expect (set.getRange (1) == Range<int> (2, 4));
173             expect (set.getRange (2) == Range<int> (6, 10));
174         }
175 
176         beginTest ("range contains & overlaps checks");
177         {
178             SparseSet<int> set;
179             set.addRange ({0, 10});
180 
181             expect (set.containsRange (Range<int> (0, 2)));
182             expect (set.containsRange (Range<int> (8, 10)));
183             expect (set.containsRange (Range<int> (0, 10)));
184 
185             expect (! set.containsRange (Range<int> (-2, 0)));
186             expect (! set.containsRange (Range<int> (-2, 10)));
187             expect (! set.containsRange (Range<int> (10, 12)));
188             expect (! set.containsRange (Range<int> (0, 12)));
189 
190             expect (set.overlapsRange (Range<int> (0, 2)));
191             expect (set.overlapsRange (Range<int> (8, 10)));
192             expect (set.overlapsRange (Range<int> (0, 10)));
193 
194             expect (! set.overlapsRange (Range<int> (-2, 0)));
195             expect (  set.overlapsRange (Range<int> (-2, 10)));
196             expect (! set.overlapsRange (Range<int> (10, 12)));
197             expect (  set.overlapsRange (Range<int> (0, 12)));
198         }
199     }
200 };
201 
202 static SparseSetTests sparseSetTests;
203 
204 #endif
205 
206 } // namespace juce
207