lemon/radix_heap.h
changeset 788 c92296660262
parent 710 f1fe0ddad6f7
equal deleted inserted replaced
3:311de133feb1 4:fddcbf50454d
    56     /// \brief Exception thrown by RadixHeap.
    56     /// \brief Exception thrown by RadixHeap.
    57     ///
    57     ///
    58     /// This exception is thrown when an item is inserted into a
    58     /// This exception is thrown when an item is inserted into a
    59     /// RadixHeap with a priority smaller than the last erased one.
    59     /// RadixHeap with a priority smaller than the last erased one.
    60     /// \see RadixHeap
    60     /// \see RadixHeap
    61     class UnderFlowPriorityError : public Exception {
    61     class PriorityUnderflowError : public Exception {
    62     public:
    62     public:
    63       virtual const char* what() const throw() {
    63       virtual const char* what() const throw() {
    64         return "lemon::RadixHeap::UnderFlowPriorityError";
    64         return "lemon::RadixHeap::PriorityUnderflowError";
    65       }
    65       }
    66     };
    66     };
    67 
    67 
    68     /// \brief Type to represent the states of the items.
    68     /// \brief Type to represent the states of the items.
    69     ///
    69     ///
    92       int first;
    92       int first;
    93       int min, size;
    93       int min, size;
    94       RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
    94       RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
    95     };
    95     };
    96 
    96 
    97     std::vector<RadixItem> data;
    97     std::vector<RadixItem> _data;
    98     std::vector<RadixBox> boxes;
    98     std::vector<RadixBox> _boxes;
    99 
    99 
   100     ItemIntMap &_iim;
   100     ItemIntMap &_iim;
   101 
   101 
   102   public:
   102   public:
   103 
   103 
   110     /// \param minimum The initial minimum value of the heap.
   110     /// \param minimum The initial minimum value of the heap.
   111     /// \param capacity The initial capacity of the heap.
   111     /// \param capacity The initial capacity of the heap.
   112     RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
   112     RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
   113       : _iim(map)
   113       : _iim(map)
   114     {
   114     {
   115       boxes.push_back(RadixBox(minimum, 1));
   115       _boxes.push_back(RadixBox(minimum, 1));
   116       boxes.push_back(RadixBox(minimum + 1, 1));
   116       _boxes.push_back(RadixBox(minimum + 1, 1));
   117       while (lower(boxes.size() - 1, capacity + minimum - 1)) {
   117       while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
   118         extend();
   118         extend();
   119       }
   119       }
   120     }
   120     }
   121 
   121 
   122     /// \brief The number of items stored in the heap.
   122     /// \brief The number of items stored in the heap.
   123     ///
   123     ///
   124     /// This function returns the number of items stored in the heap.
   124     /// This function returns the number of items stored in the heap.
   125     int size() const { return data.size(); }
   125     int size() const { return _data.size(); }
   126 
   126 
   127     /// \brief Check if the heap is empty.
   127     /// \brief Check if the heap is empty.
   128     ///
   128     ///
   129     /// This function returns \c true if the heap is empty.
   129     /// This function returns \c true if the heap is empty.
   130     bool empty() const { return data.empty(); }
   130     bool empty() const { return _data.empty(); }
   131 
   131 
   132     /// \brief Make the heap empty.
   132     /// \brief Make the heap empty.
   133     ///
   133     ///
   134     /// This functon makes the heap empty.
   134     /// This functon makes the heap empty.
   135     /// It does not change the cross reference map. If you want to reuse
   135     /// It does not change the cross reference map. If you want to reuse
   137     /// then you should set the cross reference map to \c PRE_HEAP
   137     /// then you should set the cross reference map to \c PRE_HEAP
   138     /// for each item.
   138     /// for each item.
   139     /// \param minimum The minimum value of the heap.
   139     /// \param minimum The minimum value of the heap.
   140     /// \param capacity The capacity of the heap.
   140     /// \param capacity The capacity of the heap.
   141     void clear(int minimum = 0, int capacity = 0) {
   141     void clear(int minimum = 0, int capacity = 0) {
   142       data.clear(); boxes.clear();
   142       _data.clear(); _boxes.clear();
   143       boxes.push_back(RadixBox(minimum, 1));
   143       _boxes.push_back(RadixBox(minimum, 1));
   144       boxes.push_back(RadixBox(minimum + 1, 1));
   144       _boxes.push_back(RadixBox(minimum + 1, 1));
   145       while (lower(boxes.size() - 1, capacity + minimum - 1)) {
   145       while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
   146         extend();
   146         extend();
   147       }
   147       }
   148     }
   148     }
   149 
   149 
   150   private:
   150   private:
   151 
   151 
   152     bool upper(int box, Prio pr) {
   152     bool upper(int box, Prio pr) {
   153       return pr < boxes[box].min;
   153       return pr < _boxes[box].min;
   154     }
   154     }
   155 
   155 
   156     bool lower(int box, Prio pr) {
   156     bool lower(int box, Prio pr) {
   157       return pr >= boxes[box].min + boxes[box].size;
   157       return pr >= _boxes[box].min + _boxes[box].size;
   158     }
   158     }
   159 
   159 
   160     // Remove item from the box list
   160     // Remove item from the box list
   161     void remove(int index) {
   161     void remove(int index) {
   162       if (data[index].prev >= 0) {
   162       if (_data[index].prev >= 0) {
   163         data[data[index].prev].next = data[index].next;
   163         _data[_data[index].prev].next = _data[index].next;
   164       } else {
   164       } else {
   165         boxes[data[index].box].first = data[index].next;
   165         _boxes[_data[index].box].first = _data[index].next;
   166       }
   166       }
   167       if (data[index].next >= 0) {
   167       if (_data[index].next >= 0) {
   168         data[data[index].next].prev = data[index].prev;
   168         _data[_data[index].next].prev = _data[index].prev;
   169       }
   169       }
   170     }
   170     }
   171 
   171 
   172     // Insert item into the box list
   172     // Insert item into the box list
   173     void insert(int box, int index) {
   173     void insert(int box, int index) {
   174       if (boxes[box].first == -1) {
   174       if (_boxes[box].first == -1) {
   175         boxes[box].first = index;
   175         _boxes[box].first = index;
   176         data[index].next = data[index].prev = -1;
   176         _data[index].next = _data[index].prev = -1;
   177       } else {
   177       } else {
   178         data[index].next = boxes[box].first;
   178         _data[index].next = _boxes[box].first;
   179         data[boxes[box].first].prev = index;
   179         _data[_boxes[box].first].prev = index;
   180         data[index].prev = -1;
   180         _data[index].prev = -1;
   181         boxes[box].first = index;
   181         _boxes[box].first = index;
   182       }
   182       }
   183       data[index].box = box;
   183       _data[index].box = box;
   184     }
   184     }
   185 
   185 
   186     // Add a new box to the box list
   186     // Add a new box to the box list
   187     void extend() {
   187     void extend() {
   188       int min = boxes.back().min + boxes.back().size;
   188       int min = _boxes.back().min + _boxes.back().size;
   189       int bs = 2 * boxes.back().size;
   189       int bs = 2 * _boxes.back().size;
   190       boxes.push_back(RadixBox(min, bs));
   190       _boxes.push_back(RadixBox(min, bs));
   191     }
   191     }
   192 
   192 
   193     // Move an item up into the proper box.
   193     // Move an item up into the proper box.
   194     void bubble_up(int index) {
   194     void bubbleUp(int index) {
   195       if (!lower(data[index].box, data[index].prio)) return;
   195       if (!lower(_data[index].box, _data[index].prio)) return;
   196       remove(index);
   196       remove(index);
   197       int box = findUp(data[index].box, data[index].prio);
   197       int box = findUp(_data[index].box, _data[index].prio);
   198       insert(box, index);
   198       insert(box, index);
   199     }
   199     }
   200 
   200 
   201     // Find up the proper box for the item with the given priority
   201     // Find up the proper box for the item with the given priority
   202     int findUp(int start, int pr) {
   202     int findUp(int start, int pr) {
   203       while (lower(start, pr)) {
   203       while (lower(start, pr)) {
   204         if (++start == int(boxes.size())) {
   204         if (++start == int(_boxes.size())) {
   205           extend();
   205           extend();
   206         }
   206         }
   207       }
   207       }
   208       return start;
   208       return start;
   209     }
   209     }
   210 
   210 
   211     // Move an item down into the proper box
   211     // Move an item down into the proper box
   212     void bubble_down(int index) {
   212     void bubbleDown(int index) {
   213       if (!upper(data[index].box, data[index].prio)) return;
   213       if (!upper(_data[index].box, _data[index].prio)) return;
   214       remove(index);
   214       remove(index);
   215       int box = findDown(data[index].box, data[index].prio);
   215       int box = findDown(_data[index].box, _data[index].prio);
   216       insert(box, index);
   216       insert(box, index);
   217     }
   217     }
   218 
   218 
   219     // Find down the proper box for the item with the given priority
   219     // Find down the proper box for the item with the given priority
   220     int findDown(int start, int pr) {
   220     int findDown(int start, int pr) {
   221       while (upper(start, pr)) {
   221       while (upper(start, pr)) {
   222         if (--start < 0) throw UnderFlowPriorityError();
   222         if (--start < 0) throw PriorityUnderflowError();
   223       }
   223       }
   224       return start;
   224       return start;
   225     }
   225     }
   226 
   226 
   227     // Find the first non-empty box
   227     // Find the first non-empty box
   228     int findFirst() {
   228     int findFirst() {
   229       int first = 0;
   229       int first = 0;
   230       while (boxes[first].first == -1) ++first;
   230       while (_boxes[first].first == -1) ++first;
   231       return first;
   231       return first;
   232     }
   232     }
   233 
   233 
   234     // Gives back the minimum priority of the given box
   234     // Gives back the minimum priority of the given box
   235     int minValue(int box) {
   235     int minValue(int box) {
   236       int min = data[boxes[box].first].prio;
   236       int min = _data[_boxes[box].first].prio;
   237       for (int k = boxes[box].first; k != -1; k = data[k].next) {
   237       for (int k = _boxes[box].first; k != -1; k = _data[k].next) {
   238         if (data[k].prio < min) min = data[k].prio;
   238         if (_data[k].prio < min) min = _data[k].prio;
   239       }
   239       }
   240       return min;
   240       return min;
   241     }
   241     }
   242 
   242 
   243     // Rearrange the items of the heap and make the first box non-empty
   243     // Rearrange the items of the heap and make the first box non-empty
   244     void moveDown() {
   244     void moveDown() {
   245       int box = findFirst();
   245       int box = findFirst();
   246       if (box == 0) return;
   246       if (box == 0) return;
   247       int min = minValue(box);
   247       int min = minValue(box);
   248       for (int i = 0; i <= box; ++i) {
   248       for (int i = 0; i <= box; ++i) {
   249         boxes[i].min = min;
   249         _boxes[i].min = min;
   250         min += boxes[i].size;
   250         min += _boxes[i].size;
   251       }
   251       }
   252       int curr = boxes[box].first, next;
   252       int curr = _boxes[box].first, next;
   253       while (curr != -1) {
   253       while (curr != -1) {
   254         next = data[curr].next;
   254         next = _data[curr].next;
   255         bubble_down(curr);
   255         bubbleDown(curr);
   256         curr = next;
   256         curr = next;
   257       }
   257       }
   258     }
   258     }
   259 
   259 
   260     void relocate_last(int index) {
   260     void relocateLast(int index) {
   261       if (index != int(data.size()) - 1) {
   261       if (index != int(_data.size()) - 1) {
   262         data[index] = data.back();
   262         _data[index] = _data.back();
   263         if (data[index].prev != -1) {
   263         if (_data[index].prev != -1) {
   264           data[data[index].prev].next = index;
   264           _data[_data[index].prev].next = index;
   265         } else {
   265         } else {
   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:
   277 
   277 
   278     /// \brief Insert an item into the heap with the given priority.
   278     /// \brief Insert an item into the heap with the given priority.
   282     /// \param i The item to insert.
   282     /// \param i The item to insert.
   283     /// \param p The priority of the item.
   283     /// \param p The priority of the item.
   284     /// \pre \e i must not be stored in the heap.
   284     /// \pre \e i must not be stored in the heap.
   285     /// \warning This method may throw an \c UnderFlowPriorityException.
   285     /// \warning This method may throw an \c UnderFlowPriorityException.
   286     void push(const Item &i, const Prio &p) {
   286     void push(const Item &i, const Prio &p) {
   287       int n = data.size();
   287       int n = _data.size();
   288       _iim.set(i, n);
   288       _iim.set(i, n);
   289       data.push_back(RadixItem(i, p));
   289       _data.push_back(RadixItem(i, p));
   290       while (lower(boxes.size() - 1, p)) {
   290       while (lower(_boxes.size() - 1, p)) {
   291         extend();
   291         extend();
   292       }
   292       }
   293       int box = findDown(boxes.size() - 1, p);
   293       int box = findDown(_boxes.size() - 1, p);
   294       insert(box, n);
   294       insert(box, n);
   295     }
   295     }
   296 
   296 
   297     /// \brief Return the item having minimum priority.
   297     /// \brief Return the item having minimum priority.
   298     ///
   298     ///
   299     /// This function returns the item having minimum priority.
   299     /// This function returns the item having minimum priority.
   300     /// \pre The heap must be non-empty.
   300     /// \pre The heap must be non-empty.
   301     Item top() const {
   301     Item top() const {
   302       const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
   302       const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
   303       return data[boxes[0].first].item;
   303       return _data[_boxes[0].first].item;
   304     }
   304     }
   305 
   305 
   306     /// \brief The minimum priority.
   306     /// \brief The minimum priority.
   307     ///
   307     ///
   308     /// This function returns the minimum priority.
   308     /// This function returns the minimum priority.
   309     /// \pre The heap must be non-empty.
   309     /// \pre The heap must be non-empty.
   310     Prio prio() const {
   310     Prio prio() const {
   311       const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
   311       const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
   312       return data[boxes[0].first].prio;
   312       return _data[_boxes[0].first].prio;
   313      }
   313      }
   314 
   314 
   315     /// \brief Remove the item having minimum priority.
   315     /// \brief Remove the item having minimum priority.
   316     ///
   316     ///
   317     /// This function removes the item having minimum priority.
   317     /// This function removes the item having minimum priority.
   318     /// \pre The heap must be non-empty.
   318     /// \pre The heap must be non-empty.
   319     void pop() {
   319     void pop() {
   320       moveDown();
   320       moveDown();
   321       int index = boxes[0].first;
   321       int index = _boxes[0].first;
   322       _iim[data[index].item] = POST_HEAP;
   322       _iim[_data[index].item] = POST_HEAP;
   323       remove(index);
   323       remove(index);
   324       relocate_last(index);
   324       relocateLast(index);
   325     }
   325     }
   326 
   326 
   327     /// \brief Remove the given item from the heap.
   327     /// \brief Remove the given item from the heap.
   328     ///
   328     ///
   329     /// This function removes the given item from the heap if it is
   329     /// This function removes the given item from the heap if it is
   332     /// \pre \e i must be in the heap.
   332     /// \pre \e i must be in the heap.
   333     void erase(const Item &i) {
   333     void erase(const Item &i) {
   334       int index = _iim[i];
   334       int index = _iim[i];
   335       _iim[i] = POST_HEAP;
   335       _iim[i] = POST_HEAP;
   336       remove(index);
   336       remove(index);
   337       relocate_last(index);
   337       relocateLast(index);
   338    }
   338    }
   339 
   339 
   340     /// \brief The priority of the given item.
   340     /// \brief The priority of the given item.
   341     ///
   341     ///
   342     /// This function returns the priority of the given item.
   342     /// This function returns the priority of the given item.
   343     /// \param i The item.
   343     /// \param i The item.
   344     /// \pre \e i must be in the heap.
   344     /// \pre \e i must be in the heap.
   345     Prio operator[](const Item &i) const {
   345     Prio operator[](const Item &i) const {
   346       int idx = _iim[i];
   346       int idx = _iim[i];
   347       return data[idx].prio;
   347       return _data[idx].prio;
   348     }
   348     }
   349 
   349 
   350     /// \brief Set the priority of an item or insert it, if it is
   350     /// \brief Set the priority of an item or insert it, if it is
   351     /// not stored in the heap.
   351     /// not stored in the heap.
   352     ///
   352     ///
   360     void set(const Item &i, const Prio &p) {
   360     void set(const Item &i, const Prio &p) {
   361       int idx = _iim[i];
   361       int idx = _iim[i];
   362       if( idx < 0 ) {
   362       if( idx < 0 ) {
   363         push(i, p);
   363         push(i, p);
   364       }
   364       }
   365       else if( p >= data[idx].prio ) {
   365       else if( p >= _data[idx].prio ) {
   366         data[idx].prio = p;
   366         _data[idx].prio = p;
   367         bubble_up(idx);
   367         bubbleUp(idx);
   368       } else {
   368       } else {
   369         data[idx].prio = p;
   369         _data[idx].prio = p;
   370         bubble_down(idx);
   370         bubbleDown(idx);
   371       }
   371       }
   372     }
   372     }
   373 
   373 
   374     /// \brief Decrease the priority of an item to the given value.
   374     /// \brief Decrease the priority of an item to the given value.
   375     ///
   375     ///
   378     /// \param p The priority.
   378     /// \param p The priority.
   379     /// \pre \e i must be stored in the heap with priority at least \e p.
   379     /// \pre \e i must be stored in the heap with priority at least \e p.
   380     /// \warning This method may throw an \c UnderFlowPriorityException.
   380     /// \warning This method may throw an \c UnderFlowPriorityException.
   381     void decrease(const Item &i, const Prio &p) {
   381     void decrease(const Item &i, const Prio &p) {
   382       int idx = _iim[i];
   382       int idx = _iim[i];
   383       data[idx].prio = p;
   383       _data[idx].prio = p;
   384       bubble_down(idx);
   384       bubbleDown(idx);
   385     }
   385     }
   386 
   386 
   387     /// \brief Increase the priority of an item to the given value.
   387     /// \brief Increase the priority of an item to the given value.
   388     ///
   388     ///
   389     /// This function increases the priority of an item to the given value.
   389     /// This function increases the priority of an item to the given value.
   390     /// \param i The item.
   390     /// \param i The item.
   391     /// \param p The priority.
   391     /// \param p The priority.
   392     /// \pre \e i must be stored in the heap with priority at most \e p.
   392     /// \pre \e i must be stored in the heap with priority at most \e p.
   393     void increase(const Item &i, const Prio &p) {
   393     void increase(const Item &i, const Prio &p) {
   394       int idx = _iim[i];
   394       int idx = _iim[i];
   395       data[idx].prio = p;
   395       _data[idx].prio = p;
   396       bubble_up(idx);
   396       bubbleUp(idx);
   397     }
   397     }
   398 
   398 
   399     /// \brief Return the state of an item.
   399     /// \brief Return the state of an item.
   400     ///
   400     ///
   401     /// This method returns \c PRE_HEAP if the given item has never
   401     /// This method returns \c PRE_HEAP if the given item has never