OpenShot Audio Library | OpenShotAudio  0.3.1
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()
32  : UnitTest ("SparseSet class", UnitTestCategories::containers)
33  {}
34 
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