COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2263:9273fe7d850c in lemon-0.x


Ignore:
Timestamp:
10/26/06 16:20:17 (17 years ago)
Author:
mqrelly
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3021
Message:

Bug #46 fixed: Superfluous template parameter in Heap concept
NOTE: Not every affected file tested.

Location:
lemon
Files:
12 edited

Legend:

Unmodified
Added
Removed

  • lemon/bin_heap.h

    r2258 r2263  
    4040  ///one can change the priority of an item, add or erase an item, etc.
    4141  ///
    42   ///\param Item Type of the items to be stored. 
    4342  ///\param Prio Type of the priority of the items.
    4443  ///\param ItemIntMap A read and writable Item int map, used internally
    … …  
    4948  ///\sa FibHeap
    5049  ///\sa Dijkstra
    51   template <typename Item, typename Prio, typename ItemIntMap,
     50  template <typename Prio, typename ItemIntMap,
    5251            typename Compare = std::less<Prio> >
    5352  class BinHeap {
    5453
    5554  public:
    56     typedef Item                             ItemType;
     55    typedef typename ItemIntMap::Key         ItemType;
    5756    typedef Prio                             PrioType;
    5857    typedef std::pair<ItemType,PrioType>     PairType;
    … …  
    162161    /// \param i The item to insert.
    163162    /// \param p The priority of the item.
    164     void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
     163    void push(const ItemType &i, const Prio &p) { push(PairType(i,p)); }
    165164
    166165    /// \brief Returns the item with minimum priority relative to \c Compare.
    … …  
    169168    /// Compare. 
    170169    /// \pre The heap must be nonempty. 
    171     Item top() const {
     170    ItemType top() const {
    172171      return data[0].first;
    173172    }
    … …  
    195194    /// already stored in the heap.
    196195    /// \param i The item to erase.
    197     void erase(const Item &i) {
     196    void erase(const ItemType &i) {
    198197      rmidx(iim[i]);
    199198    }
    … …  
    205204    /// \pre \c i must be in the heap.
    206205    /// \param i The item.
    207     Prio operator[](const Item &i) const {
     206    Prio operator[](const ItemType &i) const {
    208207      int idx = iim[i];
    209208      return data[idx].second;
    … …  
    217216    /// \param i The item.
    218217    /// \param p The priority.
    219     void set(const Item &i, const Prio &p) {
     218    void set(const ItemType &i, const Prio &p) {
    220219      int idx = iim[i];
    221220      if( idx < 0 ) {
    … …  
    237236    /// \param i The item.
    238237    /// \param p The priority.
    239     void decrease(const Item &i, const Prio &p) {
     238    void decrease(const ItemType &i, const Prio &p) {
    240239      int idx = iim[i];
    241240      bubble_up(idx, PairType(i,p));
    … …  
    249248    /// \param i The item.
    250249    /// \param p The priority.
    251     void increase(const Item &i, const Prio &p) {
     250    void increase(const ItemType &i, const Prio &p) {
    252251      int idx = iim[i];
    253252      bubble_down(idx, PairType(i,p), data.size());
    … …  
    262261    /// get back to the heap again.
    263262    /// \param i The item.
    264     state_enum state(const Item &i) const {
     263    state_enum state(const ItemType &i) const {
    265264      int s = iim[i];
    266265      if( s>=0 )
    … …  
    276275    /// \param i The item.
    277276    /// \param st The state. It should not be \c IN_HEAP.
    278     void state(const Item& i, state_enum st) {
     277    void state(const ItemType& i, state_enum st) {
    279278      switch (st) {
    280279      case POST_HEAP:
    … …  
    293292
    294293 
    295   template <typename K, typename V, typename M, typename C>
    296   int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
     294  template <typename V, typename M, typename C>
     295  int BinHeap<V,M,C>::bubble_up(int hole, PairType p) {
    297296    int par = parent(hole);
    298297    while( hole>0 && less(p,data[par]) ) {
    … …  
    305304  }
    306305
    307   template <typename K, typename V, typename M, typename C>
    308   int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
     306  template <typename V, typename M, typename C>
     307  int BinHeap<V,M,C>::bubble_down(int hole, PairType p, int length) {
    309308    int child = second_child(hole);
    310309    while(child < length) {

  • lemon/bipartite_matching.h

    r2151 r2263  
    522522    ///
    523523    /// \sa BinHeap
    524     typedef BinHeap<typename BpUGraph::Node, Value, HeapCrossRef> Heap;
     524    typedef BinHeap<Value, HeapCrossRef> Heap;
    525525   
    526526    /// \brief Instantiates a Heap.

  • lemon/bucket_heap.h

    r2110 r2263  
    4242  /// the priorities are small. It is not intended to use as dijkstra heap.
    4343  ///
    44   /// \param _Item Type of the items to be stored. 
    4544  /// \param _ItemIntMap A read and writable Item int map, used internally
    4645  /// to handle the cross references.
    4746  /// \param minimize If the given parameter is true then the heap gives back
    4847  /// the lowest priority.
    49   template <typename _Item, typename _ItemIntMap, bool minimize = true >
     48  template <typename _ItemIntMap, bool minimize = true >
    5049  class BucketHeap {
    5150
    5251  public:
    53     typedef _Item Item;
     52    typedef typename _ItemIntMap::Key Item;
    5453    typedef int Prio;
    5554    typedef std::pair<Item, Prio> Pair;
    … …  
    327326
    328327
    329   template <typename _Item, typename _ItemIntMap>
    330   class BucketHeap<_Item, _ItemIntMap, false> {
    331 
    332   public:
    333     typedef _Item Item;
     328  template <typename _ItemIntMap>
     329  class BucketHeap<_ItemIntMap, false> {
     330
     331  public:
     332    typedef typename _ItemIntMap::Key Item;
    334333    typedef int Prio;
    335334    typedef std::pair<Item, Prio> Pair;
    … …  
    525524  /// minimal and it does not supports key increasing, decreasing.
    526525  ///
    527   /// \param _Item Type of the items to be stored. 
    528526  /// \param _ItemIntMap A read and writable Item int map, used internally
    529527  /// to handle the cross references.
    … …  
    532530  ///
    533531  /// \sa BucketHeap
    534   template <typename _Item, typename _ItemIntMap, bool minimize = true >
     532  template <typename _ItemIntMap, bool minimize = true >
    535533  class SimpleBucketHeap {
    536534
    537535  public:
    538     typedef _Item Item;
     536    typedef typename _ItemIntMap::Key Item;
    539537    typedef int Prio;
    540538    typedef std::pair<Item, Prio> Pair;
    … …  
    710708  }; // class SimpleBucketHeap
    711709
    712   template <typename _Item, typename _ItemIntMap>
    713   class SimpleBucketHeap<_Item, _ItemIntMap, false> {
    714 
    715   public:
    716     typedef _Item Item;
     710  template <typename _ItemIntMap>
     711  class SimpleBucketHeap<_ItemIntMap, false> {
     712
     713  public:
     714    typedef typename _ItemIntMap::Key Item;
    717715    typedef int Prio;
    718716    typedef std::pair<Item, Prio> Pair;

  • lemon/concepts/heap.h

    r2260 r2263  
    3737    /// A concept structure describes the main interface of heaps.
    3838    ///
    39     template <typename Item, typename Prio, typename ItemIntMap>
     39    template <typename Prio, typename ItemIntMap>
    4040    class Heap {
    4141    public:
     42
     43      ///\brief Type of the items stored in the heap.
     44      typedef typename ItemIntMap::Key  Item;
    4245 
    4346

  • lemon/dijkstra.h

    r2260 r2263  
    7474    ///\sa BinHeap
    7575    ///\sa Dijkstra
    76     typedef BinHeap<typename Graph::Node, typename LM::Value,
    77                     HeapCrossRef, std::less<Value> > Heap;
     76    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
    7877
    7978    static Heap *createHeap(HeapCrossRef& R)
    … …  
    848847    ///\sa BinHeap
    849848    ///\sa Dijkstra
    850     typedef BinHeap<typename Graph::Node, typename LM::Value,
    851                     typename GR::template NodeMap<int>,
     849    typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
    852850                    std::less<Value> > Heap;
    853851

  • lemon/fib_heap.h

    r2050 r2263  
    4444  ///\e binary \e heap.
    4545  ///
    46   ///\param Item Type of the items to be stored. 
    4746  ///\param Prio Type of the priority of the items.
    4847  ///\param ItemIntMap A read and writable Item int map, used internally
    … …  
    5655 
    5756#ifdef DOXYGEN
    58   template <typename Item,
    59             typename Prio,
     57  template <typename Prio,
    6058            typename ItemIntMap,
    6159            typename Compare>
    6260#else
    63   template <typename Item,
    64             typename Prio,
     61  template <typename Prio,
    6562            typename ItemIntMap,
    6663            typename Compare = std::less<Prio> >
    6764#endif
    6865  class FibHeap {
    69   public:     
     66  public:
     67    typedef typename ItemIntMap::Key Item;
    7068    typedef Prio PrioType;
    7169   
    … …  
    272270    // **********************************************************************
    273271   
    274   template <typename Item, typename Prio, typename ItemIntMap,
    275     typename Compare>
    276   void FibHeap<Item, Prio, ItemIntMap, Compare>::set
     272  template <typename Prio, typename ItemIntMap,
     273    typename Compare>
     274  void FibHeap<Prio, ItemIntMap, Compare>::set
    277275  (Item const item, PrioType const value)
    278276  {
    … …  
    284282  }
    285283   
    286   template <typename Item, typename Prio, typename ItemIntMap,
    287     typename Compare>
    288   void FibHeap<Item, Prio, ItemIntMap, Compare>::push
     284  template <typename Prio, typename ItemIntMap,
     285    typename Compare>
     286  void FibHeap<Prio, ItemIntMap, Compare>::push
    289287  (Item const item, PrioType const value) {
    290288      int i=iimap[item];     
    … …  
    317315    }
    318316   
    319   template <typename Item, typename Prio, typename ItemIntMap,
    320     typename Compare>
    321   void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
     317  template <typename Prio, typename ItemIntMap,
     318    typename Compare>
     319  void FibHeap<Prio, ItemIntMap, Compare>::pop() {
    322320      /*The first case is that there are only one root.*/
    323321      if ( container[minimum].left_neighbor==minimum ) {
    … …  
    351349
    352350
    353   template <typename Item, typename Prio, typename ItemIntMap,
    354     typename Compare>
    355   void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
     351  template <typename Prio, typename ItemIntMap,
     352    typename Compare>
     353  void FibHeap<Prio, ItemIntMap, Compare>::erase
    356354  (const Item& item) {
    357355      int i=iimap[item];
    … …  
    368366  }
    369367   
    370   template <typename Item, typename Prio, typename ItemIntMap,
    371     typename Compare>
    372   void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
     368  template <typename Prio, typename ItemIntMap,
     369    typename Compare>
     370  void FibHeap<Prio, ItemIntMap, Compare>::decrease
    373371  (Item item, PrioType const value) {
    374372      int i=iimap[item];
    … …  
    384382 
    385383
    386   template <typename Item, typename Prio, typename ItemIntMap,
    387     typename Compare>
    388   void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {     
     384  template <typename Prio, typename ItemIntMap,
     385    typename Compare>
     386  void FibHeap<Prio, ItemIntMap, Compare>::balance() {     
    389387
    390388    int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
    … …  
    429427    }
    430428
    431   template <typename Item, typename Prio, typename ItemIntMap,
    432     typename Compare>
    433   void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
     429  template <typename Prio, typename ItemIntMap,
     430    typename Compare>
     431  void FibHeap<Prio, ItemIntMap, Compare>::makeroot
    434432  (int c) {
    435433      int s=c;
    … …  
    441439 
    442440 
    443   template <typename Item, typename Prio, typename ItemIntMap,
    444     typename Compare>
    445   void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
     441  template <typename Prio, typename ItemIntMap,
     442    typename Compare>
     443  void FibHeap<Prio, ItemIntMap, Compare>::cut
    446444  (int a, int b) {   
    447445    /*
    … …  
    470468 
    471469
    472   template <typename Item, typename Prio, typename ItemIntMap,
    473     typename Compare>
    474   void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
     470  template <typename Prio, typename ItemIntMap,
     471    typename Compare>
     472  void FibHeap<Prio, ItemIntMap, Compare>::cascade
    475473  (int a)
    476474    {
    … …  
    487485
    488486
    489   template <typename Item, typename Prio, typename ItemIntMap,
    490     typename Compare>
    491   void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
     487  template <typename Prio, typename ItemIntMap,
     488    typename Compare>
     489  void FibHeap<Prio, ItemIntMap, Compare>::fuse
    492490  (int a, int b) {
    493491      unlace(b);
    … …  
    518516   *It is invoked only if a has siblings.
    519517   */
    520   template <typename Item, typename Prio, typename ItemIntMap,
    521     typename Compare>
    522   void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
     518  template <typename Prio, typename ItemIntMap,
     519    typename Compare>
     520  void FibHeap<Prio, ItemIntMap, Compare>::unlace
    523521  (int a) {     
    524522      int leftn=container[a].left_neighbor;

  • lemon/fredman_tarjan.h

    r2260 r2263  
    281281      typedef typename SrcGraph::template NodeMap<UEdge> PredMap;
    282282      HeapCrossRef crossref(graph,-1);
    283       FibHeap<Node,Value,HeapCrossRef> heap(crossref);
     283      FibHeap<Value,HeapCrossRef> heap(crossref);
    284284      PredMap pred(graph,INVALID);
    285285      int rate=2*edgenum/countNodes(graph);

  • lemon/johnson.h

    r2260 r2263  
    131131    ///\sa BinHeap
    132132    ///\sa Dijkstra
    133     typedef BinHeap<typename Graph::Node, typename LengthMap::Value,
     133    typedef BinHeap<typename LengthMap::Value,
    134134                    HeapCrossRef, std::less<Value> > Heap;
    135135

  • lemon/min_cost_arborescence.h

    r2260 r2263  
    225225    HeapCrossRef *_heap_cross_ref;
    226226
    227     typedef BinHeap<Node, int, HeapCrossRef> Heap;
     227    typedef BinHeap<int, HeapCrossRef> Heap;
    228228
    229229    Heap *_heap;

  • lemon/min_cut.h

    r2260 r2263  
    3939    template <typename CapacityMap>
    4040    struct HeapSelector {
    41       template <typename Key, typename Value, typename Ref>
     41      template <typename Value, typename Ref>
    4242      struct Selector {
    43         typedef BinHeap<Key, Value, Ref, std::greater<Value> > Heap;
     43        typedef BinHeap<Value, Ref, std::greater<Value> > Heap;
    4444      };
    4545    };
    … …  
    4747    template <typename CapacityKey>
    4848    struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
    49       template <typename Key, typename Value, typename Ref>
     49      template <typename Value, typename Ref>
    5050      struct Selector {
    51         typedef BucketHeap<Key, Ref, false > Heap;
     51        typedef BucketHeap<Ref, false > Heap;
    5252      };
    5353    };
    … …  
    100100    typedef typename _min_cut_bits
    101101    ::HeapSelector<CapacityMap>
    102     ::template Selector<typename Graph::Node, Value, HeapCrossRef>
     102    ::template Selector<Value, HeapCrossRef>
    103103    ::Heap Heap;
    104104
    … …  
    767767    typedef typename _min_cut_bits
    768768    ::HeapSelector<CapacityMap>
    769     ::template Selector<typename AuxGraph::Node, Value, HeapCrossRef>
     769    ::template Selector<Value, HeapCrossRef>
    770770    ::Heap Heap;
    771771   

  • lemon/prim.h

    r2260 r2263  
    7171    ///\sa BinHeap
    7272    ///\sa Prim
    73     typedef BinHeap<typename UGraph::Node, typename CM::Value,
     73    typedef BinHeap<typename CM::Value,
    7474                    HeapCrossRef, std::less<Value> > Heap;
    7575

  • lemon/radix_heap.h

    r2151 r2263  
    5555  /// item's priority.
    5656  ///
    57   /// \param _Item Type of the items to be stored. 
    5857  /// \param _ItemIntMap A read and writable Item int map, used internally
    5958  /// to handle the cross references.
    … …  
    6362  /// \author Balazs Dezso
    6463
    65   template <typename _Item, typename _ItemIntMap>
     64  template <typename _ItemIntMap>
    6665  class RadixHeap {
    6766
    6867  public:
    69     typedef _Item Item;
     68    typedef typename _ItemIntMap::Key Item;
    7069    typedef int Prio;
    7170    typedef _ItemIntMap ItemIntMap;
    … …  
    300299    /// \pre The heap must be nonempty. 
    301300    Item top() const {
    302       const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
     301      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
    303302      return data[boxes[0].first].item;
    304303    }
    … …  
    309308    /// \pre The heap must be nonempty.
    310309    Prio prio() const {
    311       const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
     310      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
    312311      return data[boxes[0].first].prio;
    313312     }
Note: See TracChangeset for help on using the changeset viewer.