alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@100: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. alpar@100: * alpar@877: * Copyright (C) 2003-2010 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: kpeter@709: #ifndef LEMON_CONCEPTS_HEAP_H kpeter@709: #define LEMON_CONCEPTS_HEAP_H kpeter@709: alpar@100: ///\ingroup concept alpar@100: ///\file kpeter@113: ///\brief The concept of heaps. alpar@100: deba@220: #include deba@519: #include alpar@100: alpar@100: namespace lemon { kpeter@113: alpar@100: namespace concepts { kpeter@113: alpar@100: /// \addtogroup concept alpar@100: /// @{ alpar@100: kpeter@113: /// \brief The heap concept. alpar@100: /// kpeter@709: /// This concept class describes the main interface of heaps. kpeter@710: /// The various \ref heaps "heap structures" are efficient kpeter@709: /// implementations of the abstract data type \e priority \e queue. kpeter@709: /// They store items with specified values called \e priorities kpeter@709: /// in such a way that finding and removing the item with minimum kpeter@709: /// priority are efficient. The basic operations are adding and kpeter@709: /// erasing items, changing the priority of an item, etc. kpeter@559: /// kpeter@709: /// Heaps are crucial in several algorithms, such as Dijkstra and Prim. kpeter@709: /// Any class that conforms to this concept can be used easily in such kpeter@709: /// algorithms. kpeter@709: /// kpeter@709: /// \tparam PR Type of the priorities of the items. kpeter@709: /// \tparam IM A read-writable item map with \c int values, used kpeter@559: /// internally to handle the cross references. kpeter@709: /// \tparam CMP A functor class for comparing the priorities. kpeter@559: /// The default is \c std::less. kpeter@559: #ifdef DOXYGEN kpeter@709: template kpeter@559: #else kpeter@709: template > kpeter@559: #endif alpar@100: class Heap { alpar@100: public: alpar@100: kpeter@559: /// Type of the item-int map. kpeter@559: typedef IM ItemIntMap; kpeter@559: /// Type of the priorities. kpeter@559: typedef PR Prio; kpeter@113: /// Type of the items stored in the heap. kpeter@113: typedef typename ItemIntMap::Key Item; alpar@100: kpeter@113: /// \brief Type to represent the states of the items. alpar@100: /// kpeter@113: /// Each item has a state associated to it. It can be "in heap", kpeter@709: /// "pre-heap" or "post-heap". The latter two are indifferent from the kpeter@709: /// heap's point of view, but may be useful to the user. alpar@100: /// kpeter@559: /// The item-int map must be initialized in such way that it assigns kpeter@559: /// \c PRE_HEAP (-1) to any element to be put in the heap. alpar@100: enum State { kpeter@584: IN_HEAP = 0, ///< = 0. The "in heap" state constant. kpeter@709: PRE_HEAP = -1, ///< = -1. The "pre-heap" state constant. kpeter@709: POST_HEAP = -2 ///< = -2. The "post-heap" state constant. alpar@100: }; alpar@209: kpeter@709: /// \brief Constructor. alpar@100: /// kpeter@709: /// Constructor. kpeter@113: /// \param map A map that assigns \c int values to keys of type kpeter@113: /// \c Item. It is used internally by the heap implementations to kpeter@113: /// handle the cross references. The assigned value must be kpeter@709: /// \c PRE_HEAP (-1) for each item. kpeter@817: #ifdef DOXYGEN kpeter@113: explicit Heap(ItemIntMap &map) {} kpeter@817: #else kpeter@817: explicit Heap(ItemIntMap&) {} alpar@877: #endif kpeter@584: kpeter@709: /// \brief Constructor. kpeter@709: /// kpeter@709: /// Constructor. kpeter@709: /// \param map A map that assigns \c int values to keys of type kpeter@709: /// \c Item. It is used internally by the heap implementations to kpeter@709: /// handle the cross references. The assigned value must be kpeter@709: /// \c PRE_HEAP (-1) for each item. kpeter@709: /// \param comp The function object used for comparing the priorities. kpeter@817: #ifdef DOXYGEN kpeter@709: explicit Heap(ItemIntMap &map, const CMP &comp) {} kpeter@817: #else kpeter@817: explicit Heap(ItemIntMap&, const CMP&) {} alpar@877: #endif alpar@100: alpar@100: /// \brief The number of items stored in the heap. alpar@100: /// kpeter@709: /// This function returns the number of items stored in the heap. alpar@100: int size() const { return 0; } alpar@100: kpeter@709: /// \brief Check if the heap is empty. alpar@100: /// kpeter@709: /// This function returns \c true if the heap is empty. alpar@100: bool empty() const { return false; } alpar@100: kpeter@709: /// \brief Make the heap empty. alpar@100: /// kpeter@709: /// This functon makes the heap empty. kpeter@709: /// It does not change the cross reference map. If you want to reuse kpeter@709: /// a heap that is not surely empty, you should first clear it and kpeter@709: /// then you should set the cross reference map to \c PRE_HEAP kpeter@709: /// for each item. kpeter@709: void clear() {} alpar@100: kpeter@709: /// \brief Insert an item into the heap with the given priority. alpar@209: /// kpeter@709: /// This function inserts the given item into the heap with the kpeter@709: /// given priority. alpar@100: /// \param i The item to insert. alpar@100: /// \param p The priority of the item. kpeter@709: /// \pre \e i must not be stored in the heap. kpeter@817: #ifdef DOXYGEN alpar@100: void push(const Item &i, const Prio &p) {} kpeter@817: #else kpeter@817: void push(const Item&, const Prio&) {} alpar@877: #endif alpar@100: kpeter@709: /// \brief Return the item having minimum priority. alpar@100: /// kpeter@709: /// This function returns the item having minimum priority. kpeter@113: /// \pre The heap must be non-empty. kpeter@817: Item top() const { return Item(); } alpar@100: kpeter@113: /// \brief The minimum priority. alpar@100: /// kpeter@709: /// This function returns the minimum priority. kpeter@113: /// \pre The heap must be non-empty. kpeter@817: Prio prio() const { return Prio(); } alpar@100: kpeter@709: /// \brief Remove the item having minimum priority. alpar@100: /// kpeter@709: /// This function removes the item having minimum priority. kpeter@113: /// \pre The heap must be non-empty. alpar@100: void pop() {} alpar@100: kpeter@709: /// \brief Remove the given item from the heap. alpar@100: /// kpeter@709: /// This function removes the given item from the heap if it is kpeter@709: /// already stored. alpar@209: /// \param i The item to delete. kpeter@709: /// \pre \e i must be in the heap. kpeter@817: #ifdef DOXYGEN alpar@100: void erase(const Item &i) {} kpeter@817: #else kpeter@817: void erase(const Item&) {} alpar@877: #endif alpar@100: kpeter@709: /// \brief The priority of the given item. alpar@100: /// kpeter@709: /// This function returns the priority of the given item. kpeter@559: /// \param i The item. kpeter@709: /// \pre \e i must be in the heap. kpeter@817: #ifdef DOXYGEN alpar@100: Prio operator[](const Item &i) const {} kpeter@817: #else kpeter@817: Prio operator[](const Item&) const { return Prio(); } alpar@877: #endif alpar@100: kpeter@709: /// \brief Set the priority of an item or insert it, if it is kpeter@113: /// not stored in the heap. alpar@100: /// kpeter@113: /// This method sets the priority of the given item if it is kpeter@709: /// already stored in the heap. Otherwise it inserts the given kpeter@709: /// item into the heap with the given priority. kpeter@113: /// alpar@100: /// \param i The item. alpar@100: /// \param p The priority. kpeter@817: #ifdef DOXYGEN alpar@100: void set(const Item &i, const Prio &p) {} kpeter@817: #else kpeter@817: void set(const Item&, const Prio&) {} alpar@877: #endif alpar@209: kpeter@709: /// \brief Decrease the priority of an item to the given value. alpar@100: /// kpeter@709: /// This function decreases the priority of an item to the given value. alpar@100: /// \param i The item. alpar@100: /// \param p The priority. kpeter@709: /// \pre \e i must be stored in the heap with priority at least \e p. kpeter@817: #ifdef DOXYGEN alpar@100: void decrease(const Item &i, const Prio &p) {} kpeter@817: #else kpeter@817: void decrease(const Item&, const Prio&) {} alpar@877: #endif alpar@100: kpeter@709: /// \brief Increase the priority of an item to the given value. alpar@100: /// kpeter@709: /// This function increases the priority of an item to the given value. alpar@100: /// \param i The item. alpar@100: /// \param p The priority. kpeter@709: /// \pre \e i must be stored in the heap with priority at most \e p. kpeter@817: #ifdef DOXYGEN alpar@100: void increase(const Item &i, const Prio &p) {} kpeter@817: #else kpeter@817: void increase(const Item&, const Prio&) {} alpar@877: #endif alpar@100: kpeter@709: /// \brief Return the state of an item. alpar@100: /// kpeter@113: /// This method returns \c PRE_HEAP if the given item has never kpeter@113: /// been in the heap, \c IN_HEAP if it is in the heap at the moment, kpeter@113: /// and \c POST_HEAP otherwise. kpeter@113: /// In the latter case it is possible that the item will get back kpeter@113: /// to the heap again. alpar@100: /// \param i The item. kpeter@817: #ifdef DOXYGEN alpar@100: State state(const Item &i) const {} kpeter@817: #else kpeter@817: State state(const Item&) const { return PRE_HEAP; } alpar@877: #endif alpar@100: kpeter@709: /// \brief Set the state of an item in the heap. alpar@100: /// kpeter@709: /// This function sets the state of the given item in the heap. kpeter@709: /// It can be used to manually clear the heap when it is important kpeter@709: /// to achive better time complexity. alpar@100: /// \param i The item. kpeter@113: /// \param st The state. It should not be \c IN_HEAP. kpeter@817: #ifdef DOXYGEN alpar@100: void state(const Item& i, State st) {} kpeter@817: #else kpeter@817: void state(const Item&, State) {} alpar@877: #endif alpar@100: alpar@100: alpar@100: template alpar@100: struct Constraints { alpar@100: public: alpar@209: void constraints() { alpar@209: typedef typename _Heap::Item OwnItem; alpar@209: typedef typename _Heap::Prio OwnPrio; alpar@209: typedef typename _Heap::State OwnState; kpeter@113: alpar@209: Item item; alpar@209: Prio prio; alpar@209: item=Item(); alpar@209: prio=Prio(); alpar@209: ignore_unused_variable_warning(item); alpar@209: ignore_unused_variable_warning(prio); alpar@100: alpar@209: OwnItem own_item; alpar@209: OwnPrio own_prio; alpar@209: OwnState own_state; alpar@209: own_item=Item(); alpar@209: own_prio=Prio(); alpar@209: ignore_unused_variable_warning(own_item); alpar@209: ignore_unused_variable_warning(own_prio); alpar@209: ignore_unused_variable_warning(own_state); alpar@100: alpar@209: _Heap heap1(map); alpar@209: _Heap heap2 = heap1; alpar@209: ignore_unused_variable_warning(heap1); alpar@209: ignore_unused_variable_warning(heap2); alpar@100: alpar@209: int s = heap.size(); alpar@209: ignore_unused_variable_warning(s); alpar@209: bool e = heap.empty(); alpar@209: ignore_unused_variable_warning(e); alpar@100: alpar@209: prio = heap.prio(); alpar@209: item = heap.top(); alpar@209: prio = heap[item]; alpar@209: own_prio = heap.prio(); alpar@209: own_item = heap.top(); alpar@209: own_prio = heap[own_item]; alpar@100: alpar@209: heap.push(item, prio); alpar@209: heap.push(own_item, own_prio); alpar@209: heap.pop(); alpar@100: alpar@209: heap.set(item, prio); alpar@209: heap.decrease(item, prio); alpar@209: heap.increase(item, prio); alpar@209: heap.set(own_item, own_prio); alpar@209: heap.decrease(own_item, own_prio); alpar@209: heap.increase(own_item, own_prio); alpar@100: alpar@209: heap.erase(item); alpar@209: heap.erase(own_item); alpar@209: heap.clear(); alpar@100: alpar@209: own_state = heap.state(own_item); alpar@209: heap.state(own_item, own_state); alpar@100: alpar@209: own_state = _Heap::PRE_HEAP; alpar@209: own_state = _Heap::IN_HEAP; alpar@209: own_state = _Heap::POST_HEAP; alpar@209: } alpar@209: alpar@209: _Heap& heap; alpar@209: ItemIntMap& map; alpar@975: Constraints() {} alpar@100: }; alpar@100: }; alpar@100: alpar@100: /// @} alpar@100: } // namespace lemon alpar@100: } deba@529: #endif