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

Files:

• lemon/Makefile.am (modified) (3 diffs)
• lemon/bin_heap.h (modified) (3 diffs)
• lemon/bits/map_extender.h (modified) (8 diffs)
• lemon/bucket_heap.h (added)
• lemon/concepts/maps.h (modified) (1 diff)
• lemon/fib_heap.h (added)
• lemon/glpk.h (modified) (3 diffs)
• lemon/path.h (modified) (11 diffs)
• lemon/radix_heap.h (added)
• 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 \
@@ -77 +78 @@
         lemon/error.h \
         lemon/euler.h \
+        lemon/fib_heap.h \
         lemon/full_graph.h \
         lemon/glpk.h \
@@ -100 +102 @@
         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 Comp specifies the ordering of the priorities.
+  ///priority is efficient. \c CMP 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 Comp A functor class for the ordering of the priorities.
+  ///\tparam CMP 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 Comp = std::less<PR> >
+  template <typename PR, typename IM, typename CMP = std::less<PR> >
   class BinHeap {
 
@@ -63 +63 @@
     typedef std::pair<Item,Prio> Pair;
     ///\e
-    typedef Comp Compare;
+    typedef CMP 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;
@@ -83 +85 @@
       typedef typename Map::Value Value;
 
-      MapIt() {}
-
-      MapIt(Invalid i) : Parent(i) { }
-
-      explicit MapIt(Map& _map) : map(_map) {
-        map.notifier()->first(*this);
+      MapIt() : map(NULL) {}
+
+      MapIt(Invalid i) : Parent(i), map(NULL) {}
+
+      explicit MapIt(Map& _map) : map(&_map) {
+        map->notifier()->first(*this);
       }
 
       MapIt(const Map& _map, const Item& item)
+        : Parent(item), map(&_map) {}
+
+      MapIt& operator++() {
+        map->notifier()->next(*this);
+        return *this;
+      }
+
+      typename MapTraits<Map>::ConstReturnValue operator*() const {
+        return (*map)[*this];
+      }
+
+      typename MapTraits<Map>::ReturnValue operator*() {
+        return (*map)[*this];
+      }
+
+      void set(const Value& value) {
+        map->set(*this, value);
+      }
+
+    protected:
+      Map* map;
+
+    };
+
+    class ConstMapIt : public Item {
+      typedef Item Parent;
+
+    public:
+
+      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(const Map& _map, const Item& item)
         : Parent(item), map(_map) {}
 
-      MapIt& operator++() {
-        map.notifier()->next(*this);
+      ConstMapIt& operator++() {
+        map->notifier()->next(*this);
         return *this;
       }
@@ -103 +145 @@
       }
 
-      typename MapTraits<Map>::ReturnValue operator*() {
-        return map[*this];
-      }
-
-      void set(const Value& value) {
-        map.set(*this, value);
-      }
-
-    protected:
-      Map& map;
-
-    };
-
-    class ConstMapIt : public Item {
-      typedef Item Parent;
-
-    public:
-
-      typedef typename Map::Value Value;
-
-      ConstMapIt() {}
-
-      ConstMapIt(Invalid i) : Parent(i) { }
-
-      explicit ConstMapIt(Map& _map) : map(_map) {
-        map.notifier()->first(*this);
-      }
-
-      ConstMapIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
-
-      ConstMapIt& operator++() {
-        map.notifier()->next(*this);
-        return *this;
-      }
-
-      typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return map[*this];
-      }
-
-    protected:
-      const Map& map;
+    protected:
+      const Map* map;
     };
 
@@ -151 +153 @@
 
     public:
-
-      ItemIt() {}
-
-      ItemIt(Invalid i) : Parent(i) { }
-
-      explicit ItemIt(Map& _map) : map(_map) {
-        map.notifier()->first(*this);
+      ItemIt() : map(NULL) {}
+
+
+      ItemIt(Invalid i) : Parent(i), map(NULL) {}
+
+      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;
 
     };
@@ -192 +194 @@
     typedef typename Parent::ConstReference ConstReference;
 
+    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
+
     class MapIt;
     class ConstMapIt;
@@ -228 +232 @@
       typedef typename Map::Value Value;
 
-      MapIt() {}
-
-      MapIt(Invalid i) : Parent(i) { }
-
-      explicit MapIt(Map& _map) : map(_map) {
-        map.graph.first(*this);
+      MapIt() : map(NULL) {}
+
+      MapIt(Invalid i) : Parent(i), map(NULL) { }
+
+      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;
 
     };
@@ -268 +272 @@
       typedef typename Map::Value Value;
 
-      ConstMapIt() {}
-
-      ConstMapIt(Invalid i) : Parent(i) { }
-
-      explicit ConstMapIt(Map& _map) : map(_map) {
-        map.graph.first(*this);
+      ConstMapIt() : map(NULL) {}
+
+      ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
+
+      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;
     };
 
@@ -296 +300 @@
 
     public:
-
-      ItemIt() {}
-
-      ItemIt(Invalid i) : Parent(i) { }
-
-      explicit ItemIt(Map& _map) : map(_map) {
-        map.graph.first(*this);
+      ItemIt() : map(NULL) {}
+
+
+      ItemIt(Invalid i) : Parent(i), map(NULL) { }
+
+      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 {
-        void constraints() {
+        typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
+        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
@@ -44 +56 @@
   protected:
 
-    typedef glp_prob LPX;
-    glp_prob* lp;
+    _solver_bits::VoidPtr lp;
 
     GlpkBase();
@@ -123 +134 @@
 
     ///Pointer to the underlying GLPK data structure.
-    LPX *lpx() {return lp;}
+    _solver_bits::VoidPtr lpx() {return lp;}
     ///Const pointer to the underlying GLPK data structure.
-    const LPX *lpx() const {return lp;}
+    _solver_bits::VoidPtr lpx() const {return lp;}
 
     ///Returns the constraint identifier understood by GLPK.

lemon/path.h

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