39 /// efficient. The bucket heap is very simple implementation, it can store |
39 /// efficient. The bucket heap is very simple implementation, it can store |
40 /// only integer priorities and it stores for each priority in the |
40 /// only integer priorities and it stores for each priority in the |
41 /// \f$ [0..C) \f$ range a list of items. So it should be used only when |
41 /// \f$ [0..C) \f$ range a list of items. So it should be used only when |
42 /// the priorities are small. It is not intended to use as dijkstra heap. |
42 /// the priorities are small. It is not intended to use as dijkstra heap. |
43 /// |
43 /// |
44 /// \param _Item Type of the items to be stored. |
|
45 /// \param _ItemIntMap A read and writable Item int map, used internally |
44 /// \param _ItemIntMap A read and writable Item int map, used internally |
46 /// to handle the cross references. |
45 /// to handle the cross references. |
47 /// \param minimize If the given parameter is true then the heap gives back |
46 /// \param minimize If the given parameter is true then the heap gives back |
48 /// the lowest priority. |
47 /// the lowest priority. |
49 template <typename _Item, typename _ItemIntMap, bool minimize = true > |
48 template <typename _ItemIntMap, bool minimize = true > |
50 class BucketHeap { |
49 class BucketHeap { |
51 |
50 |
52 public: |
51 public: |
53 typedef _Item Item; |
52 typedef typename _ItemIntMap::Key Item; |
54 typedef int Prio; |
53 typedef int Prio; |
55 typedef std::pair<Item, Prio> Pair; |
54 typedef std::pair<Item, Prio> Pair; |
56 typedef _ItemIntMap ItemIntMap; |
55 typedef _ItemIntMap ItemIntMap; |
57 |
56 |
58 /// \brief Type to represent the items states. |
57 /// \brief Type to represent the items states. |
324 mutable int minimal; |
323 mutable int minimal; |
325 |
324 |
326 }; // class BucketHeap |
325 }; // class BucketHeap |
327 |
326 |
328 |
327 |
329 template <typename _Item, typename _ItemIntMap> |
328 template <typename _ItemIntMap> |
330 class BucketHeap<_Item, _ItemIntMap, false> { |
329 class BucketHeap<_ItemIntMap, false> { |
331 |
330 |
332 public: |
331 public: |
333 typedef _Item Item; |
332 typedef typename _ItemIntMap::Key Item; |
334 typedef int Prio; |
333 typedef int Prio; |
335 typedef std::pair<Item, Prio> Pair; |
334 typedef std::pair<Item, Prio> Pair; |
336 typedef _ItemIntMap ItemIntMap; |
335 typedef _ItemIntMap ItemIntMap; |
337 |
336 |
338 enum state_enum { |
337 enum state_enum { |
522 /// difference is that the BucketHeap stores for every key a double |
521 /// difference is that the BucketHeap stores for every key a double |
523 /// linked list while this class stores just simple lists. In the |
522 /// linked list while this class stores just simple lists. In the |
524 /// other way it does not supports erasing each elements just the |
523 /// other way it does not supports erasing each elements just the |
525 /// minimal and it does not supports key increasing, decreasing. |
524 /// minimal and it does not supports key increasing, decreasing. |
526 /// |
525 /// |
527 /// \param _Item Type of the items to be stored. |
|
528 /// \param _ItemIntMap A read and writable Item int map, used internally |
526 /// \param _ItemIntMap A read and writable Item int map, used internally |
529 /// to handle the cross references. |
527 /// to handle the cross references. |
530 /// \param minimize If the given parameter is true then the heap gives back |
528 /// \param minimize If the given parameter is true then the heap gives back |
531 /// the lowest priority. |
529 /// the lowest priority. |
532 /// |
530 /// |
533 /// \sa BucketHeap |
531 /// \sa BucketHeap |
534 template <typename _Item, typename _ItemIntMap, bool minimize = true > |
532 template <typename _ItemIntMap, bool minimize = true > |
535 class SimpleBucketHeap { |
533 class SimpleBucketHeap { |
536 |
534 |
537 public: |
535 public: |
538 typedef _Item Item; |
536 typedef typename _ItemIntMap::Key Item; |
539 typedef int Prio; |
537 typedef int Prio; |
540 typedef std::pair<Item, Prio> Pair; |
538 typedef std::pair<Item, Prio> Pair; |
541 typedef _ItemIntMap ItemIntMap; |
539 typedef _ItemIntMap ItemIntMap; |
542 |
540 |
543 /// \brief Type to represent the items states. |
541 /// \brief Type to represent the items states. |
707 int free, num; |
705 int free, num; |
708 mutable int minimal; |
706 mutable int minimal; |
709 |
707 |
710 }; // class SimpleBucketHeap |
708 }; // class SimpleBucketHeap |
711 |
709 |
712 template <typename _Item, typename _ItemIntMap> |
710 template <typename _ItemIntMap> |
713 class SimpleBucketHeap<_Item, _ItemIntMap, false> { |
711 class SimpleBucketHeap<_ItemIntMap, false> { |
714 |
712 |
715 public: |
713 public: |
716 typedef _Item Item; |
714 typedef typename _ItemIntMap::Key Item; |
717 typedef int Prio; |
715 typedef int Prio; |
718 typedef std::pair<Item, Prio> Pair; |
716 typedef std::pair<Item, Prio> Pair; |
719 typedef _ItemIntMap ItemIntMap; |
717 typedef _ItemIntMap ItemIntMap; |
720 |
718 |
721 enum state_enum { |
719 enum state_enum { |