author Dmitriy Morozov <>
Sun, 17 Feb 2008 09:16:30 -0500
changeset 45 7c15f27bfa1b
parent 19 efa14432761a
child 56 f480ec018512
permissions -rw-r--r--
Merged the branch resulting from the upstream pull

#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
		typedef						Simulator_									Simulator;
		typedef						typename Simulator::PolynomialKernel		PolynomialKernel;
		typedef						SortDS_										SortDS;
		typedef						TrajectoryExtractor_						TrajectoryExtractor;
		typedef						typename Simulator::Key						SimulatorKey;
		typedef						typename SortDS::iterator					SortDSIterator;

		/* 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;

		typedef						typename NodeList::iterator					iterator;
		typedef						boost::function<void(SortDS*, SortDSIterator pos)>	

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

		class SwapEvent;
		void						schedule_swaps(iterator b, iterator e, Simulator* s);
		void						schedule_swaps(iterator i, Simulator* s);

		NodeList					list_;
		SortDS*						sort_;			
		SwapCallback				swap_callback_;	

#include "kinetic-sort.hpp"

#endif // __KINETIC_SORT_H__