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
14namespace BPrivate {
15
16
17template<typename Value>
18struct 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
36template<typename Value>
37class RangeArray {
38public:
39			typedef Range<Value> RangeType;
40
41public:
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
77private:
78	inline	 RangeType&			_RangeAt(int32 index)
79									{ return fRanges.ElementAt(index); }
80
81private:
82			Array<RangeType>	fRanges;
83};
84
85
86template<typename Value>
87inline
88RangeArray<Value>::RangeArray()
89{
90}
91
92
93template<typename Value>
94inline
95RangeArray<Value>::RangeArray(const RangeArray<Value>& other)
96	:
97	fRanges(other.fRanges)
98{
99}
100
101
102template<typename Value>
103inline bool
104RangeArray<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*/
117template<typename Value>
118bool
119RangeArray<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
157template<typename Value>
158inline bool
159RangeArray<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*/
176template<typename Value>
177bool
178RangeArray<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
233template<typename Value>
234inline bool
235RangeArray<Value>::RemoveRanges(int32 index, int32 count)
236{
237	return fRanges.Remove(index, count);
238}
239
240
241template<typename Value>
242inline bool
243RangeArray<Value>::IntersectsWith(const RangeType& range) const
244{
245	return IntersectsWith(range.offset, range.size);
246}
247
248
249template<typename Value>
250bool
251RangeArray<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*/
267template<typename Value>
268int32
269RangeArray<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
288template<typename Value>
289inline RangeArray<Value>&
290RangeArray<Value>::operator=(const RangeArray<Value>& other)
291{
292	fRanges = other.fRanges;
293	return *this;
294}
295
296
297}	// namespace BPrivate
298
299
300using BPrivate::Range;
301using BPrivate::RangeArray;
302
303
304#endif	// _RANGE_ARRAY_H
305