juce/source/src/containers/juce_SparseSet.h

   1 /*
   2   ==============================================================================
   3
   4    This file is part of the JUCE library - "Jules' Utility Class Extensions"
   5    Copyright 2004-11 by Raw Material Software Ltd.
   6
   7   ------------------------------------------------------------------------------
   8
   9    JUCE can be redistributed and/or modified under the terms of the GNU General
  10    Public License (Version 2), as published by the Free Software Foundation.
  11    A copy of the license is included in the JUCE distribution, or can be found
  12    online at www.gnu.org/licenses.
  13
  14    JUCE is distributed in the hope that it will be useful, but WITHOUT ANY
  15    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  16    A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
  17
  18   ------------------------------------------------------------------------------
  19
  20    To release a closed-source product which uses JUCE, commercial licenses are
  21    available: visit www.rawmaterialsoftware.com/juce for more information.
  22
  23   ==============================================================================
  24 */
  25
  26 #ifndef __JUCE_SPARSESET_JUCEHEADER__
  27 #define __JUCE_SPARSESET_JUCEHEADER__
  28
  29 #include "../maths/juce_Range.h"
  30 #include "../threads/juce_CriticalSection.h"
  31
  32
  33 //==============================================================================
  34 /**
  35     Holds a set of primitive values, storing them as a set of ranges.
  36
  37     This container acts like an array, but can efficiently hold large continguous
  38     ranges of values. It's quite a specialised class, mostly useful for things
  39     like keeping the set of selected rows in a listbox.
  40
  41     The type used as a template paramter must be an integer type, such as int, short,
  42     int64, etc.
  43 */
  44 template <class Type>
  45 class SparseSet
  46 {
  47 public:
  48     //==============================================================================
  49     /** Creates a new empty set. */
  50     SparseSet()
  51     {
  52     }
  53
  54     /** Creates a copy of another SparseSet. */
  55     SparseSet (const SparseSet<Type>& other)
  56         : values (other.values)
  57     {
  58     }
  59
  60     //==============================================================================
  61     /** Clears the set. */
  62     void clear()
  63     {
  64         values.clear();
  65     }
  66
  67     /** Checks whether the set is empty.
  68
  69         This is much quicker than using (size() == 0).
  70     */
  71     bool isEmpty() const noexcept
  72     {
  73         return values.size() == 0;
  74     }
  75
  76     /** Returns the number of values in the set.
  77
  78         Because of the way the data is stored, this method can take longer if there
  79         are a lot of items in the set. Use isEmpty() for a quick test of whether there
  80         are any items.
  81     */
  82     Type size() const
  83     {
  84         Type total (0);
  85
  86         for (int i = 0; i < values.size(); i += 2)
  87             total += values.getUnchecked (i + 1) - values.getUnchecked (i);
  88
  89         return total;
  90     }
  91
  92     /** Returns one of the values in the set.
  93
  94         @param index    the index of the value to retrieve, in the range 0 to (size() - 1).
  95         @returns        the value at this index, or 0 if it's out-of-range
  96     */
  97     Type operator[] (Type index) const
  98     {
  99         for (int i = 0; i < values.size(); i += 2)
 100         {
 101             const Type start (values.getUnchecked (i));
 102             const Type len (values.getUnchecked (i + 1) - start);
 103
 104             if (index < len)
 105                 return start + index;
 106
 107             index -= len;
 108         }
 109
 110         return Type();
 111     }
 112
 113     /** Checks whether a particular value is in the set. */
 114     bool contains (const Type valueToLookFor) const
 115     {
 116         for (int i = 0; i < values.size(); ++i)
 117             if (valueToLookFor < values.getUnchecked(i))
 118                 return (i & 1) != 0;
 119
 120         return false;
 121     }
 122
 123     //==============================================================================
 124     /** Returns the number of contiguous blocks of values.
 125         @see getRange
 126     */
 127     int getNumRanges() const noexcept
 128     {
 129         return values.size() >> 1;
 130     }
 131
 132     /** Returns one of the contiguous ranges of values stored.
 133         @param rangeIndex   the index of the range to look up, between 0
 134                             and (getNumRanges() - 1)
 135         @see getTotalRange
 136     */
 137     const Range<Type> getRange (const int rangeIndex) const
 138     {
 139         if (isPositiveAndBelow (rangeIndex, getNumRanges()))
 140             return Range<Type> (values.getUnchecked (rangeIndex << 1),
 141                                 values.getUnchecked ((rangeIndex << 1) + 1));
 142         else
 143             return Range<Type>();
 144     }
 145
 146     /** Returns the range between the lowest and highest values in the set.
 147         @see getRange
 148     */
 149     const Range<Type> getTotalRange() const
 150     {
 151         if (values.size() > 0)
 152         {
 153             jassert ((values.size() & 1) == 0);
 154             return Range<Type> (values.getUnchecked (0),
 155                                 values.getUnchecked (values.size() - 1));
 156         }
 157
 158         return Range<Type>();
 159     }
 160
 161     //==============================================================================
 162     /** Adds a range of contiguous values to the set.
 163         e.g. addRange (Range \<int\> (10, 14)) will add (10, 11, 12, 13) to the set.
 164     */
 165     void addRange (const Range<Type>& range)
 166     {
 167         jassert (range.getLength() >= 0);
 168         if (range.getLength() > 0)
 169         {
 170             removeRange (range);
 171
 172             values.addUsingDefaultSort (range.getStart());
 173             values.addUsingDefaultSort (range.getEnd());
 174
 175             simplify();
 176         }
 177     }
 178
 179     /** Removes a range of values from the set.
 180         e.g. removeRange (Range\<int\> (10, 14)) will remove (10, 11, 12, 13) from the set.
 181     */
 182     void removeRange (const Range<Type>& rangeToRemove)
 183     {
 184         jassert (rangeToRemove.getLength() >= 0);
 185
 186         if (rangeToRemove.getLength() > 0
 187              && values.size() > 0
 188              && rangeToRemove.getStart() < values.getUnchecked (values.size() - 1)
 189              && values.getUnchecked(0) < rangeToRemove.getEnd())
 190         {
 191             const bool onAtStart = contains (rangeToRemove.getStart() - 1);
 192             const Type lastValue (jmin (rangeToRemove.getEnd(), values.getLast()));
 193             const bool onAtEnd = contains (lastValue);
 194
 195             for (int i = values.size(); --i >= 0;)
 196             {
 197                 if (values.getUnchecked(i) <= lastValue)
 198                 {
 199                     while (values.getUnchecked(i) >= rangeToRemove.getStart())
 200                     {
 201                         values.remove (i);
 202
 203                         if (--i < 0)
 204                             break;
 205                     }
 206
 207                     break;
 208                 }
 209             }
 210
 211             if (onAtStart)   values.addUsingDefaultSort (rangeToRemove.getStart());
 212             if (onAtEnd)     values.addUsingDefaultSort (lastValue);
 213
 214             simplify();
 215         }
 216     }
 217
 218     /** Does an XOR of the values in a given range. */
 219     void invertRange (const Range<Type>& range)
 220     {
 221         SparseSet newItems;
 222         newItems.addRange (range);
 223
 224         int i;
 225         for (i = getNumRanges(); --i >= 0;)
 226             newItems.removeRange (getRange (i));
 227
 228         removeRange (range);
 229
 230         for (i = newItems.getNumRanges(); --i >= 0;)
 231             addRange (newItems.getRange(i));
 232     }
 233
 234     /** Checks whether any part of a given range overlaps any part of this set. */
 235     bool overlapsRange (const Range<Type>& range)
 236     {
 237         if (range.getLength() > 0)
 238         {
 239             for (int i = getNumRanges(); --i >= 0;)
 240             {
 241                 if (values.getUnchecked ((i << 1) + 1) <= range.getStart())
 242                     return false;
 243
 244                 if (values.getUnchecked (i << 1) < range.getEnd())
 245                     return true;
 246             }
 247         }
 248
 249         return false;
 250     }
 251
 252     /** Checks whether the whole of a given range is contained within this one. */
 253     bool containsRange (const Range<Type>& range)
 254     {
 255         if (range.getLength() > 0)
 256         {
 257             for (int i = getNumRanges(); --i >= 0;)
 258             {
 259                 if (values.getUnchecked ((i << 1) + 1) <= range.getStart())
 260                     return false;
 261
 262                 if (values.getUnchecked (i << 1) <= range.getStart()
 263                      && range.getEnd() <= values.getUnchecked ((i << 1) + 1))
 264                     return true;
 265             }
 266         }
 267
 268         return false;
 269     }
 270
 271     //==============================================================================
 272     bool operator== (const SparseSet<Type>& other) noexcept
 273     {
 274         return values == other.values;
 275     }
 276
 277     bool operator!= (const SparseSet<Type>& other) noexcept
 278     {
 279         return values != other.values;
 280     }
 281
 282 private:
 283     //==============================================================================
 284     // alternating start/end values of ranges of values that are present.
 285     Array<Type, DummyCriticalSection> values;
 286
 287     void simplify()
 288     {
 289         jassert ((values.size() & 1) == 0);
 290
 291         for (int i = values.size(); --i > 0;)
 292             if (values.getUnchecked(i) == values.getUnchecked (i - 1))
 293                 values.removeRange (--i, 2);
 294     }
 295 };
 296
 297
 298
 299 #endif   // __JUCE_SPARSESET_JUCEHEADER__