[u/mrichter/AliRoot.git] / HLT / MUON / src / Buffers / QuadTree.hpp

////////////////////////////////////////////////////////////////////////////////
//
// Author: Artur Szostak
// Email:  artur@alice.phy.uct.ac.za | artursz@iafrica.com
//
////////////////////////////////////////////////////////////////////////////////

#ifndef dHLT_BUFFERS_QUAD_TREE_HPP
#define dHLT_BUFFERS_QUAD_TREE_HPP

#include "BasicTypes.hpp"
#include "Utils.hpp"
#include "new.hpp"

namespace dHLT
{
namespace Buffers
{


template <typename DataType>
class QuadTree
{
public:

	class Handler
	{
	public:

		/* Called when the specified node falls exactly within the region
		   passed to ForAllOverlapping.
		 */
		inline void AddTo(QuadTree* /*node*/) {};
		
		/* Called for the first node of a tree when the specified node has
		   just been created and needs to be initialised. This method 
		   corresponds to FoundOverlapping except it is called when the node
		   was not found and must be created.
		 */
		inline void InitialiseFirst(QuadTree* /*node*/) {};
		
		/* Called when the specified node has just been created and needs to be
		   initialised. The specified parent is the parent of the new node. This
		   method corresponds to FoundOverlapping except it is called when the
		   node was not found and must be created.
		 */
		inline void Initialise(QuadTree* /*node*/, QuadTree* /*parent*/) {};
		
		/* Called when a node was found that partialy overlaps the region given
		   to ForAllOverlapping. This method corresponds to Initialise(First)
		   except it is called when the node has been found.
		 */
		inline void FoundOverlapping(QuadTree* /*node*/) {};
		
		/* Called when a child node was found to be contained in the region
		   given to the ForAllOverlapping method.
		 */
		inline void FoundContained(QuadTree* /*node*/) {};
	};


	QuadTree()
	{
		child[0][0] = child[0][1] = child[1][0] = child[1][1] = NULL;
	};


	~QuadTree()
	{
		// Perform a recursive delete of all children.
		if (child[0][0] != NULL) delete child[0][0];
		if (child[0][1] != NULL) delete child[0][1];
		if (child[1][0] != NULL) delete child[1][0];
		if (child[1][1] != NULL) delete child[1][1];
	};


	/* Checks to see if the child node at grid position x, y on grid level 'level'
	   exists or not. True is retured if it exists otherwise false is returned.
	 */
	bool Empty(const UInt x, const UInt y, const UChar level) const
	{
		return child[(x >> level) & 1][(y >> level) & 1] == NULL;
	};


	/* Adds a new child node to this parent node at grid position x, y
	   on grid level 'level'.
	 */
	QuadTree* Add(const UInt x, const UInt y, const UChar level)
	{
		Assert( Empty(x, y, level) );
		QuadTree* newnode = new QuadTree();
		child[(x >> level) & 1][(y >> level) & 1] = newnode;
		return newnode;
	};


	/* Deletes the child subtree of this node at grid position x, y
	   on grid level 'level'.
	 */
	void Remove(const UInt x, const UInt y, const UChar level)
	{
		Assert( not Empty(x, y, level) );
		delete child[(x >> level) & 1][(y >> level) & 1];
		child[(x >> level) & 1][(y >> level) & 1] = NULL;
	};


	/* Gets the child of this node at grid position x, y on grid level 'level'.
	 */
	QuadTree* Child(const UInt x, const UInt y, const UChar level)
	{
		return child[(x >> level) & 1][(y >> level) & 1];
	};
	
	// Constant method version of Child above.
	const QuadTree* Child(const UInt x, const UInt y, const UChar level) const
	{
		return child[(x >> level) & 1][(y >> level) & 1];
	};


	/* Performs a depth first traversal to the specified level (tree depth),
	   calling FoundOverlapping or Initialise method of the given event handler.
	   Initialise is called if the node has to be created.
	   When the given level is reached then the handlers AddTo method is called
	   for all 4 nodes on that level, for grid positions: (left, bottom) ;
	   (left+1, bottom) ; (left, bottom+1) ; (left+1, bottom+1).
	   For all children nodes for levels i > 'level' the tree is traversed and
	   FoundContained method is called for every child node found.
	 */
	template <class Handler>
	void ForAllOverlapping(const UInt left, const UInt bottom, const UChar level, Handler& handler)
	{
		UInt right = left + 1;
		UInt top = bottom + 1;

		QuadTree* current = this;

		UChar i;
		for (i = level; i > 0; i--)
		{
			if ( OnSameBranch(left, right, i) )
			{
				if ( OnSameBranch(bottom, top, i) )
				{
					if ( current->Empty(left, bottom, i) )
					{
						QuadTree* parent = current;
						current = current->Add(left, bottom, i);
						handler.Initialise(current, parent);
					}
					else
					{
						current = current->Child(left, bottom, i);
						handler.FoundOverlapping(current);
					};
				}
				else
				{
					ForAllOverlappingHorizontal(current, left, right, bottom, i, handler);
					ForAllOverlappingHorizontal(current, left, right, top, i, handler);
					return;
				};
			}
			else
			{
				if ( OnSameBranch(bottom, top, i) )
				{
					ForAllOverlappingVertical(current, left, bottom, top, i, handler);
					ForAllOverlappingVertical(current, right, bottom, top, i, handler);
				}
				else
				{
					ForAllOverlapping(current, left, bottom, i, handler);
					ForAllOverlapping(current, left, top, i, handler);
					ForAllOverlapping(current, right, bottom, i, handler);
					ForAllOverlapping(current, right, top, i, handler);
				};
				return;
			};
		};

		QuadTree* leaf;
		if ( OnSameBranch(left, right, i) )
		{
			leaf = current->Fetch(left, bottom, i, handler);
			handler.AddTo(leaf);
			leaf->Traverse(handler);
			if ( not OnSameBranch(bottom, top, i) )
			{
				leaf = current->Fetch(left, top, i, handler);
				handler.AddTo(leaf);
				leaf->Traverse(handler);
			}
		}
		else
		{
			leaf = current->Fetch(left, bottom, i, handler);
			handler.AddTo(leaf);
			leaf->Traverse(handler);
			leaf = current->Fetch(right, bottom, i, handler);
			handler.AddTo(leaf);
			leaf->Traverse(handler);
			if ( not OnSameBranch(bottom, top, i) )
			{
				leaf = current->Fetch(left, top, i, handler);
				handler.AddTo(leaf);
				leaf->Traverse(handler);
				leaf = current->Fetch(right, top, i, handler);
				handler.AddTo(leaf);
				leaf->Traverse(handler);
			};
		};
	};


	/*
	template <class Function>
	void Traverse(Function process)
	{
		QuadTree* stack[14*4];
		QuadTree** bottom = &stack[14*4];
		QuadTree** top = &stack[14*4-1];
		*top = this;
		do
		{
			QuadTree* current = *top++;  // pop the stack;
			(*process)(current);
			// Push the children of the current node onto the stack.
			if (current->child[0][0] != NULL) *(--top) = current->child[0][0];
			if (current->child[0][1] != NULL) *(--top) = current->child[0][1];
			if (current->child[1][0] != NULL) *(--top) = current->child[1][0];
			if (current->child[1][1] != NULL) *(--top) = current->child[1][1];
		}
		while (top != bottom);
	};
	*/

	/* Traverses the whole sub tree stopping at every child and calling the
	   FoundContained method of the given event handler.
	 */
	template <class Handler>
	void Traverse(Handler& handler)
	{
		if (child[0][0] != NULL)
		{
			handler.FoundContained(child[0][0]);
			child[0][0]->Traverse(handler);
		};
		if (child[0][1] != NULL)
		{
			handler.FoundContained(child[0][1]);
			child[0][1]->Traverse(handler);
		};
		if (child[1][0] != NULL)
		{
			handler.FoundContained(child[1][0]);
			child[1][0]->Traverse(handler);
		};
		if (child[1][1] != NULL)
		{
			handler.FoundContained(child[1][1]);
			child[1][1]->Traverse(handler);
		};
	};


	/* Finds the child that corresponds to the x, y grid position on the
	   given grid level. (Level can also be though of as tree depth).
	 */
	QuadTree* Find(const UInt x, const UInt y, const UChar level)
	{
		QuadTree* current = this;
		for (Char i = level; i >= 0; i--)
		{
			current = current->Child(x, y, i);
			if (current == NULL) break;
		};
		return current;
	};
	
	// The constant version of Find above.
	const QuadTree* Find(const UInt x, const UInt y, const UChar level) const
	{
		QuadTree* current = this;
		for (Char i = level; i >= 0; i--)
		{
			current = current->Child(x, y, i);
			if (current == NULL) break;
		};
		return current;
	};

	
	DataType data;   // The data stored in the tree.

private:
	
	inline bool OnSameBranch(const UInt a, const UInt b, const UChar level) const
	{
		return a >> level == b >> level;
	};


	template <class Handler>
	inline QuadTree* Fetch(const UInt x, const UInt y, const UChar level, Handler& handler)
	{
		QuadTree* node;
		if ( Empty(x, y, level) )
		{
			node = Add(x, y, level);
			handler.Initialise(node, this);   // use this as the parent
		}
		else
		{
			node = Child(x, y, level);
			handler.FoundContained(node);
		};
		return node;
	};


	template <class Handler>
	inline void ForAllOverlapping(QuadTree* current, const UInt x, const UInt y, const UChar level, Handler& handler)
	{
		UChar i;
		for (i = level; i > 0; i--)
		{
			if ( current->Empty(x, y, i) )
			{
				QuadTree* parent = current;
				current = current->Add(x, y, i);
				handler.Initialise(current, parent);
			}
			else
			{
				current = current->Child(x, y, i);
				handler.FoundOverlapping(current);
			};
		};

		QuadTree* leaf = current->Fetch(x, y, i, handler);
		handler.AddTo(leaf);
		leaf->Traverse(handler);
	};


	template <class Handler>
	inline void ForAllOverlappingHorizontal(
			QuadTree* current, const UInt left, const UInt right, const UInt bottom, const UChar level, Handler& handler
		)
	{
		UChar i;
		for (i = level; i > 0; i--)
		{
			if ( OnSameBranch(left, right, i) )
			{
				if ( current->Empty(left, bottom, i) )
				{
					QuadTree* parent = current;
					current = current->Add(left, bottom, i);
					handler.Initialise(current, parent);
				}
				else
				{
					current = current->Child(left, bottom, i);
					handler.FoundOverlapping(current);
				};
			}
			else
			{
				ForAllOverlapping(current, left, bottom, i, handler);
				ForAllOverlapping(current, right, bottom, i, handler);
				return;
			};
		};

		QuadTree* leaf = current->Fetch(left, bottom, i, handler);
		handler.AddTo(leaf);
		leaf->Traverse(handler);
		if ( not OnSameBranch(left, right, i) )
		{
			leaf = current->Fetch(right, bottom, i, handler);
			handler.AddTo(leaf);
			leaf->Traverse(handler);
		};
	};


	template <class Handler>
	inline void ForAllOverlappingVertical(
			QuadTree* current, const UInt left, const UInt bottom, const UInt top, const UChar level, Handler& handler
		)
	{
		UChar i;
		for (i = level; i > 0; i--)
		{
			if ( OnSameBranch(bottom, top, i) )
			{
				if ( current->Empty(left, bottom, i) )
				{
					QuadTree* parent = current;
					current = current->Add(left, bottom, i);
					handler.Initialise(current, parent);
				}
				else
				{
					current = current->Child(left, bottom, i);
					handler.FoundOverlapping(current);
				};
			}
			else
			{
				ForAllOverlapping(current, left, bottom, i, handler);
				ForAllOverlapping(current, left, top, i, handler);
				return;
			};
		};

		QuadTree* leaf = current->Fetch(left, bottom, i, handler);
		handler.AddTo(leaf);
		leaf->Traverse(handler);
		if ( not OnSameBranch(bottom, top, i) )
		{
			leaf = current->Fetch(left, top, i, handler);
			handler.AddTo(leaf);
			leaf->Traverse(handler);
		};
	};

	
	QuadTree* child[2][2];
};


} // Buffers
} // dHLT

#endif // dHLT_BUFFERS_QUAD_TREE_HPP
Commit	Line	Data
8356cc1d	1	////////////////////////////////////////////////////////////////////////////////
	2	//
	3	// Author: Artur Szostak
	4	// Email: artur@alice.phy.uct.ac.za \| artursz@iafrica.com
	5	//
	6	////////////////////////////////////////////////////////////////////////////////
	7
	8	#ifndef dHLT_BUFFERS_QUAD_TREE_HPP
	9	#define dHLT_BUFFERS_QUAD_TREE_HPP
	10
	11	#include "BasicTypes.hpp"
	12	#include "Utils.hpp"
	13	#include "new.hpp"
	14
	15	namespace dHLT
	16	{
	17	namespace Buffers
	18	{
	19
	20
	21	template <typename DataType>
	22	class QuadTree
	23	{
	24	public:
	25
	26	class Handler
	27	{
	28	public:
	29
	30	/* Called when the specified node falls exactly within the region
	31	passed to ForAllOverlapping.
	32	*/
	33	inline void AddTo(QuadTree* /node/) {};
	34
	35	/* Called for the first node of a tree when the specified node has
	36	just been created and needs to be initialised. This method
	37	corresponds to FoundOverlapping except it is called when the node
	38	was not found and must be created.
	39	*/
	40	inline void InitialiseFirst(QuadTree* /node/) {};
	41
	42	/* Called when the specified node has just been created and needs to be
	43	initialised. The specified parent is the parent of the new node. This
	44	method corresponds to FoundOverlapping except it is called when the
	45	node was not found and must be created.
	46	*/
	47	inline void Initialise(QuadTree* /node/, QuadTree* /parent/) {};
	48
	49	/* Called when a node was found that partialy overlaps the region given
	50	to ForAllOverlapping. This method corresponds to Initialise(First)
	51	except it is called when the node has been found.
	52	*/
	53	inline void FoundOverlapping(QuadTree* /node/) {};
	54
	55	/* Called when a child node was found to be contained in the region
	56	given to the ForAllOverlapping method.
	57	*/
	58	inline void FoundContained(QuadTree* /node/) {};
	59	};
	60
	61
	62	QuadTree()
	63	{
	64	child[0][0] = child[0][1] = child[1][0] = child[1][1] = NULL;
65	};
66
67
68	~QuadTree()
69	{
70	// Perform a recursive delete of all children.
71	if (child[0][0] != NULL) delete child[0][0];
72	if (child[0][1] != NULL) delete child[0][1];
73	if (child[1][0] != NULL) delete child[1][0];
74	if (child[1][1] != NULL) delete child[1][1];
75	};
76
77
78	/* Checks to see if the child node at grid position x, y on grid level 'level'
79	exists or not. True is retured if it exists otherwise false is returned.
80	*/
81	bool Empty(const UInt x, const UInt y, const UChar level) const
82	{
83	return child[(x >> level) & 1][(y >> level) & 1] == NULL;
84	};
85
86
87	/* Adds a new child node to this parent node at grid position x, y
88	on grid level 'level'.
89	*/
90	QuadTree* Add(const UInt x, const UInt y, const UChar level)
91	{
92	Assert( Empty(x, y, level) );
93	QuadTree* newnode = new QuadTree();
94	child[(x >> level) & 1][(y >> level) & 1] = newnode;
95	return newnode;
96	};
97
98
99	/* Deletes the child subtree of this node at grid position x, y
100	on grid level 'level'.
101	*/
102	void Remove(const UInt x, const UInt y, const UChar level)
103	{
104	Assert( not Empty(x, y, level) );
105	delete child[(x >> level) & 1][(y >> level) & 1];
106	child[(x >> level) & 1][(y >> level) & 1] = NULL;
107	};
108
109
110	/* Gets the child of this node at grid position x, y on grid level 'level'.
111	*/
112	QuadTree* Child(const UInt x, const UInt y, const UChar level)
113	{
114	return child[(x >> level) & 1][(y >> level) & 1];
115	};
116
117	// Constant method version of Child above.
118	const QuadTree* Child(const UInt x, const UInt y, const UChar level) const
119	{
120	return child[(x >> level) & 1][(y >> level) & 1];
121	};
122
123
124	/* Performs a depth first traversal to the specified level (tree depth),
125	calling FoundOverlapping or Initialise method of the given event handler.
126	Initialise is called if the node has to be created.
127	When the given level is reached then the handlers AddTo method is called
128	for all 4 nodes on that level, for grid positions: (left, bottom) ;
129	(left+1, bottom) ; (left, bottom+1) ; (left+1, bottom+1).
130	For all children nodes for levels i > 'level' the tree is traversed and
131	FoundContained method is called for every child node found.
132	*/
133	template <class Handler>
134	void ForAllOverlapping(const UInt left, const UInt bottom, const UChar level, Handler& handler)
135	{
136	UInt right = left + 1;
137	UInt top = bottom + 1;
138
139	QuadTree* current = this;
140
141	UChar i;
142	for (i = level; i > 0; i--)
143	{
144	if ( OnSameBranch(left, right, i) )
145	{
146	if ( OnSameBranch(bottom, top, i) )
147	{
148	if ( current->Empty(left, bottom, i) )
149	{
150	QuadTree* parent = current;
151	current = current->Add(left, bottom, i);
152	handler.Initialise(current, parent);
153	}
154	else
155	{
156	current = current->Child(left, bottom, i);
157	handler.FoundOverlapping(current);
158	};
159	}
160	else
161	{
162	ForAllOverlappingHorizontal(current, left, right, bottom, i, handler);
163	ForAllOverlappingHorizontal(current, left, right, top, i, handler);
164	return;
165	};
166	}
167	else
168	{
169	if ( OnSameBranch(bottom, top, i) )
170	{
171	ForAllOverlappingVertical(current, left, bottom, top, i, handler);
172	ForAllOverlappingVertical(current, right, bottom, top, i, handler);
173	}
174	else
175	{
176	ForAllOverlapping(current, left, bottom, i, handler);
177	ForAllOverlapping(current, left, top, i, handler);
178	ForAllOverlapping(current, right, bottom, i, handler);
179	ForAllOverlapping(current, right, top, i, handler);
180	};
181	return;
182	};
183	};
184
185	QuadTree* leaf;
186	if ( OnSameBranch(left, right, i) )
187	{
188	leaf = current->Fetch(left, bottom, i, handler);
189	handler.AddTo(leaf);
190	leaf->Traverse(handler);
191	if ( not OnSameBranch(bottom, top, i) )
192	{
193	leaf = current->Fetch(left, top, i, handler);
194	handler.AddTo(leaf);
195	leaf->Traverse(handler);
196	}
197	}
198	else
199	{
200	leaf = current->Fetch(left, bottom, i, handler);
201	handler.AddTo(leaf);
202	leaf->Traverse(handler);
203	leaf = current->Fetch(right, bottom, i, handler);
204	handler.AddTo(leaf);
205	leaf->Traverse(handler);
206	if ( not OnSameBranch(bottom, top, i) )
207	{
208	leaf = current->Fetch(left, top, i, handler);
209	handler.AddTo(leaf);
210	leaf->Traverse(handler);
211	leaf = current->Fetch(right, top, i, handler);
212	handler.AddTo(leaf);
213	leaf->Traverse(handler);
214	};
215	};
216	};
217
218
219	/*
220	template <class Function>
221	void Traverse(Function process)
222	{
223	QuadTree* stack[14*4];
224	QuadTree** bottom = &stack[14*4];
225	QuadTree** top = &stack[14*4-1];
226	*top = this;
227	do
228	{
229	QuadTree* current = *top++; // pop the stack;
230	(*process)(current);
231	// Push the children of the current node onto the stack.
232	if (current->child[0][0] != NULL) *(--top) = current->child[0][0];
233	if (current->child[0][1] != NULL) *(--top) = current->child[0][1];
234	if (current->child[1][0] != NULL) *(--top) = current->child[1][0];
235	if (current->child[1][1] != NULL) *(--top) = current->child[1][1];
236	}
237	while (top != bottom);
238	};
239	*/
240
241	/* Traverses the whole sub tree stopping at every child and calling the
242	FoundContained method of the given event handler.
243	*/
244	template <class Handler>
245	void Traverse(Handler& handler)
246	{
247	if (child[0][0] != NULL)
248	{
249	handler.FoundContained(child[0][0]);
250	child[0][0]->Traverse(handler);
251	};
252	if (child[0][1] != NULL)
253	{
254	handler.FoundContained(child[0][1]);
255	child[0][1]->Traverse(handler);
256	};
257	if (child[1][0] != NULL)
258	{
259	handler.FoundContained(child[1][0]);
260	child[1][0]->Traverse(handler);
261	};
262	if (child[1][1] != NULL)
263	{
264	handler.FoundContained(child[1][1]);
265	child[1][1]->Traverse(handler);
266	};
267	};
268
269
270	/* Finds the child that corresponds to the x, y grid position on the
271	given grid level. (Level can also be though of as tree depth).
272	*/
273	QuadTree* Find(const UInt x, const UInt y, const UChar level)
274	{
275	QuadTree* current = this;
276	for (Char i = level; i >= 0; i--)
277	{
278	current = current->Child(x, y, i);
279	if (current == NULL) break;
280	};
281	return current;
282	};
283
284	// The constant version of Find above.
285	const QuadTree* Find(const UInt x, const UInt y, const UChar level) const
286	{
287	QuadTree* current = this;
288	for (Char i = level; i >= 0; i--)
289	{
290	current = current->Child(x, y, i);
291	if (current == NULL) break;
292	};
293	return current;
294	};
295
296
297	DataType data; // The data stored in the tree.
298
299	private:
300
301	inline bool OnSameBranch(const UInt a, const UInt b, const UChar level) const
302	{
303	return a >> level == b >> level;
304	};
305
306
307	template <class Handler>
308	inline QuadTree* Fetch(const UInt x, const UInt y, const UChar level, Handler& handler)
309	{
310	QuadTree* node;
311	if ( Empty(x, y, level) )
312	{
313	node = Add(x, y, level);
314	handler.Initialise(node, this); // use this as the parent
315	}
316	else
317	{
318	node = Child(x, y, level);
319	handler.FoundContained(node);
320	};
321	return node;
322	};
323
324
325	template <class Handler>
326	inline void ForAllOverlapping(QuadTree* current, const UInt x, const UInt y, const UChar level, Handler& handler)
327	{
328	UChar i;
329	for (i = level; i > 0; i--)
330	{
331	if ( current->Empty(x, y, i) )
332	{
333	QuadTree* parent = current;
334	current = current->Add(x, y, i);
335	handler.Initialise(current, parent);
336	}
337	else
338	{
339	current = current->Child(x, y, i);
340	handler.FoundOverlapping(current);
341	};
342	};
343
344	QuadTree* leaf = current->Fetch(x, y, i, handler);
345	handler.AddTo(leaf);
346	leaf->Traverse(handler);
347	};
348
349
350	template <class Handler>
351	inline void ForAllOverlappingHorizontal(
352	QuadTree* current, const UInt left, const UInt right, const UInt bottom, const UChar level, Handler& handler
353	)
354	{
355	UChar i;
356	for (i = level; i > 0; i--)
357	{
358	if ( OnSameBranch(left, right, i) )
359	{
360	if ( current->Empty(left, bottom, i) )
361	{
362	QuadTree* parent = current;
363	current = current->Add(left, bottom, i);
364	handler.Initialise(current, parent);
365	}
366	else
367	{
368	current = current->Child(left, bottom, i);
369	handler.FoundOverlapping(current);
370	};
371	}
372	else
373	{
374	ForAllOverlapping(current, left, bottom, i, handler);
375	ForAllOverlapping(current, right, bottom, i, handler);
376	return;
377	};
378	};
379
380	QuadTree* leaf = current->Fetch(left, bottom, i, handler);
381	handler.AddTo(leaf);
382	leaf->Traverse(handler);
383	if ( not OnSameBranch(left, right, i) )
384	{
385	leaf = current->Fetch(right, bottom, i, handler);
386	handler.AddTo(leaf);
387	leaf->Traverse(handler);
388	};
389	};
390
391
392	template <class Handler>
393	inline void ForAllOverlappingVertical(
394	QuadTree* current, const UInt left, const UInt bottom, const UInt top, const UChar level, Handler& handler
395	)
396	{
397	UChar i;
398	for (i = level; i > 0; i--)
399	{
400	if ( OnSameBranch(bottom, top, i) )
401	{
402	if ( current->Empty(left, bottom, i) )
403	{
404	QuadTree* parent = current;
405	current = current->Add(left, bottom, i);
406	handler.Initialise(current, parent);
407	}
408	else
409	{
410	current = current->Child(left, bottom, i);
411	handler.FoundOverlapping(current);
412	};
413	}
414	else
415	{
416	ForAllOverlapping(current, left, bottom, i, handler);
417	ForAllOverlapping(current, left, top, i, handler);
418	return;
419	};
420	};
421
422	QuadTree* leaf = current->Fetch(left, bottom, i, handler);
423	handler.AddTo(leaf);
424	leaf->Traverse(handler);
425	if ( not OnSameBranch(bottom, top, i) )
426	{
427	leaf = current->Fetch(left, top, i, handler);
428	handler.AddTo(leaf);
429	leaf->Traverse(handler);
430	};
431	};
432
433
434	QuadTree* child[2][2];
435	};
436
437
438	} // Buffers
439	} // dHLT
440
441	#endif // dHLT_BUFFERS_QUAD_TREE_HPP