/**
 *  Copyright (C) 2004 Alo Sarv <madcat_@users.sourceforge.net>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#ifndef __RANGE2_H__
#define __RANGE2_H__

#include <hn/osdep.h>
#include <boost/logic/tribool.hpp>
#include <set>
#include <limits>

/**
 * Range object represents a range of values. Range object always has a begin
 * and an end (inclusive). Ranges can be compared, merged, and split. The
 * underlying object type used for representing the begin/end values of the
 * range are generally required to be of integer type, but any suitable
 * user-defined type can also be used that satisfies the comparison operations
 * used by this class.
 */
template<typename T>
class Range {
public:
	/**
	 * @name Construction
	 */
	//@{
	template<typename X>
	Range(const X &begin, const X &end) : m_begin(begin), m_end(end) {
		CHECK_THROW(m_begin <= m_end);
	}
	template<typename X>
	Range(const Range<X> &x) {
		m_begin = x.m_begin;
		m_end = x.m_end;
	}
	template<typename X>
	Range(const std::pair<X, X> r) : m_begin(r.first), m_end(r.second) {
		CHECK_THROW(m_begin <= m_end);
	}
	template<typename X>
	Range& operator=(const Range<X> &x) {
		m_begin = x.m_begin;
		m_end = x.m_end;
	}
	//@}

	/**
	 * @name Comparing ranges
	 */
	//@{
	template<typename X>
	bool operator<(const Range<X> &x) const {
		return m_begin < x.m_begin ? true : m_end < x.m_end;
	}
	template<typename X>
	bool operator>(const Range<X> &x) const {
		return m_begin > x.m_begin ? true : m_end > x.m_end;
	}
	template<typename X>
	bool operator==(const Range<X> &x) const {
		return m_begin == x.m_begin && m_end == x.m_end;
	}
	template<typename X>
	bool operator!=(const Range<X> &x) const {
		return !(m_begin == x.m_begin && m_end == x.m_end);
	}
	//@}

	/**
	 * @name Accessors
	 */
	//@{
	T begin()  const { return m_begin;             }
	T end()    const { return m_end;               }
	T length() const { return m_end - m_begin + 1; }
	void begin(const T &b) {
		CHECK_THROW(b <= m_end);
		m_begin = b;
	}
	void end(const T &e) {
		CHECK_THROW(e >= m_begin);
		m_end = e;
	}
	//@}

	/**
	 * @name Operations
	 */
	//@{

	/**
	 * Merge another range with current one.
	 *
	 * @param x    Range to merge into current one.
	 *
	 * \note Implies that *this contains() @param x. Does nothing if that
	 *       is not true.
	 */
	template<typename X>
	void merge(const Range<X> &x) {
		if (m_begin > x.m_begin) {
			m_begin = x.m_begin;
		}
		if (m_end < x.m_end) {
			m_end = x.m_end;
		}
		if (m_end + 1 == x.m_begin) {
			m_end = x.m_end;
		}
		if (m_begin - 1 == x.m_end) {
			m_begin = x.m_begin;
		}
	}

	/**
	 * Erase target range from current one.
	 *
	 * @param x    Pointer to range to be erased. If range splitting
	 *             happened, it will be modified to contain the second half
	 *             of the resulting two ranges.
	 * @return     True if *this was truncated. False if this range was
	 *             completely cleared out by @param x. boost::indeterminate
	 *             if *this was split into two, and @param x contains the
	 *             second half.
	 */
	template<typename X>
	boost::logic::tribool erase(Range<X> *x) {
		if (x->m_begin <= m_begin && x->m_end >= m_end) {
			return false;
		}
		if (m_begin < x->m_begin && m_end > x->m_end) {
			X tmp = x->m_begin;
			x->m_begin = x->m_end + 1;
			x->m_end = m_end;
			m_end = tmp - 1;
			return boost::indeterminate;
		}
		if (m_begin <= x->m_begin && m_end >= x->m_begin) {
			m_end = x->m_begin - 1;
		} else if (m_begin >= x->m_begin && x->m_end > m_begin) {
			m_begin = x->m_end + 1;
		}
		return true;
	}

	/**
	 * Check if *this contains @param x. A range is considered to contain
	 * another range if it even partially overlaps with another range. To
	 * check if another range is completely contained within current range,
	 * use containsFull() method.
	 *
	 * @param x      Range to be checked against current range.
	 * @return       True if containment is true, false otherwise.
	 */
	template<typename X>
	bool contains(const Range<X> &x) const {
		if (containsFull(x)) {
			return true;
		} else if (m_end < x.m_begin || m_begin > x.m_end) {
			return false;
		} else {
			return true;
		}
	}

	/**
	 * Check if *this completely contains @param x
	 *
	 * @param x    Range to be checked against current range
	 * @return     True if @param x is completely within *this.
	 */
	template<typename X>
	bool containsFull(const Range<X> &x) const {
		if (m_begin <= x.m_begin && m_end >= x.m_end) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 * Check if @param x borders with *this. Bordering is defined if @param
	 * x begins right after *this's end, or *this's begin starts right after
	 * @param x's end.
	 *
	 * @param x      Range to be checked against bordering
	 * @return       True if @param x borders with *this.
	 */
	template<typename X>
	bool borders(const Range<X> &x) const {
		if (m_begin - 1 == x.m_end) {
			return true;
		}
		if (m_end + 1 == x.m_begin) {
			return true;
		}
		return false;
	}
	//@}

	friend std::ostream& operator<<(std::ostream &o, const Range &x) {
		return o << (int)x.m_begin << ".." << (int)x.m_end;
	}

	/**
	 * @name Convenience methods for easier usage
	 */
	//@{
	template<typename X>
	bool contains(const X &x, const X &y) {
		return contains(Range(x, y));
	}
	template<typename X>
	bool containsFull(const X &x, const X &y) {
		return containsFull(Range(x, y));
	}
	template<typename X>
	boost::logic::tribool erase(const X &x, const X &y) {
		return erase(Range(x, y));
	}
	//@}
private:
	//! Default constructor behaviour cannot be defined and is forbidden
	Range();

	T m_begin;   //! begin offset
	T m_end;     //! end offset

	//! Be-friend with all our instances
	template<typename X> friend class Range;
};

typedef Range<uint64_t> Range64;
typedef Range<uint32_t> Range32;
typedef Range<uint16_t> Range16;
typedef Range<uint8_t>  Range8;

/**
 * RangeList<T> is a generic container for Range<T> type objects. It supports
 * all the operations single Range<T> objects support, however is also capable
 * of performing those operations over several ranges. RangeList<T> provides
 * public typedef CIter for iterating on the underlying implementation.
 * Ranges in RangeList are guaranteed to be ordered based on Range begin values,
 * as defined by Range<T> object.
 *
 * RangeList does not perform any lower or upper bound checking, except for
 * those inherent from the underlying data type.
 *
 * Ranges can be either push()'ed or merge()'d into RangeList. In the former
 * case, duplicates are allowed, and overlapping/bordering ranges are not merged
 * together into larger ranges. In the latter case, overlapping/bordering ranges
 * are compacted into bigger Range objects. The same logic applies to remove()
 * and erase() methods, former erasing an exact copy of the passed Range, latter
 * erasing a region of RangeList, possibly modifying existing ranges. After
 * call to erase(X, Y), it is guaranteed that RangeList::contains(X, Y) shall
 * return false, however in case of remove(), there is no such guarantee.
 *
 * \note Almost all RangeList operations have only linear complexity, thus
 * storing vast amounts of small ranges here can very quickly get a performance
 * bottleneck. Future versions of RangeList API will improve this.
 */
template<typename T>
class RangeList {
	typedef Range<T>                      RangeType;
	typedef std::multiset<RangeType>      Impl;
	typedef typename Impl::iterator       Iter;
public:
	typedef typename Impl::const_iterator CIter;

	bool push(const RangeType &r) {
		std::pair<Iter, Iter> ret = m_ranges.equal_range(r);
		for (Iter i = m_ranges.begin(); i != m_ranges.end(); ++i) {
			if ((*i) == r) {
				return false;
			}
		}
		m_ranges.insert(r);
		return true;
	}
	bool remove(const RangeType &r) {
		for (Iter i = m_ranges.begin(); i != m_ranges.end(); ++i) {
			if ((*i) == r) {
				m_ranges.erase(i);
				return true;
			}
		}
		return false;
	}
	void merge(RangeType r) {
		std::vector<Iter> toRemove;
		for (Iter i = m_ranges.begin(); i != m_ranges.end(); ++i) {
			if ((*i).contains(r) | (*i).borders(r)) {
				r.merge(*i);
				toRemove.push_back(i);
			}
		}
		while (toRemove.size()) {
			m_ranges.erase(toRemove.back());
			toRemove.pop_back();
		}
		m_ranges.insert(r);
	}
	void erase(const RangeType &r) {
		std::vector<Iter> toRemove;
		std::vector<RangeType> toAdd;
		for (Iter i = m_ranges.begin(); i != m_ranges.end(); ++i) {
			if ((*i).contains(r)) {
				RangeType one(*i), two(r);
				toRemove.push_back(i);
				boost::logic::tribool ret(one.erase(&two));
				if (ret == true) {
					toAdd.push_back(one);
				} else if (boost::indeterminate(ret)) {
					toAdd.push_back(one);
					toAdd.push_back(two);
				}
			}
		}
		while (toRemove.size()) {
			m_ranges.erase(toRemove.back());
			toRemove.pop_back();
		}
		while (toAdd.size()) {
			m_ranges.insert(toAdd.back());
			toAdd.pop_back();
		}
	}

	RangeType getFirstFree(
		const T &limit = std::numeric_limits<T>::max()
	) const {
		T curPos = std::numeric_limits<T>::min();
		T endPos = std::numeric_limits<T>::max();
		if (count()) {
			if ((*begin()).begin() > curPos) {
				endPos = (*begin()).begin() - 1;
				if (endPos - curPos + 1 > limit) {
					endPos = curPos + limit - 1;
				}
			} else {
				curPos = (*begin()).end() + 1;
				if (++begin() == end()) {
					endPos = curPos + limit - 1;
				} else {
					endPos = (*++begin()).begin() - 1;
				}
			}
		} else {
			endPos = curPos + limit - 1;
		}
		return RangeType(curPos, endPos);
	}

	// more convenient versions for the above functions
	// ------------------------------------------------

	template<typename X>
	bool push(const X &x, const X &y) {
		return push(RangeType(x, y));
	}
	template<typename X>
	bool remove(const X &x, const X &y) {
		return remove(RangeType(x, y));
	}
	template<typename X>
	void merge(const X &x, const X &y) {
		return merge(RangeType(x, y));
	}
	template<typename X>
	void erase(const X &x, const X &y) {
		erase(RangeType(x, y));
	}

	// generic accessors
	// -----------------

	size_t count() const { return m_ranges.size(); }
	T max() const {
		CHECK_THROW(count());
		T m((*m_ranges.begin()).end());
		for (CIter i(m_ranges.begin()); i != m_ranges.end(); ++i) {
			if (m < (*i).end()) {
				m = (*i).end();
			}
		}
		return m;
	}
	T min() const {
		CHECK_THROW(count());
		T m((*m_ranges.begin()).begin());
		for (CIter i(m_ranges.begin()); i != m_ranges.end(); ++i) {
			if (m > (*i).begin()) {
				m = (*i).begin();
			}
		}
		return m;
	}
	void clear() { m_ranges.clear(); }
	bool empty() const { return !m_ranges.size(); }
	CIter begin() const { return m_ranges.begin(); }
	CIter end()   const { return m_ranges.end(); }
private:
	Impl m_ranges;
};

typedef RangeList<uint64_t> RangeList64;
typedef RangeList<uint32_t> RangeList32;
typedef RangeList<uint16_t> RangeList16;
typedef RangeList<uint8_t>  RangeList8;

#endif