/*
 * Copyright 2013, Rene Gollent, rene@gollent.com.
 * Distributed under the terms of the MIT License.
 */


#include "RangeList.h"

#include <AutoDeleter.h>


RangeList::RangeList()
        :
        BObjectList<Range, true>(20)
{
}


RangeList::~RangeList()
{
}


status_t
RangeList::AddRange(int32 lowValue, int32 highValue)
{
        if (lowValue > highValue)
                return B_BAD_VALUE;

        int32 i = 0;
        if (CountItems() != 0) {
                for (; i < CountItems(); i++) {
                        Range* range = ItemAt(i);
                        if (lowValue < range->lowerBound) {
                                if (highValue < range->lowerBound) {
                                        // the new range is completely below the bounds
                                        // of the ranges we currently contain,
                                        // insert it here.
                                        break;
                                } else if (highValue <= range->upperBound) {
                                        // the new range partly overlaps the lower
                                        // current range
                                        range->lowerBound = lowValue;
                                        return B_OK;
                                } else {
                                        // the new range completely encompasses
                                        // the current range
                                        range->lowerBound = lowValue;
                                        range->upperBound = highValue;
                                        _CollapseOverlappingRanges(i +1, highValue);
                                }

                        } else if (lowValue < range->upperBound) {
                                if (highValue <= range->upperBound) {
                                        // the requested range is already completely contained
                                        // within our existing range list
                                        return B_OK;
                                } else {
                                        range->upperBound = highValue;
                                        _CollapseOverlappingRanges(i + 1, highValue);
                                        return B_OK;
                                }
                        }
                }
        }

        Range* range = new(std::nothrow) Range(lowValue, highValue);
        if (range == NULL)
                return B_NO_MEMORY;

        BPrivate::ObjectDeleter<Range> rangeDeleter(range);
        if (!AddItem(range, i))
                return B_NO_MEMORY;

        rangeDeleter.Detach();
        return B_OK;
}


status_t
RangeList::AddRange(const Range& range)
{
        return AddRange(range.lowerBound, range.upperBound);
}


void
RangeList::RemoveRangeAt(int32 index)
{
        if (index < 0 || index >= CountItems())
                return;

        RemoveItem(ItemAt(index));
}


bool
RangeList::Contains(int32 value) const
{
        for (int32 i = 0; i < CountItems(); i++) {
                const Range* range = ItemAt(i);
                if (value < range->lowerBound || value > range->upperBound)
                        break;
                else if (value >= range->lowerBound && value <= range->upperBound)
                        return true;
        }

        return false;
}


int32
RangeList::CountRanges() const
{
        return CountItems();
}


const Range*
RangeList::RangeAt(int32 index) const
{
        return ItemAt(index);
}


void
RangeList::_CollapseOverlappingRanges(int32 startIndex, int32 highValue)
{
        for (int32 i = startIndex; i < CountItems();) {
                // check if it also overlaps any of the following
                // ranges.
                Range* nextRange = ItemAt(i);
                if (nextRange->lowerBound > highValue)
                        return;
                else if (nextRange->upperBound < highValue) {
                        RemoveItem(nextRange);
                        continue;
                } else {
                        nextRange->lowerBound = highValue + 1;
                        return;
                }
        }
}