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