lemon/radix_heap.h
changeset 692 33f417de9e70
parent 681 532697c9fa53
child 709 0747f332c478
equal deleted inserted replaced
0:5c7138624722 1:bd56ac0cab91
    39   /// efficient. This heap type can store only items with \e int priority.
    39   /// efficient. This heap type can store only items with \e int priority.
    40   /// In a heap one can change the priority of an item, add or erase an
    40   /// In a heap one can change the priority of an item, add or erase an
    41   /// item, but the priority cannot be decreased under the last removed
    41   /// item, but the priority cannot be decreased under the last removed
    42   /// item's priority.
    42   /// item's priority.
    43   ///
    43   ///
    44   /// \param _ItemIntMap A read and writable Item int map, used internally
    44   /// \param IM A read and writable Item int map, used internally
    45   /// to handle the cross references.
    45   /// to handle the cross references.
    46   ///
    46   ///
    47   /// \see BinHeap
    47   /// \see BinHeap
    48   /// \see Dijkstra
    48   /// \see Dijkstra
    49   template <typename _ItemIntMap>
    49   template <typename IM>
    50   class RadixHeap {
    50   class RadixHeap {
    51 
    51 
    52   public:
    52   public:
    53     typedef typename _ItemIntMap::Key Item;
    53     typedef typename IM::Key Item;
    54     typedef int Prio;
    54     typedef int Prio;
    55     typedef _ItemIntMap ItemIntMap;
    55     typedef IM ItemIntMap;
    56 
    56 
    57     /// \brief Exception thrown by RadixHeap.
    57     /// \brief Exception thrown by RadixHeap.
    58     ///
    58     ///
    59     /// This Exception is thrown when a smaller priority
    59     /// This Exception is thrown when a smaller priority
    60     /// is inserted into the \e RadixHeap then the last time erased.
    60     /// is inserted into the \e RadixHeap then the last time erased.
    97     };
    97     };
    98 
    98 
    99     std::vector<RadixItem> data;
    99     std::vector<RadixItem> data;
   100     std::vector<RadixBox> boxes;
   100     std::vector<RadixBox> boxes;
   101 
   101 
   102     ItemIntMap &iim;
   102     ItemIntMap &_iim;
   103 
   103 
   104 
   104 
   105   public:
   105   public:
   106     /// \brief The constructor.
   106     /// \brief The constructor.
   107     ///
   107     ///
   108     /// The constructor.
   108     /// The constructor.
   109     ///
   109     ///
   110     /// \param _iim It should be given to the constructor, since it is used
   110     /// \param map It should be given to the constructor, since it is used
   111     /// internally to handle the cross references. The value of the map
   111     /// internally to handle the cross references. The value of the map
   112     /// should be PRE_HEAP (-1) for each element.
   112     /// should be PRE_HEAP (-1) for each element.
   113     ///
   113     ///
   114     /// \param minimal The initial minimal value of the heap.
   114     /// \param minimal The initial minimal value of the heap.
   115     /// \param capacity It determines the initial capacity of the heap.
   115     /// \param capacity It determines the initial capacity of the heap.
   116     RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
   116     RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
   117       : iim(_iim) {
   117       : _iim(map) {
   118       boxes.push_back(RadixBox(minimal, 1));
   118       boxes.push_back(RadixBox(minimal, 1));
   119       boxes.push_back(RadixBox(minimal + 1, 1));
   119       boxes.push_back(RadixBox(minimal + 1, 1));
   120       while (lower(boxes.size() - 1, capacity + minimal - 1)) {
   120       while (lower(boxes.size() - 1, capacity + minimal - 1)) {
   121         extend();
   121         extend();
   122       }
   122       }
   266           boxes[data[index].box].first = index;
   266           boxes[data[index].box].first = index;
   267         }
   267         }
   268         if (data[index].next != -1) {
   268         if (data[index].next != -1) {
   269           data[data[index].next].prev = index;
   269           data[data[index].next].prev = index;
   270         }
   270         }
   271         iim[data[index].item] = index;
   271         _iim[data[index].item] = index;
   272       }
   272       }
   273       data.pop_back();
   273       data.pop_back();
   274     }
   274     }
   275 
   275 
   276   public:
   276   public:
   280     /// Adds \c i to the heap with priority \c p.
   280     /// Adds \c i to the heap with priority \c p.
   281     /// \param i The item to insert.
   281     /// \param i The item to insert.
   282     /// \param p The priority of the item.
   282     /// \param p The priority of the item.
   283     void push(const Item &i, const Prio &p) {
   283     void push(const Item &i, const Prio &p) {
   284       int n = data.size();
   284       int n = data.size();
   285       iim.set(i, n);
   285       _iim.set(i, n);
   286       data.push_back(RadixItem(i, p));
   286       data.push_back(RadixItem(i, p));
   287       while (lower(boxes.size() - 1, p)) {
   287       while (lower(boxes.size() - 1, p)) {
   288         extend();
   288         extend();
   289       }
   289       }
   290       int box = findDown(boxes.size() - 1, p);
   290       int box = findDown(boxes.size() - 1, p);
   314     /// This method deletes the item with minimum priority.
   314     /// This method deletes the item with minimum priority.
   315     /// \pre The heap must be non-empty.
   315     /// \pre The heap must be non-empty.
   316     void pop() {
   316     void pop() {
   317       moveDown();
   317       moveDown();
   318       int index = boxes[0].first;
   318       int index = boxes[0].first;
   319       iim[data[index].item] = POST_HEAP;
   319       _iim[data[index].item] = POST_HEAP;
   320       remove(index);
   320       remove(index);
   321       relocate_last(index);
   321       relocate_last(index);
   322     }
   322     }
   323 
   323 
   324     /// \brief Deletes \c i from the heap.
   324     /// \brief Deletes \c i from the heap.
   325     ///
   325     ///
   326     /// This method deletes item \c i from the heap, if \c i was
   326     /// This method deletes item \c i from the heap, if \c i was
   327     /// already stored in the heap.
   327     /// already stored in the heap.
   328     /// \param i The item to erase.
   328     /// \param i The item to erase.
   329     void erase(const Item &i) {
   329     void erase(const Item &i) {
   330       int index = iim[i];
   330       int index = _iim[i];
   331       iim[i] = POST_HEAP;
   331       _iim[i] = POST_HEAP;
   332       remove(index);
   332       remove(index);
   333       relocate_last(index);
   333       relocate_last(index);
   334    }
   334    }
   335 
   335 
   336     /// \brief Returns the priority of \c i.
   336     /// \brief Returns the priority of \c i.
   337     ///
   337     ///
   338     /// This function returns the priority of item \c i.
   338     /// This function returns the priority of item \c i.
   339     /// \pre \c i must be in the heap.
   339     /// \pre \c i must be in the heap.
   340     /// \param i The item.
   340     /// \param i The item.
   341     Prio operator[](const Item &i) const {
   341     Prio operator[](const Item &i) const {
   342       int idx = iim[i];
   342       int idx = _iim[i];
   343       return data[idx].prio;
   343       return data[idx].prio;
   344     }
   344     }
   345 
   345 
   346     /// \brief \c i gets to the heap with priority \c p independently
   346     /// \brief \c i gets to the heap with priority \c p independently
   347     /// if \c i was already there.
   347     /// if \c i was already there.
   350     /// in the heap and sets the priority of \c i to \c p otherwise.
   350     /// in the heap and sets the priority of \c i to \c p otherwise.
   351     /// It may throw an \e UnderFlowPriorityException.
   351     /// It may throw an \e UnderFlowPriorityException.
   352     /// \param i The item.
   352     /// \param i The item.
   353     /// \param p The priority.
   353     /// \param p The priority.
   354     void set(const Item &i, const Prio &p) {
   354     void set(const Item &i, const Prio &p) {
   355       int idx = iim[i];
   355       int idx = _iim[i];
   356       if( idx < 0 ) {
   356       if( idx < 0 ) {
   357         push(i, p);
   357         push(i, p);
   358       }
   358       }
   359       else if( p >= data[idx].prio ) {
   359       else if( p >= data[idx].prio ) {
   360         data[idx].prio = p;
   360         data[idx].prio = p;
   372     /// \pre \c i must be stored in the heap with priority at least \c p, and
   372     /// \pre \c i must be stored in the heap with priority at least \c p, and
   373     /// \c should be greater or equal to the last removed item's priority.
   373     /// \c should be greater or equal to the last removed item's priority.
   374     /// \param i The item.
   374     /// \param i The item.
   375     /// \param p The priority.
   375     /// \param p The priority.
   376     void decrease(const Item &i, const Prio &p) {
   376     void decrease(const Item &i, const Prio &p) {
   377       int idx = iim[i];
   377       int idx = _iim[i];
   378       data[idx].prio = p;
   378       data[idx].prio = p;
   379       bubble_down(idx);
   379       bubble_down(idx);
   380     }
   380     }
   381 
   381 
   382     /// \brief Increases the priority of \c i to \c p.
   382     /// \brief Increases the priority of \c i to \c p.
   384     /// This method sets the priority of item \c i to \c p.
   384     /// This method sets the priority of item \c i to \c p.
   385     /// \pre \c i must be stored in the heap with priority at most \c p
   385     /// \pre \c i must be stored in the heap with priority at most \c p
   386     /// \param i The item.
   386     /// \param i The item.
   387     /// \param p The priority.
   387     /// \param p The priority.
   388     void increase(const Item &i, const Prio &p) {
   388     void increase(const Item &i, const Prio &p) {
   389       int idx = iim[i];
   389       int idx = _iim[i];
   390       data[idx].prio = p;
   390       data[idx].prio = p;
   391       bubble_up(idx);
   391       bubble_up(idx);
   392     }
   392     }
   393 
   393 
   394     /// \brief Returns if \c item is in, has already been in, or has
   394     /// \brief Returns if \c item is in, has already been in, or has
   398     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   398     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   399     /// otherwise. In the latter case it is possible that \c item will
   399     /// otherwise. In the latter case it is possible that \c item will
   400     /// get back to the heap again.
   400     /// get back to the heap again.
   401     /// \param i The item.
   401     /// \param i The item.
   402     State state(const Item &i) const {
   402     State state(const Item &i) const {
   403       int s = iim[i];
   403       int s = _iim[i];
   404       if( s >= 0 ) s = 0;
   404       if( s >= 0 ) s = 0;
   405       return State(s);
   405       return State(s);
   406     }
   406     }
   407 
   407 
   408     /// \brief Sets the state of the \c item in the heap.
   408     /// \brief Sets the state of the \c item in the heap.
   417       case POST_HEAP:
   417       case POST_HEAP:
   418       case PRE_HEAP:
   418       case PRE_HEAP:
   419         if (state(i) == IN_HEAP) {
   419         if (state(i) == IN_HEAP) {
   420           erase(i);
   420           erase(i);
   421         }
   421         }
   422         iim[i] = st;
   422         _iim[i] = st;
   423         break;
   423         break;
   424       case IN_HEAP:
   424       case IN_HEAP:
   425         break;
   425         break;
   426       }
   426       }
   427     }
   427     }