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