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