LEMON/LEMON-official Changeset - r395:d916b8995e22

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r395:d916b8995e22

« 394:1bab3a

396:b04e43 »

r395:d916b8995e22

Mon, 17 Nov 2008 16:41:15

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Rename markToBottom() to dirtyTopButOne() + better doc (#174)

0 1 0

default

1 file changed with 17 insertions and 19 deletions:

lemon/elevator.h

↑ Collapse diff ↑

lemon/elevator.h

Show inline comments

@@ -287,206 +287,205 @@
 		    ///Functions for working with the active items.
 		    ///@{
 		    ///Returns an active item on level \c l.
 		    ///Returns an active item on level \c l.
 		    ///
 		    ///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.
 		    ///Lifts the active item returned by \c activeOn() member function
 		    ///by one.
 		    Item liftActiveOn(int level)
+		    {
 		      ++_level[*_last_active[level]];
 		      swap(_last_active[level]--, --_first[level+1]);
 		      if (level+1>_highest_active) ++_highest_active;
+		    }
 		    ///Lifts the active item returned by \c activeOn() member function.
 		    ///Lifts the active item returned by \c activeOn() member function
 		    ///to the given level.
 		    void liftActiveOn(int level, int new_level)
+		    {
 		      const Item ai = *_last_active[level];
 		      copy(--_first[level+1], _last_active[level]--);
 		      for(int l=level+1;l<new_level;l++)
+		        {
 		          copy(_last_active[l],_first[l]);
 		          copy(--_first[l+1], _last_active[l]--);
+		        }
 		      copy(ai,_first[new_level]);
 		      _level[ai]=new_level;
 		      if (new_level>_highest_active) _highest_active=new_level;
+		    }
 		    ///Lifts the active item returned by \c activeOn() member function.
 		    ///Lifts the active item returned by \c activeOn() member function
 		    ///to the top level.
 		    void liftActiveToTop(int level)
+		    {
 		      const Item ai = *_last_active[level];
 		      copy(--_first[level+1],_last_active[level]--);
 		      for(int l=level+1;l<_max_level;l++)
+		        {
 		          copy(_last_active[l],_first[l]);
 		          copy(--_first[l+1], _last_active[l]--);
+		        }
 		      copy(ai,_first[_max_level]);
 		      --_last_active[_max_level];
 		      _level[ai]=_max_level;
 		      if (_highest_active==level) {
 		        while(_highest_active>=0 &&
 		              _last_active[_highest_active]<_first[_highest_active])
 		          _highest_active--;
+		      }
+		    }
 		    ///@}
 		    ///Lift an active item to a higher level.
 		    ///Lift an active item to a higher level.
 		    ///\param i The item to be lifted. It must be active.
 		    ///\param new_level The new level of \c i. It must be strictly higher
 		    ///than the current level.
 		    ///
 		    void lift(Item i, int new_level)
+		    {
 		      const int lo = _level[i];
 		      const Vit w = _where[i];
 		      copy(_last_active[lo],w);
 		      copy(--_first[lo+1],_last_active[lo]--);
 		      for(int l=lo+1;l<new_level;l++)
+		        {
 		          copy(_last_active[l],_first[l]);
 		          copy(--_first[l+1],_last_active[l]--);
+		        }
 		      copy(i,_first[new_level]);
 		      _level[i]=new_level;
 		      if(new_level>_highest_active) _highest_active=new_level;
+		    }
-		    ///Mark the node as it did not reach the max level
+		    ///Move an inactive item to the top but one level (in a dirty way).
 		    ///Mark the node as it did not reach the max level. It sets the
 		    ///level to the under the max level value. The node will be never
 		    ///more activated because the push operation from the maximum
 		    ///level is forbidden in the push-relabel algorithms. The node
 		    ///should be lifted previously to the top level.
 		    void markToBottom(Item i) {
 		    ///This function moves an inactive item to the top but one level.
 		    ///It makes the underlying datastructure corrupt, so use is only if
 		    ///you really know what it is for.
 		    ///\pre The item is on the top level.
 		    void dirtyTopButOne(Item i) {
 		      _level[i] = _max_level - 1;
+		    }
-		    ///Lift all nodes on and above a level to the top (and deactivate them).
+		    ///Lift all items on and above a level to the top (and deactivate them).
-		    ///This function lifts all nodes on and above level \c l to \c
+		    ///This function lifts all items on and above level \c l to \c
 		    ///maxLevel(), and also deactivates them.
 		    void liftToTop(int l)
+		    {
 		      const Vit f=_first[l];
 		      const Vit tl=_first[_max_level];
 		      for(Vit i=f;i!=tl;++i)
 		        _level[*i]=_max_level;
 		      for(int i=l;i<=_max_level;i++)
+		        {
 		          _first[i]=f;
 		          _last_active[i]=f-1;
+		        }
 		      for(_highest_active=l-1;
 		          _highest_active>=0 &&
 		            _last_active[_highest_active]<_first[_highest_active];
 		          _highest_active--) ;
+		    }
 		  private:
 		    int _init_lev;
 		    Vit _init_num;
 		  public:
 		    ///\name Initialization
 		    ///Using this function you can initialize the levels of the item.
 		    ///\n
 		    ///This initializatios is started with calling \c initStart().
 		    ///Then the
 		    ///items should be listed levels by levels statring with the lowest one
 		    ///(with level 0). This is done by using \c initAddItem()
 		    ///and \c initNewLevel(). Finally \c initFinish() must be called.
 		    ///The items not listed will be put on the highest level.
 		    ///@{
 		    ///Start the initialization process.
 		    void initStart()
+		    {
 		      _init_lev=0;
 		      _init_num=_items.begin();
 		      _first[0]=_items.begin();
 		      _last_active[0]=_items.begin()-1;
 		      Vit n=_items.begin();
 		      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
+		        {
 		          *n=i;
 		          _where[i]=n;
 		          _level[i]=_max_level;
 		          ++n;
+		        }
+		    }
 		    ///Add an item to the current level.
 		    void initAddItem(Item i)
+		    {
 		     swap(_where[i],_init_num);
 		      _level[i]=_init_lev;
 		      ++_init_num;
+		    }
 		    ///Start a new level.
 		    ///Start a new level.
 		    ///It shouldn't be used before the items on level 0 are listed.
 		    void initNewLevel()
+		    {
 		      _init_lev++;
 		      _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;
 		          _last_active[_init_lev]=_init_num-1;
+		        }
 		      _first[_max_level+1]=_items.begin()+_item_num;
 		      _last_active[_max_level+1]=_items.begin()+_item_num-1;
 		      _highest_active = -1;
+		    }
 		    ///@}
 		  };
 		  ///Class for handling "labels" in push-relabel type algorithms.
 		  ///A class for handling "labels" in push-relabel type algorithms.
 		  ///
 		  ///\ingroup auxdat
@@ -656,348 +655,347 @@
 		      return num;
+		    }
 		    ///Return true if there is not active item on level \c l.
 		    bool activeFree(int l) const {
 		      return _first[l] == INVALID || !_active[_first[l]];
+		    }
 		    ///Return the maximum allowed level.
 		    int maxLevel() const {
 		      return _max_level;
+		    }
 		    ///\name Highest Active Item
 		    ///Functions for working with the highest level
 		    ///active item.
 		    ///@{
 		    ///Return a highest level active item.
 		    ///Return a highest level 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 a highest active level.
 		    ///
 		    ///\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.
 		    ///Lift the item returned by highestActive() by one.
 		    ///
 		    void liftHighestActive() {
 		      Item i = _first[_highest_active];
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], INVALID);
 		        _first[_highest_active] = _next[i];
 		      } else {
 		        _first[_highest_active] = INVALID;
 		        _last[_highest_active] = INVALID;
+		      }
 		      _level.set(i, ++_highest_active);
 		      if (_first[_highest_active] == INVALID) {
 		        _first[_highest_active] = i;
 		        _last[_highest_active] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		      } else {
 		        _prev.set(_first[_highest_active], i);
 		        _next.set(i, _first[_highest_active]);
 		        _first[_highest_active] = i;
+		      }
+		    }
 		    ///Lift the highest active item.
 		    ///Lift the item returned by highestActive() to level \c new_level.
 		    ///
 		    ///\warning \c new_level must be strictly higher
 		    ///than the current level.
 		    ///
 		    void liftHighestActive(int new_level) {
 		      Item i = _first[_highest_active];
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], INVALID);
 		        _first[_highest_active] = _next[i];
 		      } else {
 		        _first[_highest_active] = INVALID;
 		        _last[_highest_active] = INVALID;
+		      }
 		      _level.set(i, _highest_active = new_level);
 		      if (_first[_highest_active] == INVALID) {
 		        _first[_highest_active] = _last[_highest_active] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		      } else {
 		        _prev.set(_first[_highest_active], i);
 		        _next.set(i, _first[_highest_active]);
 		        _first[_highest_active] = i;
+		      }
+		    }
 		    ///Lift the highest active to top.
 		    ///Lift the item returned by highestActive() to the top level and
-		    ///deactivates the node.
+		    ///deactivates the item.
 		    ///
 		    void liftHighestActiveToTop() {
 		      Item i = _first[_highest_active];
 		      _level.set(i, _max_level);
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], INVALID);
 		        _first[_highest_active] = _next[i];
 		      } else {
 		        _first[_highest_active] = INVALID;
 		        _last[_highest_active] = INVALID;
+		      }
 		      while (_highest_active >= 0 && activeFree(_highest_active))
 		        --_highest_active;
+		    }
 		    ///@}
 		    ///\name Active Item on Certain Level
 		    ///Functions for working with the active items.
 		    ///@{
 		    ///Returns an active item on level \c l.
 		    ///Returns an active item on level \c l.
 		    ///
 		    ///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.
 		    ///Lifts the active item returned by \c activeOn() member function
 		    ///by one.
 		    Item liftActiveOn(int l)
+		    {
 		      Item i = _first[l];
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], INVALID);
 		        _first[l] = _next[i];
 		      } else {
 		        _first[l] = INVALID;
 		        _last[l] = INVALID;
+		      }
 		      _level.set(i, ++l);
 		      if (_first[l] == INVALID) {
 		        _first[l] = _last[l] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		      } else {
 		        _prev.set(_first[l], i);
 		        _next.set(i, _first[l]);
 		        _first[l] = i;
+		      }
 		      if (_highest_active < l) {
 		        _highest_active = l;
+		      }
+		    }
 		    /// \brief Lifts the active item returned by \c activeOn() member function.
 		    ///
 		    /// Lifts the active item returned by \c activeOn() member function
 		    /// to the given level.
 		    void liftActiveOn(int l, int new_level)
+		    {
 		      Item i = _first[l];
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], INVALID);
 		        _first[l] = _next[i];
 		      } else {
 		        _first[l] = INVALID;
 		        _last[l] = INVALID;
+		      }
 		      _level.set(i, l = new_level);
 		      if (_first[l] == INVALID) {
 		        _first[l] = _last[l] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		      } else {
 		        _prev.set(_first[l], i);
 		        _next.set(i, _first[l]);
 		        _first[l] = i;
+		      }
 		      if (_highest_active < l) {
 		        _highest_active = l;
+		      }
+		    }
 		    ///Lifts the active item returned by \c activeOn() member function.
 		    ///Lifts the active item returned by \c activeOn() member function
 		    ///to the top level.
 		    void liftActiveToTop(int l)
+		    {
 		      Item i = _first[l];
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], INVALID);
 		        _first[l] = _next[i];
 		      } else {
 		        _first[l] = INVALID;
 		        _last[l] = INVALID;
+		      }
 		      _level.set(i, _max_level);
 		      if (l == _highest_active) {
 		        while (_highest_active >= 0 && activeFree(_highest_active))
 		          --_highest_active;
+		      }
+		    }
 		    ///@}
 		    /// \brief Lift an active item to a higher level.
 		    ///
 		    /// Lift an active item to a higher level.
 		    /// \param i The item to be lifted. It must be active.
 		    /// \param new_level The new level of \c i. It must be strictly higher
 		    /// than the current level.
 		    ///
 		    void lift(Item i, int new_level) {
 		      if (_next[i] != INVALID) {
 		        _prev.set(_next[i], _prev[i]);
 		      } else {
 		        _last[new_level] = _prev[i];
+		      }
 		      if (_prev[i] != INVALID) {
 		        _next.set(_prev[i], _next[i]);
 		      } else {
 		        _first[new_level] = _next[i];
+		      }
 		      _level.set(i, new_level);
 		      if (_first[new_level] == INVALID) {
 		        _first[new_level] = _last[new_level] = i;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		      } else {
 		        _prev.set(_first[new_level], i);
 		        _next.set(i, _first[new_level]);
 		        _first[new_level] = i;
+		      }
 		      if (_highest_active < new_level) {
 		        _highest_active = new_level;
+		      }
+		    }
-		    ///Mark the node as it did not reach the max level
+		    ///Move an inactive item to the top but one level (in a dirty way).
 		    ///Mark the node as it did not reach the max level. It sets the
 		    ///level to the under the max level value. The node will be never
 		    ///more activated because the push operation from the maximum
 		    ///level is forbidden in the push-relabel algorithms. The node
 		    ///should be lifted previously to the top level.
 		    void markToBottom(Item i) {
 		    ///This function moves an inactive item to the top but one level.
 		    ///It makes the underlying datastructure corrupt, so use is 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 nodes on and above a level to the top (and deactivate them).
+		    ///Lift all items on and above a level to the top (and deactivate them).
-		    ///This function lifts all nodes on and above level \c l to \c
+		    ///This function lifts all items on and above level \c l to \c
 		    ///maxLevel(), and also 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);
 		          n = _next[n];
+		        }
 		        _first[i] = INVALID;
 		        _last[i] = INVALID;
+		      }
 		      if (_highest_active > l - 1) {
 		        _highest_active = l - 1;
 		        while (_highest_active >= 0 && activeFree(_highest_active))
 		          --_highest_active;
+		      }
+		    }
 		  private:
 		    int _init_level;
 		  public:
 		    ///\name Initialization
 		    ///Using this function you can initialize the levels of the item.
 		    ///\n
 		    ///This initializatios is started with calling \c initStart().
 		    ///Then the
 		    ///items should be listed levels by levels statring with the lowest one
 		    ///(with level 0). This is done by using \c initAddItem()
 		    ///and \c initNewLevel(). Finally \c initFinish() must be called.
 		    ///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;
+		      }
 		      _init_level = 0;
 		      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
 		          i != INVALID; ++i) {
 		        _level.set(i, _max_level);
 		        _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;
 		        _prev.set(i, INVALID);
 		        _next.set(i, INVALID);
 		      } else {
 		        _prev.set(i, _last[_init_level]);
 		        _next.set(i, INVALID);
 		        _next.set(_last[_init_level], i);
 		        _last[_init_level] = i;
+		      }
+		    }
 		    ///Start a new level.
 		    ///Start a new level.
 		    ///It shouldn't be used before the items on level 0 are listed.
 		    void initNewLevel() {
 		      ++_init_level;
+		    }
 		    ///Finalize the initialization process.
 		    void initFinish() {
 		      _highest_active = -1;
+		    }
 		    ///@}
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif

0 comments (0 inline)

RhodeCode

Login to your account