headers/private/shared/RangeArray.h

   1 /*
   2  * Copyright 2011, Ingo Weinhold, ingo_weinhold@gmx.de.
   3  * Distributed under the terms of the MIT License.
   4  */
   5 #ifndef _RANGE_ARRAY_H
   6 #define _RANGE_ARRAY_H
   7
   8
   9 #include <algorithm>
  10
  11 #include <Array.h>
  12
  13
  14 namespace BPrivate {
  15
  16
  17 template<typename Value>
  18 struct Range {
  19         Value   offset;
  20         Value   size;
  21
  22         Range(const Value& offset, const Value& size)
  23                 :
  24                 offset(offset),
  25                 size(size)
  26         {
  27         }
  28
  29         Value EndOffset() const
  30         {
  31                 return offset + size;
  32         }
  33 };
  34
  35
  36 template<typename Value>
  37 class RangeArray {
  38 public:
  39                         typedef Range<Value> RangeType;
  40
  41 public:
  42         inline                                          RangeArray();
  43         inline                                          RangeArray(const RangeArray<Value>& other);
  44
  45         inline  int32                           CountRanges() const
  46                                                                         { return fRanges.Count(); }
  47         inline  bool                            IsEmpty() const
  48                                                                         { return fRanges.IsEmpty(); }
  49         inline  const RangeType*        Ranges() const
  50                                                                         { return fRanges.Elements(); }
  51
  52         inline  bool                            AddRange(const RangeType& range);
  53                         bool                            AddRange(const Value& offset,
  54                                                                         const Value& size);
  55         inline  bool                            RemoveRange(const RangeType& range);
  56                         bool                            RemoveRange(const Value& offset,
  57                                                                         const Value& size);
  58         inline  bool                            RemoveRanges(int32 index, int32 count = 1);
  59
  60         inline  void                            Clear()                 { fRanges.Clear(); }
  61         inline  void                            MakeEmpty()             { fRanges.MakeEmpty(); }
  62
  63         inline  bool                            IntersectsWith(const RangeType& range) const;
  64                         bool                            IntersectsWith(const Value& offset,
  65                                                                         const Value& size) const;
  66
  67                         int32                           InsertionIndex(const Value& offset) const;
  68
  69         inline  const RangeType&        RangeAt(int32 index) const
  70                                                                         { return fRanges.ElementAt(index); }
  71
  72         inline  const RangeType&        operator[](int32 index) const
  73                                                                         { return fRanges[index]; }
  74
  75         inline  RangeArray<Value>&      operator=(const RangeArray<Value>& other);
  76
  77 private:
  78         inline   RangeType&                     _RangeAt(int32 index)
  79                                                                         { return fRanges.ElementAt(index); }
  80
  81 private:
  82                         Array<RangeType>        fRanges;
  83 };
  84
  85
  86 template<typename Value>
  87 inline
  88 RangeArray<Value>::RangeArray()
  89 {
  90 }
  91
  92
  93 template<typename Value>
  94 inline
  95 RangeArray<Value>::RangeArray(const RangeArray<Value>& other)
  96         :
  97         fRanges(other.fRanges)
  98 {
  99 }
 100
 101
 102 template<typename Value>
 103 inline bool
 104 RangeArray<Value>::AddRange(const RangeType& range)
 105 {
 106         return AddRange(range.offset, range.size);
 107 }
 108
 109
 110 /*!     Adds the range starting at \a offset with size \a size.
 111
 112         The range is automatically joined with ranges it adjoins or overlaps with.
 113
 114         \return \c true, if the range was added successfully, \c false, if a memory
 115                 allocation failed.
 116 */
 117 template<typename Value>
 118 bool
 119 RangeArray<Value>::AddRange(const Value& offset, const Value& size)
 120 {
 121         if (size == 0)
 122                 return true;
 123
 124         int32 index = InsertionIndex(offset);
 125
 126         // determine the last range the range intersects with/adjoins
 127         Value endOffset = offset + size;
 128         int32 endIndex = index;
 129                 // index after the last affected range
 130         int32 count = CountRanges();
 131         while (endIndex < count && RangeAt(endIndex).offset <= endOffset)
 132                 endIndex++;
 133
 134         // determine whether the range adjoins the previous range
 135         if (index > 0 && offset == RangeAt(index - 1).EndOffset())
 136                 index--;
 137
 138         if (index == endIndex) {
 139                 // no joining possible -- just insert the new range
 140                 return fRanges.Insert(RangeType(offset, size), index);
 141         }
 142
 143         // Joining is possible. We'll adjust the first affected range and remove the
 144         // others (if any).
 145         endOffset = std::max(endOffset, RangeAt(endIndex - 1).EndOffset());
 146         RangeType& firstRange = _RangeAt(index);
 147         firstRange.offset = std::min(firstRange.offset, offset);
 148         firstRange.size = endOffset - firstRange.offset;
 149
 150         if (index + 1 < endIndex)
 151                 RemoveRanges(index + 1, endIndex - index - 1);
 152
 153         return true;
 154 }
 155
 156
 157 template<typename Value>
 158 inline bool
 159 RangeArray<Value>::RemoveRange(const RangeType& range)
 160 {
 161         return RemoveRange(range.offset, range.size);
 162 }
 163
 164
 165 /*!     Removes the range starting at \a offset with size \a size.
 166
 167         Ranges that are completely covered by the given range are removed. Ranges
 168         that partially intersect with it are cut accordingly.
 169
 170         If a range is split into two ranges by the operation, a memory allocation
 171         might be necessary and the method can fail, if the memory allocation fails.
 172
 173         \return \c true, if the range was removed successfully, \c false, if a
 174                 memory allocation failed.
 175 */
 176 template<typename Value>
 177 bool
 178 RangeArray<Value>::RemoveRange(const Value& offset, const Value& size)
 179 {
 180         if (size == 0)
 181                 return true;
 182
 183         int32 index = InsertionIndex(offset);
 184
 185         // determine the last range the range intersects with
 186         Value endOffset = offset + size;
 187         int32 endIndex = index;
 188                 // index after the last affected range
 189         int32 count = CountRanges();
 190         while (endIndex < count && RangeAt(endIndex).offset < endOffset)
 191                 endIndex++;
 192
 193         if (index == endIndex) {
 194                 // the given range doesn't intersect with any exiting range
 195                 return true;
 196         }
 197
 198         // determine what ranges to remove completely
 199         RangeType& firstRange = _RangeAt(index);
 200         RangeType& lastRange = _RangeAt(endIndex - 1);
 201
 202         int32 firstRemoveIndex = firstRange.offset >= offset ? index : index + 1;
 203         int32 endRemoveIndex = lastRange.EndOffset() <= endOffset
 204                 ? endIndex : endIndex - 1;
 205
 206         if (firstRemoveIndex > endRemoveIndex) {
 207                 // The range lies in the middle of an existing range. We need to split.
 208                 RangeType newRange(endOffset, firstRange.EndOffset() - endOffset);
 209                 if (!fRanges.Insert(newRange, index + 1))
 210                         return false;
 211
 212                 firstRange.size = offset - firstRange.offset;
 213                 return true;
 214         }
 215
 216         // cut first and last range
 217         if (index < firstRemoveIndex)
 218                 firstRange.size = offset - firstRange.offset;
 219
 220         if (endOffset > endRemoveIndex) {
 221                 lastRange.size = lastRange.EndOffset() - endOffset;
 222                 lastRange.offset = endOffset;
 223         }
 224
 225         // remove ranges
 226         if (firstRemoveIndex < endRemoveIndex)
 227                 RemoveRanges(firstRemoveIndex, endRemoveIndex - firstRemoveIndex);
 228
 229         return true;
 230 }
 231
 232
 233 template<typename Value>
 234 inline bool
 235 RangeArray<Value>::RemoveRanges(int32 index, int32 count)
 236 {
 237         return fRanges.Remove(index, count);
 238 }
 239
 240
 241 template<typename Value>
 242 inline bool
 243 RangeArray<Value>::IntersectsWith(const RangeType& range) const
 244 {
 245         return IntersectsWith(range.offset, range.size);
 246 }
 247
 248
 249 template<typename Value>
 250 bool
 251 RangeArray<Value>::IntersectsWith(const Value& offset, const Value& size) const
 252 {
 253         int32 index = InsertionIndex(offset);
 254         return index < CountRanges() && RangeAt(index).offset < offset + size;
 255 }
 256
 257
 258 /*!     Returns the insertion index of a range starting at \a offset.
 259
 260         If the array contains a range that starts at, includes (but doesn't end at)
 261         \a offset, the index of that range is returned. If \a offset lies in between
 262         two ranges or before the first range, the index of the range following
 263         \a offset is returned. Otherwise \c CountRanges() is returned.
 264
 265         \return The insertion index for a range starting at \a offset.
 266 */
 267 template<typename Value>
 268 int32
 269 RangeArray<Value>::InsertionIndex(const Value& offset) const
 270 {
 271         // binary search the index
 272         int32 lower = 0;
 273         int32 upper = CountRanges();
 274
 275         while (lower < upper) {
 276                 int32 mid = (lower + upper) / 2;
 277                 const RangeType& range = RangeAt(mid);
 278                 if (offset >= range.EndOffset())
 279                         lower = mid + 1;
 280                 else
 281                         upper = mid;
 282         }
 283
 284         return lower;
 285 }
 286
 287
 288 template<typename Value>
 289 inline RangeArray<Value>&
 290 RangeArray<Value>::operator=(const RangeArray<Value>& other)
 291 {
 292         fRanges = other.fRanges;
 293         return *this;
 294 }
 295
 296
 297 }       // namespace BPrivate
 298
 299
 300 using BPrivate::Range;
 301 using BPrivate::RangeArray;
 302
 303
 304 #endif  // _RANGE_ARRAY_H