lemon: comparison lemon/elevator.h

equal deleted inserted replaced

-:052089a90157
+:57611c56ba90
 ///
 ///Elevator class implements an efficient data structure
 ///for labeling items in push-relabel type algorithms.
 ///
-#include <test/test_tools.h>
+#include <lemon/bits/traits.h>
 namespace lemon {
 ///Class for handling "labels" in push-relabel type algorithms.
 ///A class for handling "labels" in push-relabel type algorithms.
 ///Each item is either \em active or not, and you can also choose a
 ///highest level active item.
 ///
 ///\sa LinkedElevator
 ///
-///\param Graph the underlying graph type
+///\param Graph Type of the underlying graph.
 ///\param Item Type of the items the data is assigned to (Graph::Node,
-///Graph::Edge, Graph::UEdge)
+///Graph::Arc, Graph::Edge).
 template<class Graph, class Item>
 class Elevator
 {
 public:
 ///Constructor with given maximum level.
 ///Constructor with given maximum level.
 ///
-///\param g The underlying graph
+///\param graph The underlying graph.
-///\param max_level Set the range of the possible labels to
+///\param max_level The maximum allowed level.
-///[0...\c max_level]
+///Set the range of the possible labels to <tt>[0..max_level]</tt>.
-Elevator(const Graph &g,int max_level) :
+Elevator(const Graph &graph,int max_level) :
-_g(g),
+_g(graph),
 _max_level(max_level),
 _item_num(_max_level),
-_where(g),
+_where(graph),
-_level(g,0),
+_level(graph,0),
 _items(_max_level),
 _first(_max_level+2),
 _last_active(_max_level+2),
 _highest_active(-1) {}
 ///Constructor.
 ///Constructor.
 ///
-///\param g The underlying graph
+///\param graph The underlying graph.
-///The range of the possible labels is [0...\c max_level],
+///Set the range of the possible labels to <tt>[0..max_level]</tt>,
 ///where \c max_level is equal to the number of labeled items in the graph.
-Elevator(const Graph &g) :
+Elevator(const Graph &graph) :
-_g(g),
+_g(graph),
-_max_level(countItems<Graph, Item>(g)),
+_max_level(countItems<Graph, Item>(graph)),
 _item_num(_max_level),
-_where(g),
+_where(graph),
-_level(g,0),
+_level(graph,0),
 _items(_max_level),
 _first(_max_level+2),
 _last_active(_max_level+2),
 _highest_active(-1)
 {
 ///Return the number of items on level \c l.
 int onLevel(int l) const
 {
 return _first[l+1]-_first[l];
 }
-///Return true if the level is empty.
+///Return true if level \c l is empty.
 bool emptyLevel(int l) const
 {
 return _first[l+1]-_first[l]==0;
 }
 ///Return the number of items above level \c l.
 ///Return the number of active items on level \c l.
 int activesOnLevel(int l) const
 {
 return _last_active[l]-_first[l]+1;
 }
-///Return true if there is not active item on level \c l.
+///Return true if there is no active item on level \c l.
 bool activeFree(int l) const
 {
 return _last_active[l]<_first[l];
 }
 ///Return the maximum allowed level.
 ///@{
 ///Return a highest level active item.
-///Return a highest level active item.
+///Return a highest level active item or INVALID if there is no active
-///
-///\return the highest level active item or INVALID if there is no active
 ///item.
 Item highestActive() const
 {
 return _highest_active>=0?*_last_active[_highest_active]:INVALID;
 }
-///Return a highest active level.
+///Return the highest active level.
-///Return a highest active level.
+///Return the level of the highest active item or -1 if there is no active
-///
-///\return the level of the highest active item or -1 if there is no active
 ///item.
 int highestActiveLevel() const
 {
 return _highest_active;
 }
 _level.set(it,_level[it]+1);
 swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
 --_first[++_highest_active];
 }
-///Lift the highest active item.
+///Lift the highest active item to the given level.
 ///Lift the item returned by highestActive() to level \c new_level.
 ///
 ///\warning \c new_level must be strictly higher
 ///than the current level.
 copy(li,_first[new_level]);
 _level.set(li,new_level);
 _highest_active=new_level;
 }
-///Lift the highest active item.
+///Lift the highest active item to the top level.
 ///Lift the item returned by highestActive() to the top level and
-///deactivates it.
+///deactivate it.
-///
-///\warning \c new_level must be strictly higher
-///than the current level.
-///
 void liftHighestActiveToTop()
 {
 const Item li = *_last_active[_highest_active];
 copy(--_first[_highest_active+1],_last_active[_highest_active]--);
 ///\name Active Item on Certain Level
 ///Functions for working with the active items.
 ///@{
-///Returns an active item on level \c l.
+///Return an active item on level \c l.
-///Returns an active item on level \c l.
+///Return an active item on level \c l or \ref INVALID if there is no such
-///
-///Returns an active item on level \c l or \ref INVALID if there is no such
 ///an item. (\c l must be from the range [0...\c max_level].
 Item activeOn(int l) const
 {
 return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
 }
-///Lifts the active item returned by \c activeOn() member function.
+///Lift the active item returned by \c activeOn(level) by one.
-///Lifts the active item returned by \c activeOn() member function
+///Lift the active item returned by \ref activeOn() "activeOn(level)"
 ///by one.
 Item liftActiveOn(int level)
 {
 Item it =*_last_active[level];
 _level.set(it,_level[it]+1);
 swap(_last_active[level]--, --_first[level+1]);
 if (level+1>_highest_active) ++_highest_active;
 }
-///Lifts the active item returned by \c activeOn() member function.
+///Lift the active item returned by \c activeOn(level) to the given level.
-///Lifts the active item returned by \c activeOn() member function
+///Lift the active item returned by \ref activeOn() "activeOn(level)"
 ///to the given level.
 void liftActiveOn(int level, int new_level)
 {
 const Item ai = *_last_active[level];
 copy(ai,_first[new_level]);
 _level.set(ai,new_level);
 if (new_level>_highest_active) _highest_active=new_level;
 }
-///Lifts the active item returned by \c activeOn() member function.
+///Lift the active item returned by \c activeOn(level) to the top level.
-///Lifts the active item returned by \c activeOn() member function
+///Lift the active item returned by \ref activeOn() "activeOn(level)"
-///to the top level.
+///to the top level and deactivate it.
 void liftActiveToTop(int level)
 {
 const Item ai = *_last_active[level];
 copy(--_first[level+1],_last_active[level]--);
 if(new_level>_highest_active) _highest_active=new_level;
 }
 ///Move an inactive item to the top but one level (in a dirty way).
-///This function moves an inactive item to the top but one level.
+///This function moves an inactive item from the top level to the top
-///It makes the underlying datastructure corrupt, so use is only if
+///but one level (in a dirty way).
-///you really know what it is for.
+///\warning It makes the underlying datastructure corrupt, so use it
+///only if you really know what it is for.
 ///\pre The item is on the top level.
 void dirtyTopButOne(Item i) {
 _level.set(i,_max_level - 1);
 }
-///Lift all items on and above a level to the top (and deactivate them).
+///Lift all items on and above the given level to the top level.
-///This function lifts all items on and above level \c l to \c
+///This function lifts all items on and above level \c l to the top
-///maxLevel(), and also deactivates them.
+///level and deactivates them.
 void liftToTop(int l)
 {
 const Vit f=_first[l];
 const Vit tl=_first[_max_level];
 for(Vit i=f;i!=tl;++i)
 Vit _init_num;
 public:
 ///\name Initialization
-///Using this function you can initialize the levels of the item.
+///Using these functions you can initialize the levels of the items.
 ///\n
-///This initializatios is started with calling \c initStart().
+///The initialization must be started with calling \c initStart().
-///Then the
+///Then the items should be listed level by level starting with the
-///items should be listed levels by levels statring with the lowest one
+///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
-///(with level 0). This is done by using \c initAddItem()
+///Finally \c initFinish() must be called.
-///and \c initNewLevel(). Finally \c initFinish() must be called.
+///The items not listed are put on the highest level.
-///The items not listed will be put on the highest level.
 ///@{
 ///Start the initialization process.
 void initStart()
 {
 _init_lev=0;
 _init_num=&_items[0];
 _first[0]=&_items[0];
 ++n;
 }
 }
 ///Add an item to the current level.
 void initAddItem(Item i)
 {
 swap(_where[i],_init_num);
 _level.set(i,_init_lev);
 ++_init_num;
 _first[_init_lev]=_init_num;
 _last_active[_init_lev]=_init_num-1;
 }
 ///Finalize the initialization process.
 void initFinish()
 {
 for(_init_lev++;_init_lev<=_max_level;_init_lev++)
 {
 _first[_init_lev]=_init_num;
 ///Each item is either \em active or not, and you can also choose a
 ///highest level active item.
 ///
 ///\sa Elevator
 ///
-///\param Graph the underlying graph type
+///\param Graph Type of the underlying graph.
 ///\param Item Type of the items the data is assigned to (Graph::Node,
-///Graph::Edge, Graph::UEdge)
+///Graph::Arc, Graph::Edge).
 template <class Graph, class Item>
 class LinkedElevator {
 public:
 typedef Item Key;
 public:
 ///Constructor with given maximum level.
 ///Constructor with given maximum level.
 ///
-///\param g The underlying graph
+///\param graph The underlying graph.
-///\param max_level Set the range of the possible labels to
+///\param max_level The maximum allowed level.
-///[0...\c max_level]
+///Set the range of the possible labels to <tt>[0..max_level]</tt>.
 LinkedElevator(const Graph& graph, int max_level)
 : _graph(graph), _max_level(max_level), _item_num(_max_level),
 _first(_max_level + 1), _last(_max_level + 1),
 _prev(graph), _next(graph),
 _highest_active(-1), _level(graph), _active(graph) {}
 ///Constructor.
 ///Constructor.
 ///
-///\param g The underlying graph
+///\param graph The underlying graph.
-///The range of the possible labels is [0...\c max_level],
+///Set the range of the possible labels to <tt>[0..max_level]</tt>,
 ///where \c max_level is equal to the number of labeled items in the graph.
 LinkedElevator(const Graph& graph)
 : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
 _item_num(_max_level),
 _first(_max_level + 1), _last(_max_level + 1),
 n = _next[n];
 }
 return num;
 }
-///Return true if there is not active item on level \c l.
+///Return true if there is no active item on level \c l.
 bool activeFree(int l) const {
 return _first[l] == INVALID || !_active[_first[l]];
 }
 ///Return the maximum allowed level.
 ///@{
 ///Return a highest level active item.
-///Return a highest level active item.
+///Return a highest level active item or INVALID if there is no active
-///
+///item.
-///\return the highest level active item or INVALID if there is no
-///active item.
 Item highestActive() const {
 return _highest_active >= 0 ? _first[_highest_active] : INVALID;
 }
-///Return a highest active level.
+///Return the highest active level.
-///Return a highest active level.
+///Return the level of the highest active item or -1 if there is no active
-///
+///item.
-///\return the level of the highest active item or -1 if there is
-///no active item.
 int highestActiveLevel() const {
 return _highest_active;
 }
 ///Lift the highest active item by one.
 _next.set(i, _first[_highest_active]);
 _first[_highest_active] = i;
 }
 }
-///Lift the highest active item.
+///Lift the highest active item to the given level.
 ///Lift the item returned by highestActive() to level \c new_level.
 ///
 ///\warning \c new_level must be strictly higher
 ///than the current level.
 _next.set(i, _first[_highest_active]);
 _first[_highest_active] = i;
 }
 }
-///Lift the highest active to top.
+///Lift the highest active item to the top level.
 ///Lift the item returned by highestActive() to the top level and
-///deactivates the item.
+///deactivate it.
-///
 void liftHighestActiveToTop() {
 Item i = _first[_highest_active];
 _level.set(i, _max_level);
 if (_next[i] != INVALID) {
 _prev.set(_next[i], INVALID);
 ///\name Active Item on Certain Level
 ///Functions for working with the active items.
 ///@{
-///Returns an active item on level \c l.
+///Return an active item on level \c l.
-///Returns an active item on level \c l.
+///Return an active item on level \c l or \ref INVALID if there is no such
-///
-///Returns an active item on level \c l or \ref INVALID if there is no such
 ///an item. (\c l must be from the range [0...\c max_level].
 Item activeOn(int l) const
 {
 return _active[_first[l]] ? _first[l] : INVALID;
 }
-///Lifts the active item returned by \c activeOn() member function.
+///Lift the active item returned by \c activeOn(l) by one.
-///Lifts the active item returned by \c activeOn() member function
+///Lift the active item returned by \ref activeOn() "activeOn(l)"
 ///by one.
 Item liftActiveOn(int l)
 {
 Item i = _first[l];
 if (_next[i] != INVALID) {
 if (_highest_active < l) {
 _highest_active = l;
 }
 }
-/// \brief Lifts the active item returned by \c activeOn() member function.
+///Lift the active item returned by \c activeOn(l) to the given level.
-///
-/// Lifts the active item returned by \c activeOn() member function
+///Lift the active item returned by \ref activeOn() "activeOn(l)"
-/// to the given level.
+///to the given level.
 void liftActiveOn(int l, int new_level)
 {
 Item i = _first[l];
 if (_next[i] != INVALID) {
 _prev.set(_next[i], INVALID);
 if (_highest_active < l) {
 _highest_active = l;
 }
 }
-///Lifts the active item returned by \c activeOn() member function.
+///Lift the active item returned by \c activeOn(l) to the top level.
-///Lifts the active item returned by \c activeOn() member function
+///Lift the active item returned by \ref activeOn() "activeOn(l)"
-///to the top level.
+///to the top level and deactivate it.
 void liftActiveToTop(int l)
 {
 Item i = _first[l];
 if (_next[i] != INVALID) {
 _prev.set(_next[i], INVALID);
 }
 }
 ///Move an inactive item to the top but one level (in a dirty way).
-///This function moves an inactive item to the top but one level.
+///This function moves an inactive item from the top level to the top
-///It makes the underlying datastructure corrupt, so use is only if
+///but one level (in a dirty way).
-///you really know what it is for.
+///\warning It makes the underlying datastructure corrupt, so use it
+///only if you really know what it is for.
 ///\pre The item is on the top level.
 void dirtyTopButOne(Item i) {
 _level.set(i, _max_level - 1);
 }
-///Lift all items on and above a level to the top (and deactivate them).
+///Lift all items on and above the given level to the top level.
-///This function lifts all items on and above level \c l to \c
+///This function lifts all items on and above level \c l to the top
-///maxLevel(), and also deactivates them.
+///level and deactivates them.
 void liftToTop(int l)  {
 for (int i = l + 1; _first[i] != INVALID; ++i) {
 Item n = _first[i];
 while (n != INVALID) {
 _level.set(n, _max_level);
 int _init_level;
 public:
 ///\name Initialization
-///Using this function you can initialize the levels of the item.
+///Using these functions you can initialize the levels of the items.
 ///\n
-///This initializatios is started with calling \c initStart().
+///The initialization must be started with calling \c initStart().
-///Then the
+///Then the items should be listed level by level starting with the
-///items should be listed levels by levels statring with the lowest one
+///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
-///(with level 0). This is done by using \c initAddItem()
+///Finally \c initFinish() must be called.
-///and \c initNewLevel(). Finally \c initFinish() must be called.
+///The items not listed are put on the highest level.
-///The items not listed will be put on the highest level.
 ///@{
 ///Start the initialization process.
 void initStart() {
 for (int i = 0; i <= _max_level; ++i) {
 _first[i] = _last[i] = INVALID;
 }
 _active.set(i, false);
 }
 }
 ///Add an item to the current level.
 void initAddItem(Item i) {
 _level.set(i, _init_level);
 if (_last[_init_level] == INVALID) {
 _first[_init_level] = i;
 _last[_init_level] = i;
 void initNewLevel() {
 ++_init_level;
 }
 ///Finalize the initialization process.
 void initFinish() {
 _highest_active = -1;
 }
 ///@}

changeset 408	37054b67d807
parent 397	61fbd77f0f44
child 463	88ed40ad0d4f