COIN-OR::LEMON - Graph Library

Changeset 161:743fa50c442e in lemon-0.x


Ignore:
Timestamp:
03/09/04 19:42:14 (16 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@228
Message:

* empty log message *

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/fib_heap.h

    r159 r161  
    1616 *bool empty() : true iff size()=0
    1717 *
    18  *void push(Item, Prio) : pushes Item to the heap with priority Prio. If
    19  *     Item was already in the heap, it calls decrease(Item, Prio)
     18 *void set(Item, Prio) : calls push(Item, Prio) if Item is not
     19 *     in the heap, and calls decrease/increase(Item, Prio) otherwise
     20 *
     21 *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
     22 *     mustn't be in the heap.
    2023 *
    2124 *Item top() : returns the Item with least Prio
     
    2932 *void erase(Item) : deletes Item from the heap if it was already there
    3033 *
    31  *void decrease(Item, P) : If Item was not in the heap, then it calls
    32  *     push(Item, P). If item is in the heap with Prio more than P
    33  *     then sets its Prio to P.
    34  *
    35  *void increase(Item, P) : If Item was not in the heap, then it calls
    36  *     push(Item, P). If item is in the heap with Prio less than P
    37  *     then sets its Prio to P.
     34 *void decrease(Item, P) : decreases prio of Item to P. Item must be in the heap
     35 *     with prio at least P.
     36 *
     37 *void increase(Item, P) : sets prio of Item to P.
    3838 *
    3939 *
     
    8181
    8282
    83    bool empty() const { return blank; }
    84    
    85    
    86    void push (Item const it, PrioType const value)
    87    {
    88    
    89      int i=iimap.get(it);
    90      
    91      if ( i >= 0 && container[i].in ) decrease(it, value);
    92      else {
    93        if ( i < 0 ) {
    94          int s=container.size();
    95          iimap.set( it, s );   
    96          store st;
    97          st.name=it;
    98          container.push_back(st);
    99          i=s;
    100        }
    101        
    102        if ( !blank ) {
    103          container[container[minimum].right_neighbor].left_neighbor=i;
    104          container[i].right_neighbor=container[minimum].right_neighbor;
    105          container[minimum].right_neighbor=i;
    106          container[i].left_neighbor=minimum;
    107          if ( !comp( container[minimum].prio, value) ) minimum=i;
    108 
    109 
    110 
    111        } else {
    112          container[i].right_neighbor=container[i].left_neighbor=i;
    113          minimum=i;     
    114          blank=false;
    115        }
    116        container[i].prio=value;
    117      }
    118    }
     83    bool empty() const { return blank; }
     84
     85
     86    void set (Item const it, PrioType const value) {
     87      int i=iimap.get(it);
     88      if ( i >= 0 && container[i].in ) {
     89        if ( !comp(container[i].prio, value) ) decrease(it, value);
     90        if ( comp(container[i].prio, value) ) increase(it, value);
     91      } else push(it, value);
     92    }
     93   
     94
     95    void push (Item const it, PrioType const value) {
     96      int i=iimap.get(it);     
     97      if ( i < 0 ) {
     98        int s=container.size();
     99        iimap.set( it, s );     
     100        store st;
     101        st.name=it;
     102        container.push_back(st);
     103        i=s;
     104      }
     105     
     106      if ( !blank ) {
     107        container[container[minimum].right_neighbor].left_neighbor=i;
     108        container[i].right_neighbor=container[minimum].right_neighbor;
     109        container[minimum].right_neighbor=i;
     110        container[i].left_neighbor=minimum;
     111        if ( !comp( container[minimum].prio, value) ) minimum=i;
     112       
     113      } else {
     114        container[i].right_neighbor=container[i].left_neighbor=i;
     115        minimum=i;     
     116        blank=false;
     117      }
     118      container[i].prio=value;
     119    }
     120   
    119121
    120122
     
    200202   
    201203
    202    void decrease (Item it, PrioType const value) {
    203      int i=iimap.get(it);
    204      if ( i >= 0 && container[i].in ) {
    205        
    206        if ( comp(value, container[i].prio) ) {
    207          container[i].prio=value;
    208          
    209          if ( container[i].parent!=-1 ) {
    210            int p=container[i].parent;
    211            
    212            if ( !comp(container[p].prio, value) ) {
    213              cut(i,p);     
    214              cascade(p);
    215              if ( comp(value, container[minimum].prio) ) minimum=i;
    216            }
    217          }
    218        }
    219      } else push(it, value);
    220    }
     204    void decrease (Item it, PrioType const value) {
     205      int i=iimap.get(it);
     206      container[i].prio=value;
     207      int p=container[i].parent;
     208 
     209      if ( p!=-1 && comp(value, container[p].prio) ) {
     210        cut(i,p);           
     211        cascade(p);
     212        if ( comp(value, container[minimum].prio) ) minimum=i;
     213      }
     214    }
    221215   
    222216
    223217    void increase (Item it, PrioType const value) {
    224       int i=iimap.get(it);
    225      
    226       if ( i >= 0 && container[i].in ) {
    227         if ( comp(container[i].prio, value) ) {
    228           erase(it);
    229           push(it, value);
    230         }
    231       } else push(it, value);
     218      erase(it);
     219      push(it, value);
    232220    }
    233221
Note: See TracChangeset for help on using the changeset viewer.