Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/bucket_heap.h
changeset 2547 f393a8162688
parent 2391 14a343be7a5a
child 2553 bfced05fa852
equal deleted inserted replaced
7:e4ced73b1f83 8:ea46cd4454bb 
    47   /// the lowest priority. 
    47   /// the lowest priority. 
    48   template <typename _ItemIntMap, bool minimize = true >
 
    48   template <typename _ItemIntMap, bool minimize = true >
 
    49   class BucketHeap {
 
    49   class BucketHeap {
 
    50 
    50 
    51   public:
 
    51   public:
 
       
    52     /// \e
 
    52     typedef typename _ItemIntMap::Key Item;
 
    53     typedef typename _ItemIntMap::Key Item;
 
       
    54     /// \e
 
    53     typedef int Prio;
 
    55     typedef int Prio;
 
       
    56     /// \e
 
    54     typedef std::pair<Item, Prio> Pair;
 
    57     typedef std::pair<Item, Prio> Pair;
 
       
    58     /// \e
 
    55     typedef _ItemIntMap ItemIntMap;
 
    59     typedef _ItemIntMap ItemIntMap;
 
    56 
    60 
    57     /// \brief Type to represent the items states.
 
    61     /// \brief Type to represent the items states.
 
    58     ///
 
    62     ///
 
    59     /// Each Item element have a state associated to it. It may be "in heap",
 
    63     /// Each Item element have a state associated to it. It may be "in heap",
 
    60     /// "pre heap" or "post heap". The latter two are indifferent from the
 
    64     /// "pre heap" or "post heap". The latter two are indifferent from the
 
    61     /// heap's point of view, but may be useful to the user.
 
    65     /// heap's point of view, but may be useful to the user.
 
    62     ///
 
    66     ///
 
    63     /// The ItemIntMap \e should be initialized in such way that it maps
 
    67     /// The ItemIntMap \e should be initialized in such way that it maps
 
    64     /// PRE_HEAP (-1) to any element to be put in the heap...
 
    68     /// PRE_HEAP (-1) to any element to be put in the heap...
 
    65     enum state_enum {
 
    69     enum State {
 
    66       IN_HEAP = 0,
 
    70       IN_HEAP = 0,
 
    67       PRE_HEAP = -1,
 
    71       PRE_HEAP = -1,
 
    68       POST_HEAP = -2
 
    72       POST_HEAP = -2
 
    69     };
 
    73     };
 
    70 
    74 
   276     /// This method returns PRE_HEAP if \c item has never been in the
 
   280     /// This method returns PRE_HEAP if \c item has never been in the
 
   277     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
 
   281     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
 
   278     /// otherwise. In the latter case it is possible that \c item will
 
   282     /// otherwise. In the latter case it is possible that \c item will
 
   279     /// get back to the heap again.
 
   283     /// get back to the heap again.
 
   280     /// \param i The item.
 
   284     /// \param i The item.
 
   281     state_enum state(const Item &i) const {
 
   285     State state(const Item &i) const {
 
   282       int idx = index[i];
 
   286       int idx = index[i];
 
   283       if (idx >= 0) idx = 0;
 
   287       if (idx >= 0) idx = 0;
 
   284       return state_enum(idx);
 
   288       return State(idx);
 
   285     }
 
   289     }
 
   286 
   290 
   287     /// \brief Sets the state of the \c item in the heap.
 
   291     /// \brief Sets the state of the \c item in the heap.
 
   288     ///
 
   292     ///
 
   289     /// Sets the state of the \c item in the heap. It can be used to
 
   293     /// Sets the state of the \c item in the heap. It can be used to
 
   290     /// manually clear the heap when it is important to achive the
 
   294     /// manually clear the heap when it is important to achive the
 
   291     /// better time complexity.
 
   295     /// better time complexity.
 
   292     /// \param i The item.
 
   296     /// \param i The item.
 
   293     /// \param st The state. It should not be \c IN_HEAP. 
   297     /// \param st The state. It should not be \c IN_HEAP. 
   294     void state(const Item& i, state_enum st) {
 
   298     void state(const Item& i, State st) {
 
   295       switch (st) {
 
   299       switch (st) {
 
   296       case POST_HEAP:
 
   300       case POST_HEAP:
 
   297       case PRE_HEAP:
 
   301       case PRE_HEAP:
 
   298         if (state(i) == IN_HEAP) {
 
   302         if (state(i) == IN_HEAP) {
 
   299           erase(i);
 
   303           erase(i);
 
   332     typedef typename _ItemIntMap::Key Item;
 
   336     typedef typename _ItemIntMap::Key Item;
 
   333     typedef int Prio;
 
   337     typedef int Prio;
 
   334     typedef std::pair<Item, Prio> Pair;
 
   338     typedef std::pair<Item, Prio> Pair;
 
   335     typedef _ItemIntMap ItemIntMap;
 
   339     typedef _ItemIntMap ItemIntMap;
 
   336 
   340 
   337     enum state_enum {
 
   341     enum State {
 
   338       IN_HEAP = 0,
 
   342       IN_HEAP = 0,
 
   339       PRE_HEAP = -1,
 
   343       PRE_HEAP = -1,
 
   340       POST_HEAP = -2
 
   344       POST_HEAP = -2
 
   341     };
 
   345     };
 
   342 
   346 
   470       unlace(idx);
 
   474       unlace(idx);
 
   471       data[idx].value = p;
 
   475       data[idx].value = p;
 
   472       lace(idx);
 
   476       lace(idx);
 
   473     }
 
   477     }
 
   474 
   478 
   475     state_enum state(const Item &i) const {
 
   479     State state(const Item &i) const {
 
   476       int idx = index[i];
 
   480       int idx = index[i];
 
   477       if (idx >= 0) idx = 0;
 
   481       if (idx >= 0) idx = 0;
 
   478       return state_enum(idx);
 
   482       return State(idx);
 
   479     }
 
   483     }
 
   480 
   484 
   481     void state(const Item& i, state_enum st) {
 
   485     void state(const Item& i, State st) {
 
   482       switch (st) {
 
   486       switch (st) {
 
   483       case POST_HEAP:
 
   487       case POST_HEAP:
 
   484       case PRE_HEAP:
 
   488       case PRE_HEAP:
 
   485         if (state(i) == IN_HEAP) {
 
   489         if (state(i) == IN_HEAP) {
 
   486           erase(i);
 
   490           erase(i);
 
   544     /// "pre heap" or "post heap". The latter two are indifferent from the
 
   548     /// "pre heap" or "post heap". The latter two are indifferent from the
 
   545     /// heap's point of view, but may be useful to the user.
 
   549     /// heap's point of view, but may be useful to the user.
 
   546     ///
 
   550     ///
 
   547     /// The ItemIntMap \e should be initialized in such way that it maps
 
   551     /// The ItemIntMap \e should be initialized in such way that it maps
 
   548     /// PRE_HEAP (-1) to any element to be put in the heap...
 
   552     /// PRE_HEAP (-1) to any element to be put in the heap...
 
   549     enum state_enum {
 
   553     enum State {
 
   550       IN_HEAP = 0,
 
   554       IN_HEAP = 0,
 
   551       PRE_HEAP = -1,
 
   555       PRE_HEAP = -1,
 
   552       POST_HEAP = -2
 
   556       POST_HEAP = -2
 
   553     };
 
   557     };
 
   554 
   558 
   681     /// This method returns PRE_HEAP if \c item has never been in the
 
   685     /// This method returns PRE_HEAP if \c item has never been in the
 
   682     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
 
   686     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
 
   683     /// otherwise. In the latter case it is possible that \c item will
 
   687     /// otherwise. In the latter case it is possible that \c item will
 
   684     /// get back to the heap again.
 
   688     /// get back to the heap again.
 
   685     /// \param i The item.
 
   689     /// \param i The item.
 
   686     state_enum state(const Item &i) const {
 
   690     State state(const Item &i) const {
 
   687       int idx = index[i];
 
   691       int idx = index[i];
 
   688       if (idx >= 0) idx = 0;
 
   692       if (idx >= 0) idx = 0;
 
   689       return state_enum(idx);
 
   693       return State(idx);
 
   690     }
 
   694     }
 
   691 
   695 
   692   private:
 
   696   private:
 
   693 
   697 
   694     struct BucketItem {
 
   698     struct BucketItem {
 
   714     typedef typename _ItemIntMap::Key Item;
 
   718     typedef typename _ItemIntMap::Key Item;
 
   715     typedef int Prio;
 
   719     typedef int Prio;
 
   716     typedef std::pair<Item, Prio> Pair;
 
   720     typedef std::pair<Item, Prio> Pair;
 
   717     typedef _ItemIntMap ItemIntMap;
 
   721     typedef _ItemIntMap ItemIntMap;
 
   718 
   722 
   719     enum state_enum {
 
   723     enum State {
 
   720       IN_HEAP = 0,
 
   724       IN_HEAP = 0,
 
   721       PRE_HEAP = -1,
 
   725       PRE_HEAP = -1,
 
   722       POST_HEAP = -2
 
   726       POST_HEAP = -2
 
   723     };
 
   727     };
 
   724 
   728 
   796         }
 
   800         }
 
   797       }
 
   801       }
 
   798       return -1;
 
   802       return -1;
 
   799     }
 
   803     }
 
   800 
   804 
   801     state_enum state(const Item &i) const {
 
   805     State state(const Item &i) const {
 
   802       int idx = index[i];
 
   806       int idx = index[i];
 
   803       if (idx >= 0) idx = 0;
 
   807       if (idx >= 0) idx = 0;
 
   804       return state_enum(idx);
 
   808       return State(idx);
 
   805     }
 
   809     }
 
   806 
   810 
   807   private:
 
   811   private:
 
   808 
   812 
   809     struct BucketItem {
 
   813     struct BucketItem {
lemon-0.x