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