# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 2009-09-29 13:32:01
# Node ID 65a0521e744e683924d5aff918686b3773c11822
# Parent  0977046c60d27196e3b008fe9f65350180ec5362

Rename heap structures (#301)

 - KaryHeap --> DHeap
 - FouraryHeap --> QuadHeap
 - BinomHeap --> BinomialHeap

diff --git a/lemon/Makefile.am b/lemon/Makefile.am
--- a/lemon/Makefile.am
+++ b/lemon/Makefile.am
@@ -60,7 +60,7 @@
 	lemon/bellman_ford.h \
 	lemon/bfs.h \
 	lemon/bin_heap.h \
-	lemon/binom_heap.h \
+	lemon/binomial_heap.h \
 	lemon/bucket_heap.h \
 	lemon/cbc.h \
 	lemon/circulation.h \
@@ -72,6 +72,7 @@
 	lemon/core.h \
 	lemon/cplex.h \
 	lemon/dfs.h \
+	lemon/dheap.h \
 	lemon/dijkstra.h \
 	lemon/dim2.h \
 	lemon/dimacs.h \
@@ -80,14 +81,12 @@
 	lemon/error.h \
 	lemon/euler.h \
 	lemon/fib_heap.h \
-	lemon/fourary_heap.h \
 	lemon/full_graph.h \
 	lemon/glpk.h \
 	lemon/gomory_hu.h \
 	lemon/graph_to_eps.h \
 	lemon/grid_graph.h \
 	lemon/hypercube_graph.h \
-	lemon/kary_heap.h \
 	lemon/kruskal.h \
 	lemon/hao_orlin.h \
 	lemon/lgf_reader.h \
@@ -105,6 +104,7 @@
 	lemon/pairing_heap.h \
 	lemon/path.h \
 	lemon/preflow.h \
+	lemon/quad_heap.h \
 	lemon/radix_heap.h \
 	lemon/radix_sort.h \
 	lemon/random.h \
diff --git a/lemon/binom_heap.h b/lemon/binomial_heap.h
rename from lemon/binom_heap.h
rename to lemon/binomial_heap.h
--- a/lemon/binom_heap.h
+++ b/lemon/binomial_heap.h
@@ -16,8 +16,8 @@
  *
  */
 
-#ifndef LEMON_BINOM_HEAP_H
-#define LEMON_BINOM_HEAP_H
+#ifndef LEMON_BINOMIAL_HEAP_H
+#define LEMON_BINOMIAL_HEAP_H
 
 ///\file
 ///\ingroup heaps
@@ -53,7 +53,7 @@
 #else
   template <typename PR, typename IM, typename CMP = std::less<PR> >
 #endif
-  class BinomHeap {
+  class BinomialHeap {
   public:
     /// Type of the item-int map.
     typedef IM ItemIntMap;
@@ -94,7 +94,7 @@
     /// \param map A map that assigns \c int values to the items.
     /// 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) {}
 
     /// \brief Constructor.
@@ -104,7 +104,7 @@
     /// It is used internally to handle the cross references.
     /// 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) {}
 
     /// \brief The number of items stored in the heap.
@@ -424,7 +424,7 @@
   private:
 
     class Store {
-      friend class BinomHeap;
+      friend class BinomialHeap;
 
       Item name;
       int parent;
@@ -441,5 +441,5 @@
 
 } //namespace lemon
 
-#endif //LEMON_BINOM_HEAP_H
+#endif //LEMON_BINOMIAL_HEAP_H
 
diff --git a/lemon/kary_heap.h b/lemon/dheap.h
rename from lemon/kary_heap.h
rename to lemon/dheap.h
--- a/lemon/kary_heap.h
+++ b/lemon/dheap.h
@@ -16,12 +16,12 @@
  *
  */
 
-#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>
 #include <utility>
@@ -31,21 +31,21 @@
 
   /// \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
   /// nodes of the heap could be performed faster.
@@ -55,12 +55,12 @@
   ///\sa BinHeap
   ///\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.
     typedef IM ItemIntMap;
@@ -99,7 +99,7 @@
     /// \param map A map that assigns \c int values to the items.
     /// 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.
     ///
@@ -108,7 +108,7 @@
     /// It is used internally to handle the cross references.
     /// 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) {}
 
     /// \brief The number of items stored in the heap.
@@ -131,8 +131,8 @@
     void clear() { _data.clear(); }
 
   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 {
       return _comp(p1.second, p2.second);
@@ -151,9 +151,9 @@
     void bubbleDown(int hole, Pair p, int length) {
       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;
           }
@@ -345,8 +345,8 @@
       _data[idx].first=j;
     }
 
-  }; // class KaryHeap
+  }; // class DHeap
 
 } // namespace lemon
 
-#endif // LEMON_KARY_HEAP_H
+#endif // LEMON_DHEAP_H
diff --git a/lemon/fourary_heap.h b/lemon/quad_heap.h
rename from lemon/fourary_heap.h
rename to lemon/quad_heap.h
--- a/lemon/fourary_heap.h
+++ b/lemon/quad_heap.h
@@ -16,12 +16,12 @@
  *
  */
 
-#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>
 #include <utility>
@@ -31,13 +31,14 @@
 
   /// \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.
   ///
   /// \tparam PR Type of the priorities of the items.
@@ -47,13 +48,13 @@
   /// The default is \c std::less<PR>.
   ///
   ///\sa BinHeap
-  ///\sa KaryHeap
+  ///\sa DHeap
 #ifdef DOXYGEN
   template <typename PR, typename IM, typename CMP>
 #else
   template <typename PR, typename IM, typename CMP = std::less<PR> >
 #endif
-  class FouraryHeap {
+  class QuadHeap {
   public:
     /// Type of the item-int map.
     typedef IM ItemIntMap;
@@ -92,7 +93,7 @@
     /// \param map A map that assigns \c int values to the items.
     /// 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.
     ///
@@ -101,7 +102,7 @@
     /// It is used internally to handle the cross references.
     /// 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) {}
 
     /// \brief The number of items stored in the heap.
@@ -335,7 +336,7 @@
       _data[idx].first = j;
     }
 
-  }; // class FouraryHeap
+  }; // class QuadHeap
 
 } // namespace lemon
 
diff --git a/test/heap_test.cc b/test/heap_test.cc
--- a/test/heap_test.cc
+++ b/test/heap_test.cc
@@ -30,12 +30,12 @@
 #include <lemon/maps.h>
 
 #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>
 
 #include "test_tools.h"
@@ -185,26 +185,26 @@
     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   }
 
-  // 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);
   }
@@ -245,14 +245,14 @@
     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   }
 
-  // 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);
   }