lemon-main: comparison lemon/radix

equal deleted inserted replaced

-:5c7138624722
+:bd56ac0cab91
 /// efficient. This heap type can store only items with \e int priority.
 /// In a heap one can change the priority of an item, add or erase an
 /// item, but the priority cannot be decreased under the last removed
 /// item's priority.
 ///
-/// \param _ItemIntMap A read and writable Item int map, used internally
+/// \param IM A read and writable Item int map, used internally
 /// to handle the cross references.
 ///
 /// \see BinHeap
 /// \see Dijkstra
-template <typename _ItemIntMap>
+template <typename IM>
 class RadixHeap {
 public:
-typedef typename _ItemIntMap::Key Item;
+typedef typename IM::Key Item;
 typedef int Prio;
-typedef _ItemIntMap ItemIntMap;
+typedef IM ItemIntMap;
 /// \brief Exception thrown by RadixHeap.
 ///
 /// This Exception is thrown when a smaller priority
 /// is inserted into the \e RadixHeap then the last time erased.
 };
 std::vector<RadixItem> data;
 std::vector<RadixBox> boxes;
-ItemIntMap &iim;
+ItemIntMap &_iim;
 public:
 /// \brief The constructor.
 ///
 /// The constructor.
 ///
-/// \param _iim It should be given to the constructor, since it is used
+/// \param map It should be given to the constructor, since it is used
 /// internally to handle the cross references. The value of the map
 /// should be PRE_HEAP (-1) for each element.
 ///
 /// \param minimal The initial minimal value of the heap.
 /// \param capacity It determines the initial capacity of the heap.
-RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
+RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
-: iim(_iim) {
+: _iim(map) {
 boxes.push_back(RadixBox(minimal, 1));
 boxes.push_back(RadixBox(minimal + 1, 1));
 while (lower(boxes.size() - 1, capacity + minimal - 1)) {
 extend();
 }
 boxes[data[index].box].first = index;
 }
 if (data[index].next != -1) {
 data[data[index].next].prev = index;
 }
-iim[data[index].item] = index;
+_iim[data[index].item] = index;
 }
 data.pop_back();
 }
 public:
 /// Adds \c i to the heap with priority \c p.
 /// \param i The item to insert.
 /// \param p The priority of the item.
 void push(const Item &i, const Prio &p) {
 int n = data.size();
-iim.set(i, n);
+_iim.set(i, n);
 data.push_back(RadixItem(i, p));
 while (lower(boxes.size() - 1, p)) {
 extend();
 }
 int box = findDown(boxes.size() - 1, p);
 /// This method deletes the item with minimum priority.
 /// \pre The heap must be non-empty.
 void pop() {
 moveDown();
 int index = boxes[0].first;
-iim[data[index].item] = POST_HEAP;
+_iim[data[index].item] = POST_HEAP;
 remove(index);
 relocate_last(index);
 }
 /// \brief Deletes \c i from the heap.
 ///
 /// This method deletes item \c i from the heap, if \c i was
 /// already stored in the heap.
 /// \param i The item to erase.
 void erase(const Item &i) {
-int index = iim[i];
+int index = _iim[i];
-iim[i] = POST_HEAP;
+_iim[i] = POST_HEAP;
 remove(index);
 relocate_last(index);
 }
 /// \brief Returns the priority of \c i.
 ///
 /// This function returns the priority of item \c i.
 /// \pre \c i must be in the heap.
 /// \param i The item.
 Prio operator[](const Item &i) const {
-int idx = iim[i];
+int idx = _iim[i];
 return data[idx].prio;
 }
 /// \brief \c i gets to the heap with priority \c p independently
 /// if \c i was already there.
 /// in the heap and sets the priority of \c i to \c p otherwise.
 /// It may throw an \e UnderFlowPriorityException.
 /// \param i The item.
 /// \param p The priority.
 void set(const Item &i, const Prio &p) {
-int idx = iim[i];
+int idx = _iim[i];
 if( idx < 0 ) {
 push(i, p);
 }
 else if( p >= data[idx].prio ) {
 data[idx].prio = 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.
 void decrease(const Item &i, const Prio &p) {
-int idx = iim[i];
+int idx = _iim[i];
 data[idx].prio = p;
 bubble_down(idx);
 }
 /// \brief Increases the priority of \c i to \c p.
 /// This method sets the priority of item \c i to \c p.
 /// \pre \c i must be stored in the heap with priority at most \c p
 /// \param i The item.
 /// \param p The priority.
 void increase(const Item &i, const Prio &p) {
-int idx = iim[i];
+int idx = _iim[i];
 data[idx].prio = p;
 bubble_up(idx);
 }
 /// \brief Returns if \c item is in, has already been in, or has
 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
 /// otherwise. In the latter case it is possible that \c item will
 /// get back to the heap again.
 /// \param i The item.
 State state(const Item &i) const {
-int s = iim[i];
+int s = _iim[i];
 if( s >= 0 ) s = 0;
 return State(s);
 }
 /// \brief Sets the state of the \c item in the heap.
 case POST_HEAP:
 case PRE_HEAP:
 if (state(i) == IN_HEAP) {
 erase(i);
 }
-iim[i] = st;
+_iim[i] = st;
 break;
 case IN_HEAP:
 break;
 }
 }

changeset 740	819ca5b50de0
parent 681	532697c9fa53
child 709	0747f332c478