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

@@ -62,3 +62,3 @@
 			lemon/bin_heap.h \
-			lemon/binom_heap.h \
+			lemon/binomial_heap.h \
 			lemon/bucket_heap.h \
@@ -77,2 +77,3 @@
 			lemon/dfs.h \
 			lemon/dheap.h \
 			lemon/dijkstra.h \
@@ -85,3 +86,2 @@
 			lemon/fib_heap.h \
 			lemon/fourary_heap.h \
 			lemon/full_graph.h \
@@ -95,3 +95,2 @@
 			lemon/karp.h \
 			lemon/kary_heap.h \
 			lemon/kruskal.h \
@@ -114,2 +113,3 @@
 			lemon/preflow.h \
 			lemon/quad_heap.h \
 			lemon/radix_heap.h \

lemon/binomial_heap.h

Show inline comments

@@ -18,4 +18,4 @@
 		#ifndef LEMON_BINOM_HEAP_H
 		#define LEMON_BINOM_HEAP_H
 		#ifndef LEMON_BINOMIAL_HEAP_H
 		#define LEMON_BINOMIAL_HEAP_H
@@ -55,3 +55,3 @@
 		#endif
-		  class BinomHeap {
+		  class BinomialHeap {
 		  public:
@@ -96,3 +96,3 @@
 		    /// 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) {}
@@ -106,3 +106,3 @@
 		    /// \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) {}
@@ -426,3 +426,3 @@
 		    class Store {
-		      friend class BinomHeap;
+		      friend class BinomialHeap;
@@ -443,3 +443,3 @@
-		#endif //LEMON_BINOM_HEAP_H
+		#endif //LEMON_BINOMIAL_HEAP_H

lemon/dheap.h

Show inline comments

@@ -18,4 +18,4 @@
 		#ifndef LEMON_KARY_HEAP_H
 		#define LEMON_KARY_HEAP_H
 		#ifndef LEMON_DHEAP_H
 		#define LEMON_DHEAP_H
@@ -23,3 +23,3 @@
 		///\file
-		///\brief Fourary heap implementation.
+		///\brief D-ary heap implementation.
@@ -33,12 +33,12 @@
 		  ///
-		  ///\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.
 		  ///
@@ -47,3 +47,3 @@
 		  /// 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
@@ -57,8 +57,8 @@
 		#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:
@@ -101,3 +101,3 @@
 		    /// 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) {}
@@ -110,3 +110,3 @@
 		    /// \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) {}
@@ -133,4 +133,4 @@
 		  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; }
@@ -153,5 +153,5 @@
 		        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]) )
@@ -347,3 +347,3 @@
-		  }; // class KaryHeap
+		  }; // class DHeap
@@ -351,2 +351,2 @@
-		#endif // LEMON_KARY_HEAP_H
+		#endif // LEMON_DHEAP_H

lemon/quad_heap.h

Show inline comments

@@ -18,4 +18,4 @@
 		#ifndef LEMON_FOURARY_HEAP_H
 		#define LEMON_FOURARY_HEAP_H
 		#ifndef LEMON_QUAD_HEAP_H
 		#define LEMON_QUAD_HEAP_H
@@ -23,3 +23,3 @@
 		///\file
 		///\brief Fourary heap implementation.
+		///\brief Fourary (quaternary) heap implementation.
@@ -33,9 +33,10 @@
 		  ///
 		  ///\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.
@@ -49,3 +50,3 @@
 		  ///\sa BinHeap
-		  ///\sa KaryHeap
+		  ///\sa DHeap
 		#ifdef DOXYGEN
@@ -55,3 +56,3 @@
 		#endif
-		  class FouraryHeap {
+		  class QuadHeap {
 		  public:
@@ -94,3 +95,3 @@
 		    /// 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) {}
@@ -103,3 +104,3 @@
 		    /// \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) {}
@@ -337,3 +338,3 @@
-		  }; // class FouraryHeap
+		  }; // class QuadHeap

test/heap_test.cc

Show inline comments

@@ -32,4 +32,4 @@
 		#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>
@@ -37,3 +37,3 @@
 		#include <lemon/radix_heap.h>
-		#include <lemon/binom_heap.h>
+		#include <lemon/binomial_heap.h>
 		#include <lemon/bucket_heap.h>
@@ -187,5 +187,5 @@
-		  // FouraryHeap
+		  // QuadHeap
+		  {
-		    typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
+		    typedef QuadHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
@@ -194,3 +194,3 @@
-		    typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
+		    typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
@@ -199,5 +199,5 @@
-		  // KaryHeap
+		  // DHeap
+		  {
-		    typedef KaryHeap<Prio, ItemIntMap> IntHeap;
+		    typedef DHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
@@ -206,3 +206,3 @@
-		    typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
+		    typedef DHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
@@ -247,5 +247,5 @@
-		  // BinomHeap
+		  // BinomialHeap
+		  {
-		    typedef BinomHeap<Prio, ItemIntMap> IntHeap;
+		    typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
@@ -254,3 +254,3 @@
-		    typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
+		    typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

0 comments (0 inline)

RhodeCode

Login to your account