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

@@ -59,9 +59,9 @@
 			lemon/assert.h \
 			lemon/bellman_ford.h \
 			lemon/bfs.h \
 			lemon/bin_heap.h \
-			lemon/binom_heap.h \
+			lemon/binomial_heap.h \
 			lemon/bucket_heap.h \
 			lemon/capacity_scaling.h \
 			lemon/cbc.h \
 			lemon/circulation.h \
@@ -74,17 +74,17 @@
 			lemon/counter.h \
 			lemon/cplex.h \
 			lemon/cycle_canceling.h \
 			lemon/dfs.h \
 			lemon/dheap.h \
 			lemon/dijkstra.h \
 			lemon/dim2.h \
 			lemon/dimacs.h \
 			lemon/edge_set.h \
 			lemon/elevator.h \
 			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 \
@@ -92,9 +92,8 @@
 			lemon/hartmann_orlin.h \
 			lemon/howard.h \
 			lemon/hypercube_graph.h \
 			lemon/karp.h \
 			lemon/kary_heap.h \
 			lemon/kruskal.h \
 			lemon/hao_orlin.h \
 			lemon/lgf_reader.h \
 			lemon/lgf_writer.h \
@@ -111,8 +110,9 @@
 			lemon/pairing_heap.h \
 			lemon/path.h \
 			lemon/planarity.h \
 			lemon/preflow.h \
 			lemon/quad_heap.h \
 			lemon/radix_heap.h \
 			lemon/radix_sort.h \
 			lemon/random.h \
 			lemon/smart_graph.h \

lemon/binomial_heap.h

Show inline comments

@@ -15,10 +15,10 @@
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BINOM_HEAP_H
 		#define LEMON_BINOM_HEAP_H
 		#ifndef LEMON_BINOMIAL_HEAP_H
 		#define LEMON_BINOMIAL_HEAP_H
 		///\file
 		///\ingroup heaps
 		///\brief Binomial Heap implementation.
@@ -52,9 +52,9 @@
 		  template <typename PR, typename IM, typename CMP>
 		#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;
 		    /// Type of the priorities.
@@ -93,9 +93,9 @@
 		    /// Constructor.
 		    /// \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.
 		    ///
@@ -103,9 +103,9 @@
 		    /// \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.
 		    /// \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.
 		    ///
@@ -423,9 +423,9 @@
 		  private:
 		    class Store {
-		      friend class BinomHeap;
+		      friend class BinomialHeap;
 		      Item name;
 		      int parent;
 		      int right_neighbor;
@@ -440,6 +440,6 @@
 		  };
 		} //namespace lemon
-		#endif //LEMON_BINOM_HEAP_H
+		#endif //LEMON_BINOMIAL_HEAP_H

lemon/dheap.h

Show inline comments

@@ -15,14 +15,14 @@
 		 * purpose.
+		 *
 		 */
 		#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>
 		#include <functional>
@@ -30,23 +30,23 @@
 		namespace lemon {
 		  /// \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.
 		  /// \tparam CMP A functor class for comparing the priorities.
@@ -54,14 +54,14 @@
 		  ///
 		  ///\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;
 		    /// Type of the priorities.
@@ -98,18 +98,18 @@
 		    /// Constructor.
 		    /// \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.
 		    ///
 		    /// Constructor.
 		    /// \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.
 		    /// \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.
 		    ///
@@ -130,10 +130,10 @@
 		    /// for each item.
 		    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);
+		    }
@@ -150,11 +150,11 @@
 		    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;
+		          }
 		          if( !less(_data[min], p) )
@@ -344,9 +344,9 @@
 		      _iim.set(j, idx);
 		      _data[idx].first=j;
+		    }
-		  }; // class KaryHeap
+		  }; // class DHeap
 		} // namespace lemon
-		#endif // LEMON_KARY_HEAP_H
+		#endif // LEMON_DHEAP_H

lemon/quad_heap.h

Show inline comments

@@ -15,14 +15,14 @@
 		 * purpose.
+		 *
 		 */
 		#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>
 		#include <functional>
@@ -30,15 +30,16 @@
 		namespace lemon {
 		  /// \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.
 		  /// \tparam IM A read-writable item map with \c int values, used
@@ -46,15 +47,15 @@
 		  /// \tparam CMP A functor class for comparing the priorities.
 		  /// 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;
 		    /// Type of the priorities.
@@ -91,18 +92,18 @@
 		    /// Constructor.
 		    /// \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.
 		    ///
 		    /// Constructor.
 		    /// \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.
 		    /// \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.
 		    ///
@@ -334,9 +335,9 @@
 		      _iim.set(j, idx);
 		      _data[idx].first = j;
+		    }
-		  }; // class FouraryHeap
+		  }; // class QuadHeap
 		} // namespace lemon
 		#endif // LEMON_FOURARY_HEAP_H

test/heap_test.cc

Show inline comments

@@ -29,14 +29,14 @@
 		#include <lemon/dijkstra.h>
 		#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"
@@ -184,28 +184,28 @@
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    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);
+		  }
@@ -244,16 +244,16 @@
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    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);
+		  }

0 comments (0 inline)

RhodeCode

Login to your account