#ifndef __KINETIC_SORT_H__
#define __KINETIC_SORT_H__
#include <list>
#include <boost/function.hpp>
#include <boost/utility.hpp>
#include <iostream>
/**
* Maintains elements of the given data structure in the sorted order assuming the elements follow
* trajectories given by TrajectoryExtractor_.
*
* \arg SortDS_ should be forward and backward iterable, swaps are handles via SwapCallback
* \arg TrajectoryExtractor_ applied to the iterator into SortDS_ should return a rational
* function describing the
* \arg Simulator_ the Simulator type, e.g. Simulator. Note that KineticSort does not store
* a pointer to the Simulator (so a pointer is passed in each relevant operation)
*/
template<class SortDS_, class TrajectoryExtractor_, class Simulator_>
class KineticSort
{
public:
typedef Simulator_ Simulator;
typedef typename Simulator::PolynomialKernel PolynomialKernel;
typedef SortDS_ SortDS;
typedef TrajectoryExtractor_ TrajectoryExtractor;
typedef typename Simulator::Key SimulatorKey;
typedef typename SortDS::iterator SortDSIterator;
private:
/* Implementation */
struct Node
{
SortDSIterator element;
SimulatorKey swap_event_key;
Node(SortDSIterator e, SimulatorKey k):
element(e), swap_event_key(k) {}
};
typedef std::list<Node> NodeList;
public:
typedef typename NodeList::iterator iterator;
typedef boost::function<void(SortDS*, SortDSIterator pos)>
SwapCallback;
/// \name Core Functionality
/// @{
KineticSort(SortDS* sort, Simulator* simulator, SwapCallback swap_callback);
template<class InputIterator>
void insert(iterator pos, InputIterator f, InputIterator l, Simulator* simulator);
void erase(iterator pos, Simulator* simulator);
void update_trajectory(iterator pos, Simulator* simulator);
void swap(iterator pos, Simulator* simulator);
bool audit(Simulator* simulator) const;
/// @}
private:
class SwapEvent;
void schedule_swaps(iterator b, iterator e, Simulator* s);
void schedule_swaps(iterator i, Simulator* s);
private:
NodeList list_;
SortDS* sort_;
SwapCallback swap_callback_;
};
#include "kinetic-sort.hpp"
#endif // __KINETIC_SORT_H__