Simplified implementation of bucket heaps (#50)
authorBalazs Dezso <deba@inf.elte.hu>
Thu, 11 Jun 2009 22:16:11 +0200
changeset 704bb8c4cd57900
parent 703 532697c9fa53
child 705 9f529abcaebf
Simplified implementation of bucket heaps (#50)
lemon/bucket_heap.h
     1.1 --- a/lemon/bucket_heap.h	Thu Jun 11 22:11:29 2009 +0200
     1.2 +++ b/lemon/bucket_heap.h	Thu Jun 11 22:16:11 2009 +0200
     1.3 @@ -29,6 +29,30 @@
     1.4  
     1.5  namespace lemon {
     1.6  
     1.7 +  namespace _bucket_heap_bits {
     1.8 +
     1.9 +    template <bool minimize>
    1.10 +    struct DirectionTraits {
    1.11 +      static bool less(int left, int right) {
    1.12 +        return left < right;
    1.13 +      }
    1.14 +      static void increase(int& value) {
    1.15 +        ++value;
    1.16 +      }
    1.17 +    };
    1.18 +
    1.19 +    template <>
    1.20 +    struct DirectionTraits<false> {
    1.21 +      static bool less(int left, int right) {
    1.22 +        return left > right;
    1.23 +      }
    1.24 +      static void increase(int& value) {
    1.25 +        --value;
    1.26 +      }
    1.27 +    };
    1.28 +
    1.29 +  }
    1.30 +
    1.31    /// \ingroup auxdat
    1.32    ///
    1.33    /// \brief A Bucket Heap implementation.
    1.34 @@ -45,7 +69,7 @@
    1.35    /// to handle the cross references.
    1.36    /// \param minimize If the given parameter is true then the heap gives back
    1.37    /// the lowest priority.
    1.38 -  template <typename _ItemIntMap, bool minimize = true >
    1.39 +  template <typename _ItemIntMap, bool minimize = true>
    1.40    class BucketHeap {
    1.41  
    1.42    public:
    1.43 @@ -58,6 +82,12 @@
    1.44      /// \e
    1.45      typedef _ItemIntMap ItemIntMap;
    1.46  
    1.47 +  private:
    1.48 +
    1.49 +    typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
    1.50 +
    1.51 +  public:
    1.52 +
    1.53      /// \brief Type to represent the items states.
    1.54      ///
    1.55      /// Each Item element have a state associated to it. It may be "in heap",
    1.56 @@ -161,7 +191,7 @@
    1.57        index[i] = idx;
    1.58        data.push_back(BucketItem(i, p));
    1.59        lace(idx);
    1.60 -      if (p < minimal) {
    1.61 +      if (Direction::less(p, minimal)) {
    1.62          minimal = p;
    1.63        }
    1.64      }
    1.65 @@ -172,7 +202,7 @@
    1.66      /// \pre The heap must be nonempty.
    1.67      Item top() const {
    1.68        while (first[minimal] == -1) {
    1.69 -        ++minimal;
    1.70 +        Direction::increase(minimal);
    1.71        }
    1.72        return data[first[minimal]].item;
    1.73      }
    1.74 @@ -183,7 +213,7 @@
    1.75      /// \pre The heap must be nonempty.
    1.76      Prio prio() const {
    1.77        while (first[minimal] == -1) {
    1.78 -        ++minimal;
    1.79 +        Direction::increase(minimal);
    1.80        }
    1.81        return minimal;
    1.82      }
    1.83 @@ -194,7 +224,7 @@
    1.84      /// \pre The heap must be non-empty.
    1.85      void pop() {
    1.86        while (first[minimal] == -1) {
    1.87 -        ++minimal;
    1.88 +        Direction::increase(minimal);
    1.89        }
    1.90        int idx = first[minimal];
    1.91        index[data[idx].item] = -2;
    1.92 @@ -235,11 +265,11 @@
    1.93      void set(const Item &i, const Prio &p) {
    1.94        int idx = index[i];
    1.95        if (idx < 0) {
    1.96 -        push(i,p);
    1.97 -      } else if (p > data[idx].value) {
    1.98 +        push(i, p);
    1.99 +      } else if (Direction::less(p, data[idx].value)) {
   1.100 +        decrease(i, p);
   1.101 +      } else {
   1.102          increase(i, p);
   1.103 -      } else {
   1.104 -        decrease(i, p);
   1.105        }
   1.106      }
   1.107  
   1.108 @@ -254,7 +284,7 @@
   1.109        int idx = index[i];
   1.110        unlace(idx);
   1.111        data[idx].value = p;
   1.112 -      if (p < minimal) {
   1.113 +      if (Direction::less(p, minimal)) {
   1.114          minimal = p;
   1.115        }
   1.116        lace(idx);
   1.117 @@ -328,193 +358,6 @@
   1.118  
   1.119    }; // class BucketHeap
   1.120  
   1.121 -
   1.122 -  template <typename _ItemIntMap>
   1.123 -  class BucketHeap<_ItemIntMap, false> {
   1.124 -
   1.125 -  public:
   1.126 -    typedef typename _ItemIntMap::Key Item;
   1.127 -    typedef int Prio;
   1.128 -    typedef std::pair<Item, Prio> Pair;
   1.129 -    typedef _ItemIntMap ItemIntMap;
   1.130 -
   1.131 -    enum State {
   1.132 -      IN_HEAP = 0,
   1.133 -      PRE_HEAP = -1,
   1.134 -      POST_HEAP = -2
   1.135 -    };
   1.136 -
   1.137 -  public:
   1.138 -
   1.139 -    explicit BucketHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
   1.140 -
   1.141 -    int size() const { return data.size(); }
   1.142 -    bool empty() const { return data.empty(); }
   1.143 -
   1.144 -    void clear() {
   1.145 -      data.clear(); first.clear(); maximal = -1;
   1.146 -    }
   1.147 -
   1.148 -  private:
   1.149 -
   1.150 -    void relocate_last(int idx) {
   1.151 -      if (idx + 1 != int(data.size())) {
   1.152 -        data[idx] = data.back();
   1.153 -        if (data[idx].prev != -1) {
   1.154 -          data[data[idx].prev].next = idx;
   1.155 -        } else {
   1.156 -          first[data[idx].value] = idx;
   1.157 -        }
   1.158 -        if (data[idx].next != -1) {
   1.159 -          data[data[idx].next].prev = idx;
   1.160 -        }
   1.161 -        index[data[idx].item] = idx;
   1.162 -      }
   1.163 -      data.pop_back();
   1.164 -    }
   1.165 -
   1.166 -    void unlace(int idx) {
   1.167 -      if (data[idx].prev != -1) {
   1.168 -        data[data[idx].prev].next = data[idx].next;
   1.169 -      } else {
   1.170 -        first[data[idx].value] = data[idx].next;
   1.171 -      }
   1.172 -      if (data[idx].next != -1) {
   1.173 -        data[data[idx].next].prev = data[idx].prev;
   1.174 -      }
   1.175 -    }
   1.176 -
   1.177 -    void lace(int idx) {
   1.178 -      if (int(first.size()) <= data[idx].value) {
   1.179 -        first.resize(data[idx].value + 1, -1);
   1.180 -      }
   1.181 -      data[idx].next = first[data[idx].value];
   1.182 -      if (data[idx].next != -1) {
   1.183 -        data[data[idx].next].prev = idx;
   1.184 -      }
   1.185 -      first[data[idx].value] = idx;
   1.186 -      data[idx].prev = -1;
   1.187 -    }
   1.188 -
   1.189 -  public:
   1.190 -
   1.191 -    void push(const Pair& p) {
   1.192 -      push(p.first, p.second);
   1.193 -    }
   1.194 -
   1.195 -    void push(const Item &i, const Prio &p) {
   1.196 -      int idx = data.size();
   1.197 -      index[i] = idx;
   1.198 -      data.push_back(BucketItem(i, p));
   1.199 -      lace(idx);
   1.200 -      if (data[idx].value > maximal) {
   1.201 -        maximal = data[idx].value;
   1.202 -      }
   1.203 -    }
   1.204 -
   1.205 -    Item top() const {
   1.206 -      while (first[maximal] == -1) {
   1.207 -        --maximal;
   1.208 -      }
   1.209 -      return data[first[maximal]].item;
   1.210 -    }
   1.211 -
   1.212 -    Prio prio() const {
   1.213 -      while (first[maximal] == -1) {
   1.214 -        --maximal;
   1.215 -      }
   1.216 -      return maximal;
   1.217 -    }
   1.218 -
   1.219 -    void pop() {
   1.220 -      while (first[maximal] == -1) {
   1.221 -        --maximal;
   1.222 -      }
   1.223 -      int idx = first[maximal];
   1.224 -      index[data[idx].item] = -2;
   1.225 -      unlace(idx);
   1.226 -      relocate_last(idx);
   1.227 -    }
   1.228 -
   1.229 -    void erase(const Item &i) {
   1.230 -      int idx = index[i];
   1.231 -      index[data[idx].item] = -2;
   1.232 -      unlace(idx);
   1.233 -      relocate_last(idx);
   1.234 -    }
   1.235 -
   1.236 -    Prio operator[](const Item &i) const {
   1.237 -      int idx = index[i];
   1.238 -      return data[idx].value;
   1.239 -    }
   1.240 -
   1.241 -    void set(const Item &i, const Prio &p) {
   1.242 -      int idx = index[i];
   1.243 -      if (idx < 0) {
   1.244 -        push(i,p);
   1.245 -      } else if (p > data[idx].value) {
   1.246 -        decrease(i, p);
   1.247 -      } else {
   1.248 -        increase(i, p);
   1.249 -      }
   1.250 -    }
   1.251 -
   1.252 -    void decrease(const Item &i, const Prio &p) {
   1.253 -      int idx = index[i];
   1.254 -      unlace(idx);
   1.255 -      data[idx].value = p;
   1.256 -      if (p > maximal) {
   1.257 -        maximal = p;
   1.258 -      }
   1.259 -      lace(idx);
   1.260 -    }
   1.261 -
   1.262 -    void increase(const Item &i, const Prio &p) {
   1.263 -      int idx = index[i];
   1.264 -      unlace(idx);
   1.265 -      data[idx].value = p;
   1.266 -      lace(idx);
   1.267 -    }
   1.268 -
   1.269 -    State state(const Item &i) const {
   1.270 -      int idx = index[i];
   1.271 -      if (idx >= 0) idx = 0;
   1.272 -      return State(idx);
   1.273 -    }
   1.274 -
   1.275 -    void state(const Item& i, State st) {
   1.276 -      switch (st) {
   1.277 -      case POST_HEAP:
   1.278 -      case PRE_HEAP:
   1.279 -        if (state(i) == IN_HEAP) {
   1.280 -          erase(i);
   1.281 -        }
   1.282 -        index[i] = st;
   1.283 -        break;
   1.284 -      case IN_HEAP:
   1.285 -        break;
   1.286 -      }
   1.287 -    }
   1.288 -
   1.289 -  private:
   1.290 -
   1.291 -    struct BucketItem {
   1.292 -      BucketItem(const Item& _item, int _value)
   1.293 -        : item(_item), value(_value) {}
   1.294 -
   1.295 -      Item item;
   1.296 -      int value;
   1.297 -
   1.298 -      int prev, next;
   1.299 -    };
   1.300 -
   1.301 -    ItemIntMap& index;
   1.302 -    std::vector<int> first;
   1.303 -    std::vector<BucketItem> data;
   1.304 -    mutable int maximal;
   1.305 -
   1.306 -  }; // class BucketHeap
   1.307 -
   1.308    /// \ingroup auxdat
   1.309    ///
   1.310    /// \brief A Simplified Bucket Heap implementation.
   1.311 @@ -524,7 +367,7 @@
   1.312    /// and simplier data structure than the BucketHeap. The main
   1.313    /// difference is that the BucketHeap stores for every key a double
   1.314    /// linked list while this class stores just simple lists. In the
   1.315 -  /// other way it does not supports erasing each elements just the
   1.316 +  /// other way it does not support erasing each elements just the
   1.317    /// minimal and it does not supports key increasing, decreasing.
   1.318    ///
   1.319    /// \param _ItemIntMap A read and writable Item int map, used internally
   1.320 @@ -542,6 +385,12 @@
   1.321      typedef std::pair<Item, Prio> Pair;
   1.322      typedef _ItemIntMap ItemIntMap;
   1.323  
   1.324 +  private:
   1.325 +
   1.326 +    typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
   1.327 +
   1.328 +  public:
   1.329 +
   1.330      /// \brief Type to represent the items states.
   1.331      ///
   1.332      /// Each Item element have a state associated to it. It may be "in heap",
   1.333 @@ -614,7 +463,7 @@
   1.334        if (p >= int(first.size())) first.resize(p + 1, -1);
   1.335        data[idx].next = first[p];
   1.336        first[p] = idx;
   1.337 -      if (p < minimal) {
   1.338 +      if (Direction::less(p, minimal)) {
   1.339          minimal = p;
   1.340        }
   1.341        ++num;
   1.342 @@ -626,7 +475,7 @@
   1.343      /// \pre The heap must be nonempty.
   1.344      Item top() const {
   1.345        while (first[minimal] == -1) {
   1.346 -        ++minimal;
   1.347 +        Direction::increase(minimal);
   1.348        }
   1.349        return data[first[minimal]].item;
   1.350      }
   1.351 @@ -637,7 +486,7 @@
   1.352      /// \pre The heap must be nonempty.
   1.353      Prio prio() const {
   1.354        while (first[minimal] == -1) {
   1.355 -        ++minimal;
   1.356 +        Direction::increase(minimal);
   1.357        }
   1.358        return minimal;
   1.359      }
   1.360 @@ -648,7 +497,7 @@
   1.361      /// \pre The heap must be non-empty.
   1.362      void pop() {
   1.363        while (first[minimal] == -1) {
   1.364 -        ++minimal;
   1.365 +        Direction::increase(minimal);
   1.366        }
   1.367        int idx = first[minimal];
   1.368        index[data[idx].item] = -2;
   1.369 @@ -711,121 +560,6 @@
   1.370  
   1.371    }; // class SimpleBucketHeap
   1.372  
   1.373 -  template <typename _ItemIntMap>
   1.374 -  class SimpleBucketHeap<_ItemIntMap, false> {
   1.375 -
   1.376 -  public:
   1.377 -    typedef typename _ItemIntMap::Key Item;
   1.378 -    typedef int Prio;
   1.379 -    typedef std::pair<Item, Prio> Pair;
   1.380 -    typedef _ItemIntMap ItemIntMap;
   1.381 -
   1.382 -    enum State {
   1.383 -      IN_HEAP = 0,
   1.384 -      PRE_HEAP = -1,
   1.385 -      POST_HEAP = -2
   1.386 -    };
   1.387 -
   1.388 -  public:
   1.389 -
   1.390 -    explicit SimpleBucketHeap(ItemIntMap &_index)
   1.391 -      : index(_index), free(-1), num(0), maximal(0) {}
   1.392 -
   1.393 -    int size() const { return num; }
   1.394 -
   1.395 -    bool empty() const { return num == 0; }
   1.396 -
   1.397 -    void clear() {
   1.398 -      data.clear(); first.clear(); free = -1; num = 0; maximal = 0;
   1.399 -    }
   1.400 -
   1.401 -    void push(const Pair& p) {
   1.402 -      push(p.first, p.second);
   1.403 -    }
   1.404 -
   1.405 -    void push(const Item &i, const Prio &p) {
   1.406 -      int idx;
   1.407 -      if (free == -1) {
   1.408 -        idx = data.size();
   1.409 -        data.push_back(BucketItem(i));
   1.410 -      } else {
   1.411 -        idx = free;
   1.412 -        free = data[idx].next;
   1.413 -        data[idx].item = i;
   1.414 -      }
   1.415 -      index[i] = idx;
   1.416 -      if (p >= int(first.size())) first.resize(p + 1, -1);
   1.417 -      data[idx].next = first[p];
   1.418 -      first[p] = idx;
   1.419 -      if (p > maximal) {
   1.420 -        maximal = p;
   1.421 -      }
   1.422 -      ++num;
   1.423 -    }
   1.424 -
   1.425 -    Item top() const {
   1.426 -      while (first[maximal] == -1) {
   1.427 -        --maximal;
   1.428 -      }
   1.429 -      return data[first[maximal]].item;
   1.430 -    }
   1.431 -
   1.432 -    Prio prio() const {
   1.433 -      while (first[maximal] == -1) {
   1.434 -        --maximal;
   1.435 -      }
   1.436 -      return maximal;
   1.437 -    }
   1.438 -
   1.439 -    void pop() {
   1.440 -      while (first[maximal] == -1) {
   1.441 -        --maximal;
   1.442 -      }
   1.443 -      int idx = first[maximal];
   1.444 -      index[data[idx].item] = -2;
   1.445 -      first[maximal] = data[idx].next;
   1.446 -      data[idx].next = free;
   1.447 -      free = idx;
   1.448 -      --num;
   1.449 -    }
   1.450 -
   1.451 -    Prio operator[](const Item &i) const {
   1.452 -      for (int k = 0; k < first.size(); ++k) {
   1.453 -        int idx = first[k];
   1.454 -        while (idx != -1) {
   1.455 -          if (data[idx].item == i) {
   1.456 -            return k;
   1.457 -          }
   1.458 -          idx = data[idx].next;
   1.459 -        }
   1.460 -      }
   1.461 -      return -1;
   1.462 -    }
   1.463 -
   1.464 -    State state(const Item &i) const {
   1.465 -      int idx = index[i];
   1.466 -      if (idx >= 0) idx = 0;
   1.467 -      return State(idx);
   1.468 -    }
   1.469 -
   1.470 -  private:
   1.471 -
   1.472 -    struct BucketItem {
   1.473 -      BucketItem(const Item& _item) : item(_item) {}
   1.474 -
   1.475 -      Item item;
   1.476 -
   1.477 -      int next;
   1.478 -    };
   1.479 -
   1.480 -    ItemIntMap& index;
   1.481 -    std::vector<int> first;
   1.482 -    std::vector<BucketItem> data;
   1.483 -    int free, num;
   1.484 -    mutable int maximal;
   1.485 -
   1.486 -  };
   1.487 -
   1.488  }
   1.489  
   1.490  #endif