// 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 "multimap.h"
#include <stdio.h>

int MultiMap::getBegin() const
{
if (isEmpty()) return 0;
return getBegin(0);
}

int MultiMap::getEnd() const
{
if (isEmpty()) return -1;
return getBegin(mappingCount()-1)-1;
}

int MultiMap::findData(int x) const
{
if (isEmpty()) return -1;
if (getBegin(0)>x) return -1;
int a,b,c;
int n=mappingCount()-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;
		}
	}
}

int MultiMap::addRange(int &r,const MultiRange& mr)
{
// precondition: 0 <= r < (mappingCount()-1)
// 1.maybe change mapping in this range
int ret=0;
SingleMapping *sm=getMapping(r);
if (sm->to.contains(mr)) return 0; // do nothing
sm->to.add(mr);
// after adding mr to this mapping it could be the same as the previous/next one
if (r>0) // prev exists
	{
	SingleMapping *prev=getMapping(r-1);
	if (prev->to == sm->to)
		{ // splice with prev
		removeData(r);
		delete sm;
		sm=prev;
		r--;
		ret--;
		}
	}
if (r<(mappingCount()-2)) // next exists
	{
	SingleMapping *next=getMapping(r+1);
	if (next->to == sm->to)
		{ // splice with next
		removeData(r+1);
		delete next;
		ret--;
		r--;
		}
	}
return ret;
}

int MultiMap::addRangeBeginEnd(int &r,int begin,int end,const MultiRange& mr)
{
// precondition: -1 <= r < mappingCount()
//               begin <= end
//               begin >= mapping.begin
//               end < nextmapping.begin
SingleMapping *m,*m2,*m1;
if (r<0)
	{
	if (mappingCount())
		{
		m=getMapping(0);
		if (end==(m->begin-1))
			{ // adjacent to m
			if (m->to==mr)
				{ // shift only
				m->begin=begin;
				return 0;
				}
			// single add
			SingleMapping *newmap=new SingleMapping(begin,mr);
			addData(0,newmap);
			r=0;
			return 1;
			}
		}
	// double add
	SingleMapping *newmap=new SingleMapping(begin,mr);
	SingleMapping *newmap2=new SingleMapping(end+1);
	addData(0,newmap);
	addData(1,newmap2);
	r=1;
	return 2;
	}

if (r==(mappingCount()-1))
	{
	m=getMapping(r);
	m1=getMapping(r-1);
	if (begin==m->begin)
		{ // adjacent
		if (m1->to==mr)
			{ // shift only
			m->begin=end+1;
			return 0;
			}
		// single add
		m->begin=end+1;
		SingleMapping *newmap=new SingleMapping(begin,mr);
		addData(r,newmap);
		return 1;
		}
	// double add
	SingleMapping *newmap=new SingleMapping(begin,mr);
	SingleMapping *newmap2=new SingleMapping(end+1);
	addData(r+1,newmap);
	addData(r+2,newmap2);
	r+=2;
	return 2;
	}

m=getMapping(r);
if (m->to.contains(mr)) return 0;
if (begin==m->begin) // begin at range boundary
	{
	m2=getMapping(r+1);
	if (end==(m2->begin-1)) return addRange(r,mr);

	SingleMapping *newmap=new SingleMapping(begin,m->to);
	newmap->to.add(mr);
	if (r>0)
		{ // join prev possible...
		m1=getMapping(r-1);
		if (m1->to==newmap->to)
			{ // joint prev = shift
			delete newmap;
			m->begin=end+1;
			return 0;
			}
		}
	// single add:
	m->begin=end+1;
	addData(r,newmap);
	return 1;
	}

m2=getMapping(r+1);
if (end==(m2->begin-1)) // end at range boundary
	{
	SingleMapping *newmap=new SingleMapping(begin,m->to);
	newmap->to.add(mr);
	if (r<(mappingCount()-2))
		{ // join next possible...
		if (m2->to==newmap->to)
			{ // joint next = shift
			m2->begin=begin;
			delete newmap;
			return 0;
			}
		}
	// single add
	r++;
	addData(r,newmap);
	return 1;
	}
// double add:
SingleMapping *newmap=new SingleMapping(begin,m->to);
newmap->to.add(mr);
SingleMapping *newmap2=new SingleMapping(end+1,m->to);
addData(r+1,newmap);
addData(r+2,newmap2);
r+=2;
return 2;
}

void MultiMap::add(int begin,int end,const MultiRange& to)
{
if (to.isEmpty()) return;
if (end<begin) return;
int r1=findData(begin);
int r2=findData(end);
if (r1==r2)
	{
	addRangeBeginEnd(r1,begin,end,to);
	}
else
	{
	r2+=addRangeBeginEnd(r1,begin,getBegin(r1+1)-1,to);
	r1++;
	for (;r1<r2;r1++)
		r2+=addRange(r1,to);
	addRangeBeginEnd(r1,getBegin(r1),end,to);
	}
}

const MultiRange& MultiMap::map(int x) const
{
static MultiRange empty;
int m=findData(x);
if (m<0) return empty;
SingleMapping *sm=getMapping(m);
return sm->to;
}

MultiRange MultiMap::map(int begin,int end) const
{
MultiRange mr;
int m=findData(begin);
for (;m<rangeCount();m++)
	if (m>=0)
	{
	SingleMapping *sm=getMapping(m);
	if (sm->begin > end) break;
	mr.add(sm->to);
	}
return mr;
}

MultiRange MultiMap::map(const MultiRange& ranges) const
{
MultiRange mr;
for(int i=0;i<ranges.rangeCount();i++)
	mr.add(map(ranges.getRange(i)));
return mr;
}

IRange MultiMap::getRange(int i) const
{
if ((i<0)||(i>(data.size()-1))) return IRange();
return IRange(getBegin(i),getBegin(i+1)-1);
}

void MultiMap::operator=(const MultiMap& mm)
{
clear();
for(int i=0;i<mm.mappingCount();i++)
	addData(i,new SingleMapping(*mm.getMapping(i)));
}

void MultiMap::addCombined(const MultiMap& m1,const MultiMap& m2)
{
for(int i=0;i<m1.rangeCount();i++)
	{
	IRange r=m1.getRange(i);
	add(r,m2.map(m1.getMapping(i)->to));
	}
}

void MultiMap::add(const MultiRange& from,const MultiRange& to)
{
for(int i=0;i<from.rangeCount();i++)
	add(from.getRange(i),to);
}

void MultiMap::addReversed(const MultiMap& m)
{
for(int i=0;i<m.rangeCount();i++)
	{
	IRange r=m.getRange(i);
	const MultiRange& mr=m.getMapping(i)->to;
	for (int j=0;j<mr.rangeCount();j++)
		add(mr.getRange(j),r);
	}
}

MultiMap::~MultiMap()
{ clear();}

void MultiMap::clear()
{
for(int i=0;i<data.size();i++)
	delete getData(i);
data.clear();
}

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

void MultiMap::print() const
{
printf("{ ");
for (int i=0;i<(mappingCount()-1);i++)
	{
	if (i) printf("  ");
	SingleMapping *sm=getMapping(i);
	SingleMapping *sm2=getMapping(i+1);
	if (sm2->begin==sm->begin+1)
		printf("[%d] -> ",sm->begin);
	else
		printf("[%d-%d] -> ",sm->begin,sm2->begin-1);
	sm->to.print();
	printf("\n");
	}
printf("}\n");
}

void MultiMap::print2() const
{
int y;
int id=0,id2;
if (isEmpty())
	{
	printf("{ empty }\n");
	return;
	}
printf("{\n");
for (y=getBegin();y<=getEnd();y++)
	{
	id2=findMappingId(y+1);
	printf("%2d %c",y,(id2!=id)?'_':' ');
	id=id2;
	map(y).print2();
	printf("\n");
	}
printf("}\n");
}