1.1 --- a/lemon/concepts/heap.h Fri Nov 13 12:33:33 2009 +0100
1.2 +++ b/lemon/concepts/heap.h Thu Dec 10 17:05:35 2009 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2008
1.8 + * Copyright (C) 2003-2009
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -20,10 +20,11 @@
1.13 ///\file
1.14 ///\brief The concept of heaps.
1.15
1.16 -#ifndef LEMON_CONCEPT_HEAP_H
1.17 -#define LEMON_CONCEPT_HEAP_H
1.18 +#ifndef LEMON_CONCEPTS_HEAP_H
1.19 +#define LEMON_CONCEPTS_HEAP_H
1.20
1.21 #include <lemon/core.h>
1.22 +#include <lemon/concept_check.h>
1.23
1.24 namespace lemon {
1.25
1.26 @@ -34,17 +35,32 @@
1.27
1.28 /// \brief The heap concept.
1.29 ///
1.30 - /// Concept class describing the main interface of heaps.
1.31 - template <typename Priority, typename ItemIntMap>
1.32 + /// Concept class describing the main interface of heaps. A \e heap
1.33 + /// is a data structure for storing items with specified values called
1.34 + /// \e priorities in such a way that finding the item with minimum
1.35 + /// priority is efficient. In a heap one can change the priority of an
1.36 + /// item, add or erase an item, etc.
1.37 + ///
1.38 + /// \tparam PR Type of the priority of the items.
1.39 + /// \tparam IM A read and writable item map with int values, used
1.40 + /// internally to handle the cross references.
1.41 + /// \tparam Comp A functor class for the ordering of the priorities.
1.42 + /// The default is \c std::less<PR>.
1.43 +#ifdef DOXYGEN
1.44 + template <typename PR, typename IM, typename Comp = std::less<PR> >
1.45 +#else
1.46 + template <typename PR, typename IM>
1.47 +#endif
1.48 class Heap {
1.49 public:
1.50
1.51 + /// Type of the item-int map.
1.52 + typedef IM ItemIntMap;
1.53 + /// Type of the priorities.
1.54 + typedef PR Prio;
1.55 /// Type of the items stored in the heap.
1.56 typedef typename ItemIntMap::Key Item;
1.57
1.58 - /// Type of the priorities.
1.59 - typedef Priority Prio;
1.60 -
1.61 /// \brief Type to represent the states of the items.
1.62 ///
1.63 /// Each item has a state associated to it. It can be "in heap",
1.64 @@ -52,12 +68,12 @@
1.65 /// from the point of view of the heap, but may be useful for
1.66 /// the user.
1.67 ///
1.68 - /// The \c ItemIntMap must be initialized in such a way, that it
1.69 - /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
1.70 + /// The item-int map must be initialized in such way that it assigns
1.71 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
1.72 enum State {
1.73 - IN_HEAP = 0,
1.74 - PRE_HEAP = -1,
1.75 - POST_HEAP = -2
1.76 + IN_HEAP = 0, ///< = 0. The "in heap" state constant.
1.77 + PRE_HEAP = -1, ///< = -1. The "pre heap" state constant.
1.78 + POST_HEAP = -2 ///< = -2. The "post heap" state constant.
1.79 };
1.80
1.81 /// \brief The constructor.
1.82 @@ -118,8 +134,8 @@
1.83 /// \brief The priority of an item.
1.84 ///
1.85 /// Returns the priority of the given item.
1.86 + /// \param i The item.
1.87 /// \pre \c i must be in the heap.
1.88 - /// \param i The item.
1.89 Prio operator[](const Item &i) const {}
1.90
1.91 /// \brief Sets the priority of an item or inserts it, if it is
1.92 @@ -136,17 +152,17 @@
1.93 /// \brief Decreases the priority of an item to the given value.
1.94 ///
1.95 /// Decreases the priority of an item to the given value.
1.96 - /// \pre \c i must be stored in the heap with priority at least \c p.
1.97 /// \param i The item.
1.98 /// \param p The priority.
1.99 + /// \pre \c i must be stored in the heap with priority at least \c p.
1.100 void decrease(const Item &i, const Prio &p) {}
1.101
1.102 /// \brief Increases the priority of an item to the given value.
1.103 ///
1.104 /// Increases the priority of an item to the given value.
1.105 - /// \pre \c i must be stored in the heap with priority at most \c p.
1.106 /// \param i The item.
1.107 /// \param p The priority.
1.108 + /// \pre \c i must be stored in the heap with priority at most \c p.
1.109 void increase(const Item &i, const Prio &p) {}
1.110
1.111 /// \brief Returns if an item is in, has already been in, or has
1.112 @@ -242,4 +258,4 @@
1.113 /// @}
1.114 } // namespace lemon
1.115 }
1.116 -#endif // LEMON_CONCEPT_PATH_H
1.117 +#endif