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