ternarytree.cs

itextsharp for pdf document

			sc = na;
		}

		public int Size {
			get {
				return length;
			}
		}

		public Object Clone() {
			TernaryTree t = new TernaryTree();
			t.lo = (char[])this.lo.Clone();
			t.hi = (char[])this.hi.Clone();
			t.eq = (char[])this.eq.Clone();
			t.sc = (char[])this.sc.Clone();
			t.kv = (CharVector)this.kv.Clone();
			t.root = this.root;
			t.freenode = this.freenode;
			t.length = this.length;

			return t;
		}

		/**
		 * Recursively insert the median first and then the median of the
		 * lower and upper halves, and so on in order to get a balanced
		 * tree. The array of keys is assumed to be sorted in ascending
		 * order.
		 */
		protected void insertBalanced(string[] k, char[] v, int offset, int n) {
			int m;
			if (n < 1)
				return;
			m = n >> 1;

			insert(k[m + offset], v[m + offset]);
			insertBalanced(k, v, offset, m);

			insertBalanced(k, v, offset + m + 1, n - m - 1);
		}


		/**
		 * Balance the tree for best search performance
		 */
		public void balance() {
			// System.out.print("Before root splitchar = "); System.out.println(sc[root]);

			int i = 0, n = length;
			string[] k = new string[n];
			char[] v = new char[n];
			Iterator iter = new Iterator(this);
			while (iter.hasMoreElements()) {
				v[i] = iter.Value;
				k[i++] = (string)iter.nextElement();
			}
			init();
			insertBalanced(k, v, 0, n);

			// With uniform letter distribution sc[root] should be around 'm'
			// System.out.print("After root splitchar = "); System.out.println(sc[root]);
		}

		/**
		 * Each node stores a character (splitchar) which is part of
		 * some key(s). In a compressed branch (one that only contain
		 * a single string key) the trailer of the key which is not
		 * already in nodes is stored  externally in the kv array.
		 * As items are inserted, key substrings decrease.
		 * Some substrings may completely  disappear when the whole
		 * branch is totally decompressed.
		 * The tree is traversed to find the key substrings actually
		 * used. In addition, duplicate substrings are removed using
		 * a map (implemented with a TernaryTree!).
		 *
		 */
		public void trimToSize() {
			// first balance the tree for best performance
			balance();

			// redimension the node arrays
			redimNodeArrays(freenode);

			// ok, compact kv array
			CharVector kx = new CharVector();
			kx.alloc(1);
			TernaryTree map = new TernaryTree();
			compact(kx, map, root);
			kv = kx;
			kv.trimToSize();
		}

		private void compact(CharVector kx, TernaryTree map, char p) {
			int k;
			if (p == 0)
				return;
			if (sc[p] == 0xFFFF) {
				k = map.find(kv.Arr, lo[p]);
				if (k < 0) {
					k = kx.alloc(strlen(kv.Arr, lo[p]) + 1);
					strcpy(kx.Arr, k, kv.Arr, lo[p]);
					map.insert(kx.Arr, k, (char)k);
				}
				lo[p] = (char)k;
			} else {
				compact(kx, map, lo[p]);
				if (sc[p] != 0)
					compact(kx, map, eq[p]);
				compact(kx, map, hi[p]);
			}
		}


		public Iterator Keys {
			get {
				return new Iterator(this);
			}
		}

		public class Iterator {

			/**
			* current node index
			*/
			int cur;

			/**
			 * current key
			 */
			string curkey;

			/**
			 * TernaryTree parent
			 */
			TernaryTree parent; 

			private class Item : ICloneable {
				internal char parent;
				internal char child;

				public Item() {
					parent = (char)0;
					child = (char)0;
				}

				public Item(char p, char c) {
					parent = p;
					child = c;
				}

				public Object Clone() {
					return new Item(parent, child);
				}

			}

			/**
			 * Node stack
			 */
			Stack ns;

			/**
			 * key stack implemented with a StringBuilder
			 */
			StringBuilder ks;

			public Iterator(TernaryTree parent) {
				this.parent = parent;
				cur = -1;
				ns = new Stack();
				ks = new StringBuilder();
				rewind();
			}

			public void rewind() {
				ns.Clear();
				ks.Length = 0;
				cur = parent.root;
				run();
			}

			public Object nextElement() {
				string res = curkey;
				cur = up();
				run();
				return res;
			}

			public char Value {
				get {
					if (cur >= 0)
						return this.parent.eq[cur];
					return (char)0;
				}
			}

			public bool hasMoreElements() {
				return (cur != -1);
			}

			/**
			 * traverse upwards
			 */
			private int up() {
				Item i = new Item();
				int res = 0;

				if (ns.Count == 0)
					return -1;

				if (cur != 0 && parent.sc[cur] == 0)
					return parent.lo[cur];

				bool climb = true;

				while (climb) {
					i = (Item)ns.Pop();
					i.child++;
					switch (i.child) {
						case (char)1:
							if (parent.sc[i.parent] != 0) {
								res = parent.eq[i.parent];
								ns.Push(i.Clone());
								ks.Append(parent.sc[i.parent]);
							} else {
								i.child++;
								ns.Push(i.Clone());
								res = parent.hi[i.parent];
							}
							climb = false;
							break;

						case (char)2:
							res = parent.hi[i.parent];
							ns.Push(i.Clone());
							if (ks.Length > 0)
								ks.Length = ks.Length - 1;    // pop
							climb = false;
							break;

						default:
							if (ns.Count == 0)
								return -1;
							climb = true;
							break;
					}
				}
				return res;
			}

			/**
			 * traverse the tree to find next key
			 */
			private int run() {
				if (cur == -1)
					return -1;

				bool leaf = false;
				for (; ; ) {
					// first go down on low branch until leaf or compressed branch
					while (cur != 0) {
						if (parent.sc[cur] == 0xFFFF) {
							leaf = true;
							break;
						}
						ns.Push(new Item((char)cur, '\u0000'));
						if (parent.sc[cur] == 0) {
							leaf = true;
							break;
						}
						cur = parent.lo[cur];
					}
					if (leaf)
						break;
					// nothing found, go up one node and try again
					cur = up();
					if (cur == -1) {
						return -1;
					}
				}
				// The current node should be a data node and
				// the key should be in the key stack (at least partially)
				StringBuilder buf = new StringBuilder(ks.ToString());
				if (parent.sc[cur] == 0xFFFF) {
					int p = parent.lo[cur];
					while (parent.kv[p] != 0)
						buf.Append(parent.kv[p++]);
				}
				curkey = buf.ToString();
				return 0;
			}

		}

		public virtual void printStats() {
			Console.Error.WriteLine("Number of keys = " + length.ToString());
			Console.Error.WriteLine("Node count = " + freenode.ToString());
			// Console.Error.WriteLine("Array length = " + int.ToString(eq.Length));
			Console.Error.WriteLine("Key Array length = "
					   + kv.Length.ToString());

			/*
			 * for(int i=0; i<kv.Length; i++)
			 * if ( kv[i] != 0 )
			 * System.out.print(kv[i]);
			 * else
			 * System.out.println("");
			 * System.out.println("Keys:");
			 * for(Enumeration enum = keys(); enum.hasMoreElements(); )
			 * System.out.println(enum.nextElement());
			 */

		}
	}
}