include/utilities/orderlist.h
 author Dmitriy Morozov Mon, 05 Jul 2010 23:51:26 -0700 branch dev changeset 211 347b3461965a parent 30 6d4e450015e4 child 208 36ea2751f290 permissions -rw-r--r--
Bug in the tutorial: simplices = [] -> simplices = Filtration()
```
/*
* Author: Dmitriy Morozov
* Department of Computer Science, Duke University, 2006
*
* Implements the simplified order list data strcutre given in ``Two Simplified
* Algorithms for Maintaining Order in a List'' by Bender et al.
*
* Indirection is not implemented, so the insertion cost is amortized O(log n),
* while comparison and deletion are O(1).
*/

#ifndef __ORDERLIST_H__
#define __ORDERLIST_H__

#include "log.h"

#include <iterator>
#include <iostream>
#include <list>

#include "types.h"

#include <boost/utility.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 maintaining their total order under
* the operations of insert(), swap(), and delete(). push_back() is provided for
* uniformity, OrderComparison member class carries out comparison of the
* elements.
*/
template<class T>
class OrderList: public std::list<OrderListNode<T> >
{
public:
class 			OrderComparison;

/// OrderComparison type
typedef			OrderComparison								OrderComparison;

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
template<class BinaryPredicate>
void			sort(BinaryPredicate cmp);					///< Sorts the elements in accordance with cmp

/// \name Container operations
/// @{
// Explicit calls instead of using declarations for Doxygen
iterator		push_back(const_reference x);
iterator		insert(iterator predecessor, const_reference x);	///< Inserts x immediately after predecessor (has to be a valid iterator)
void			erase(iterator x)							{ Parent::erase(x.get_base()); }

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())); }
/// @}

/// \name Debugging operations
/// @{
void			show_elements() const;
/// @}

private:
static const float density_threshold = 1.2;
};

/// 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
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 t):
data(d), tag(t)
{}

T 				data;
OrderType		tag;

std::ostream& 	operator<<(std::ostream& out) const				{ return out << data << ": " << tag; }
};

template<class T, class BinaryPredicate>
class OrderListNodeComparison
{
public:
typedef 		OrderListNode<T>								Node;
OrderListNodeComparison(BinaryPredicate cmp): cmp_(cmp) 		{}
bool operator()(const Node& a, const Node& b) const				{ return cmp_(a.data, b.data); }

private:
BinaryPredicate cmp_;
};

template<class T>
std::ostream&			operator<<(std::ostream& out, const OrderListNode<T>& n)	{ return n.operator<<(out); }

template<class T>
typename OrderList<T>::Parent::iterator,
T>
{
private:
struct			enabler										{};

public:
typedef			typename OrderList<T>::Parent				OrderListParent;
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(const OrderListIterator<T>& other):
{}

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>
typename OrderList<T>::Parent::const_iterator,
const T>
{
private:
struct			enabler										{};

public:
typedef			typename OrderList<T>::Parent				OrderListParent;
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(const const_OrderListIterator<T>& other):
{}
const_OrderListIterator(const OrderListIterator<T>& other):
{}

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>;
friend class 	OrderList<T>::OrderComparison;
};

#include "orderlist.hpp"

#endif // __ORDERLIST_H__
```