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

@@ -335,110 +335,109 @@
 		    ///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;
@@ -704,97 +703,97 @@
 		      } 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);
@@ -852,110 +851,109 @@
 		        _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);
+		      }

0 comments (0 inline)

RhodeCode

Login to your account