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 12 RangeList::RangeList() 13 : BObjectList<Range>(20, true) 14 { 15 } 16 17 18 RangeList::~RangeList() 19 { 20 } 21 22 23 status_t 24 RangeList::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 79 status_t 80 RangeList::AddRange(const Range& range) 81 { 82 return AddRange(range.lowerBound, range.upperBound); 83 } 84 85 86 void 87 RangeList::RemoveRangeAt(int32 index) 88 { 89 if (index < 0 || index >= CountItems()) 90 return; 91 92 RemoveItem(ItemAt(index)); 93 } 94 95 96 bool 97 RangeList::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 111 int32 112 RangeList::CountRanges() const 113 { 114 return CountItems(); 115 } 116 117 118 const Range* 119 RangeList::RangeAt(int32 index) const 120 { 121 return ItemAt(index); 122 } 123 124 125 void 126 RangeList::_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