Changes in / [944:b4af20d02ae0:933:66156a3498ea] in lemon-main

Files:

• lemon/Makefile.am (modified) (3 diffs)
• lemon/bin_heap.h (modified) (3 diffs)
• lemon/bits/map_extender.h (modified) (10 diffs)
• lemon/bucket_heap.h (deleted)
• lemon/concepts/maps.h (modified) (1 diff)
• lemon/fib_heap.h (deleted)
• lemon/glpk.h (modified) (3 diffs)
• lemon/path.h (modified) (11 diffs)
• lemon/radix_heap.h (deleted)
• test/heap_test.cc (modified) (2 diffs)

lemon/Makefile.am

@@ -60 +60 @@
         lemon/bfs.h \
         lemon/bin_heap.h \
-        lemon/bucket_heap.h \
         lemon/cbc.h \
         lemon/circulation.h \
@@ -78 +77 @@
         lemon/error.h \
         lemon/euler.h \
-        lemon/fib_heap.h \
         lemon/full_graph.h \
         lemon/glpk.h \
@@ -102 +100 @@
         lemon/path.h \
         lemon/preflow.h \
-        lemon/radix_heap.h \
         lemon/radix_sort.h \
         lemon/random.h \

lemon/bin_heap.h

@@ -34 +34 @@
   ///\brief A Binary Heap implementation.
   ///
-  ///This class implements the \e binary \e heap data structure.
-  ///
+  ///This class implements the \e binary \e heap data structure. 
+  /// 
   ///A \e heap is a data structure for storing items with specified values
   ///called \e priorities in such a way that finding the item with minimum
-  ///priority is efficient. \c CMP specifies the ordering of the priorities.
+  ///priority is efficient. \c Comp specifies the ordering of the priorities.
   ///In a heap one can change the priority of an item, add or erase an
   ///item, etc.
@@ -45 +45 @@
   ///\tparam IM A read and writable item map with int values, used internally
   ///to handle the cross references.
-  ///\tparam CMP A functor class for the ordering of the priorities.
+  ///\tparam Comp A functor class for the ordering of the priorities.
   ///The default is \c std::less<PR>.
   ///
   ///\sa FibHeap
   ///\sa Dijkstra
-  template <typename PR, typename IM, typename CMP = std::less<PR> >
+  template <typename PR, typename IM, typename Comp = std::less<PR> >
   class BinHeap {
 
@@ -63 +63 @@
     typedef std::pair<Item,Prio> Pair;
     ///\e
-    typedef CMP Compare;
+    typedef Comp Compare;
 
     /// \brief Type to represent the items states.

lemon/bits/map_extender.h

@@ -50 +50 @@
     typedef typename Parent::ConstReference ConstReference;
 
-    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
-
     class MapIt;
     class ConstMapIt;
@@ -85 +83 @@
       typedef typename Map::Value Value;
 
-      MapIt() : map(NULL) {}
-
-      MapIt(Invalid i) : Parent(i), map(NULL) {}
-
-      explicit MapIt(Map& _map) : map(&_map) {
-        map->notifier()->first(*this);
+      MapIt() {}
+
+      MapIt(Invalid i) : Parent(i) { }
+
+      explicit MapIt(Map& _map) : map(_map) {
+        map.notifier()->first(*this);
       }
 
       MapIt(const Map& _map, const Item& item)
-        : Parent(item), map(&_map) {}
+        : Parent(item), map(_map) {}
 
       MapIt& operator++() {
-        map->notifier()->next(*this);
+        map.notifier()->next(*this);
         return *this;
       }
 
       typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return (*map)[*this];
+        return map[*this];
       }
 
       typename MapTraits<Map>::ReturnValue operator*() {
-        return (*map)[*this];
+        return map[*this];
       }
 
       void set(const Value& value) {
-        map->set(*this, value);
-      }
-
-    protected:
-      Map* map;
+        map.set(*this, value);
+      }
+
+    protected:
+      Map& map;
 
     };
@@ -125 +123 @@
       typedef typename Map::Value Value;
 
-      ConstMapIt() : map(NULL) {}
-
-      ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
-
-      explicit ConstMapIt(Map& _map) : map(&_map) {
-        map->notifier()->first(*this);
+      ConstMapIt() {}
+
+      ConstMapIt(Invalid i) : Parent(i) { }
+
+      explicit ConstMapIt(Map& _map) : map(_map) {
+        map.notifier()->first(*this);
       }
 
@@ -137 +135 @@
 
       ConstMapIt& operator++() {
-        map->notifier()->next(*this);
+        map.notifier()->next(*this);
         return *this;
       }
@@ -146 +144 @@
 
     protected:
-      const Map* map;
+      const Map& map;
     };
 
@@ -153 +151 @@
 
     public:
-      ItemIt() : map(NULL) {}
-
-
-      ItemIt(Invalid i) : Parent(i), map(NULL) {}
-
-      explicit ItemIt(Map& _map) : map(&_map) {
-        map->notifier()->first(*this);
+
+      ItemIt() {}
+
+      ItemIt(Invalid i) : Parent(i) { }
+
+      explicit ItemIt(Map& _map) : map(_map) {
+        map.notifier()->first(*this);
       }
 
       ItemIt(const Map& _map, const Item& item)
-        : Parent(item), map(&_map) {}
+        : Parent(item), map(_map) {}
 
       ItemIt& operator++() {
-        map->notifier()->next(*this);
-        return *this;
-      }
-
-    protected:
-      const Map* map;
+        map.notifier()->next(*this);
+        return *this;
+      }
+
+    protected:
+      const Map& map;
 
     };
@@ -194 +192 @@
     typedef typename Parent::ConstReference ConstReference;
 
-    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
-
     class MapIt;
     class ConstMapIt;
@@ -232 +228 @@
       typedef typename Map::Value Value;
 
-      MapIt() : map(NULL) {}
-
-      MapIt(Invalid i) : Parent(i), map(NULL) { }
-
-      explicit MapIt(Map& _map) : map(&_map) {
-        map->graph.first(*this);
+      MapIt() {}
+
+      MapIt(Invalid i) : Parent(i) { }
+
+      explicit MapIt(Map& _map) : map(_map) {
+        map.graph.first(*this);
       }
 
       MapIt(const Map& _map, const Item& item)
-        : Parent(item), map(&_map) {}
+        : Parent(item), map(_map) {}
 
       MapIt& operator++() {
-        map->graph.next(*this);
+        map.graph.next(*this);
         return *this;
       }
 
       typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return (*map)[*this];
+        return map[*this];
       }
 
       typename MapTraits<Map>::ReturnValue operator*() {
-        return (*map)[*this];
+        return map[*this];
       }
 
       void set(const Value& value) {
-        map->set(*this, value);
-      }
-
-    protected:
-      Map* map;
+        map.set(*this, value);
+      }
+
+    protected:
+      Map& map;
 
     };
@@ -272 +268 @@
       typedef typename Map::Value Value;
 
-      ConstMapIt() : map(NULL) {}
-
-      ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
-
-      explicit ConstMapIt(Map& _map) : map(&_map) {
-        map->graph.first(*this);
+      ConstMapIt() {}
+
+      ConstMapIt(Invalid i) : Parent(i) { }
+
+      explicit ConstMapIt(Map& _map) : map(_map) {
+        map.graph.first(*this);
       }
 
       ConstMapIt(const Map& _map, const Item& item)
-        : Parent(item), map(&_map) {}
+        : Parent(item), map(_map) {}
 
       ConstMapIt& operator++() {
-        map->graph.next(*this);
+        map.graph.next(*this);
         return *this;
       }
 
       typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return (*map)[*this];
-      }
-
-    protected:
-      const Map* map;
+        return map[*this];
+      }
+
+    protected:
+      const Map& map;
     };
 
@@ -300 +296 @@
 
     public:
-      ItemIt() : map(NULL) {}
-
-
-      ItemIt(Invalid i) : Parent(i), map(NULL) { }
-
-      explicit ItemIt(Map& _map) : map(&_map) {
-        map->graph.first(*this);
+
+      ItemIt() {}
+
+      ItemIt(Invalid i) : Parent(i) { }
+
+      explicit ItemIt(Map& _map) : map(_map) {
+        map.graph.first(*this);
       }
 
       ItemIt(const Map& _map, const Item& item)
-        : Parent(item), map(&_map) {}
+        : Parent(item), map(_map) {}
 
       ItemIt& operator++() {
-        map->graph.next(*this);
-        return *this;
-      }
-
-    protected:
-      const Map* map;
+        map.graph.next(*this);
+        return *this;
+      }
+
+    protected:
+      const Map& map;
 
     };

lemon/concepts/maps.h

@@ -183 +183 @@
       template<typename _ReferenceMap>
       struct Constraints {
-        typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
-        constraints() {
+        void constraints() {
           checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
           ref = m[key];

lemon/glpk.h

@@ -26 +26 @@
 #include <lemon/lp_base.h>
 
+// forward declaration
+#if !defined _GLP_PROB && !defined GLP_PROB
+#define _GLP_PROB
+#define GLP_PROB
+typedef struct { double _opaque_prob; } glp_prob;
+/* LP/MIP problem object */
+#endif
+
 namespace lemon {
 
-  namespace _solver_bits {
-    class VoidPtr {
-    private:
-      void *_ptr;      
-    public:
-      VoidPtr() : _ptr(0) {}
-
-      template <typename T>
-      VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {}
-
-      template <typename T>
-      VoidPtr& operator=(T* ptr) { 
-        _ptr = reinterpret_cast<void*>(ptr); 
-        return *this;
-      }
-
-      template <typename T>
-      operator T*() const { return reinterpret_cast<T*>(_ptr); }
-    };
-  }
 
   /// \brief Base interface for the GLPK LP and MIP solver
@@ -56 +44 @@
   protected:
 
-    _solver_bits::VoidPtr lp;
+    typedef glp_prob LPX;
+    glp_prob* lp;
 
     GlpkBase();
@@ -134 +123 @@
 
     ///Pointer to the underlying GLPK data structure.
-    _solver_bits::VoidPtr lpx() {return lp;}
+    LPX *lpx() {return lp;}
     ///Const pointer to the underlying GLPK data structure.
-    _solver_bits::VoidPtr lpx() const {return lp;}
+    const LPX *lpx() const {return lp;}
 
     ///Returns the constraint identifier understood by GLPK.

lemon/path.h

@@ -71 +71 @@
     template <typename CPath>
     Path(const CPath& cpath) {
-      pathCopy(cpath, *this);
+      copyPath(*this, cpath);
     }
 
@@ -79 +79 @@
     template <typename CPath>
     Path& operator=(const CPath& cpath) {
-      pathCopy(cpath, *this);
+      copyPath(*this, cpath);
       return *this;
     }
@@ -259 +259 @@
     template <typename CPath>
     SimplePath(const CPath& cpath) {
-      pathCopy(cpath, *this);
+      copyPath(*this, cpath);
     }
 
@@ -268 +268 @@
     template <typename CPath>
     SimplePath& operator=(const CPath& cpath) {
-      pathCopy(cpath, *this);
+      copyPath(*this, cpath);
       return *this;
     }
@@ -438 +438 @@
     template <typename CPath>
     ListPath(const CPath& cpath) : first(0), last(0) {
-      pathCopy(cpath, *this);
+      copyPath(*this, cpath);
     }
 
@@ -454 +454 @@
     template <typename CPath>
     ListPath& operator=(const CPath& cpath) {
-      pathCopy(cpath, *this);
+      copyPath(*this, cpath);
       return *this;
     }
@@ -764 +764 @@
     template <typename CPath>
     StaticPath(const CPath& cpath) : arcs(0) {
-      pathCopy(cpath, *this);
+      copyPath(*this, cpath);
     }
 
@@ -780 +780 @@
     template <typename CPath>
     StaticPath& operator=(const CPath& cpath) {
-      pathCopy(cpath, *this);
+      copyPath(*this, cpath);
       return *this;
     }
@@ -929 +929 @@
     };
 
-    template <typename From, typename To,
-              bool buildEnable = BuildTagIndicator<To>::value>
+    template <typename Target, typename Source,
+              bool buildEnable = BuildTagIndicator<Target>::value>
     struct PathCopySelectorForward {
-      static void copy(const From& from, To& to) {
-        to.clear();
-        for (typename From::ArcIt it(from); it != INVALID; ++it) {
-          to.addBack(it);
+      static void copy(Target& target, const Source& source) {
+        target.clear();
+        for (typename Source::ArcIt it(source); it != INVALID; ++it) {
+          target.addBack(it);
         }
       }
     };
 
-    template <typename From, typename To>
-    struct PathCopySelectorForward<From, To, true> {
-      static void copy(const From& from, To& to) {
-        to.clear();
-        to.build(from);
-      }
-    };
-
-    template <typename From, typename To,
-              bool buildEnable = BuildTagIndicator<To>::value>
+    template <typename Target, typename Source>
+    struct PathCopySelectorForward<Target, Source, true> {
+      static void copy(Target& target, const Source& source) {
+        target.clear();
+        target.build(source);
+      }
+    };
+
+    template <typename Target, typename Source,
+              bool buildEnable = BuildTagIndicator<Target>::value>
     struct PathCopySelectorBackward {
-      static void copy(const From& from, To& to) {
-        to.clear();
-        for (typename From::RevArcIt it(from); it != INVALID; ++it) {
-          to.addFront(it);
+      static void copy(Target& target, const Source& source) {
+        target.clear();
+        for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
+          target.addFront(it);
         }
       }
     };
 
-    template <typename From, typename To>
-    struct PathCopySelectorBackward<From, To, true> {
-      static void copy(const From& from, To& to) {
-        to.clear();
-        to.buildRev(from);
+    template <typename Target, typename Source>
+    struct PathCopySelectorBackward<Target, Source, true> {
+      static void copy(Target& target, const Source& source) {
+        target.clear();
+        target.buildRev(source);
       }
     };
 
     
-    template <typename From, typename To,
-              bool revEnable = RevPathTagIndicator<From>::value>
+    template <typename Target, typename Source,
+              bool revEnable = RevPathTagIndicator<Source>::value>
     struct PathCopySelector {
-      static void copy(const From& from, To& to) {
-        PathCopySelectorForward<From, To>::copy(from, to);
+      static void copy(Target& target, const Source& source) {
+        PathCopySelectorForward<Target, Source>::copy(target, source);
       }      
     };
 
-    template <typename From, typename To>
-    struct PathCopySelector<From, To, true> {
-      static void copy(const From& from, To& to) {
-        PathCopySelectorBackward<From, To>::copy(from, to);
+    template <typename Target, typename Source>
+    struct PathCopySelector<Target, Source, true> {
+      static void copy(Target& target, const Source& source) {
+        PathCopySelectorBackward<Target, Source>::copy(target, source);
       }      
     };
@@ -988 +988 @@
   /// \brief Make a copy of a path.
   ///
-  /// This function makes a copy of a path.
-  template <typename From, typename To>
-  void pathCopy(const From& from, To& to) {
-    checkConcept<concepts::PathDumper<typename From::Digraph>, From>();
-    _path_bits::PathCopySelector<From, To>::copy(from, to);
-  }
-
-  /// \brief Deprecated version of \ref pathCopy().
-  ///
-  /// Deprecated version of \ref pathCopy() (only for reverse compatibility).
-  template <typename To, typename From>
-  void copyPath(To& to, const From& from) {
-    pathCopy(from, to);
+  ///  This function makes a copy of a path.
+  template <typename Target, typename Source>
+  void copyPath(Target& target, const Source& source) {
+    checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
+    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
   }
 
@@ -1024 +1016 @@
   /// \brief The source of a path
   ///
-  /// This function returns the source node of the given path.
-  /// If the path is empty, then it returns \c INVALID.
+  /// This function returns the source of the given path.
   template <typename Digraph, typename Path>
   typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
-    return path.empty() ? INVALID : digraph.source(path.front());
+    return digraph.source(path.front());
   }
 
   /// \brief The target of a path
   ///
-  /// This function returns the target node of the given path.
-  /// If the path is empty, then it returns \c INVALID.
+  /// This function returns the target of the given path.
   template <typename Digraph, typename Path>
   typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
-    return path.empty() ? INVALID : digraph.target(path.back());
+    return digraph.target(path.back());
   }
 

test/heap_test.cc

@@ -32 +32 @@
 
 #include <lemon/bin_heap.h>
-#include <lemon/fib_heap.h>
-#include <lemon/radix_heap.h>
-#include <lemon/bucket_heap.h>
 
 #include "test_tools.h"
@@ -187 +184 @@
   }
 
-  {
-    typedef FibHeap<Prio, ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>();
-    heapIncreaseTest<IntHeap>();
-
-    typedef FibHeap<Prio, IntNodeMap > NodeHeap;
-    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
-    dijkstraHeapTest<NodeHeap>(digraph, length, source);
-  }
-
-  {
-    typedef RadixHeap<ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>();
-    heapIncreaseTest<IntHeap>();
-
-    typedef RadixHeap<IntNodeMap > NodeHeap;
-    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
-    dijkstraHeapTest<NodeHeap>(digraph, length, source);
-  }
-
-  {
-    typedef BucketHeap<ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>();
-    heapIncreaseTest<IntHeap>();
-
-    typedef BucketHeap<IntNodeMap > NodeHeap;
-    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
-    dijkstraHeapTest<NodeHeap>(digraph, length, source);
-  }
-
-
   return 0;
 }