/**
* Author: Dmitriy Morozov
* Department of Computer Science, Duke University, 2005-2006
*/
#ifndef __CYCLE_H__
#define __CYCLE_H__
#include "utilities/types.h"
#include "utilities/circular_list.h"
#include <list>
#include <boost/serialization/access.hpp>
/**
* Class storing a cycle of simplices. Stores items in the order defined by ConsistencyCmp.
* The actual order of the elements is defined by OrderCmp. Instances of those
* classes are not stored in Cycle for efficiency, and are passed as arguments to those methods
* that require them.
*/
template <class Itm, class OrderCmp, class ConsistencyCmp = OrderCmp>
class Cycle: public List<Itm>
{
public:
/// \name Template Parameters
/// @{
typedef Itm Item;
typedef OrderCmp OrderComparison;
typedef ConsistencyCmp ConsistencyComparison;
/// @}
typedef Cycle<Item, OrderComparison, ConsistencyCmp> Self;
typedef List<Item> CycleRepresentation;
/// \name Accessor typedefs
/// @{
typedef typename CycleRepresentation::iterator iterator;
typedef typename CycleRepresentation::const_iterator const_iterator;
typedef typename CycleRepresentation::const_reference const_reference;
typedef typename CycleRepresentation::reference reference;
typedef typename CycleRepresentation::pointer pointer;
typedef typename CycleRepresentation::const_pointer const_pointer;
/// @}
public:
Cycle();
Cycle(const Cycle& c);
/// \name Whole Cycle operations
/// @{
/** Add c to *this assuming both Cycles are sorted in increasing order according to cmp. */
Self& add(const Self& c, const ConsistencyComparison& cmp);
void swap(Cycle& c); ///< Swaps the contents of c and *this (like STL's swap destroys c)
//void insertion_sort(const Comparison& cmp); ///< Sort list[i] using insertion sort
void sort(const ConsistencyComparison& cmp); ///< Sort elements to enforce consistency
using CycleRepresentation::empty;
using CycleRepresentation::clear;
using CycleRepresentation::size;
/// @}
/// \name Modifiers
/// @{
using CycleRepresentation::erase;
void append(const_reference x, const ConsistencyComparison& cmp);
/// @}
/// \name Accessors
/// @{
using CycleRepresentation::begin;
using CycleRepresentation::end;
const_reference top(const OrderComparison& cmp) const; ///< First element in cmp order
iterator get_second(const OrderComparison& cmp) const; ///< Second element in cmp order
/// @}
/// \name Block access optimizations
// Between operations used in optimization of transpositions for regular vertices. Maybe we don't need these? TODO
/// @{
/** Return first after i, but before or equal j; return i if no such element found */
const_reference first_between(const_reference i, const_reference j, const OrderComparison& cmp);
/// Add lists and remove all elements after i and before or equal to j
const_reference add_and_first_between(const Self& c, const ConsistencyComparison& consistency_cmp,
const_reference i, const_reference j, const OrderComparison& order_cmp);
/// Erase everything after i, but before or equal to j
void erase_between(const_reference i, const_reference j, const OrderComparison& cmp);
/// @}
/// \name Debugging
/// @{
const_reference get_first(const OrderComparison& cmp) const; ///< First element in cmp order
std::ostream& operator<<(std::ostream& out) const;
/// @}
private:
typedef std::list<Item> TemporaryCycleRepresenation;
using CycleRepresentation::push_back;
using CycleRepresentation::insert;
private:
size_t sz;
private:
// Serialization
typedef List<Item> Parent;
friend class boost::serialization::access;
template<class Archive>
void serialize(Archive& ar, version_type );
};
#include "cycle.hpp"
#endif // __CYCLE_H__