1 /*
2  * Copyright (c) 2006 prissi
3  *
4  * This file is part of the Simutrans project under the artistic license.
5  * (see license.txt)
6  */
7 
8 #ifndef tpl_binary_heap_tpl_h
9 #define tpl_binary_heap_tpl_h
10 
11 #include "../simmem.h"
12 
13 
14 /**
15  *
16  * my try on a binary heap template
17  * inspired by the pathfinder of OTTD written by kuDr
18  *
19  * For information about Binary Heap algorithm,
20  *   see: http://www.policyalmanac.org/games/binaryHeaps.htm *
21  *
22  * @date September 2006
23  * @author prissi
24  */
25 
26 #include "../simtypes.h"
27 
28 template <class T>
29 class binary_heap_tpl
30 {
31 private:
32 	T *nodes;
33 
34 public:
35 	uint32 node_count;
36 	uint32 node_size;
37 
binary_heap_tpl()38 	binary_heap_tpl()
39 	{
40 		nodes = MALLOCN(T, 4096);
41 		node_size = 4096;
42 		node_count = 0;
43 	}
44 
45 
~binary_heap_tpl()46 	~binary_heap_tpl()
47 	{
48 		free( nodes );
49 	}
50 
51 
52 	/**
53 	* Inserts an element into the queue.
54 	* in such a way that the lowest is at the top of this tree in an array
55 	* parts inspired from OTTD
56 	*/
insert(const T item)57 	void insert(const T item)
58 	{
59 		node_count ++;
60 
61 		// need to enlarge? (must be 2^x)
62 		if(node_count==node_size) {
63 			T *tmp=nodes;
64 			node_size *= 2;
65 			nodes = MALLOCN(T, node_size);
66 			memcpy( nodes, tmp, sizeof(T)*(node_size/2) );
67 			free( tmp );
68 		}
69 
70 		// now we have to move it to the right position
71 		int gap = node_count;
72 		for (int parent = gap/2; (parent>0) && (*item <= *nodes[parent]);  ) {
73 			nodes[gap] = nodes[parent];
74 			gap = parent;
75 			parent /= 2;
76 		}
77 		nodes[gap] = item;
78 	}
79 
80 
81 	/**
82 	* unfortunately, the removing is as much effort as the insertion ...
83 	*/
pop()84 	T pop() {
85 		assert(!empty());
86 
87 		T result = nodes[1];
88 
89 		// at index 1 is the lowest one
90 		uint32 gap = 1;
91 
92 		// this is the last one
93 		T item = nodes[node_count--];
94 
95 		// now we must maintain relation between parent and its children:
96 		//   parent <= any child
97 		// from head down to the tail
98 		uint32 child = 2; // first child is at [parent * 2]
99 
100 		// while children are valid
101 		while(child<=node_count) {
102 
103 			// choose the smaller child
104 			if(  child<node_count && *nodes[child+1] <= *nodes[child]) {
105 				child++;
106 			}
107 
108 			if(!(*nodes[child] <= *item)) {
109 				// the smaller child is still bigger or same as parent => we are done
110 				break;
111 			}
112 
113 			// if smaller child is smaller than parent, it will become new parent
114 			nodes[gap] = nodes[child];
115 			gap = child;
116 			// where do we have our new children?
117 			child = gap * 2;
118 		}
119 		// move last item to the proper place
120 		if (node_count>0) {
121 			nodes[gap] = item;
122 		}
123 
124 		return result;
125 	}
126 
127 	/**
128 	* Recycles all nodes. Doesn't delete the objects.
129 	* Leaves the list empty.
130 	* @author Hj. Malthaner
131 	*/
clear()132 	void clear()
133 	{
134 		node_count = 0;
135 	}
136 
137 
get_count()138 	uint32 get_count() const
139 	{
140 		return node_count;
141 	}
142 
143 
empty()144 	bool empty() const { return node_count == 0; }
145 
146 
front()147 	const T& front() {
148 		assert(!empty());
149 
150 		return nodes[1];
151 	}
152 private:
153 	binary_heap_tpl(const binary_heap_tpl& other);
154 	binary_heap_tpl& operator=( binary_heap_tpl const& other );
155 };
156 
157 #endif
158