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@440: * Copyright (C) 2003-2009 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 kpeter@113: ///\brief The concept of heaps. alpar@100: deba@514: #ifndef LEMON_CONCEPTS_HEAP_H deba@514: #define LEMON_CONCEPTS_HEAP_H alpar@100: deba@220: #include deba@503: #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@550: /// Concept class describing the main interface of heaps. A \e heap kpeter@550: /// is a data structure for storing items with specified values called kpeter@550: /// \e priorities in such a way that finding the item with minimum kpeter@550: /// priority is efficient. In a heap one can change the priority of an kpeter@550: /// item, add or erase an item, etc. kpeter@550: /// kpeter@550: /// \tparam PR Type of the priority of the items. kpeter@550: /// \tparam IM A read and writable item map with int values, used kpeter@550: /// internally to handle the cross references. kpeter@550: /// \tparam Comp A functor class for the ordering of the priorities. kpeter@550: /// The default is \c std::less. kpeter@550: #ifdef DOXYGEN kpeter@550: template > kpeter@550: #else kpeter@550: template kpeter@550: #endif alpar@100: class Heap { alpar@100: public: alpar@100: kpeter@550: /// Type of the item-int map. kpeter@550: typedef IM ItemIntMap; kpeter@550: /// Type of the priorities. kpeter@550: 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@113: /// "pre heap" or "post heap". The later two are indifferent kpeter@113: /// from the point of view of the heap, but may be useful for kpeter@113: /// the user. alpar@100: /// kpeter@550: /// The item-int map must be initialized in such way that it assigns kpeter@550: /// \c PRE_HEAP (-1) to any element to be put in the heap. alpar@100: enum State { kpeter@576: IN_HEAP = 0, ///< = 0. The "in heap" state constant. kpeter@576: PRE_HEAP = -1, ///< = -1. The "pre heap" state constant. kpeter@576: POST_HEAP = -2 ///< = -2. The "post heap" state constant. alpar@100: }; alpar@209: alpar@100: /// \brief The constructor. alpar@100: /// alpar@100: /// The 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@113: /// \c PRE_HEAP (-1) for every item. kpeter@113: explicit Heap(ItemIntMap &map) {} 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: kpeter@113: /// \brief Checks if the heap is empty. alpar@100: /// kpeter@113: /// Returns \c true if the heap is empty. alpar@100: bool empty() const { return false; } alpar@100: kpeter@113: /// \brief Makes the heap empty. alpar@100: /// kpeter@113: /// Makes the heap empty. alpar@100: void clear(); alpar@100: kpeter@113: /// \brief Inserts an item into the heap with the given priority. alpar@209: /// alpar@209: /// Inserts the given item into the heap with the given priority. 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: kpeter@113: /// \brief Returns the item having minimum priority. alpar@100: /// kpeter@113: /// Returns the item having minimum priority. kpeter@113: /// \pre The heap must be non-empty. alpar@100: Item top() const {} alpar@100: kpeter@113: /// \brief The minimum priority. alpar@100: /// kpeter@113: /// Returns the minimum priority. kpeter@113: /// \pre The heap must be non-empty. alpar@100: Prio prio() const {} alpar@100: kpeter@113: /// \brief Removes the item having minimum priority. alpar@100: /// kpeter@113: /// Removes the item having minimum priority. kpeter@113: /// \pre The heap must be non-empty. alpar@100: void pop() {} alpar@100: kpeter@113: /// \brief Removes an item from the heap. alpar@100: /// kpeter@113: /// Removes the given item from the heap if it is already stored. alpar@209: /// \param i The item to delete. alpar@100: void erase(const Item &i) {} alpar@100: kpeter@113: /// \brief The priority of an item. alpar@100: /// alpar@209: /// Returns the priority of the given item. kpeter@550: /// \param i The item. alpar@100: /// \pre \c i must be in the heap. alpar@100: Prio operator[](const Item &i) const {} alpar@100: kpeter@113: /// \brief Sets the priority of an item or inserts 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@113: /// already stored in the heap. kpeter@113: /// Otherwise it inserts the given item with the given priority. kpeter@113: /// alpar@100: /// \param i The item. alpar@100: /// \param p The priority. alpar@100: void set(const Item &i, const Prio &p) {} alpar@209: kpeter@113: /// \brief Decreases the priority of an item to the given value. alpar@100: /// kpeter@113: /// Decreases the priority of an item to the given value. alpar@100: /// \param i The item. alpar@100: /// \param p The priority. kpeter@550: /// \pre \c i must be stored in the heap with priority at least \c p. alpar@100: void decrease(const Item &i, const Prio &p) {} alpar@100: kpeter@113: /// \brief Increases the priority of an item to the given value. alpar@100: /// kpeter@113: /// Increases the priority of an item to the given value. alpar@100: /// \param i The item. alpar@100: /// \param p The priority. kpeter@550: /// \pre \c i must be stored in the heap with priority at most \c p. alpar@100: void increase(const Item &i, const Prio &p) {} alpar@100: kpeter@113: /// \brief Returns if an item is in, has already been in, or has alpar@100: /// never been in the heap. 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. alpar@100: State state(const Item &i) const {} alpar@100: kpeter@113: /// \brief Sets the state of an item in the heap. alpar@100: /// kpeter@113: /// Sets the state of the given item in the heap. It can be used kpeter@113: /// to manually clear the heap when it is important to achive the alpar@100: /// better time complexity. alpar@100: /// \param i The item. kpeter@113: /// \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@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@783: Constraints() {} alpar@100: }; alpar@100: }; alpar@100: alpar@100: /// @} alpar@100: } // namespace lemon alpar@100: } deba@514: #endif