diff -r d8475431bbbb -r 8e85e6bbefdf src/lemon/concept/heap.h --- a/src/lemon/concept/heap.h Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,201 +0,0 @@ -/* -*- C++ -*- - * src/lemon/concept/heap.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -///\ingroup concept -///\file -///\brief Classes for representing heaps. -/// - -#ifndef LEMON_CONCEPT_HEAP_H -#define LEMON_CONCEPT_HEAP_H - -#include - -namespace lemon { - namespace concept { - /// \addtogroup concept - /// @{ - - - /// \brief A concept structure describes the main interface of heaps. - /// - /// A concept structure describes the main interface of heaps. - /// - template - class Heap { - public: - - - /// \brief Type to represent the items states. - /// - /// Each Item element have a state associated to it. It may be "in heap", - /// "pre heap" or "post heap". The later two are indifferent from the - /// heap's point of view, but may be useful to the user. - /// - /// The ItemIntMap _should_ be initialized in such way, that it maps - /// PRE_HEAP (-1) to any element to be put in the heap... - enum state_enum { - IN_HEAP = 0, - PRE_HEAP = -1, - POST_HEAP = -2 - }; - - /// \brief The constructor. - /// - /// The constructor. - /// \param _iim should be given to the constructor, since it is used - /// internally to handle the cross references. The value of the map - /// should be PRE_HEAP (-1) for each element. - explicit Heap(ItemIntMap &_iim) {} - - /// The number of items stored in the heap. - /// - /// \brief Returns the number of items stored in the heap. - int size() const { return 0; } - /// \brief Checks if the heap stores no items. - /// - /// Returns \c true if and only if the heap stores no items. - bool empty() const { return false; } - - /// \brief Insert an item into the heap with the given heap. - /// - /// Adds \c i to the heap with priority \c p. - /// \param i The item to insert. - /// \param p The priority of the item. - void push(const Item &i, const Prio &p) {} - - /// \brief Returns the item with minimum priority. - /// - /// This method returns the item with minimum priority. - /// \pre The heap must be nonempty. - Item top() const {} - - /// \brief Returns the minimum priority. - /// - /// It returns the minimum priority. - /// \pre The heap must be nonempty. - Prio prio() const {} - - /// \brief Deletes the item with minimum priority. - /// - /// This method deletes the item with minimum priority. - /// \pre The heap must be non-empty. - void pop() {} - - /// \brief Deletes \c i from the heap. - /// - /// This method deletes item \c i from the heap, if \c i was - /// already stored in the heap. - /// \param i The item to erase. - void erase(const Item &i) {} - - /// \brief Returns the priority of \c i. - /// - /// This function returns the priority of item \c i. - /// \pre \c i must be in the heap. - /// \param i The item. - Prio operator[](const Item &i) const {} - - /// \brief \c i gets to the heap with priority \c p independently - /// if \c i was already there. - /// - /// This method calls \ref push(\c i, \c p) if \c i is not stored - /// in the heap and sets the priority of \c i to \c p otherwise. - /// It may throw an \e UnderFlowPriorityException. - /// \param i The item. - /// \param p The priority. - void set(const Item &i, const Prio &p) {} - - /// \brief Decreases the priority of \c i to \c p. - /// - /// This method decreases the priority of item \c i to \c p. - /// \pre \c i must be stored in the heap with priority at least \c p. - /// \param i The item. - /// \param p The priority. - void decrease(const Item &i, const Prio &p) {} - - /// \brief Increases the priority of \c i to \c p. - /// - /// This method sets the priority of item \c i to \c p. - /// \pre \c i must be stored in the heap with priority at most \c - /// p relative to \c Compare. - /// \param i The item. - /// \param p The priority. - void increase(const Item &i, const Prio &p) {} - - /// \brief Returns if \c item is in, has already been in, or has - /// never been in the heap. - /// - /// This method returns PRE_HEAP if \c item has never been in the - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP - /// otherwise. In the latter case it is possible that \c item will - /// get back to the heap again. - /// \param i The item. - state_enum state(const Item &i) const {} - - - template - struct Constraints { - public: - - void constraints() { - Item item; - Prio prio; - - ignore_unused_variable_warning(item); - ignore_unused_variable_warning(prio); - - typedef typename _Heap::state_enum state_enum; - state_enum state; - - ignore_unused_variable_warning(state); - - _Heap heap1 = _Heap(map); - - ignore_unused_variable_warning(heap1); - - heap.push(item, prio); - - prio = heap.prio(); - item = heap.top(); - - heap.pop(); - - heap.set(item, prio); - heap.decrease(item, prio); - heap.increase(item, prio); - prio = heap[item]; - - heap.erase(item); - - state = heap.state(item); - - state = _Heap::PRE_HEAP; - state = _Heap::IN_HEAP; - state = _Heap::POST_HEAP; - } - - _Heap& heap; - ItemIntMap& map; - - Constraints() : heap(0), map(0) {} - }; - }; - - /// @} - } // namespace lemon -} -#endif // LEMON_CONCEPT_PATH_H