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
RangeRange22 Range(const Value& offset, const Value& size)
23 :
24 offset(offset),
25 size(size)
26 {
27 }
28
EndOffsetRange29 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
CountRanges()45 inline int32 CountRanges() const
46 { return fRanges.Count(); }
IsEmpty()47 inline bool IsEmpty() const
48 { return fRanges.IsEmpty(); }
Ranges()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
Clear()60 inline void Clear() { fRanges.Clear(); }
MakeEmpty()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
RangeAt(int32 index)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:
_RangeAt(int32 index)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
RangeArray()88 RangeArray<Value>::RangeArray()
89 {
90 }
91
92
93 template<typename Value>
94 inline
RangeArray(const RangeArray<Value> & other)95 RangeArray<Value>::RangeArray(const RangeArray<Value>& other)
96 :
97 fRanges(other.fRanges)
98 {
99 }
100
101
102 template<typename Value>
103 inline bool
AddRange(const RangeType & range)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
AddRange(const Value & offset,const Value & size)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
RemoveRange(const RangeType & range)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
RemoveRange(const Value & offset,const Value & size)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
RemoveRanges(int32 index,int32 count)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
IntersectsWith(const RangeType & range)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
IntersectsWith(const Value & offset,const Value & size)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
InsertionIndex(const Value & offset)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