26 #include <vector> |
26 #include <vector> |
27 #include <lemon/error.h> |
27 #include <lemon/error.h> |
28 |
28 |
29 namespace lemon { |
29 namespace lemon { |
30 |
30 |
31 /// \brief Exception thrown by RadixHeap. |
|
32 /// |
|
33 /// This Exception is thrown when a smaller priority |
|
34 /// is inserted into the \e RadixHeap then the last time erased. |
|
35 /// \see RadixHeap |
|
36 /// \author Balazs Dezso |
|
37 |
|
38 class UnderFlowPriorityError : public RuntimeError { |
|
39 public: |
|
40 virtual const char* what() const throw() { |
|
41 return "lemon::UnderFlowPriorityError"; |
|
42 } |
|
43 }; |
|
44 |
31 |
45 /// \ingroup auxdata |
32 /// \ingroup auxdata |
46 /// |
33 /// |
47 /// \brief A Radix Heap implementation. |
34 /// \brief A Radix Heap implementation. |
48 /// |
35 /// |
67 public: |
54 public: |
68 typedef typename _ItemIntMap::Key Item; |
55 typedef typename _ItemIntMap::Key Item; |
69 typedef int Prio; |
56 typedef int Prio; |
70 typedef _ItemIntMap ItemIntMap; |
57 typedef _ItemIntMap ItemIntMap; |
71 |
58 |
|
59 /// \brief Exception thrown by RadixHeap. |
|
60 /// |
|
61 /// This Exception is thrown when a smaller priority |
|
62 /// is inserted into the \e RadixHeap then the last time erased. |
|
63 /// \see RadixHeap |
|
64 /// \author Balazs Dezso |
|
65 |
|
66 class UnderFlowPriorityError : public RuntimeError { |
|
67 public: |
|
68 virtual const char* what() const throw() { |
|
69 return "lemon::RadixHeap::UnderFlowPriorityError"; |
|
70 } |
|
71 }; |
|
72 |
72 /// \brief Type to represent the items states. |
73 /// \brief Type to represent the items states. |
73 /// |
74 /// |
74 /// Each Item element have a state associated to it. It may be "in heap", |
75 /// Each Item element have a state associated to it. It may be "in heap", |
75 /// "pre heap" or "post heap". The latter two are indifferent from the |
76 /// "pre heap" or "post heap". The latter two are indifferent from the |
76 /// heap's point of view, but may be useful to the user. |
77 /// heap's point of view, but may be useful to the user. |
77 /// |
78 /// |
78 /// The ItemIntMap \e should be initialized in such way that it maps |
79 /// The ItemIntMap \e should be initialized in such way that it maps |
79 /// PRE_HEAP (-1) to any element to be put in the heap... |
80 /// PRE_HEAP (-1) to any element to be put in the heap... |
80 enum state_enum { |
81 enum State { |
81 IN_HEAP = 0, |
82 IN_HEAP = 0, |
82 PRE_HEAP = -1, |
83 PRE_HEAP = -1, |
83 POST_HEAP = -2 |
84 POST_HEAP = -2 |
84 }; |
85 }; |
85 |
86 |
399 /// This method returns PRE_HEAP if \c item has never been in the |
400 /// This method returns PRE_HEAP if \c item has never been in the |
400 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
401 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
401 /// otherwise. In the latter case it is possible that \c item will |
402 /// otherwise. In the latter case it is possible that \c item will |
402 /// get back to the heap again. |
403 /// get back to the heap again. |
403 /// \param i The item. |
404 /// \param i The item. |
404 state_enum state(const Item &i) const { |
405 State state(const Item &i) const { |
405 int s = iim[i]; |
406 int s = iim[i]; |
406 if( s >= 0 ) s = 0; |
407 if( s >= 0 ) s = 0; |
407 return state_enum(s); |
408 return State(s); |
408 } |
409 } |
409 |
410 |
410 /// \brief Sets the state of the \c item in the heap. |
411 /// \brief Sets the state of the \c item in the heap. |
411 /// |
412 /// |
412 /// Sets the state of the \c item in the heap. It can be used to |
413 /// Sets the state of the \c item in the heap. It can be used to |
413 /// manually clear the heap when it is important to achive the |
414 /// manually clear the heap when it is important to achive the |
414 /// better time complexity. |
415 /// better time complexity. |
415 /// \param i The item. |
416 /// \param i The item. |
416 /// \param st The state. It should not be \c IN_HEAP. |
417 /// \param st The state. It should not be \c IN_HEAP. |
417 void state(const Item& i, state_enum st) { |
418 void state(const Item& i, State st) { |
418 switch (st) { |
419 switch (st) { |
419 case POST_HEAP: |
420 case POST_HEAP: |
420 case PRE_HEAP: |
421 case PRE_HEAP: |
421 if (state(i) == IN_HEAP) { |
422 if (state(i) == IN_HEAP) { |
422 erase(i); |
423 erase(i); |