heap.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00023 
00024 #ifndef LEMON_CONCEPT_HEAP_H
00025 #define LEMON_CONCEPT_HEAP_H
00026 
00027 #include <lemon/invalid.h>
00028 
00029 namespace lemon {
00030   namespace concept {
00033 
00034 
00039     template <typename Item, typename Prio, typename ItemIntMap>
00040     class Heap {
00041     public:
00042   
00043 
00052       enum state_enum {
00053         IN_HEAP = 0,
00054         PRE_HEAP = -1,
00055         POST_HEAP = -2
00056       };
00057       
00064       explicit Heap(ItemIntMap &_iim) {}
00065 
00069       int size() const { return 0; }
00070 
00074       bool empty() const { return false; }
00075 
00079       void clear();
00080 
00086       void push(const Item &i, const Prio &p) {}
00087 
00092       Item top() const {}
00093 
00098       Prio prio() const {}
00099 
00104       void pop() {}
00105 
00111       void erase(const Item &i) {}
00112 
00118       Prio operator[](const Item &i) const {}
00119 
00128       void set(const Item &i, const Prio &p) {}
00129       
00136       void decrease(const Item &i, const Prio &p) {}
00137 
00145       void increase(const Item &i, const Prio &p) {}
00146 
00155       state_enum state(const Item &i) const {}
00156 
00164       void state(const Item& i, state_enum st) {}
00165 
00166 
00167       template <typename _Heap>
00168       struct Constraints {
00169       public:
00170     
00171         void constraints() {
00172           Item item;
00173           Prio prio;
00174 
00175           item=Item();
00176           prio=Prio();
00177 
00178           ignore_unused_variable_warning(item);
00179           ignore_unused_variable_warning(prio);
00180 
00181           typedef typename _Heap::state_enum state_enum;
00182           state_enum state;
00183 
00184           ignore_unused_variable_warning(state);
00185       
00186           _Heap heap1 = _Heap(map);
00187 
00188           ignore_unused_variable_warning(heap1);
00189       
00190           heap.push(item, prio);
00191 
00192           prio = heap.prio();
00193           item = heap.top();
00194 
00195           heap.pop();
00196 
00197           heap.set(item, prio);
00198           heap.decrease(item, prio);
00199           heap.increase(item, prio);
00200           prio = heap[item];
00201 
00202           heap.erase(item);
00203 
00204           state = heap.state(item);
00205 
00206           state = _Heap::PRE_HEAP;
00207           state = _Heap::IN_HEAP;
00208           state = _Heap::POST_HEAP;
00209 
00210           heap.clear();
00211         }
00212     
00213         _Heap& heap;
00214         ItemIntMap& map;
00215 
00216         Constraints() : heap(0), map(0) {}
00217       };
00218     };
00219 
00221   } // namespace lemon
00222 }
00223 #endif // LEMON_CONCEPT_PATH_H

Generated on Fri Feb 3 18:36:02 2006 for LEMON by  doxygen 1.4.6