lemon: comparison lemon/radix

equal deleted inserted replaced

-:bd56ac0cab91
+:55c3a4d19528
 #ifndef LEMON_RADIX_HEAP_H
 #define LEMON_RADIX_HEAP_H
 ///\ingroup auxdat
 ///\file
-///\brief Radix Heap implementation.
+///\brief Radix heap implementation.
 #include <vector>
 #include <lemon/error.h>
 namespace lemon {
-/// \ingroup auxdata
+/// \ingroup auxdat
 ///
-/// \brief A Radix Heap implementation.
+/// \brief Radix heap data structure.
 ///
-/// This class implements the \e radix \e heap data structure. A \e heap
+/// This class implements the \e radix \e heap data structure.
-/// is a data structure for storing items with specified values called \e
+/// It practically conforms to the \ref concepts::Heap "heap concept",
-/// priorities in such a way that finding the item with minimum priority is
+/// but it has some limitations due its special implementation.
-/// efficient. This heap type can store only items with \e int priority.
+/// The type of the priorities must be \c int and the priority of an
-/// In a heap one can change the priority of an item, add or erase an
+/// item cannot be decreased under the priority of the last removed item.
-/// item, but the priority cannot be decreased under the last removed
-/// item's priority.
 ///
-/// \param IM A read and writable Item int map, used internally
+/// \tparam IM A read-writable item map with \c int values, used
-/// to handle the cross references.
+/// internally to handle the cross references.
-///
-/// \see BinHeap
-/// \see Dijkstra
 template <typename IM>
 class RadixHeap {
 public:
-typedef typename IM::Key Item;
+/// Type of the item-int map.
+typedef IM ItemIntMap;
+/// Type of the priorities.
 typedef int Prio;
-typedef IM ItemIntMap;
+/// Type of the items stored in the heap.
+typedef typename ItemIntMap::Key Item;
 /// \brief Exception thrown by RadixHeap.
 ///
-/// This Exception is thrown when a smaller priority
+/// This exception is thrown when an item is inserted into a
-/// is inserted into the \e RadixHeap then the last time erased.
+/// RadixHeap with a priority smaller than the last erased one.
 /// \see RadixHeap
 class UnderFlowPriorityError : public Exception {
 public:
 virtual const char* what() const throw() {
 return "lemon::RadixHeap::UnderFlowPriorityError";
 }
 };
-/// \brief Type to represent the items states.
+/// \brief Type to represent the states of the items.
 ///
-/// Each Item element have a state associated to it. It may be "in heap",
+/// Each item has a state associated to it. It can be "in heap",
-/// "pre heap" or "post heap". The latter two are indifferent from the
+/// "pre-heap" or "post-heap". The latter two are indifferent from the
 /// heap's point of view, but may be useful to the user.
 ///
-/// The ItemIntMap \e should be initialized in such way that it maps
+/// The item-int map must be initialized in such way that it assigns
-/// PRE_HEAP (-1) to any element to be put in the heap...
+/// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 enum State {
-IN_HEAP = 0,
+IN_HEAP = 0,    ///< = 0.
-PRE_HEAP = -1,
+PRE_HEAP = -1,  ///< = -1.
-POST_HEAP = -2
+POST_HEAP = -2  ///< = -2.
 };
 private:
 struct RadixItem {
 std::vector<RadixItem> data;
 std::vector<RadixBox> boxes;
 ItemIntMap &_iim;
 public:
-/// \brief The constructor.
-///
+/// \brief Constructor.
-/// The constructor.
+///
-///
+/// Constructor.
-/// \param map It should be given to the constructor, since it is used
+/// \param map A map that assigns \c int values to the items.
-/// internally to handle the cross references. The value of the map
+/// It is used internally to handle the cross references.
-/// should be PRE_HEAP (-1) for each element.
+/// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
-///
+/// \param minimum The initial minimum value of the heap.
-/// \param minimal The initial minimal value of the heap.
+/// \param capacity The initial capacity of the heap.
-/// \param capacity It determines the initial capacity of the heap.
+RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
-RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
+: _iim(map)
-: _iim(map) {
+{
-boxes.push_back(RadixBox(minimal, 1));
+boxes.push_back(RadixBox(minimum, 1));
-boxes.push_back(RadixBox(minimal + 1, 1));
+boxes.push_back(RadixBox(minimum + 1, 1));
-while (lower(boxes.size() - 1, capacity + minimal - 1)) {
+while (lower(boxes.size() - 1, capacity + minimum - 1)) {
 extend();
 }
 }
-/// The number of items stored in the heap.
+/// \brief The number of items stored in the heap.
 ///
-/// \brief Returns the number of items stored in the heap.
+/// This function returns the number of items stored in the heap.
 int size() const { return data.size(); }
-/// \brief Checks if the heap stores no items.
-///
+/// \brief Check if the heap is empty.
-/// Returns \c true if and only if the heap stores no items.
+///
+/// This function returns \c true if the heap is empty.
 bool empty() const { return data.empty(); }
-/// \brief Make empty this heap.
+/// \brief Make the heap empty.
 ///
-/// Make empty this heap. It does not change the cross reference
+/// This functon makes the heap empty.
-/// map.  If you want to reuse a heap what is not surely empty you
+/// It does not change the cross reference map. If you want to reuse
-/// should first clear the heap and after that you should set the
+/// a heap that is not surely empty, you should first clear it and
-/// cross reference map for each item to \c PRE_HEAP.
+/// then you should set the cross reference map to \c PRE_HEAP
-void clear(int minimal = 0, int capacity = 0) {
+/// for each item.
+/// \param minimum The minimum value of the heap.
+/// \param capacity The capacity of the heap.
+void clear(int minimum = 0, int capacity = 0) {
 data.clear(); boxes.clear();
-boxes.push_back(RadixBox(minimal, 1));
+boxes.push_back(RadixBox(minimum, 1));
-boxes.push_back(RadixBox(minimal + 1, 1));
+boxes.push_back(RadixBox(minimum + 1, 1));
-while (lower(boxes.size() - 1, capacity + minimal - 1)) {
+while (lower(boxes.size() - 1, capacity + minimum - 1)) {
 extend();
 }
 }
 private:
 bool lower(int box, Prio pr) {
 return pr >= boxes[box].min + boxes[box].size;
 }
-/// \brief Remove item from the box list.
+// Remove item from the box list
 void remove(int index) {
 if (data[index].prev >= 0) {
 data[data[index].prev].next = data[index].next;
 } else {
 boxes[data[index].box].first = data[index].next;
 if (data[index].next >= 0) {
 data[data[index].next].prev = data[index].prev;
 }
 }
-/// \brief Insert item into the box list.
+// Insert item into the box list
 void insert(int box, int index) {
 if (boxes[box].first == -1) {
 boxes[box].first = index;
 data[index].next = data[index].prev = -1;
 } else {
 boxes[box].first = index;
 }
 data[index].box = box;
 }
-/// \brief Add a new box to the box list.
+// Add a new box to the box list
 void extend() {
 int min = boxes.back().min + boxes.back().size;
 int bs = 2 * boxes.back().size;
 boxes.push_back(RadixBox(min, bs));
 }
-/// \brief Move an item up into the proper box.
+// Move an item up into the proper box.
 void bubble_up(int index) {
 if (!lower(data[index].box, data[index].prio)) return;
 remove(index);
 int box = findUp(data[index].box, data[index].prio);
 insert(box, index);
 }
-/// \brief Find up the proper box for the item with the given prio.
+// Find up the proper box for the item with the given priority
 int findUp(int start, int pr) {
 while (lower(start, pr)) {
 if (++start == int(boxes.size())) {
 extend();
 }
 }
 return start;
 }
-/// \brief Move an item down into the proper box.
+// Move an item down into the proper box
 void bubble_down(int index) {
 if (!upper(data[index].box, data[index].prio)) return;
 remove(index);
 int box = findDown(data[index].box, data[index].prio);
 insert(box, index);
 }
-/// \brief Find up the proper box for the item with the given prio.
+// Find down the proper box for the item with the given priority
 int findDown(int start, int pr) {
 while (upper(start, pr)) {
 if (--start < 0) throw UnderFlowPriorityError();
 }
 return start;
 }
-/// \brief Find the first not empty box.
+// Find the first non-empty box
 int findFirst() {
 int first = 0;
 while (boxes[first].first == -1) ++first;
 return first;
 }
-/// \brief Gives back the minimal prio of the box.
+// Gives back the minimum priority of the given box
 int minValue(int box) {
 int min = data[boxes[box].first].prio;
 for (int k = boxes[box].first; k != -1; k = data[k].next) {
 if (data[k].prio < min) min = data[k].prio;
 }
 return min;
 }
-/// \brief Rearrange the items of the heap and makes the
+// Rearrange the items of the heap and make the first box non-empty
-/// first box not empty.
 void moveDown() {
 int box = findFirst();
 if (box == 0) return;
 int min = minValue(box);
 for (int i = 0; i <= box; ++i) {
 public:
 /// \brief Insert an item into the heap with the given priority.
 ///
-/// Adds \c i to the heap with priority \c p.
+/// This function inserts the given item into the heap with the
+/// given priority.
 /// \param i The item to insert.
 /// \param p The priority of the item.
+/// \pre \e i must not be stored in the heap.
+/// \warning This method may throw an \c UnderFlowPriorityException.
 void push(const Item &i, const Prio &p) {
 int n = data.size();
 _iim.set(i, n);
 data.push_back(RadixItem(i, p));
 while (lower(boxes.size() - 1, p)) {
 }
 int box = findDown(boxes.size() - 1, p);
 insert(box, n);
 }
-/// \brief Returns the item with minimum priority.
+/// \brief Return the item having minimum priority.
 ///
-/// This method returns the item with minimum priority.
+/// This function returns the item having minimum priority.
-/// \pre The heap must be nonempty.
+/// \pre The heap must be non-empty.
 Item top() const {
 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
 return data[boxes[0].first].item;
 }
-/// \brief Returns the minimum priority.
+/// \brief The minimum priority.
 ///
-/// It returns the minimum priority.
+/// This function returns the minimum priority.
-/// \pre The heap must be nonempty.
+/// \pre The heap must be non-empty.
 Prio prio() const {
 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
 return data[boxes[0].first].prio;
 }
-/// \brief Deletes the item with minimum priority.
+/// \brief Remove the item having minimum priority.
 ///
-/// This method deletes the item with minimum priority.
+/// This function removes the item having minimum priority.
 /// \pre The heap must be non-empty.
 void pop() {
 moveDown();
 int index = boxes[0].first;
 _iim[data[index].item] = POST_HEAP;
 remove(index);
 relocate_last(index);
 }
-/// \brief Deletes \c i from the heap.
+/// \brief Remove the given item from the heap.
 ///
-/// This method deletes item \c i from the heap, if \c i was
+/// This function removes the given item from the heap if it is
-/// already stored in the heap.
+/// already stored.
-/// \param i The item to erase.
+/// \param i The item to delete.
+/// \pre \e i must be in the heap.
 void erase(const Item &i) {
 int index = _iim[i];
 _iim[i] = POST_HEAP;
 remove(index);
 relocate_last(index);
 }
-/// \brief Returns the priority of \c i.
+/// \brief The priority of the given item.
 ///
-/// This function returns the priority of item \c i.
+/// This function returns the priority of the given item.
-/// \pre \c i must be in the heap.
+/// \param i The item.
-/// \param i The item.
+/// \pre \e i must be in the heap.
 Prio operator[](const Item &i) const {
 int idx = _iim[i];
 return data[idx].prio;
 }
-/// \brief \c i gets to the heap with priority \c p independently
+/// \brief Set the priority of an item or insert it, if it is
-/// if \c i was already there.
+/// not stored in the heap.
 ///
-/// This method calls \ref push(\c i, \c p) if \c i is not stored
+/// This method sets the priority of the given item if it is
-/// in the heap and sets the priority of \c i to \c p otherwise.
+/// already stored in the heap. Otherwise it inserts the given
-/// It may throw an \e UnderFlowPriorityException.
+/// item into the heap with the given priority.
 /// \param i The item.
 /// \param p The priority.
+/// \pre \e i must be in the heap.
+/// \warning This method may throw an \c UnderFlowPriorityException.
 void set(const Item &i, const Prio &p) {
 int idx = _iim[i];
 if( idx < 0 ) {
 push(i, p);
 }
 data[idx].prio = p;
 bubble_down(idx);
 }
 }
+/// \brief Decrease the priority of an item to the given value.
-/// \brief Decreases the priority of \c i to \c p.
+///
-///
+/// This function decreases the priority of an item to the given value.
-/// This method decreases the priority of item \c i to \c p.
-/// \pre \c i must be stored in the heap with priority at least \c p, and
-/// \c should be greater or equal to the last removed item's priority.
 /// \param i The item.
 /// \param p The priority.
+/// \pre \e i must be stored in the heap with priority at least \e p.
+/// \warning This method may throw an \c UnderFlowPriorityException.
 void decrease(const Item &i, const Prio &p) {
 int idx = _iim[i];
 data[idx].prio = p;
 bubble_down(idx);
 }
-/// \brief Increases the priority of \c i to \c p.
+/// \brief Increase the priority of an item to the given value.
 ///
-/// This method sets the priority of item \c i to \c p.
+/// This function increases the priority of an item to the given value.
-/// \pre \c i must be stored in the heap with priority at most \c p
 /// \param i The item.
 /// \param p The priority.
+/// \pre \e i must be stored in the heap with priority at most \e p.
 void increase(const Item &i, const Prio &p) {
 int idx = _iim[i];
 data[idx].prio = p;
 bubble_up(idx);
 }
-/// \brief Returns if \c item is in, has already been in, or has
+/// \brief Return the state of an item.
-/// never been in the heap.
+///
-///
+/// This method returns \c PRE_HEAP if the given item has never
-/// This method returns PRE_HEAP if \c item has never been in the
+/// been in the heap, \c IN_HEAP if it is in the heap at the moment,
-/// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+/// and \c POST_HEAP otherwise.
-/// otherwise. In the latter case it is possible that \c item will
+/// In the latter case it is possible that the item will get back
-/// get back to the heap again.
+/// to the heap again.
 /// \param i The item.
 State state(const Item &i) const {
 int s = _iim[i];
 if( s >= 0 ) s = 0;
 return State(s);
 }
-/// \brief Sets the state of the \c item in the heap.
+/// \brief Set the state of an item in the heap.
 ///
-/// Sets the state of the \c item in the heap. It can be used to
+/// This function sets the state of the given item in the heap.
-/// manually clear the heap when it is important to achive the
+/// It can be used to manually clear the heap when it is important
-/// better time complexity.
+/// to achive better time complexity.
 /// \param i The item.
 /// \param st The state. It should not be \c IN_HEAP.
 void state(const Item& i, State st) {
 switch (st) {
 case POST_HEAP:

changeset 756	0747f332c478
parent 730	9f529abcaebf
child 757	f1fe0ddad6f7