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

// 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);
}