1.1 --- a/lemon/bucket_heap.h Wed May 17 05:54:24 2006 +0000
1.2 +++ b/lemon/bucket_heap.h Wed May 17 09:07:24 2006 +0000
1.3 @@ -30,7 +30,7 @@
1.4 namespace lemon {
1.5
1.6 /// \ingroup auxdat
1.7 -
1.8 + ///
1.9 /// \brief A Bucket Heap implementation.
1.10 ///
1.11 /// This class implements the \e bucket \e heap data structure. A \e heap
1.12 @@ -241,7 +241,7 @@
1.13 }
1.14
1.15 /// \brief Decreases the priority of \c i to \c p.
1.16 -
1.17 + ///
1.18 /// This method decreases the priority of item \c i to \c p.
1.19 /// \pre \c i must be stored in the heap with priority at least \c
1.20 /// p relative to \c Compare.
1.21 @@ -512,6 +512,303 @@
1.22
1.23 }; // class BucketHeap
1.24
1.25 + /// \ingroup auxdat
1.26 + ///
1.27 + /// \brief A Simplified Bucket Heap implementation.
1.28 + ///
1.29 + /// This class implements a simplified \e bucket \e heap data
1.30 + /// structure. It does not provide some functionality but it faster
1.31 + /// and simplier data structure than the BucketHeap. The main
1.32 + /// difference is that the BucketHeap stores for every key a double
1.33 + /// linked list while this class stores just simple lists. In the
1.34 + /// other way it does not supports erasing each elements just the
1.35 + /// minimal and it does not supports key increasing, decreasing.
1.36 + ///
1.37 + /// \param _Item Type of the items to be stored.
1.38 + /// \param _ItemIntMap A read and writable Item int map, used internally
1.39 + /// to handle the cross references.
1.40 + /// \param minimize If the given parameter is true then the heap gives back
1.41 + /// the lowest priority.
1.42 + ///
1.43 + /// \sa BucketHeap
1.44 + template <typename _Item, typename _ItemIntMap, bool minimize = true >
1.45 + class SimpleBucketHeap {
1.46 +
1.47 + public:
1.48 + typedef _Item Item;
1.49 + typedef int Prio;
1.50 + typedef std::pair<Item, Prio> Pair;
1.51 + typedef _ItemIntMap ItemIntMap;
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 + /// "pre heap" or "post heap". The latter two are indifferent from the
1.57 + /// heap's point of view, but may be useful to the user.
1.58 + ///
1.59 + /// The ItemIntMap \e should be initialized in such way that it maps
1.60 + /// PRE_HEAP (-1) to any element to be put in the heap...
1.61 + enum state_enum {
1.62 + IN_HEAP = 0,
1.63 + PRE_HEAP = -1,
1.64 + POST_HEAP = -2
1.65 + };
1.66 +
1.67 + public:
1.68 +
1.69 + /// \brief The constructor.
1.70 + ///
1.71 + /// The constructor.
1.72 + /// \param _index should be given to the constructor, since it is used
1.73 + /// internally to handle the cross references. The value of the map
1.74 + /// should be PRE_HEAP (-1) for each element.
1.75 + explicit SimpleBucketHeap(ItemIntMap &_index)
1.76 + : index(_index), free(-1), num(0), minimal(0) {}
1.77 +
1.78 + /// \brief Returns the number of items stored in the heap.
1.79 + ///
1.80 + /// The number of items stored in the heap.
1.81 + int size() const { return num; }
1.82 +
1.83 + /// \brief Checks if the heap stores no items.
1.84 + ///
1.85 + /// Returns \c true if and only if the heap stores no items.
1.86 + bool empty() const { return num == 0; }
1.87 +
1.88 + /// \brief Make empty this heap.
1.89 + ///
1.90 + /// Make empty this heap. It does not change the cross reference
1.91 + /// map. If you want to reuse a heap what is not surely empty you
1.92 + /// should first clear the heap and after that you should set the
1.93 + /// cross reference map for each item to \c PRE_HEAP.
1.94 + void clear() {
1.95 + data.clear(); first.clear(); free = -1; num = 0; minimal = 0;
1.96 + }
1.97 +
1.98 + /// \brief Insert a pair of item and priority into the heap.
1.99 + ///
1.100 + /// Adds \c p.first to the heap with priority \c p.second.
1.101 + /// \param p The pair to insert.
1.102 + void push(const Pair& p) {
1.103 + push(p.first, p.second);
1.104 + }
1.105 +
1.106 + /// \brief Insert an item into the heap with the given priority.
1.107 + ///
1.108 + /// Adds \c i to the heap with priority \c p.
1.109 + /// \param i The item to insert.
1.110 + /// \param p The priority of the item.
1.111 + void push(const Item &i, const Prio &p) {
1.112 + int idx;
1.113 + if (free == -1) {
1.114 + idx = data.size();
1.115 + data.push_back(BucketItem(i, p));
1.116 + } else {
1.117 + idx = free;
1.118 + free = data[idx].next;
1.119 + data[idx].item = i; data[idx].value = p;
1.120 + }
1.121 + index[i] = idx;
1.122 + if (p >= (int)first.size()) first.resize(p + 1, -1);
1.123 + data[idx].next = first[p];
1.124 + first[p] = idx;
1.125 + if (p < minimal) {
1.126 + minimal = p;
1.127 + }
1.128 + ++num;
1.129 + }
1.130 +
1.131 + /// \brief Returns the item with minimum priority.
1.132 + ///
1.133 + /// This method returns the item with minimum priority.
1.134 + /// \pre The heap must be nonempty.
1.135 + Item top() const {
1.136 + while (first[minimal] == -1) {
1.137 + ++minimal;
1.138 + }
1.139 + return data[first[minimal]].item;
1.140 + }
1.141 +
1.142 + /// \brief Returns the minimum priority.
1.143 + ///
1.144 + /// It returns the minimum priority.
1.145 + /// \pre The heap must be nonempty.
1.146 + Prio prio() const {
1.147 + while (first[minimal] == -1) {
1.148 + ++minimal;
1.149 + }
1.150 + return minimal;
1.151 + }
1.152 +
1.153 + /// \brief Deletes the item with minimum priority.
1.154 + ///
1.155 + /// This method deletes the item with minimum priority from the heap.
1.156 + /// \pre The heap must be non-empty.
1.157 + void pop() {
1.158 + while (first[minimal] == -1) {
1.159 + ++minimal;
1.160 + }
1.161 + int idx = first[minimal];
1.162 + index[data[idx].item] = -2;
1.163 + first[minimal] = data[idx].next;
1.164 + data[idx].next = free;
1.165 + free = idx;
1.166 + --num;
1.167 + }
1.168 +
1.169 + /// \brief Returns the priority of \c i.
1.170 + ///
1.171 + /// This function returns the priority of item \c i.
1.172 + /// \pre \c i must be in the heap.
1.173 + /// \param i The item.
1.174 + Prio operator[](const Item &i) const {
1.175 + int idx = index[i];
1.176 + return data[idx].value;
1.177 + }
1.178 +
1.179 + /// \brief Returns if \c item is in, has already been in, or has
1.180 + /// never been in the heap.
1.181 + ///
1.182 + /// This method returns PRE_HEAP if \c item has never been in the
1.183 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
1.184 + /// otherwise. In the latter case it is possible that \c item will
1.185 + /// get back to the heap again.
1.186 + /// \param i The item.
1.187 + state_enum state(const Item &i) const {
1.188 + int idx = index[i];
1.189 + if (idx >= 0) idx = 0;
1.190 + return state_enum(idx);
1.191 + }
1.192 +
1.193 + private:
1.194 +
1.195 + struct BucketItem {
1.196 + BucketItem(const Item& _item, int _value)
1.197 + : item(_item), value(_value) {}
1.198 +
1.199 + Item item;
1.200 + int value;
1.201 +
1.202 + int next;
1.203 + };
1.204 +
1.205 + ItemIntMap& index;
1.206 + std::vector<int> first;
1.207 + std::vector<BucketItem> data;
1.208 + int free, num;
1.209 + mutable int minimal;
1.210 +
1.211 + }; // class SimpleBucketHeap
1.212 +
1.213 + template <typename _Item, typename _ItemIntMap>
1.214 + class SimpleBucketHeap<_Item, _ItemIntMap, false> {
1.215 +
1.216 + public:
1.217 + typedef _Item Item;
1.218 + typedef int Prio;
1.219 + typedef std::pair<Item, Prio> Pair;
1.220 + typedef _ItemIntMap ItemIntMap;
1.221 +
1.222 + enum state_enum {
1.223 + IN_HEAP = 0,
1.224 + PRE_HEAP = -1,
1.225 + POST_HEAP = -2
1.226 + };
1.227 +
1.228 + public:
1.229 +
1.230 + explicit SimpleBucketHeap(ItemIntMap &_index)
1.231 + : index(_index), free(-1), num(0), maximal(0) {}
1.232 +
1.233 + int size() const { return num; }
1.234 +
1.235 + bool empty() const { return num == 0; }
1.236 +
1.237 + void clear() {
1.238 + data.clear(); first.clear(); free = -1; num = 0; maximal = 0;
1.239 + }
1.240 +
1.241 + void push(const Pair& p) {
1.242 + push(p.first, p.second);
1.243 + }
1.244 +
1.245 + void push(const Item &i, const Prio &p) {
1.246 + int idx;
1.247 + if (free == -1) {
1.248 + idx = data.size();
1.249 + data.push_back(BucketItem(i, p));
1.250 + } else {
1.251 + idx = free;
1.252 + free = data[idx].next;
1.253 + data[idx].item = i; data[idx].value = p;
1.254 + }
1.255 + index[i] = idx;
1.256 + if (p >= (int)first.size()) first.resize(p + 1, -1);
1.257 + data[idx].next = first[p];
1.258 + first[p] = idx;
1.259 + if (p > maximal) {
1.260 + maximal = p;
1.261 + }
1.262 + ++num;
1.263 + }
1.264 +
1.265 + Item top() const {
1.266 + while (first[maximal] == -1) {
1.267 + --maximal;
1.268 + }
1.269 + return data[first[maximal]].item;
1.270 + }
1.271 +
1.272 + Prio prio() const {
1.273 + while (first[maximal] == -1) {
1.274 + --maximal;
1.275 + }
1.276 + return maximal;
1.277 + }
1.278 +
1.279 + void pop() {
1.280 + while (first[maximal] == -1) {
1.281 + --maximal;
1.282 + }
1.283 + int idx = first[maximal];
1.284 + index[data[idx].item] = -2;
1.285 + first[maximal] = data[idx].next;
1.286 + data[idx].next = free;
1.287 + free = idx;
1.288 + --num;
1.289 + }
1.290 +
1.291 + Prio operator[](const Item &i) const {
1.292 + int idx = index[i];
1.293 + return data[idx].value;
1.294 + }
1.295 +
1.296 + state_enum state(const Item &i) const {
1.297 + int idx = index[i];
1.298 + if (idx >= 0) idx = 0;
1.299 + return state_enum(idx);
1.300 + }
1.301 +
1.302 + private:
1.303 +
1.304 + struct BucketItem {
1.305 + BucketItem(const Item& _item, int _value)
1.306 + : item(_item), value(_value) {}
1.307 +
1.308 + Item item;
1.309 + int value;
1.310 +
1.311 + int next;
1.312 + };
1.313 +
1.314 + ItemIntMap& index;
1.315 + std::vector<int> first;
1.316 + std::vector<BucketItem> data;
1.317 + int free, num;
1.318 + mutable int maximal;
1.319 +
1.320 + };
1.321 +
1.322 }
1.323
1.324 #endif