1 // -*- C++ -*- // |
1 /* -*- C++ -*- |
2 |
2 * src/hugo/bin_heap.h - Part of HUGOlib, a generic C++ optimization library |
3 /* FIXME: Copyright ... |
3 * |
4 * |
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
5 * This implementation is heavily based on STL's heap functions and |
5 * (Egervary Combinatorial Optimization Research Group, EGRES). |
6 * the similar class by Alpar Juttner in IKTA... |
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
7 */ |
15 */ |
8 |
|
9 /****** |
|
10 * |
|
11 * BinHeap<ItemType, PrioType, ItemIntMap, [PrioCompare]> |
|
12 * |
|
13 * Ez az osztaly item-prioritas parok tarolasara alkalmas binaris kupacot |
|
14 * valosit meg. |
|
15 * A kupacban legfolul mindig az a par talalhato, amiben a prioritas a |
|
16 * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz |
|
17 * lett keszitve...) |
|
18 * |
|
19 * Megjegyzes: a kupacos temakorokben a prioritast kulcsnak szoktak nevezni, |
|
20 * de mivel ez zavaro tud lenni a property-map-es kulcs-ertek szohasznalata |
|
21 * miatt, megprobaltunk valami semleges elnevezeseket kitalalni. |
|
22 * |
|
23 * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami |
|
24 * az itemekhez egy int-et tud tarolni (ezzel tudom megkeresni az illeto |
|
25 * elemet a kupacban a csokkentes es hasonlo muveletekhez). |
|
26 * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek |
|
27 * is elnie kell. (???) |
|
28 * |
|
29 * Ketfele modon hasznalhato: |
|
30 * Lusta mod: |
|
31 * set(Item, Prio) metodussal pakolunk a kupacba, |
|
32 * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor |
|
33 * csokkentettunk-e rajta, vagy noveltunk. |
|
34 * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen |
|
35 * minden szobajovo kulcs ertekre, -1 -es ertekkel! |
|
36 * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state |
|
37 metodussal: |
|
38 * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0, |
|
39 * mar kikerult a kupacbol POST_HEAP=-2). |
|
40 * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak |
|
41 * meg meg tudja mondani a "legkisebb" prioritasu elemet. De csak nagyjabol, |
|
42 * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk... |
|
43 * |
|
44 * Kozvetlen mod: |
|
45 * push(Item, Prio) metodussal belerakunk a kupacba (ha az illeto kulcs mar |
|
46 * benn volt, akkor gaz). |
|
47 * increase/decrease(Item i, Prio new_prio) metodusokkal lehet |
|
48 * novelni/csokkenteni az illeto elemhez tartozo prioritast. (Ha nem volt |
|
49 * megbenne a kupacban az illeto elem, vagy nem abba az iranyba valtoztattad |
|
50 * az erteket, amerre mondtad -- gaz). |
|
51 * |
|
52 * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni. |
|
53 * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac |
|
54 * hasznal. :-)) |
|
55 * |
|
56 * |
|
57 * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi) |
|
58 * |
|
59 */ |
|
60 |
|
61 |
16 |
62 #ifndef HUGO_BIN_HEAP_H |
17 #ifndef HUGO_BIN_HEAP_H |
63 #define HUGO_BIN_HEAP_H |
18 #define HUGO_BIN_HEAP_H |
64 |
19 |
65 ///\ingroup auxdat |
20 ///\ingroup auxdat |
66 ///\file |
21 ///\file |
67 ///\brief Binary Heap implementation. |
22 ///\brief Binary Heap implementation. |
|
23 ///\todo It should be documented. |
68 |
24 |
69 #include <vector> |
25 #include <vector> |
70 #include <utility> |
26 #include <utility> |
71 #include <functional> |
27 #include <functional> |
72 |
28 |