OpenShot Library | libopenshot-audio  0.2.0
juce_SparseSet.cpp
1 /*
2  ==============================================================================
3 
4  This file is part of the JUCE library.
5  Copyright (c) 2018 - ROLI Ltd.
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:
31  SparseSetTests() : UnitTest ("SparseSet class", "Containers") {}
32 
33  void runTest() override
34  {
35  beginTest ("basic operations");
36  {
37  SparseSet<int> set;
38 
39  expect (set.isEmpty());
40  expectEquals (set.size(), 0);
41  expectEquals (set.getNumRanges(), 0);
42  expect (set.getTotalRange().isEmpty());
43 
44  set.addRange ({0, 10});
45  expect (! set.isEmpty());
46  expectEquals (set.size(), 10);
47  expectEquals (set.getNumRanges(), 1);
48  expect (! set.getTotalRange().isEmpty());
49  expect (set.getRange (0) == Range<int> (0, 10));
50 
51  expectEquals (set[0], 0);
52  expectEquals (set[5], 5);
53  expectEquals (set[9], 9);
54  // Index out of range yields a default value for a type
55  expectEquals (set[10], 0);
56  expect (set.contains (0));
57  expect (set.contains (9));
58  expect (! set.contains (10));
59  }
60 
61  beginTest ("adding ranges");
62  {
63  SparseSet<int> set;
64 
65  // Adding same range twice should yield just a single range
66  set.addRange ({0, 10});
67  set.addRange ({0, 10});
68  expectEquals (set.getNumRanges(), 1);
69  expect (set.getRange (0) == Range<int> (0, 10));
70 
71  // Adding already included range does not increase num ranges
72  set.addRange ({0, 2});
73  expectEquals (set.getNumRanges(), 1);
74  set.addRange ({8, 10});
75  expectEquals (set.getNumRanges(), 1);
76  set.addRange ({2, 5});
77  expectEquals (set.getNumRanges(), 1);
78 
79  // Adding non adjacent range includes total number of ranges
80  set.addRange ({-10, -5});
81  expectEquals (set.getNumRanges(), 2);
82  expect (set.getRange (0) == Range<int> (-10, -5));
83  expect (set.getRange (1) == Range<int> (0, 10));
84  expect (set.getTotalRange() == Range<int> (-10, 10));
85 
86  set.addRange ({15, 20});
87  expectEquals (set.getNumRanges(), 3);
88  expect (set.getRange (0) == Range<int> (-10, -5));
89  expect (set.getRange (1) == Range<int> (0, 10));
90  expect (set.getRange (2) == Range<int> (15, 20));
91  expect (set.getTotalRange() == Range<int> (-10, 20));
92 
93  // Adding adjacent ranges merges them.
94  set.addRange ({-5, -3});
95  expectEquals (set.getNumRanges(), 3);
96  expect (set.getRange (0) == Range<int> (-10, -3));
97  expect (set.getRange (1) == Range<int> (0, 10));
98  expect (set.getRange (2) == Range<int> (15, 20));
99  expect (set.getTotalRange() == Range<int> (-10, 20));
100 
101  set.addRange ({20, 25});
102  expectEquals (set.getNumRanges(), 3);
103  expect (set.getRange (0) == Range<int> (-10, -3));
104  expect (set.getRange (1) == Range<int> (0, 10));
105  expect (set.getRange (2) == Range<int> (15, 25));
106  expect (set.getTotalRange() == Range<int> (-10, 25));
107 
108  // Adding range containing other ranges merges them
109  set.addRange ({-50, 50});
110  expectEquals (set.getNumRanges(), 1);
111  expect (set.getRange (0) == Range<int> (-50, 50));
112  expect (set.getTotalRange() == Range<int> (-50, 50));
113  }
114 
115  beginTest ("removing ranges");
116  {
117  SparseSet<int> set;
118 
119  set.addRange ({-20, -10});
120  set.addRange ({0, 10});
121  set.addRange ({20, 30});
122  expectEquals (set.getNumRanges(), 3);
123 
124  // Removing ranges not included in the set has no effect
125  set.removeRange ({-5, 5});
126  expectEquals (set.getNumRanges(), 3);
127 
128  // Removing partially overlapping range
129  set.removeRange ({-15, 5});
130  expectEquals (set.getNumRanges(), 3);
131  expect (set.getRange (0) == Range<int> (-20, -15));
132  expect (set.getRange (1) == Range<int> (5, 10));
133  expect (set.getRange (2) == Range<int> (20, 30));
134 
135  // Removing subrange of existing range
136  set.removeRange ({20, 22});
137  expectEquals (set.getNumRanges(), 3);
138  expect (set.getRange (2) == Range<int> (22, 30));
139 
140  set.removeRange ({28, 30});
141  expectEquals (set.getNumRanges(), 3);
142  expect (set.getRange (2) == Range<int> (22, 28));
143 
144  set.removeRange ({24, 26});
145  expectEquals (set.getNumRanges(), 4);
146  expect (set.getRange (0) == Range<int> (-20, -15));
147  expect (set.getRange (1) == Range<int> (5, 10));
148  expect (set.getRange (2) == Range<int> (22, 24));
149  expect (set.getRange (3) == Range<int> (26, 28));
150  }
151 
152  beginTest ("XORing ranges");
153  {
154  SparseSet<int> set;
155  set.addRange ({0, 10});
156 
157  set.invertRange ({0, 10});
158  expectEquals (set.getNumRanges(), 0);
159  set.invertRange ({0, 10});
160  expectEquals (set.getNumRanges(), 1);
161 
162  set.invertRange ({4, 6});
163  expectEquals (set.getNumRanges(), 2);
164  expect (set.getRange (0) == Range<int> (0, 4));
165  expect (set.getRange (1) == Range<int> (6, 10));
166 
167  set.invertRange ({-2, 2});
168  expectEquals (set.getNumRanges(), 3);
169  expect (set.getRange (0) == Range<int> (-2, 0));
170  expect (set.getRange (1) == Range<int> (2, 4));
171  expect (set.getRange (2) == Range<int> (6, 10));
172  }
173 
174  beginTest ("range contains & overlaps checks");
175  {
176  SparseSet<int> set;
177  set.addRange ({0, 10});
178 
179  expect (set.containsRange (Range<int> (0, 2)));
180  expect (set.containsRange (Range<int> (8, 10)));
181  expect (set.containsRange (Range<int> (0, 10)));
182 
183  expect (! set.containsRange (Range<int> (-2, 0)));
184  expect (! set.containsRange (Range<int> (-2, 10)));
185  expect (! set.containsRange (Range<int> (10, 12)));
186  expect (! set.containsRange (Range<int> (0, 12)));
187 
188  expect (set.overlapsRange (Range<int> (0, 2)));
189  expect (set.overlapsRange (Range<int> (8, 10)));
190  expect (set.overlapsRange (Range<int> (0, 10)));
191 
192  expect (! set.overlapsRange (Range<int> (-2, 0)));
193  expect ( set.overlapsRange (Range<int> (-2, 10)));
194  expect (! set.overlapsRange (Range<int> (10, 12)));
195  expect ( set.overlapsRange (Range<int> (0, 12)));
196  }
197  }
198 };
199 
200 static SparseSetTests sparseSetTests;
201 
202 #endif
203 
204 } // namespace juce