lemon/unionfind.h
changeset 784 1a7fe3bef514
parent 440 88ed40ad0d4f
child 786 e20173729589
child 867 5b926cc36a4b
     1.1 --- a/lemon/unionfind.h	Fri Oct 16 10:21:37 2009 +0200
     1.2 +++ b/lemon/unionfind.h	Thu Nov 05 15:50:01 2009 +0100
     1.3 @@ -2,7 +2,7 @@
     1.4   *
     1.5   * This file is a part of LEMON, a generic C++ optimization library.
     1.6   *
     1.7 - * Copyright (C) 2003-2008
     1.8 + * Copyright (C) 2003-2009
     1.9   * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10   * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11   *
    1.12 @@ -51,11 +51,13 @@
    1.13    ///
    1.14    /// \pre You need to add all the elements by the \ref insert()
    1.15    /// method.
    1.16 -  template <typename _ItemIntMap>
    1.17 +  template <typename IM>
    1.18    class UnionFind {
    1.19    public:
    1.20  
    1.21 -    typedef _ItemIntMap ItemIntMap;
    1.22 +    ///\e
    1.23 +    typedef IM ItemIntMap;
    1.24 +    ///\e
    1.25      typedef typename ItemIntMap::Key Item;
    1.26  
    1.27    private:
    1.28 @@ -170,11 +172,13 @@
    1.29    /// \pre You need to add all the elements by the \ref insert()
    1.30    /// method.
    1.31    ///
    1.32 -  template <typename _ItemIntMap>
    1.33 +  template <typename IM>
    1.34    class UnionFindEnum {
    1.35    public:
    1.36  
    1.37 -    typedef _ItemIntMap ItemIntMap;
    1.38 +    ///\e
    1.39 +    typedef IM ItemIntMap;
    1.40 +    ///\e
    1.41      typedef typename ItemIntMap::Key Item;
    1.42  
    1.43    private:
    1.44 @@ -627,11 +631,13 @@
    1.45    ///
    1.46    /// \pre You need to add all the elements by the \ref insert()
    1.47    /// method.
    1.48 -  template <typename _ItemIntMap>
    1.49 +  template <typename IM>
    1.50    class ExtendFindEnum {
    1.51    public:
    1.52  
    1.53 -    typedef _ItemIntMap ItemIntMap;
    1.54 +    ///\e
    1.55 +    typedef IM ItemIntMap;
    1.56 +    ///\e
    1.57      typedef typename ItemIntMap::Key Item;
    1.58  
    1.59    private:
    1.60 @@ -948,18 +954,18 @@
    1.61    ///
    1.62    /// \pre You need to add all the elements by the \ref insert()
    1.63    /// method.
    1.64 -  ///
    1.65 -  template <typename _Value, typename _ItemIntMap,
    1.66 -            typename _Comp = std::less<_Value> >
    1.67 +  template <typename V, typename IM, typename Comp = std::less<V> >
    1.68    class HeapUnionFind {
    1.69    public:
    1.70  
    1.71 -    typedef _Value Value;
    1.72 -    typedef typename _ItemIntMap::Key Item;
    1.73 -
    1.74 -    typedef _ItemIntMap ItemIntMap;
    1.75 -
    1.76 -    typedef _Comp Comp;
    1.77 +    ///\e
    1.78 +    typedef V Value;
    1.79 +    ///\e
    1.80 +    typedef typename IM::Key Item;
    1.81 +    ///\e
    1.82 +    typedef IM ItemIntMap;
    1.83 +    ///\e
    1.84 +    typedef Comp Compare;
    1.85  
    1.86    private:
    1.87  
    1.88 @@ -1189,7 +1195,7 @@
    1.89                int ld = nodes[nodes[jd].next].left;
    1.90                popLeft(nodes[jd].next);
    1.91                pushRight(jd, ld);
    1.92 -              if (less(ld, nodes[jd].left) || 
    1.93 +              if (less(ld, nodes[jd].left) ||
    1.94                    nodes[ld].item == nodes[pd].item) {
    1.95                  nodes[jd].item = nodes[ld].item;
    1.96                  nodes[jd].prio = nodes[ld].prio;
    1.97 @@ -1601,7 +1607,7 @@
    1.98  
    1.99      /// \brief Gives back the priority of the current item.
   1.100      ///
   1.101 -    /// \return Gives back the priority of the current item.
   1.102 +    /// Gives back the priority of the current item.
   1.103      const Value& operator[](const Item& item) const {
   1.104        return nodes[index[item]].prio;
   1.105      }
   1.106 @@ -1646,7 +1652,7 @@
   1.107  
   1.108      /// \brief Gives back the minimum priority of the class.
   1.109      ///
   1.110 -    /// \return Gives back the minimum priority of the class.
   1.111 +    /// Gives back the minimum priority of the class.
   1.112      const Value& classPrio(int cls) const {
   1.113        return nodes[~(classes[cls].parent)].prio;
   1.114      }
   1.115 @@ -1660,9 +1666,9 @@
   1.116  
   1.117      /// \brief Gives back a representant item of the class.
   1.118      ///
   1.119 +    /// Gives back a representant item of the class.
   1.120      /// The representant is indpendent from the priorities of the
   1.121      /// items.
   1.122 -    /// \return Gives back a representant item of the class.
   1.123      const Item& classRep(int id) const {
   1.124        int parent = classes[id].parent;
   1.125        return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;