1/*
2 * Copyright 2013, Rene Gollent, rene@gollent.com.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include "RangeList.h"
8
9#include <AutoDeleter.h>
10
11
12RangeList::RangeList()
13	: BObjectList<Range>(20, true)
14{
15}
16
17
18RangeList::~RangeList()
19{
20}
21
22
23status_t
24RangeList::AddRange(int32 lowValue, int32 highValue)
25{
26	if (lowValue > highValue)
27		return B_BAD_VALUE;
28
29	int32 i = 0;
30	if (CountItems() != 0) {
31		for (; i < CountItems(); i++) {
32			Range* range = ItemAt(i);
33			if (lowValue < range->lowerBound) {
34				if (highValue < range->lowerBound) {
35					// the new range is completely below the bounds
36					// of the ranges we currently contain,
37					// insert it here.
38					break;
39				} else if (highValue <= range->upperBound) {
40					// the new range partly overlaps the lower
41					// current range
42					range->lowerBound = lowValue;
43					return B_OK;
44				} else {
45					// the new range completely encompasses
46					// the current range
47					range->lowerBound = lowValue;
48					range->upperBound = highValue;
49					_CollapseOverlappingRanges(i +1, highValue);
50				}
51
52			} else if (lowValue < range->upperBound) {
53				if (highValue <= range->upperBound) {
54					// the requested range is already completely contained
55					// within our existing range list
56					return B_OK;
57				} else {
58					range->upperBound = highValue;
59					_CollapseOverlappingRanges(i + 1, highValue);
60					return B_OK;
61				}
62			}
63		}
64	}
65
66	Range* range = new(std::nothrow) Range(lowValue, highValue);
67	if (range == NULL)
68		return B_NO_MEMORY;
69
70	BPrivate::ObjectDeleter<Range> rangeDeleter(range);
71	if (!AddItem(range, i))
72		return B_NO_MEMORY;
73
74	rangeDeleter.Detach();
75	return B_OK;
76}
77
78
79status_t
80RangeList::AddRange(const Range& range)
81{
82	return AddRange(range.lowerBound, range.upperBound);
83}
84
85
86void
87RangeList::RemoveRangeAt(int32 index)
88{
89	if (index < 0 || index >= CountItems())
90		return;
91
92	RemoveItem(ItemAt(index));
93}
94
95
96bool
97RangeList::Contains(int32 value) const
98{
99	for (int32 i = 0; i < CountItems(); i++) {
100		const Range* range = ItemAt(i);
101		if (value < range->lowerBound || value > range->upperBound)
102			break;
103		else if (value >= range->lowerBound && value <= range->upperBound)
104			return true;
105	}
106
107	return false;
108}
109
110
111int32
112RangeList::CountRanges() const
113{
114	return CountItems();
115}
116
117
118const Range*
119RangeList::RangeAt(int32 index) const
120{
121	return ItemAt(index);
122}
123
124
125void
126RangeList::_CollapseOverlappingRanges(int32 startIndex, int32 highValue)
127{
128	for (int32 i = startIndex; i < CountItems();) {
129		// check if it also overlaps any of the following
130		// ranges.
131		Range* nextRange = ItemAt(i);
132		if (nextRange->lowerBound > highValue)
133			return;
134		else if (nextRange->upperBound < highValue) {
135			RemoveItem(nextRange);
136			continue;
137		} else {
138			nextRange->lowerBound = highValue + 1;
139			return;
140		}
141	}
142}
143