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