lemon-0.x: src/include/bin_heap.hh@1ac27e476e25 (annotated)

klao@39	1	/* FIXME: Copyright ...
klao@39	2	*
klao@39	3	* This implementation is heavily based on STL's heap functions and
klao@39	4	* the similar class by Alpar Juttner in IKTA...
klao@39	5	*/
klao@39	6
klao@39	7	/******
klao@39	8	*
klao@39	9	* BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]>
klao@39	10	*
klao@39	11	* Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot
klao@39	12	* valosit meg.
klao@39	13	* A kupacban legfolul mindig az a par talalhato, amiben az _ertek_ a
klao@39	14	* legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
klao@39	15	* lett keszitve...)
klao@39	16	*
klao@39	17	* Megjegyzes: egy kicsit gyanus nekem, hogy a kupacos temakorben nem
klao@39	18	* azt hivjak kulcsnak, amit most en annak nevezek. :) En olyan
klao@39	19	* property_map -os ertelemben hasznalom.
klao@39	20	*
klao@39	21	* A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
klao@39	22	* a kulcsokhoz egy int-et tud tarolni (ezzel tudom megkeresni az illeto
klao@39	23	* elemet a kupacban a csokkentes es hasonlo muveletekhez).
klao@39	24	* A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
klao@39	25	* is elnie kell. (???)
klao@39	26	*
klao@39	27	* Ketfele modon hasznalhato:
klao@39	28	* Lusta mod:
klao@39	29	* put(Key, Value) metodussal pakolunk a kupacba,
klao@39	30	* aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
klao@39	31	* csokkentettunk-e rajta, vagy noveltunk.
klao@39	32	* Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
klao@39	33	* minden szobajovo kulcs ertekre, -1 -es ertekkel!
klao@39	34	* Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
klao@39	35	* (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
klao@39	36	* mar kikerult a kupacbol POST_HEAP=-2).
klao@39	37	* Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
klao@39	38	* meg meg tudja mondani a "legkisebb" erteku elemet. De csak nagyjabol,
klao@39	39	* hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
klao@39	40	*
klao@39	41	* Kozvetlen mod:
klao@39	42	* push(Key, Value) metodussal belerakunk a kupacba (ha az illeto kulcs mar
klao@39	43	* benn volt, akkor gaz).
klao@39	44	* increase/decrease(Key k, Value new_value) metodusokkal lehet
klao@39	45	* novelni/csokkenteni az illeto kulcshoz tartozo erteket. (Ha nem volt meg
klao@39	46	* benne a kupacban az illeto kulcs, vagy nem abba az iranyba valtoztattad
klao@39	47	* az erteket, amerre mondtad -- gaz).
klao@39	48	*
klao@39	49	* Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
klao@39	50	* Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
klao@39	51	* hasznal. :-))
klao@39	52	*
klao@39	53	*
klao@39	54	* Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
klao@39	55	*
klao@39	56	*/
klao@39	57
klao@39	58
klao@37	59	#ifndef BIN_HEAP_HH
klao@37	60	#define BIN_HEAP_HH
klao@37	61
klao@37	62	#include <vector>
klao@37	63	#include <utility>
klao@37	64	#include <functional>
klao@37	65
alpar@114	66	namespace hugo {
klao@37	67
klao@37	68	template <typename Key, typename Val, typename KeyIntMap,
klao@37	69	typename Compare = std::less<Val> >
klao@37	70	class BinHeap {
klao@37	71
klao@37	72	public:
klao@37	73	typedef Key KeyType;
klao@37	74	// FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
klao@37	75	typedef Val ValueType;
klao@37	76	typedef std::pair<KeyType,ValueType> PairType;
klao@37	77	typedef KeyIntMap KeyIntMapType;
klao@37	78	typedef Compare ValueCompare;
klao@37	79
klao@37	80	/**
klao@37	81	* Each Key element have a state associated to it. It may be "in heap",
klao@37	82	* "pre heap" or "post heap". The later two are indifferent from the
klao@37	83	* heap's point of view, but may be useful to the user.
klao@37	84	*
klao@37	85	* The KeyIntMap _should_ be initialized in such way, that it maps
klao@37	86	* PRE_HEAP (-1) to any element to be put in the heap...
klao@37	87	*/
klao@39	88	enum state_enum {
klao@37	89	IN_HEAP = 0,
klao@37	90	PRE_HEAP = -1,
klao@37	91	POST_HEAP = -2
klao@37	92	};
klao@37	93
klao@37	94	private:
klao@37	95	std::vector<PairType> data;
klao@37	96	Compare comp;
klao@37	97	// FIXME: jo ez igy???
klao@37	98	KeyIntMap &kim;
klao@37	99
klao@37	100	public:
klao@37	101	BinHeap(KeyIntMap &_kim) : kim(_kim) {}
klao@37	102	BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
klao@37	103
klao@37	104
klao@37	105	int size() const { return data.size(); }
klao@41	106	bool empty() const { return data.empty(); }
klao@37	107
klao@37	108	private:
klao@37	109	static int parent(int i) { return (i-1)/2; }
klao@37	110	static int second_child(int i) { return 2*i+2; }
klao@37	111	bool less(const PairType &p1, const PairType &p2) {
klao@37	112	return comp(p1.second, p2.second);
klao@37	113	}
klao@37	114
klao@37	115	int bubble_up(int hole, PairType p);
klao@37	116	int bubble_down(int hole, PairType p, int length);
klao@37	117
klao@37	118	void move(const PairType &p, int i) {
klao@37	119	data[i] = p;
klao@37	120	kim.put(p.first, i);
klao@37	121	}
klao@37	122
klao@41	123	void rmidx(int h) {
klao@41	124	int n = data.size()-1;
klao@41	125	if( h>=0 && h<=n ) {
klao@41	126	kim.put(data[h].first, POST_HEAP);
klao@41	127	if ( h<n ) {
klao@41	128	bubble_down(h, data[n], n);
klao@41	129	}
klao@41	130	data.pop_back();
klao@41	131	}
klao@41	132	}
klao@41	133
klao@37	134	public:
klao@37	135	void push(const PairType &p) {
klao@37	136	int n = data.size();
klao@37	137	data.resize(n+1);
klao@37	138	bubble_up(n, p);
klao@37	139	}
klao@37	140	void push(const Key &k, const Val &v) { push(PairType(k,v)); }
klao@37	141
klao@37	142	Key top() const {
klao@37	143	// FIXME: test size>0 ?
klao@37	144	return data[0].first;
klao@37	145	}
klao@37	146	Val topValue() const {
klao@37	147	// FIXME: test size>0 ?
klao@37	148	return data[0].second;
klao@37	149	}
klao@37	150
klao@37	151	void pop() {
klao@41	152	rmidx(0);
klao@41	153	}
klao@41	154
klao@41	155	void erase(const Key &k) {
klao@41	156	rmidx(kim.get(k));
klao@37	157	}
klao@37	158
klao@37	159	const Val get(const Key &k) const {
klao@37	160	int idx = kim.get(k);
klao@37	161	return data[idx].second;
klao@37	162	}
klao@37	163	void put(const Key &k, const Val &v) {
klao@37	164	int idx = kim.get(k);
klao@37	165	if( idx < 0 ) {
klao@37	166	push(k,v);
klao@37	167	}
klao@37	168	else if( comp(v, data[idx].second) ) {
klao@37	169	bubble_up(idx, PairType(k,v));
klao@37	170	}
klao@37	171	else {
klao@37	172	bubble_down(idx, PairType(k,v), data.size());
klao@37	173	}
klao@37	174	}
klao@37	175
klao@37	176	void decrease(const Key &k, const Val &v) {
klao@37	177	int idx = kim.get(k);
klao@37	178	bubble_up(idx, PairType(k,v));
klao@37	179	}
klao@37	180	void increase(const Key &k, const Val &v) {
klao@37	181	int idx = kim.get(k);
klao@37	182	bubble_down(idx, PairType(k,v), data.size());
klao@37	183	}
klao@37	184
klao@39	185	state_enum state(const Key &k) const {
klao@39	186	int s = kim.get(k);
klao@39	187	if( s>=0 )
klao@39	188	s=0;
klao@39	189	return state_enum(s);
klao@39	190	}
klao@39	191
klao@37	192	}; // class BinHeap
klao@37	193
klao@37	194
klao@37	195	template <typename K, typename V, typename M, typename C>
klao@37	196	int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
klao@37	197	int par = parent(hole);
klao@37	198	while( hole>0 && less(p,data[par]) ) {
klao@37	199	move(data[par],hole);
klao@37	200	hole = par;
klao@37	201	par = parent(hole);
klao@37	202	}
klao@37	203	move(p, hole);
klao@37	204	return hole;
klao@37	205	}
klao@37	206
klao@37	207	template <typename K, typename V, typename M, typename C>
klao@37	208	int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
klao@37	209	int child = second_child(hole);
klao@37	210	while(child < length) {
klao@37	211	if( less(data[child-1], data[child]) ) {
klao@37	212	--child;
klao@37	213	}
klao@37	214	if( !less(data[child], p) )
klao@37	215	goto ok;
klao@37	216	move(data[child], hole);
klao@37	217	hole = child;
klao@37	218	child = second_child(hole);
klao@37	219	}
klao@37	220	child--;
klao@37	221	if( child<length && less(data[child], p) ) {
klao@37	222	move(data[child], hole);
klao@37	223	hole=child;
klao@37	224	}
klao@37	225	ok:
klao@37	226	move(p, hole);
klao@37	227	return hole;
klao@37	228	}
klao@37	229
alpar@114	230	} // namespace hugo
klao@37	231
klao@37	232	#endif // BIN_HEAP_HH

author	klao
	Thu, 26 Feb 2004 16:07:40 +0000
changeset 132	1ac27e476e25
parent 41	67f73b15855d
child 172	c645f4a2a6ae
permissions	-rw-r--r--