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 305