lemon/concepts/heap.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 519 c786cd201266
child 559 c5fd2d996909
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 ///\ingroup concept
    20 ///\file
    21 ///\brief The concept of heaps.
    22 
    23 #ifndef LEMON_CONCEPTS_HEAP_H
    24 #define LEMON_CONCEPTS_HEAP_H
    25 
    26 #include <lemon/core.h>
    27 #include <lemon/concept_check.h>
    28 
    29 namespace lemon {
    30 
    31   namespace concepts {
    32 
    33     /// \addtogroup concept
    34     /// @{
    35 
    36     /// \brief The heap concept.
    37     ///
    38     /// Concept class describing the main interface of heaps.
    39     template <typename Priority, typename ItemIntMap>
    40     class Heap {
    41     public:
    42 
    43       /// Type of the items stored in the heap.
    44       typedef typename ItemIntMap::Key Item;
    45 
    46       /// Type of the priorities.
    47       typedef Priority Prio;
    48 
    49       /// \brief Type to represent the states of the items.
    50       ///
    51       /// Each item has a state associated to it. It can be "in heap",
    52       /// "pre heap" or "post heap". The later two are indifferent
    53       /// from the point of view of the heap, but may be useful for
    54       /// the user.
    55       ///
    56       /// The \c ItemIntMap must be initialized in such a way, that it
    57       /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
    58       enum State {
    59         IN_HEAP = 0,
    60         PRE_HEAP = -1,
    61         POST_HEAP = -2
    62       };
    63 
    64       /// \brief The constructor.
    65       ///
    66       /// The constructor.
    67       /// \param map A map that assigns \c int values to keys of type
    68       /// \c Item. It is used internally by the heap implementations to
    69       /// handle the cross references. The assigned value must be
    70       /// \c PRE_HEAP (<tt>-1</tt>) for every item.
    71       explicit Heap(ItemIntMap &map) {}
    72 
    73       /// \brief The number of items stored in the heap.
    74       ///
    75       /// Returns the number of items stored in the heap.
    76       int size() const { return 0; }
    77 
    78       /// \brief Checks if the heap is empty.
    79       ///
    80       /// Returns \c true if the heap is empty.
    81       bool empty() const { return false; }
    82 
    83       /// \brief Makes the heap empty.
    84       ///
    85       /// Makes the heap empty.
    86       void clear();
    87 
    88       /// \brief Inserts an item into the heap with the given priority.
    89       ///
    90       /// Inserts the given item into the heap with the given priority.
    91       /// \param i The item to insert.
    92       /// \param p The priority of the item.
    93       void push(const Item &i, const Prio &p) {}
    94 
    95       /// \brief Returns the item having minimum priority.
    96       ///
    97       /// Returns the item having minimum priority.
    98       /// \pre The heap must be non-empty.
    99       Item top() const {}
   100 
   101       /// \brief The minimum priority.
   102       ///
   103       /// Returns the minimum priority.
   104       /// \pre The heap must be non-empty.
   105       Prio prio() const {}
   106 
   107       /// \brief Removes the item having minimum priority.
   108       ///
   109       /// Removes the item having minimum priority.
   110       /// \pre The heap must be non-empty.
   111       void pop() {}
   112 
   113       /// \brief Removes an item from the heap.
   114       ///
   115       /// Removes the given item from the heap if it is already stored.
   116       /// \param i The item to delete.
   117       void erase(const Item &i) {}
   118 
   119       /// \brief The priority of an item.
   120       ///
   121       /// Returns the priority of the given item.
   122       /// \pre \c i must be in the heap.
   123       /// \param i The item.
   124       Prio operator[](const Item &i) const {}
   125 
   126       /// \brief Sets the priority of an item or inserts it, if it is
   127       /// not stored in the heap.
   128       ///
   129       /// This method sets the priority of the given item if it is
   130       /// already stored in the heap.
   131       /// Otherwise it inserts the given item with the given priority.
   132       ///
   133       /// \param i The item.
   134       /// \param p The priority.
   135       void set(const Item &i, const Prio &p) {}
   136 
   137       /// \brief Decreases the priority of an item to the given value.
   138       ///
   139       /// Decreases the priority of an item to the given value.
   140       /// \pre \c i must be stored in the heap with priority at least \c p.
   141       /// \param i The item.
   142       /// \param p The priority.
   143       void decrease(const Item &i, const Prio &p) {}
   144 
   145       /// \brief Increases the priority of an item to the given value.
   146       ///
   147       /// Increases the priority of an item to the given value.
   148       /// \pre \c i must be stored in the heap with priority at most \c p.
   149       /// \param i The item.
   150       /// \param p The priority.
   151       void increase(const Item &i, const Prio &p) {}
   152 
   153       /// \brief Returns if an item is in, has already been in, or has
   154       /// never been in the heap.
   155       ///
   156       /// This method returns \c PRE_HEAP if the given item has never
   157       /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   158       /// and \c POST_HEAP otherwise.
   159       /// In the latter case it is possible that the item will get back
   160       /// to the heap again.
   161       /// \param i The item.
   162       State state(const Item &i) const {}
   163 
   164       /// \brief Sets the state of an item in the heap.
   165       ///
   166       /// Sets the state of the given item in the heap. It can be used
   167       /// to manually clear the heap when it is important to achive the
   168       /// better time complexity.
   169       /// \param i The item.
   170       /// \param st The state. It should not be \c IN_HEAP.
   171       void state(const Item& i, State st) {}
   172 
   173 
   174       template <typename _Heap>
   175       struct Constraints {
   176       public:
   177         void constraints() {
   178           typedef typename _Heap::Item OwnItem;
   179           typedef typename _Heap::Prio OwnPrio;
   180           typedef typename _Heap::State OwnState;
   181 
   182           Item item;
   183           Prio prio;
   184           item=Item();
   185           prio=Prio();
   186           ignore_unused_variable_warning(item);
   187           ignore_unused_variable_warning(prio);
   188 
   189           OwnItem own_item;
   190           OwnPrio own_prio;
   191           OwnState own_state;
   192           own_item=Item();
   193           own_prio=Prio();
   194           ignore_unused_variable_warning(own_item);
   195           ignore_unused_variable_warning(own_prio);
   196           ignore_unused_variable_warning(own_state);
   197 
   198           _Heap heap1(map);
   199           _Heap heap2 = heap1;
   200           ignore_unused_variable_warning(heap1);
   201           ignore_unused_variable_warning(heap2);
   202 
   203           int s = heap.size();
   204           ignore_unused_variable_warning(s);
   205           bool e = heap.empty();
   206           ignore_unused_variable_warning(e);
   207 
   208           prio = heap.prio();
   209           item = heap.top();
   210           prio = heap[item];
   211           own_prio = heap.prio();
   212           own_item = heap.top();
   213           own_prio = heap[own_item];
   214 
   215           heap.push(item, prio);
   216           heap.push(own_item, own_prio);
   217           heap.pop();
   218 
   219           heap.set(item, prio);
   220           heap.decrease(item, prio);
   221           heap.increase(item, prio);
   222           heap.set(own_item, own_prio);
   223           heap.decrease(own_item, own_prio);
   224           heap.increase(own_item, own_prio);
   225 
   226           heap.erase(item);
   227           heap.erase(own_item);
   228           heap.clear();
   229 
   230           own_state = heap.state(own_item);
   231           heap.state(own_item, own_state);
   232 
   233           own_state = _Heap::PRE_HEAP;
   234           own_state = _Heap::IN_HEAP;
   235           own_state = _Heap::POST_HEAP;
   236         }
   237 
   238         _Heap& heap;
   239         ItemIntMap& map;
   240       };
   241     };
   242 
   243     /// @}
   244   } // namespace lemon
   245 }
   246 #endif