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

@@ -359,62 +359,61 @@
 		    ///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:
@@ -728,49 +727,49 @@
 		    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.
@@ -876,62 +875,61 @@
 		        _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:

0 comments (0 inline)

RhodeCode

Login to your account