source: cpp/frams/util/multirange.cpp @ 957

// This file is a part of Framsticks SDK.  http://www.framsticks.com/
// Copyright (C) 1999-2015  Maciej Komosinski and Szymon Ulatowski.
// See LICENSE.txt for details.

#include "multirange.h"
#include <common/nonstd_stl.h>

#include <stdio.h>

int IRange::operator==(const IRange& r)
{
        if (isEmpty() && r.isEmpty()) return 1;
        return (begin == r.begin) && (end == r.end);
}

void IRange::intersect(const IRange& r)
{
        if (r.begin > begin) begin = r.begin;
        if (r.end < end) end = r.end;
}
void IRange::add(const IRange& r)
{
        if (r.begin < begin) begin = r.begin;
        if (r.end > end) end = r.end;
}

void IRange::print() const
{
        if (begin == end) printf("[%d]", begin);
        else printf("[%d-%d]", begin, end);
}

////////////////////////////////////////

void MultiRange::print() const
{
        printf("[");
        for (int i = 0; i < data.size(); i += 2)
        {
                int b = getData(i);
                int e = getData(i + 1);
                if (i) printf(",");
                if (b == e) printf("%d", b);
                else printf("%d-%d", b, e);
        }
        printf("]");
}

void MultiRange::print2() const
{
        const IRange& r = singleRange();
        for (int i = 0; i <= r.end; i++)
                printf(contains(i) ? "X" : ".");
}

void MultiRange::shift(int delta)
{
        for (int i = 0; i<data.size(); i++)
                data.get(i) += delta;
}

int MultiRange::findRange(int x) const
{
        if (isEmpty()) return -1;
        if (getData(0)>x) return -1;
        int a, b, c;
        int n = rangeCount() - 1;
        a = 0; b = n; // find c = last range with begin<=x
        while (1){
                c = (a + b + 1) / 2;
                if (getBegin(c) <= x)
                {
                        if ((c == n) || (getBegin(c + 1) > x)) return c;
                        a = c;
                }
                else
                {
                        b = c - 1;
                }
        }
}

void MultiRange::addRange(int i, int b, int e)
{
        data.insert(2 * i, b);
        data.insert(2 * i + 1, e);
}

void MultiRange::removeRanges(int r1, int r2)
{
        //data.remove(2*r1,(r2-r1)*2+2);
        for (; r2 >= r1; r2--)
                removeRange(r2);
}

void MultiRange::removeRange(int i)
{
        data.remove(2 * i, 2);
}

void MultiRange::clear()
{
        data.clear();
}

int MultiRange::isEmpty() const
{
        return rangeCount() == 0;
}

IRange MultiRange::singleRange() const
{
        if (isEmpty()) return IRange();
        int b = getData(0);
        int e = getData(data.size() - 1);
        return IRange(b, e);
}

int MultiRange::rangeCount() const
{
        return data.size() / 2;
}

IRange MultiRange::getRange(int i) const
{
        if ((i < 0) || (i >= rangeCount())) return IRange();
        return IRange(getData(2 * i), getData(2 * i + 1));
}

void MultiRange::remove(int begin, int end)
{
        if (end < begin) return; // NOP
        int count = rangeCount();
        if (!count) return;
        int r1 = findRange(begin);
        int r2 = findRange(end);
        if (r2<0) return; // NOP
        if (r1 == r2)
        {
                int e = getEnd(r1);
                int b = getBegin(r1);
                if (begin <= e)
                {
                        if (end >= e)
                        {
                                if (begin>b)
                                        setEnd(r1, begin - 1);
                                else
                                        removeRange(r1);
                        }
                        else
                        {
                                if (begin > b)
                                { //split
                                        addRange(r1 + 1, end + 1, e);
                                        setEnd(r1, begin - 1);
                                }
                                else
                                {
                                        setBegin(r1, end + 1);
                                }
                        }
                }
        }
        else
        {
                if (r1 >= 0)
                {
                        int e1 = getEnd(r1);
                        int b1 = getBegin(r1);
                        if (begin <= e1)
                        {
                                if (begin == b1)
                                {
                                        removeRange(r1);
                                        r2--;
                                        r1--;
                                }
                                else
                                {
                                        setEnd(r1, begin - 1);
                                }
                        }
                }
                int e2 = getEnd(r2);
                if (end < e2)
                {
                        setBegin(r2, end + 1);
                        removeRanges(r1 + 1, r2 - 1);
                }
                else
                {
                        removeRanges(r1 + 1, r2);
                }
        }
}

void MultiRange::add(int begin, int end)
{
        if (end < begin) return; // NOP
        int count = rangeCount();
        int last = count - 1;
        int r1 = findRange(begin);
        int r2 = findRange(end);
        if (r2 < 0) // special case: before first range
        {
                if (count && (getData(0) == (end + 1)))
                        setData(0, begin);
                else
                        addRange(0, begin, end);
                return;
        }
        if (r1 < 0) // special case: begin is before first range
        {
                setData(0, begin);
                r1 = 0;
        }
        // now r1>=0 and r2>=0
        int joinbegin = (begin <= (getEnd(r1) + 1));
        int joinend = (r2 < last) && (end >= (getBegin(r2 + 1) - 1));
        const int SAME = 1;
        const int JOINBEGIN = 2;
        const int JOINEND = 4;
        int action = ((r1 == r2) ? SAME : 0) + (joinbegin ? JOINBEGIN : 0) + (joinend ? JOINEND : 0);
        switch (action)
        {
        case SAME + JOINBEGIN + JOINEND: // remove 1 range
                setEnd(r1, getEnd(r1 + 1));
                removeRange(r1 + 1);
                break;
        case SAME + JOINBEGIN: // extend 1 range
                setEnd(r1, max(getEnd(r2), end));
                break;
        case SAME + JOINEND: // extend 1 range
                setBegin(r1 + 1, begin);
                break;
        case SAME: // add 1 range
                addRange(r1 + 1, begin, end);
                break;

        case JOINBEGIN + JOINEND: // extend r2+1
                setBegin(r2 + 1, getBegin(r1));
                removeRanges(r1, r2);
                break;
        case JOINBEGIN: // extend r1
                setEnd(r1, max(end, getEnd(r2)));
                removeRanges(r1 + 1, r2);
                break;
        case JOINEND: // extend r2+1
                setBegin(r2 + 1, begin);
                removeRanges(r1 + 1, r2);
                break;
        case 0: // extend r2
                setBegin(r2, begin);
                setEnd(r2, max(end, getEnd(r2)));
                removeRanges(r1 + 1, r2 - 1);
                break;
        }
}

void MultiRange::remove(const MultiRange &mr)
{
        for (int i = 0; i < mr.rangeCount(); i++)
        {
                IRange r = mr.getRange(i);
                remove(r);
        }
}

void MultiRange::add(const MultiRange &mr)
{
        for (int i = 0; i < mr.rangeCount(); i++)
        {
                IRange r = mr.getRange(i);
                add(r);
        }
}

void MultiRange::intersect(const MultiRange &mr)
{
        // = this - (1-mr)
        MultiRange full(singleRange());
        full.remove(mr);
        remove(full);
}

int MultiRange::contains(const MultiRange &mr) const
{
        for (int i = 0; i < mr.rangeCount(); i++)
        {
                IRange r = mr.getRange(i);
                if (!contains(r)) return 0;
        }
        return 1;
}

int MultiRange::contains(int x) const
{
        int r = findRange(x);
        if (r < 0) return 0;
        return getEnd(r) >= x;
}

int MultiRange::contains(const IRange& r) const
{
        if (r.isEmpty()) return 0;
        int r1 = findRange(r.begin);
        if (r1 < 0) return 0;
        return getRange(r1).contains(r);
}

void MultiRange::intersect(int begin, int end)
{
        if (isEmpty()) return;
        if (end < begin) { clear(); return; }
        IRange sr = singleRange();
        remove(sr.begin, begin - 1);
        remove(end + 1, sr.end);
}