COIN-OR::LEMON - Graph Library

Changeset 1902:e9af75c90c28 in lemon-0.x for lemon


Ignore:
Timestamp:
01/25/06 13:10:18 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2477
Message:

state setting function for heaps

If we know that which elements were in the heap then
we can clear it in better time complexity.

Location:
lemon
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • lemon/bin_heap.h

    r1875 r1902  
    268268    }
    269269
     270    /// \brief Sets the state of the \c item in the heap.
     271    ///
     272    /// Sets the state of the \c item in the heap. It can be used to
     273    /// manually clear the heap when it is important to achive the
     274    /// better time complexity.
     275    /// \param i The item.
     276    /// \param st The state. It should not be \c IN_HEAP.
     277    void state(const Item& i, state_enum st) {
     278      switch (st) {
     279      case POST_HEAP:
     280      case PRE_HEAP:
     281        if (state(i) == IN_HEAP) {
     282          erase(i);
     283        }
     284        index[i] = st;
     285        break;
     286      }
     287    }
     288
    270289  }; // class BinHeap
    271290
  • lemon/concept/heap.h

    r1875 r1902  
    153153      state_enum state(const Item &i) const {}
    154154
     155      /// \brief Sets the state of the \c item in the heap.
     156      ///
     157      /// Sets the state of the \c item in the heap. It can be used to
     158      /// manually clear the heap when it is important to achive the
     159      /// better time complexity.
     160      /// \param i The item.
     161      /// \param st The state. It should not be \c IN_HEAP.
     162      void state(const Item& i, state_enum st) {}
     163
    155164
    156165      template <typename _Heap>
  • lemon/fib_heap.h

    r1875 r1902  
    217217      return state_enum(i);
    218218    }   
     219
     220    /// \brief Sets the state of the \c item in the heap.
     221    ///
     222    /// Sets the state of the \c item in the heap. It can be used to
     223    /// manually clear the heap when it is important to achive the
     224    /// better time complexity.
     225    /// \param i The item.
     226    /// \param st The state. It should not be \c IN_HEAP.
     227    void state(const Item& i, state_enum st) {
     228      switch (st) {
     229      case POST_HEAP:
     230      case PRE_HEAP:
     231        if (state(i) == IN_HEAP) {
     232          erase(i);
     233        }
     234        index[i] = st;
     235        break;
     236      }
     237    }
    219238   
    220239  private:
  • lemon/linear_heap.h

    r1875 r1902  
    284284    }
    285285
     286    /// \brief Sets the state of the \c item in the heap.
     287    ///
     288    /// Sets the state of the \c item in the heap. It can be used to
     289    /// manually clear the heap when it is important to achive the
     290    /// better time complexity.
     291    /// \param i The item.
     292    /// \param st The state. It should not be \c IN_HEAP.
     293    void state(const Item& i, state_enum st) {
     294      switch (st) {
     295      case POST_HEAP:
     296      case PRE_HEAP:
     297        if (state(i) == IN_HEAP) {
     298          erase(i);
     299        }
     300        index[i] = st;
     301        break;
     302      }
     303    }
     304
    286305  private:
    287306
     
    460479    }
    461480
     481    void state(const Item& i, state_enum st) {
     482      switch (st) {
     483      case POST_HEAP:
     484      case PRE_HEAP:
     485        if (state(i) == IN_HEAP) {
     486          erase(i);
     487        }
     488        index[i] = st;
     489        break;
     490      }
     491    }
     492
    462493  private:
    463494
  • lemon/radix_heap.h

    r1875 r1902  
    407407    }
    408408
     409    /// \brief Sets the state of the \c item in the heap.
     410    ///
     411    /// Sets the state of the \c item in the heap. It can be used to
     412    /// manually clear the heap when it is important to achive the
     413    /// better time complexity.
     414    /// \param i The item.
     415    /// \param st The state. It should not be \c IN_HEAP.
     416    void state(const Item& i, state_enum st) {
     417      switch (st) {
     418      case POST_HEAP:
     419      case PRE_HEAP:
     420        if (state(i) == IN_HEAP) {
     421          erase(i);
     422        }
     423        index[i] = st;
     424        break;
     425      }
     426    }
     427
    409428  }; // class RadixHeap
    410429
Note: See TracChangeset for help on using the changeset viewer.