/* $Id$
 *
 * RangeSet defines operation for a Range and sets of ranges, like checking if
 * one range is a subset of another.
 *
 * Copyright (C) 2008-2009 FAUmachine Team <info@faumachine.org>.
 * This program is free software. You can redistribute it and/or modify it
 * under the terms of the GNU General Public License, either version 2 of
 * the License, or (at your option) any later version. See COPYING.
 */

#include <cassert>
#include "frontend/misc/RangeSet.hpp"

namespace ast {

/* **************** nested class Range **************** */
RangeSet::Range::Range(
	universal_integer l, 
	universal_integer r
) : left(l), right(r) 
{
	assert(l <= r);
}

universal_integer
RangeSet::Range::distance(const Range &other) const
{
	if (this->right < other.left) {
		return this->right - other.left;
	}

	if (other.right < this->left) {
		return this->left - other.right;
	}

	return 0;
}

bool
RangeSet::Range::isSubset(const Range &other) const
{
	if ((other.left <= this->left) && (other.right >= this->right)) {
		return true;
	}
	return false;
}

bool
RangeSet::Range::contains(universal_integer value) const
{
	return (value <= this->right) && (this->left <= value);
}


bool
RangeSet::Range::operator ==(const Range &other) const
{
	return (this->left == other.left) && (this->right == other.right);
}

bool
RangeSet::Range::operator <(const Range &other) const
{
	return this->left < other.right;
}

bool
RangeSet::Range::operator >(const Range &other) const
{
	return other.left < this->right;
}


std::list<RangeSet::Range>
RangeSet::Range::operator -(const Range &other) const
{
	std::list<Range> ret;

	if (! other.isSubset(*this)) {
		return ret;
	}

	if (other == *this) {
		return ret;
	}

	// true subset
	if (this->left < other.left) {
		Range r = Range(this->left, other.left - 1);
		ret.push_back(r);
	}

	if (other.right < this->right) {
		Range r = Range(other.right + 1, this->right);
		ret.push_back(r);
	}

	return ret;
}

void
RangeSet::Range::put(std::ostream &stream) const
{
	if (this->left < this->right) {
		stream << '[' << this->left << ", " << this->right << ']';
	} else {
		// range with only one element.
		stream << this->left;
	}

}

/* ******************** RangeSet ******************** */
RangeSet::RangeSet(
	universal_integer l, 
	universal_integer r
)
{
	Range initial = Range(l, r);
	this->ranges.push_back(initial);
}

RangeSet::RangeSet(const DiscreteRange &r)
{
	if (r.getLowerBound() <= r.getUpperBound()) {
		Range initial = Range(r.getLowerBound(), r.getUpperBound());
		this->ranges.push_back(initial);
	}
}

bool
RangeSet::minus(const DiscreteRange &r)
{
	return this->minus(r.getLowerBound(), r.getUpperBound());
}

bool
RangeSet::minus(universal_integer l, universal_integer r)
{
	Range sub = Range(l, r);
	bool found = false;
	std::list<Range>::iterator i;

	for (i = this->ranges.begin(); i != this->ranges.end(); i++) {
		if (sub.isSubset(*i)) {
			found = true;
			break;
		}
	}

	if (! found) {	
		return false;
	}

	std::list<Range> ret = (*i) - sub;
	i = this->ranges.erase(i);

	if (! ret.empty()) {
		this->ranges.insert(i, ret.begin(), ret.end());
	}
	
	return true;
}

void
RangeSet::plus(const DiscreteRange &dr)
{
	this->plus(dr.getLowerBound(), dr.getUpperBound());
}

void
RangeSet::plus(universal_integer l, universal_integer r)
{
	assert(l <= r);

	Range nr = Range(l, r);
	universal_integer lb = l;
	universal_integer ub = r;

	std::list<Range>::iterator i1 = this->ranges.begin();
	std::list<Range>::iterator i2;

	// i1 : first range that is at least directly adjacent left to nr, 
	//      or is anywhere right of that place (e.g. overlapping or
	//      right of nr).
	while ((i1 != this->ranges.end()) && (i1->distance(nr) < -1)) {
		i1++;
	}

	i2 = i1;
	// i2 : first range that is at least not adjacent right of nr,
	//      i.e. it doesn't overlap and isn't left of nr.
	while ((i2 != this->ranges.end()) && (i2->distance(nr) < 2)) {
		if (i2->right > ub) {
			ub = i2->right;
		} 
		
		i2++;
	}

	if (i1 == this->ranges.end()) {
		// no ranges that overlap or are right of r or are
		// adjacent.
		// -> just insert at end.
		this->ranges.push_back(nr);
		return;
	}

	if (i1->left < lb) {
		lb = i1->left;
	}

	// i1 == i2 -> there are no overlapping/adjacent ranges, 
	// as i1 is right of r
	if (i1 == i2) {
		assert((*i1) > nr);
		this->ranges.insert(i1, nr);
		return;
	}

	// [i1, i2) are all overlapping (or form with the new range an
	// a complete range).
	// lb, ub are the lowest and highest bound of r and [i1, i2).
	i1 = this->ranges.erase(i1, i2);
	this->ranges.insert(i1, Range(lb, ub));
}

bool
RangeSet::empty(void) const
{
	return this->ranges.empty();
}

void
RangeSet::clear(void)
{
	this->ranges.clear();
}

universal_integer
RangeSet::getUpperBound(void) const
{
	assert(! this->ranges.empty());
	return this->ranges.back().right;
}

universal_integer
RangeSet::getLowerBound(void) const
{
	assert(! this->ranges.empty());
	return this->ranges.front().left;
}

void
RangeSet::put(std::ostream &stream) const
{
	stream << "{ ";
	for (std::list<Range>::const_iterator i = this->ranges.begin();
		i != this->ranges.end(); i++) {

		if (i != this->ranges.begin()) {
			stream << ", ";
		}

		i->put(stream);
	}

	stream << " }";
}

bool
RangeSet::contains(universal_integer value) const
{
	for (std::list<Range>::const_iterator i = this->ranges.begin(); 
		i != this->ranges.end(); i++) {

		if (i->contains(value)) {
			return true;
		}
	}

	return false;
}

std::ostream &
operator <<(std::ostream &stream, const RangeSet &rs)
{
	rs.put(stream);
	return stream;
}

}; /* namespace ast */