// This file is a part of the Framsticks GDK library.
// Copyright (C) 2002-2011  Szymon Ulatowski.  See LICENSE.txt for details.
// Refer to http://www.framsticks.com/ for further information.

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