1.1 --- a/lemon/concepts/heap.h Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/lemon/concepts/heap.h Sun Jul 13 19:51:02 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -52,14 +52,14 @@
1.13 /// from the point of view of the heap, but may be useful for
1.14 /// the user.
1.15 ///
1.16 - /// The \c ItemIntMap must be initialized in such a way, that it
1.17 + /// The \c ItemIntMap must be initialized in such a way, that it
1.18 /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
1.19 enum State {
1.20 - IN_HEAP = 0,
1.21 - PRE_HEAP = -1,
1.22 - POST_HEAP = -2
1.23 + IN_HEAP = 0,
1.24 + PRE_HEAP = -1,
1.25 + POST_HEAP = -2
1.26 };
1.27 -
1.28 +
1.29 /// \brief The constructor.
1.30 ///
1.31 /// The constructor.
1.32 @@ -85,8 +85,8 @@
1.33 void clear();
1.34
1.35 /// \brief Inserts an item into the heap with the given priority.
1.36 - ///
1.37 - /// Inserts the given item into the heap with the given priority.
1.38 + ///
1.39 + /// Inserts the given item into the heap with the given priority.
1.40 /// \param i The item to insert.
1.41 /// \param p The priority of the item.
1.42 void push(const Item &i, const Prio &p) {}
1.43 @@ -112,12 +112,12 @@
1.44 /// \brief Removes an item from the heap.
1.45 ///
1.46 /// Removes the given item from the heap if it is already stored.
1.47 - /// \param i The item to delete.
1.48 + /// \param i The item to delete.
1.49 void erase(const Item &i) {}
1.50
1.51 /// \brief The priority of an item.
1.52 ///
1.53 - /// Returns the priority of the given item.
1.54 + /// Returns the priority of the given item.
1.55 /// \pre \c i must be in the heap.
1.56 /// \param i The item.
1.57 Prio operator[](const Item &i) const {}
1.58 @@ -133,7 +133,7 @@
1.59 /// \param i The item.
1.60 /// \param p The priority.
1.61 void set(const Item &i, const Prio &p) {}
1.62 -
1.63 +
1.64 /// \brief Decreases the priority of an item to the given value.
1.65 ///
1.66 /// Decreases the priority of an item to the given value.
1.67 @@ -174,69 +174,69 @@
1.68 template <typename _Heap>
1.69 struct Constraints {
1.70 public:
1.71 - void constraints() {
1.72 - typedef typename _Heap::Item OwnItem;
1.73 - typedef typename _Heap::Prio OwnPrio;
1.74 - typedef typename _Heap::State OwnState;
1.75 + void constraints() {
1.76 + typedef typename _Heap::Item OwnItem;
1.77 + typedef typename _Heap::Prio OwnPrio;
1.78 + typedef typename _Heap::State OwnState;
1.79
1.80 - Item item;
1.81 - Prio prio;
1.82 - item=Item();
1.83 - prio=Prio();
1.84 - ignore_unused_variable_warning(item);
1.85 - ignore_unused_variable_warning(prio);
1.86 + Item item;
1.87 + Prio prio;
1.88 + item=Item();
1.89 + prio=Prio();
1.90 + ignore_unused_variable_warning(item);
1.91 + ignore_unused_variable_warning(prio);
1.92
1.93 - OwnItem own_item;
1.94 - OwnPrio own_prio;
1.95 - OwnState own_state;
1.96 - own_item=Item();
1.97 - own_prio=Prio();
1.98 - ignore_unused_variable_warning(own_item);
1.99 - ignore_unused_variable_warning(own_prio);
1.100 - ignore_unused_variable_warning(own_state);
1.101 + OwnItem own_item;
1.102 + OwnPrio own_prio;
1.103 + OwnState own_state;
1.104 + own_item=Item();
1.105 + own_prio=Prio();
1.106 + ignore_unused_variable_warning(own_item);
1.107 + ignore_unused_variable_warning(own_prio);
1.108 + ignore_unused_variable_warning(own_state);
1.109
1.110 - _Heap heap1(map);
1.111 - _Heap heap2 = heap1;
1.112 - ignore_unused_variable_warning(heap1);
1.113 - ignore_unused_variable_warning(heap2);
1.114 -
1.115 - int s = heap.size();
1.116 - ignore_unused_variable_warning(s);
1.117 - bool e = heap.empty();
1.118 - ignore_unused_variable_warning(e);
1.119 + _Heap heap1(map);
1.120 + _Heap heap2 = heap1;
1.121 + ignore_unused_variable_warning(heap1);
1.122 + ignore_unused_variable_warning(heap2);
1.123
1.124 - prio = heap.prio();
1.125 - item = heap.top();
1.126 - prio = heap[item];
1.127 - own_prio = heap.prio();
1.128 - own_item = heap.top();
1.129 - own_prio = heap[own_item];
1.130 + int s = heap.size();
1.131 + ignore_unused_variable_warning(s);
1.132 + bool e = heap.empty();
1.133 + ignore_unused_variable_warning(e);
1.134
1.135 - heap.push(item, prio);
1.136 - heap.push(own_item, own_prio);
1.137 - heap.pop();
1.138 + prio = heap.prio();
1.139 + item = heap.top();
1.140 + prio = heap[item];
1.141 + own_prio = heap.prio();
1.142 + own_item = heap.top();
1.143 + own_prio = heap[own_item];
1.144
1.145 - heap.set(item, prio);
1.146 - heap.decrease(item, prio);
1.147 - heap.increase(item, prio);
1.148 - heap.set(own_item, own_prio);
1.149 - heap.decrease(own_item, own_prio);
1.150 - heap.increase(own_item, own_prio);
1.151 + heap.push(item, prio);
1.152 + heap.push(own_item, own_prio);
1.153 + heap.pop();
1.154
1.155 - heap.erase(item);
1.156 - heap.erase(own_item);
1.157 - heap.clear();
1.158 + heap.set(item, prio);
1.159 + heap.decrease(item, prio);
1.160 + heap.increase(item, prio);
1.161 + heap.set(own_item, own_prio);
1.162 + heap.decrease(own_item, own_prio);
1.163 + heap.increase(own_item, own_prio);
1.164
1.165 - own_state = heap.state(own_item);
1.166 - heap.state(own_item, own_state);
1.167 + heap.erase(item);
1.168 + heap.erase(own_item);
1.169 + heap.clear();
1.170
1.171 - own_state = _Heap::PRE_HEAP;
1.172 - own_state = _Heap::IN_HEAP;
1.173 - own_state = _Heap::POST_HEAP;
1.174 - }
1.175 + own_state = heap.state(own_item);
1.176 + heap.state(own_item, own_state);
1.177
1.178 - _Heap& heap;
1.179 - ItemIntMap& map;
1.180 + own_state = _Heap::PRE_HEAP;
1.181 + own_state = _Heap::IN_HEAP;
1.182 + own_state = _Heap::POST_HEAP;
1.183 + }
1.184 +
1.185 + _Heap& heap;
1.186 + ItemIntMap& map;
1.187 };
1.188 };
1.189