/*
* Author: Dmitriy Morozov
* Department of Computer Science, Duke University, 2006
*/
#ifndef __ORDERLIST_H__
#define __ORDERLIST_H__
#include <iterator>
#include <iostream>
#include <list>
#include "types.h"
//#include "counter.h"
#include <boost/utility.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
//#include <boost/type_traits/is_convertible.hpp>
//#include <boost/utility/enable_if.hpp>
typedef unsigned int OrderType;
template<class T> struct OrderListNode;
template<class T> class OrderListIterator;
template<class T> class const_OrderListIterator;
/**
* OrderList stores a list of objects while keeping track of two orders: proper order and consistency order.
* Consistency order is guaranteed not to change, while proper order is affected by the swap() operation.
*/
template<class T>
class OrderList: std::list<OrderListNode<T> >
{
public:
class OrderComparison;
class LessThanComparison;
class GreaterThanComparison;
class ConsistencyComparison;
/// \name Comparison types
/// @{
// Explicit typedefs for Doxygen
typedef LessThanComparison LessThanComparison;
typedef GreaterThanComparison GreaterThanComparison;
typedef ConsistencyComparison ConsistencyComparison;
/// @}
typedef OrderListNode<T> NodeType;
typedef OrderList<T> Self;
typedef std::list<NodeType > Parent;
typedef T value_type;
typedef T& reference;
typedef const T& const_reference;
typedef OrderListIterator<T> iterator;
typedef const_OrderListIterator<T> const_iterator;
OrderList() {}
~OrderList() { clear(); }
/// \name Order operations
void swap(iterator i, iterator j); ///< Exchanges the order of simplices pointed to by i and j
/// \name Container operations
/// @{
// Explicit calls instead of using declarations for Doxygen
iterator push_back(const_reference x);
void clear() { return Parent::clear(); }
bool empty() const { return Parent::empty(); }
SizeType size() const { return Parent::size(); }
iterator begin() { return iterator(Parent::begin()); }
const_iterator begin() const { return const_iterator(Parent::begin()); }
iterator end() { return iterator(Parent::end()); }
const_iterator end() const { return const_iterator(Parent::end()); }
reference back() { return Parent::back(); }
const_reference back() const { return Parent::back(); }
void pop_back() { return Parent::pop_back(); }
iterator last() { return iterator(boost::prior(end())); }
const_iterator last() const { return const_iterator(boost::prior(end())); }
/// @}
};
/// Basic comparison that LessThan and GreaterThan derive from
template<class T>
class OrderList<T>::OrderComparison
{
public:
typedef typename OrderList<T>::const_iterator ComparableType;
int compare(ComparableType a, ComparableType b) const; /// (-1,0,1) = a (precedes, ==, succeeds) b
};
/// Determines if the first element is less than the second one
template<class T>
class OrderList<T>::LessThanComparison: public OrderComparison
{
public:
typedef OrderComparison Parent;
typedef typename Parent::ComparableType ComparableType;
int compare(ComparableType a, ComparableType b) const;
bool operator()(ComparableType a, ComparableType b) const;
};
/// Determines if the first element is greater than the second one
template<class T>
class OrderList<T>::GreaterThanComparison: public OrderComparison
{
public:
typedef OrderComparison Parent;
typedef typename Parent::ComparableType ComparableType;
int compare(ComparableType a, ComparableType b) const;
bool operator()(ComparableType a, ComparableType b) const;
};
/// Determines the order of the two elements in the consistency order (that doesn't change during the execution)
template<class T>
class OrderList<T>::ConsistencyComparison
{
public:
typedef typename OrderList<T>::const_iterator ComparableType;
int compare(ComparableType a, ComparableType b) const; ///< (-1,0,1) = a (precedes, ==, succeeds) b
bool operator()(ComparableType a, ComparableType b) const;
};
/// Structure storing auxilliary information requred for each node of OrderList
template<class T>
struct OrderListNode
{
OrderListNode(const T& d, unsigned int orig, unsigned int cur):
data(d), original(orig), current(cur)
{}
T data;
OrderType original;
OrderType current;
};
template<class T>
class OrderListIterator: public boost::iterator_adaptor<OrderListIterator<T>,
typename OrderList<T>::Parent::iterator,
T>
{
private:
struct enabler {};
public:
typedef typename OrderList<T>::Parent OrderListParent;
typedef boost::iterator_adaptor<OrderListIterator<T>,
typename OrderListParent::iterator,
T> Parent;
typedef typename Parent::reference reference;
typedef typename Parent::base_type base_type;
OrderListIterator() {}
OrderListIterator(const typename OrderListParent::iterator& iter):
OrderListIterator::iterator_adaptor_(iter)
{}
OrderListIterator(const OrderListIterator<T>& other):
OrderListIterator::iterator_adaptor_(other.base())
{}
private:
friend class boost::iterator_core_access;
reference dereference() const { return Parent::base_reference()->data; }
base_type& get_base() { return Parent::base_reference(); }
friend class OrderList<T>;
};
template<class T>
class const_OrderListIterator: public boost::iterator_adaptor<const_OrderListIterator<T>,
typename OrderList<T>::Parent::const_iterator,
const T>
{
private:
struct enabler {};
public:
typedef typename OrderList<T>::Parent OrderListParent;
typedef boost::iterator_adaptor<const_OrderListIterator<T>,
typename OrderListParent::const_iterator,
const T> Parent;
typedef typename Parent::reference reference;
typedef typename Parent::base_type base_type;
const_OrderListIterator() {}
const_OrderListIterator(const typename OrderListParent::const_iterator& iter):
const_OrderListIterator::iterator_adaptor_(iter)
{}
const_OrderListIterator(const const_OrderListIterator<T>& other):
const_OrderListIterator::iterator_adaptor_(other.base())
{}
const_OrderListIterator(const OrderListIterator<T>& other):
const_OrderListIterator::iterator_adaptor_(other.base())
{}
private:
friend class boost::iterator_core_access;
reference dereference() const { return Parent::base_reference()->data; }
const base_type&
get_base() { return Parent::base_reference(); }
friend class OrderList<T>::OrderComparison;
friend class OrderList<T>::ConsistencyComparison;
};
#include "orderlist.hpp"
#endif // __ORDERLIST_H__