1.1 --- a/src/work/jacint/fib_heap.h Tue Mar 09 15:53:19 2004 +0000
1.2 +++ b/src/work/jacint/fib_heap.h Tue Mar 09 18:42:14 2004 +0000
1.3 @@ -15,8 +15,11 @@
1.4 *
1.5 *bool empty() : true iff size()=0
1.6 *
1.7 - *void push(Item, Prio) : pushes Item to the heap with priority Prio. If
1.8 - * Item was already in the heap, it calls decrease(Item, Prio)
1.9 + *void set(Item, Prio) : calls push(Item, Prio) if Item is not
1.10 + * in the heap, and calls decrease/increase(Item, Prio) otherwise
1.11 + *
1.12 + *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
1.13 + * mustn't be in the heap.
1.14 *
1.15 *Item top() : returns the Item with least Prio
1.16 *
1.17 @@ -28,13 +31,10 @@
1.18 *
1.19 *void erase(Item) : deletes Item from the heap if it was already there
1.20 *
1.21 - *void decrease(Item, P) : If Item was not in the heap, then it calls
1.22 - * push(Item, P). If item is in the heap with Prio more than P
1.23 - * then sets its Prio to P.
1.24 + *void decrease(Item, P) : decreases prio of Item to P. Item must be in the heap
1.25 + * with prio at least P.
1.26 *
1.27 - *void increase(Item, P) : If Item was not in the heap, then it calls
1.28 - * push(Item, P). If item is in the heap with Prio less than P
1.29 - * then sets its Prio to P.
1.30 + *void increase(Item, P) : sets prio of Item to P.
1.31 *
1.32 *
1.33 *In Fibonacci heaps, increase and erase are not efficient, in case of
1.34 @@ -80,42 +80,44 @@
1.35 }
1.36
1.37
1.38 - bool empty() const { return blank; }
1.39 + bool empty() const { return blank; }
1.40 +
1.41 +
1.42 + void set (Item const it, PrioType const value) {
1.43 + int i=iimap.get(it);
1.44 + if ( i >= 0 && container[i].in ) {
1.45 + if ( !comp(container[i].prio, value) ) decrease(it, value);
1.46 + if ( comp(container[i].prio, value) ) increase(it, value);
1.47 + } else push(it, value);
1.48 + }
1.49
1.50 +
1.51 + void push (Item const it, PrioType const value) {
1.52 + int i=iimap.get(it);
1.53 + if ( i < 0 ) {
1.54 + int s=container.size();
1.55 + iimap.set( it, s );
1.56 + store st;
1.57 + st.name=it;
1.58 + container.push_back(st);
1.59 + i=s;
1.60 + }
1.61 +
1.62 + if ( !blank ) {
1.63 + container[container[minimum].right_neighbor].left_neighbor=i;
1.64 + container[i].right_neighbor=container[minimum].right_neighbor;
1.65 + container[minimum].right_neighbor=i;
1.66 + container[i].left_neighbor=minimum;
1.67 + if ( !comp( container[minimum].prio, value) ) minimum=i;
1.68 +
1.69 + } else {
1.70 + container[i].right_neighbor=container[i].left_neighbor=i;
1.71 + minimum=i;
1.72 + blank=false;
1.73 + }
1.74 + container[i].prio=value;
1.75 + }
1.76
1.77 - void push (Item const it, PrioType const value)
1.78 - {
1.79 -
1.80 - int i=iimap.get(it);
1.81 -
1.82 - if ( i >= 0 && container[i].in ) decrease(it, value);
1.83 - else {
1.84 - if ( i < 0 ) {
1.85 - int s=container.size();
1.86 - iimap.set( it, s );
1.87 - store st;
1.88 - st.name=it;
1.89 - container.push_back(st);
1.90 - i=s;
1.91 - }
1.92 -
1.93 - if ( !blank ) {
1.94 - container[container[minimum].right_neighbor].left_neighbor=i;
1.95 - container[i].right_neighbor=container[minimum].right_neighbor;
1.96 - container[minimum].right_neighbor=i;
1.97 - container[i].left_neighbor=minimum;
1.98 - if ( !comp( container[minimum].prio, value) ) minimum=i;
1.99 -
1.100 -
1.101 -
1.102 - } else {
1.103 - container[i].right_neighbor=container[i].left_neighbor=i;
1.104 - minimum=i;
1.105 - blank=false;
1.106 - }
1.107 - container[i].prio=value;
1.108 - }
1.109 - }
1.110
1.111
1.112 Item top() const {
1.113 @@ -199,36 +201,22 @@
1.114 }
1.115
1.116
1.117 - void decrease (Item it, PrioType const value) {
1.118 - int i=iimap.get(it);
1.119 - if ( i >= 0 && container[i].in ) {
1.120 -
1.121 - if ( comp(value, container[i].prio) ) {
1.122 - container[i].prio=value;
1.123 -
1.124 - if ( container[i].parent!=-1 ) {
1.125 - int p=container[i].parent;
1.126 -
1.127 - if ( !comp(container[p].prio, value) ) {
1.128 - cut(i,p);
1.129 - cascade(p);
1.130 - if ( comp(value, container[minimum].prio) ) minimum=i;
1.131 - }
1.132 - }
1.133 - }
1.134 - } else push(it, value);
1.135 - }
1.136 + void decrease (Item it, PrioType const value) {
1.137 + int i=iimap.get(it);
1.138 + container[i].prio=value;
1.139 + int p=container[i].parent;
1.140 +
1.141 + if ( p!=-1 && comp(value, container[p].prio) ) {
1.142 + cut(i,p);
1.143 + cascade(p);
1.144 + if ( comp(value, container[minimum].prio) ) minimum=i;
1.145 + }
1.146 + }
1.147
1.148
1.149 void increase (Item it, PrioType const value) {
1.150 - int i=iimap.get(it);
1.151 -
1.152 - if ( i >= 0 && container[i].in ) {
1.153 - if ( comp(container[i].prio, value) ) {
1.154 - erase(it);
1.155 - push(it, value);
1.156 - }
1.157 - } else push(it, value);
1.158 + erase(it);
1.159 + push(it, value);
1.160 }
1.161
1.162