LEMON/LEMON-official Changeset - r949:ac5f72c48367

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r949:ac5f72c48367

« 911:65a052
« 948:9f6ed8

951:ab21ca »

r949:ac5f72c48367

Wed, 03 Mar 2010 18:22:13

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge #301

3 2 3

merge default

4 files changed with 56 insertions and 55 deletions:

lemon/Makefile.am

lemon/binomial_heap.h

lemon/dheap.h

lemon/quad_heap.h

test/heap_test.cc

↑ Collapse diff ↑

lemon/Makefile.am

Show inline comments

@@ -61,5 +61,5 @@
 			lemon/bfs.h \
 			lemon/bin_heap.h \
-			lemon/binom_heap.h \
+			lemon/binomial_heap.h \
 			lemon/bucket_heap.h \
 			lemon/capacity_scaling.h \
@@ -76,4 +76,5 @@
 			lemon/cycle_canceling.h \
 			lemon/dfs.h \
 			lemon/dheap.h \
 			lemon/dijkstra.h \
 			lemon/dim2.h \
@@ -84,5 +85,4 @@
 			lemon/euler.h \
 			lemon/fib_heap.h \
 			lemon/fourary_heap.h \
 			lemon/full_graph.h \
 			lemon/glpk.h \
@@ -94,5 +94,4 @@
 			lemon/hypercube_graph.h \
 			lemon/karp.h \
 			lemon/kary_heap.h \
 			lemon/kruskal.h \
 			lemon/hao_orlin.h \
@@ -113,4 +112,5 @@
 			lemon/planarity.h \
 			lemon/preflow.h \
 			lemon/quad_heap.h \
 			lemon/radix_heap.h \
 			lemon/radix_sort.h \

lemon/binomial_heap.h

Show inline comments

@@ -17,6 +17,6 @@
 		 */
 		#ifndef LEMON_BINOM_HEAP_H
 		#define LEMON_BINOM_HEAP_H
 		#ifndef LEMON_BINOMIAL_HEAP_H
 		#define LEMON_BINOMIAL_HEAP_H
 		///\file
@@ -54,5 +54,5 @@
 		  template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
-		  class BinomHeap {
+		  class BinomialHeap {
 		  public:
 		    /// Type of the item-int map.
@@ -95,5 +95,5 @@
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
-		    explicit BinomHeap(ItemIntMap &map)
+		    explicit BinomialHeap(ItemIntMap &map)
 		      : _min(0), _head(-1), _iim(map), _num_items(0) {}
@@ -105,5 +105,5 @@
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    /// \param comp The function object used for comparing the priorities.
-		    BinomHeap(ItemIntMap &map, const Compare &comp)
+		    BinomialHeap(ItemIntMap &map, const Compare &comp)
 		      : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
@@ -425,5 +425,5 @@
 		    class Store {
-		      friend class BinomHeap;
+		      friend class BinomialHeap;
 		      Item name;
@@ -442,4 +442,4 @@
 		} //namespace lemon
-		#endif //LEMON_BINOM_HEAP_H
+		#endif //LEMON_BINOMIAL_HEAP_H

lemon/dheap.h

Show inline comments

@@ -17,10 +17,10 @@
 		 */
 		#ifndef LEMON_KARY_HEAP_H
 		#define LEMON_KARY_HEAP_H
 		#ifndef LEMON_DHEAP_H
 		#define LEMON_DHEAP_H
 		///\ingroup heaps
 		///\file
-		///\brief Fourary heap implementation.
+		///\brief D-ary heap implementation.
 		#include <vector>
@@ -32,19 +32,19 @@
 		  /// \ingroup heaps
 		  ///
-		  ///\brief K-ary heap data structure.
+		  ///\brief D-ary heap data structure.
 		  ///
-		  /// This class implements the \e K-ary \e heap data structure.
+		  /// This class implements the \e D-ary \e heap data structure.
 		  /// It fully conforms to the \ref concepts::Heap "heap concept".
 		  ///
-		  /// The \ref KaryHeap "K-ary heap" is a generalization of the
+		  /// The \ref DHeap "D-ary heap" is a generalization of the
 		  /// \ref BinHeap "binary heap" structure, its nodes have at most
 		  /// \c K children, instead of two.
 		  /// \ref BinHeap and \ref FouraryHeap are specialized implementations
-		  /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively.
+		  /// \c D children, instead of two.
 		  /// \ref BinHeap and \ref QuadHeap are specialized implementations
 		  /// of this structure for <tt>D=2</tt> and <tt>D=4</tt>, respectively.
 		  ///
 		  /// \tparam PR Type of the priorities of the items.
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
-		  /// \tparam K The degree of the heap, each node have at most \e K
+		  /// \tparam D The degree of the heap, each node have at most \e D
 		  /// children. The default is 16. Powers of two are suggested to use
 		  /// so that the multiplications and divisions needed to traverse the
@@ -56,10 +56,10 @@
 		  ///\sa FouraryHeap
 		#ifdef DOXYGEN
-		  template <typename PR, typename IM, int K, typename CMP>
+		  template <typename PR, typename IM, int D, typename CMP>
 		#else
-		  template <typename PR, typename IM, int K = 16,
+		  template <typename PR, typename IM, int D = 16,
 		            typename CMP = std::less<PR> >
 		#endif
-		  class KaryHeap {
+		  class DHeap {
 		  public:
 		    /// Type of the item-int map.
@@ -100,5 +100,5 @@
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
-		    explicit KaryHeap(ItemIntMap &map) : _iim(map) {}
+		    explicit DHeap(ItemIntMap &map) : _iim(map) {}
 		    /// \brief Constructor.
@@ -109,5 +109,5 @@
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    /// \param comp The function object used for comparing the priorities.
-		    KaryHeap(ItemIntMap &map, const Compare &comp)
+		    DHeap(ItemIntMap &map, const Compare &comp)
 		      : _iim(map), _comp(comp) {}
@@ -132,6 +132,6 @@
 		  private:
 		    int parent(int i) { return (i-1)/K; }
 		    int firstChild(int i) { return K*i+1; }
 		    int parent(int i) { return (i-1)/D; }
 		    int firstChild(int i) { return D*i+1; }
 		    bool less(const Pair &p1, const Pair &p2) const {
@@ -152,7 +152,7 @@
 		      if( length>1 ) {
 		        int child = firstChild(hole);
-		        while( child+K<=length ) {
+		        while( child+D<=length ) {
 		          int min=child;
-		          for (int i=1; i<K; ++i) {
+		          for (int i=1; i<D; ++i) {
 		            if( less(_data[child+i], _data[min]) )
 		              min=child+i;
@@ -346,7 +346,7 @@
+		    }
-		  }; // class KaryHeap
+		  }; // class DHeap
 		} // namespace lemon
-		#endif // LEMON_KARY_HEAP_H
+		#endif // LEMON_DHEAP_H

lemon/quad_heap.h

Show inline comments

@@ -17,10 +17,10 @@
 		 */
 		#ifndef LEMON_FOURARY_HEAP_H
 		#define LEMON_FOURARY_HEAP_H
 		#ifndef LEMON_QUAD_HEAP_H
 		#define LEMON_QUAD_HEAP_H
 		///\ingroup heaps
 		///\file
 		///\brief Fourary heap implementation.
+		///\brief Fourary (quaternary) heap implementation.
 		#include <vector>
@@ -32,11 +32,12 @@
 		  /// \ingroup heaps
 		  ///
 		  ///\brief Fourary heap data structure.
+		  ///\brief Fourary (quaternary) heap data structure.
 		  ///
-		  /// This class implements the \e fourary \e heap data structure.
+		  /// This class implements the \e Fourary (\e quaternary) \e heap
 		  /// data structure.
 		  /// It fully conforms to the \ref concepts::Heap "heap concept".
 		  ///
 		  /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap"
 		  /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap",
 		  /// The fourary heap is a specialization of the \ref DHeap "D-ary heap"
 		  /// for <tt>D=4</tt>. It is similar to the \ref BinHeap "binary heap",
 		  /// but its nodes have at most four children, instead of two.
 		  ///
@@ -48,5 +49,5 @@
 		  ///
 		  ///\sa BinHeap
-		  ///\sa KaryHeap
+		  ///\sa DHeap
 		#ifdef DOXYGEN
 		  template <typename PR, typename IM, typename CMP>
@@ -54,5 +55,5 @@
 		  template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
-		  class FouraryHeap {
+		  class QuadHeap {
 		  public:
 		    /// Type of the item-int map.
@@ -93,5 +94,5 @@
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
-		    explicit FouraryHeap(ItemIntMap &map) : _iim(map) {}
+		    explicit QuadHeap(ItemIntMap &map) : _iim(map) {}
 		    /// \brief Constructor.
@@ -102,5 +103,5 @@
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    /// \param comp The function object used for comparing the priorities.
-		    FouraryHeap(ItemIntMap &map, const Compare &comp)
+		    QuadHeap(ItemIntMap &map, const Compare &comp)
 		      : _iim(map), _comp(comp) {}
@@ -336,5 +337,5 @@
+		    }
-		  }; // class FouraryHeap
+		  }; // class QuadHeap
 		} // namespace lemon

test/heap_test.cc

Show inline comments

@@ -31,10 +31,10 @@
 		#include <lemon/bin_heap.h>
 		#include <lemon/fourary_heap.h>
 		#include <lemon/kary_heap.h>
 		#include <lemon/quad_heap.h>
 		#include <lemon/dheap.h>
 		#include <lemon/fib_heap.h>
 		#include <lemon/pairing_heap.h>
 		#include <lemon/radix_heap.h>
-		#include <lemon/binom_heap.h>
+		#include <lemon/binomial_heap.h>
 		#include <lemon/bucket_heap.h>
@@ -186,24 +186,24 @@
+		  }
-		  // FouraryHeap
+		  // QuadHeap
+		  {
-		    typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
+		    typedef QuadHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
-		    typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
+		    typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
-		  // KaryHeap
+		  // DHeap
+		  {
-		    typedef KaryHeap<Prio, ItemIntMap> IntHeap;
+		    typedef DHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
-		    typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
+		    typedef DHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
@@ -246,12 +246,12 @@
+		  }
-		  // BinomHeap
+		  // BinomialHeap
+		  {
-		    typedef BinomHeap<Prio, ItemIntMap> IntHeap;
+		    typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
-		    typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
+		    typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);

0 comments (0 inline)

RhodeCode

Login to your account