Context Navigation

source: branches/HeuristicLab.Problems.GaussianProcessTuning/ILNumerics.2.14.4735.573/Data/ILAVLTree.cs @ 9426

Visit:

Last change on this file since 9426 was 9102, checked in by gkronber, 12 years ago
#1967: ILNumerics source for experimentation
File size: 23.5 KB

Line
1	///
2	/// This file is part of ILNumerics Community Edition.
3	///
4	/// ILNumerics Community Edition - high performance computing for applications.
5	/// Copyright (C) 2006 - 2012 Haymo Kutschbach, http://ilnumerics.net
6	///
7	/// ILNumerics Community Edition is free software: you can redistribute it and/or modify
8	/// it under the terms of the GNU General Public License version 3 as published by
9	/// the Free Software Foundation.
10	///
11	/// ILNumerics Community Edition is distributed in the hope that it will be useful,
12	/// but WITHOUT ANY WARRANTY; without even the implied warranty of
13	/// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	/// GNU General Public License for more details.
15	///
16	/// You should have received a copy of the GNU General Public License
17	/// along with ILNumerics Community Edition. See the file License.txt in the root
18	/// of your distribution package. If not, see <http://www.gnu.org/licenses/>.
19	///
20	/// In addition this software uses the following components and/or licenses:
21	///
22	/// =================================================================================
23	/// The Open Toolkit Library License
24	///
25	/// Copyright (c) 2006 - 2009 the Open Toolkit library.
26	///
27	/// Permission is hereby granted, free of charge, to any person obtaining a copy
28	/// of this software and associated documentation files (the "Software"), to deal
29	/// in the Software without restriction, including without limitation the rights to
30	/// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
31	/// the Software, and to permit persons to whom the Software is furnished to do
32	/// so, subject to the following conditions:
33	///
34	/// The above copyright notice and this permission notice shall be included in all
35	/// copies or substantial portions of the Software.
36	///
37	/// =================================================================================
38	///
39
40	using System;
41	using System.Collections.Generic;
42	using System.Linq;
43	using System.Text;
44	using keytype = System.Int64;
45
46	namespace ILNumerics.Data {
47	/// <summary>
48	/// AVL balanced search tree
49	/// </summary>
50	/// <remarks>The tree stores unique keys (type:System.Int64, configurable via build) in a balanced search tree.
51	/// <para>The implementation is optimized for random seek access and consecutive write access - if no matching key found.
52	/// Also, the next higher key for a given query can be returned in O(1).</para>
53	/// <para>The AVL tree class is not intended to be used directly. It supports the ILNumerics infrastructure (ILMemoryPool)
54	/// internally.</para></remarks>
55	internal class ILAVLTree {
56
57	internal ILAVLTreeNode m_root = getNode();
58	private int m_nodeCount = 0;
59	#if DEBUG
60	internal int m_itemCount = 0;
61	#endif
62
63	#region caching
64	private static readonly int MAX_STACKSIZE = 50;
65	private static readonly ILAVLTreeNode[] s_stack = new ILAVLTreeNode[MAX_STACKSIZE];
66	private static readonly int[] s_dirs = new int[MAX_STACKSIZE];
67	#endregion
68
69	#region public interface
70	/// <summary>
71	/// Return number of keys currently existing in the tree
72	/// </summary>
73	public int Count {
74	get { return m_nodeCount; }
75	}
76	/// <summary>
77	/// Check and add a key to the collection
78	/// </summary>
79	/// <param name="key">Key</param>
80	/// <remarks>The function makes sure, the key is stored in the tree.</remarks>
81	public void Add(keytype key) {
82	int depth, added2Side = 0;
83	if (FindNode(key, m_root, s_stack, s_dirs, out depth)) {
84	// nothing to do - key is already there
85	return;
86	} else {
87	// parent is the node where the key should be inserted below
88	ILAVLTreeNode newNode = getNode();
89	newNode.key = key;
90	m_nodeCount++;
91	added2Side = s_dirs[depth--];
92	if (added2Side == -1) { // insert as left child
93	System.Diagnostics.Debug.Assert(s_stack[depth+1] == null);
94	s_stack[depth].left = newNode;
95	s_stack[depth].balance--;
96	} else { // insert as right child
97	System.Diagnostics.Debug.Assert(s_stack[depth+1] == null);
98	s_stack[depth].right = newNode;
99	s_stack[depth].balance++;
100	}
101	}
102	// check balances along 's_stack' path -> up to root
103	// depth is at parent level now
104	ILAVLTreeNode node = s_stack[depth];
105	while (depth > 0) {
106	if (node.balance == 0) {
107	return;
108	}
109	if (node.balance * node.balance == 1) {
110	node = s_stack[--depth];
111	node.balance += s_dirs[depth+1];
112	continue;
113	}
114	if (node.balance == 2) {
115	if (node.right.balance >= 0) {
116	// rebalance RR -> simple left rotation
117	ILAVLTreeNode node2 = node.right;
118	if (s_dirs[depth] == 1) {
119	s_stack[depth-1].right = node2;
120	} else {
121	s_stack[depth-1].left = node2;
122	}
123	if (node2.balance == 0) {
124	node.balance = 1;
125	node2.balance = -1;
126	} else {
127	System.Diagnostics.Debug.Assert (node2.balance == 1);
128	node.balance = 0;
129	node2.balance = 0;
130	}
131	node.right = node2.left;
132	node2.left = node;
133	} else {
134	// rebalance RL -> double left rotation
135	ILAVLTreeNode node2 = node.right;
136	ILAVLTreeNode node3 = node2.left;
137	if (s_dirs[depth] == 1) {
138	s_stack[depth-1].right = node3;
139	} else {
140	s_stack[depth-1].left = node3;
141	}
142	if (node3.balance == -1) {
143	node2.balance = 1;
144	node.balance = 0;
145	} else if (node3.balance == 1) {
146	node2.balance = 0;
147	node.balance = -1;
148	} else {
149	node2.balance = 0;
150	node.balance = 0;
151	}
152	node3.balance = 0;
153
154	node.right = node3.left;
155	node2.left = node3.right;
156	node3.left = node;
157	node3.right = node2;
158	}
159	} else {
160	System.Diagnostics.Debug.Assert(node.balance == -2);
161	if (node.left.balance <= 0) {
162	ILAVLTreeNode node2 = node.left;
163	// rebalance LL -> simple rotate right
164	if (s_dirs[depth] == 1) {
165	s_stack[depth-1].right = node2;
166	} else {
167	s_stack[depth-1].left = node2;
168	}
169	if (node2.balance == 0) {
170	node.balance = -1;
171	node2.balance = 1;
172	} else {
173	System.Diagnostics.Debug.Assert (node2.balance == -1);
174	node.balance = 0;
175	node2.balance = 0;
176	}
177	node.left = node2.right;
178	node2.right = node;
179	} else {
180	// rebalance LR - double right rotation
181	ILAVLTreeNode node2 = node.left;
182	ILAVLTreeNode node3 = node2.right;
183	if (s_dirs[depth] == 1) {
184	s_stack[depth-1].right = node3;
185	} else {
186	s_stack[depth-1].left = node3;
187	}
188	if (node3.balance == 1) {
189	node2.balance = -1;
190	node.balance = 0;
191	} else if (node3.balance == -1) {
192	node2.balance = 0;
193	node.balance = 1;
194	} else {
195	node2.balance = 0;
196	node.balance = 0;
197	}
198	node3.balance = 0;
199
200	node.left = node3.right;
201	node2.right = node3.left;
202	node3.right = node;
203	node3.left = node2;
204	}
205	}
206	#if DEBUG
207	//if (!CheckTree()) {
208	// return;
209	//}
210	#endif
211	return;
212	}
213	}
214	/// <summary>
215	/// Remove key from tree
216	/// </summary>
217	/// <param name="key">Key to be removed</param>
218	/// <remarks>The function makes sure, the tree does not contain a node with the given key.</remarks>
219	public void Remove(keytype key) {
220	int depth;
221	if (!FindNode(key, m_root, s_stack, s_dirs, out depth)) {
222	return;
223	}
224	#if DEBUG
225	int remDepth = depth;
226	#endif
227	// last entry in stack is the matching node
228	ILAVLTreeNode cur = s_stack[depth];
229	if (cur.left != null) {
230	if (cur.right != null) {
231	// find replacement node
232	ILAVLTreeNode orig = cur;
233	cur = cur.left;
234	s_stack[++depth] = cur;
235	s_dirs[depth] = -1;
236	while (cur.right != null) {
237	cur = cur.right;
238	s_stack[++depth] = cur;
239	s_dirs[depth] = 1;
240	}
241	// exchange keys with current node
242	orig.key = cur.key;
243	cur = cur.left;
244	} else {
245	cur = cur.left;
246	}
247	} else {
248	if (cur.right != null) {
249	// replace with right child
250	cur = cur.right;
251	} else {
252	// no childs simply delete cur
253	cur = null;
254	}
255	}
256	depth--;
257	ILAVLTreeNode par = s_stack[depth];
258	if (s_dirs[depth+1] == 1) {
259	par.right = cur;
260	par.balance--;
261	} else {
262	par.left = cur;
263	par.balance++;
264	}
265	m_nodeCount--;
266	#if DEBUG
267	if (par.left != null)
268	System.Diagnostics.Debug.Assert(par.left != par);
269	if (par.right != null)
270	System.Diagnostics.Debug.Assert(par.right != par);
271
272	#endif
273	#region rebalance
274	cur = par;
275	while (depth > 0) {
276	if (cur.balance == 0) {
277	cur = s_stack[--depth];
278	cur.balance -= s_dirs[depth + 1];
279	continue;
280	}
281	if (cur.balance * cur.balance == 1) {
282	break;
283	} else if (cur.balance == 2) {
284	#region needs left rotations
285	if (cur.right.balance >= 0) {
286	// rebalance RR -> simple left rotation
287	ILAVLTreeNode node2 = cur.right;
288	if (s_dirs[depth] == 1) {
289	s_stack[depth - 1].right = node2;
290	} else {
291	s_stack[depth - 1].left = node2;
292	}
293	cur.right = node2.left;
294	node2.left = cur;
295	if (node2.balance == 0) {
296	cur.balance = 1;
297	node2.balance = -1;
298	break;
299	} else {
300	System.Diagnostics.Debug.Assert(node2.balance == 1);
301	cur.balance = 0;
302	node2.balance = 0;
303	}
304	} else {
305	// rebalance RL -> double left rotation
306	ILAVLTreeNode node2 = cur.right;
307	ILAVLTreeNode node3 = node2.left;
308	if (s_dirs[depth] == 1) {
309	s_stack[depth - 1].right = node3;
310	} else {
311	s_stack[depth - 1].left = node3;
312	}
313	if (node3.balance == -1) {
314	node2.balance = 1;
315	cur.balance = 0;
316	} else if (node3.balance == 1) {
317	node2.balance = 0;
318	cur.balance = -1;
319	} else {
320	node2.balance = 0;
321	cur.balance = 0;
322	}
323	node3.balance = 0;
324
325	cur.right = node3.left;
326	node2.left = node3.right;
327	node3.left = cur;
328	node3.right = node2;
329	}
330	#endregion
331	} else {
332	#region needs right rotation
333	System.Diagnostics.Debug.Assert(cur.balance == -2);
334	if (cur.left.balance <= 0) {
335	ILAVLTreeNode node2 = cur.left;
336	// rebalance LL -> simple rotate right
337	if (s_dirs[depth] == 1) {
338	s_stack[depth - 1].right = node2;
339	} else {
340	s_stack[depth - 1].left = node2;
341	}
342	cur.left = node2.right;
343	node2.right = cur;
344	if (node2.balance == 0) {
345	cur.balance = -1;
346	node2.balance = 1;
347	break;
348	} else {
349	System.Diagnostics.Debug.Assert(node2.balance == -1);
350	cur.balance = 0;
351	node2.balance = 0;
352	}
353	} else {
354	// rebalance LR - double right rotation
355	ILAVLTreeNode node2 = cur.left;
356	ILAVLTreeNode node3 = node2.right;
357	if (s_dirs[depth] == 1) {
358	s_stack[depth - 1].right = node3;
359	} else {
360	s_stack[depth - 1].left = node3;
361	}
362	if (node3.balance == 1) {
363	node2.balance = -1;
364	cur.balance = 0;
365	} else if (node3.balance == -1) {
366	node2.balance = 0;
367	cur.balance = 1;
368	} else {
369	node2.balance = 0;
370	cur.balance = 0;
371	}
372	node3.balance = 0;
373
374	cur.left = node3.right;
375	node2.right = node3.left;
376	node3.right = cur;
377	node3.left = node2;
378	}
379	#endregion
380	}
381	// populate to parent
382	if (--depth <= 0)
383	break;
384	cur = s_stack[depth];
385	cur.balance -= s_dirs[depth + 1];
386	}
387	#endregion
388	#if DEBUG
389	//if (!CheckTree()) {
390	// return;
391	//}
392	#endif
393	}
394	/// <summary>
395	/// Find next higher key
396	/// </summary>
397	/// <param name="key">Key to find</param>
398	/// <returns>The key with the next higher value compared with <paramref name="key"/>, or -1 if no such key exists</returns>
399	public keytype Next(keytype key) {
400	if (m_root.right == null) {
401	return -1;
402	}
403	int level = 0;
404	if (!FindNode(key, m_root, s_stack, s_dirs, out level) && level > 0)
405	level--;
406	ILAVLTreeNode node = s_stack[level];
407	if (node.key >= key) return node.key;
408	node = NextAsc(s_stack[level], s_stack, s_dirs, level);
409	if (node != null && node.key > key)
410	return node.key;
411	return -1;
412	}
413	/// <summary>
414	/// Clear the tree from all keys
415	/// </summary>
416	internal void Clear() {
417	m_root.right = null;
418	#if DEBUG
419	m_nodeCount = 0;
420	m_itemCount = 0;
421	#endif
422	}
423	#endregion
424
425	#region private helper
426	private static bool FindNode(keytype key, ILAVLTreeNode cur, ILAVLTreeNode[] path, int[] dirs, out int level) {
427	int depth = 0;
428	while (true) {
429	path[depth] = cur;
430	//if (cur.isNil) {
431	// //Console.Out.WriteLine("Key:{0} depth: {1} {2}",cur.key, depth, s_dirs[depth] );
432	// level = depth;
433	// return false;
434	//}
435	if (cur.key == key) {
436	level = depth;
437	return true;
438	} else {
439	if (key < cur.key) {
440	dirs[++depth] = -1;
441	path[depth] = cur.left;
442	if (cur.left == null) {
443	level = depth;
444	return false;
445	}
446	cur = cur.left;
447	} else { // key > cur.key
448	dirs[++depth] = 1;
449	path[depth] = cur.right;
450	if (cur.right == null) {
451	level = depth;
452	return false;
453	}
454	cur = cur.right;
455	}
456	}
457	}
458	}
459	private static ILAVLTreeNode NextAsc(ILAVLTreeNode node, ILAVLTreeNode[] path, int[] dirs, int level) {
460	ILAVLTreeNode ret = node;
461	if (node.right != null) {
462	node = node.right;
463	while (node.left != null) {
464	node = node.left;
465	}
466	ret = node;
467	} else {
468	while (level > 0) {
469	// dirs[0] is always 0 (dummy root node)
470	if (dirs[level] == -1) {
471	ret = path[--level];
472	break;
473	}
474	level--;
475	}
476	}
477	return ret;
478	}
479	/// <summary>
480	/// check the consistency of the tree
481	/// </summary>
482	/// <returns></returns>
483	internal bool CheckTree() {
484	if (m_root.right == null)
485	return true;
486	ILAVLTreeNode cur = m_root.right;
487	while (cur.left != null)
488	cur = cur.left;
489	keytype key = cur.key;
490	int depth;
491	ILAVLTreeNode node = cur;
492	do {
493	Console.Out.Write("checking node: " + node.key);
494	if (FindNode(node.key, m_root, s_stack, s_dirs, out depth)) {
495	if (s_stack[depth] != node)
496	return false;
497	if (!checkTree(node)) {
498	return false;
499	}
500	node = NextAsc(node, s_stack, s_dirs, depth);
501	} else {
502	return false;
503	}
504	Console.Out.WriteLine("... ok");
505	} while (node != null);
506	return true;
507	}
508	private static ILAVLTreeNode getNode() {
509	var ret = new ILAVLTreeNode();
510	ret.key = -1;
511	ret.balance = 0;
512	//ret.right = ret;
513	return ret;
514	}
515	private bool checkTree(int key) {
516	ILAVLTreeNode[] tmpNodes = new ILAVLTreeNode[50];
517	int[] tmpKeys = new int[50];
518	int level;
519	if (!FindNode(key, m_root, tmpNodes, tmpKeys, out level)) {
520	return false;
521	}
522	return checkTree(tmpNodes[level]);
523	}
524	private static bool checkTree(ILAVLTreeNode root) {
525	// check balance condition
526	int ltree = 0, rtree = 0;
527	if (root.left != null) {
528	ltree = levelTree(root.left);
529	}
530	if (root.right != null) {
531	rtree = levelTree(root.right);
532	}
533	int bal = rtree - ltree;
534	if (root.balance != bal)
535	return false;
536	if (bal * bal > 1) {
537	return false;
538	}
539
540	return true;
541
542	}
543	private static int levelTree(ILAVLTreeNode root) {
544	if (root.left == null && root.right == null) {
545	return 1;
546	} else {
547	int ltree = 0, rtree = 0;
548	if (root.left != null) {
549	ltree = levelTree(root.left);
550	}
551	if (root.right != null) {
552	rtree = levelTree(root.right);
553	}
554	return Math.Max(ltree,rtree) + 1;
555	}
556	}
557	#endregion
558	/// <summary>
559	/// an AVL tree node
560	/// </summary>
561	public class ILAVLTreeNode {
562	/// <summary>
563	/// Key
564	/// </summary>
565	public keytype key;
566	/// <summary>
567	/// Right child
568	/// </summary>
569	public ILAVLTreeNode right;
570	/// <summary>
571	/// Left child
572	/// </summary>
573	public ILAVLTreeNode left;
574	/// <summary>
575	/// Balance factor for the node
576	/// </summary>
577	public int balance;
578	/// <summary>
579	/// Rext representation of the node
580	/// </summary>
581	/// <returns>String representation for the node</returns>
582	public override string ToString() {
583	return String.Format("{0} [{1}-{2}]",key,(left == null) ? "" : left.key.ToString(), (right == null) ? "" : right.key.ToString());
584	}
585	}
586
587	}
588	}

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Update cookies preferences