context: // The bplusdotnet package is Copywrite Aaron Watters 2004. 
  // the package is licensed under the BSD open source license
  
  using System;
  using System.Collections;
  
  // delete next
  
  namespace BplusDotNet
  {
  	/// <summary>
  	/// Bplustree mapping fixed length strings (byte sequences) to longs (seek positions in file indexed).
  	/// "Next leaf pointer" is not used since it increases the chance of file corruption on failure.
  	/// All modifications are "shadowed" until a flush of all modifications succeeds.  Modifications are
  	/// "hardened" when the header record is rewritten with a new root.  This design trades a few "unneeded"
  	/// buffer writes for lower likelihood of file corruption.
  	/// </summary>
  	public class BplusTreeLong: ITreeIndex
  	{
  		public System.IO.Stream fromfile;
  		// should be read only
  		public bool DontUseCulture = false;
  		public System.Globalization.CultureInfo cultureContext;
  		System.Globalization.CompareInfo cmp = null;
  		// should be read only
  		public BufferFile buffers;
  		// should be read only
  		public int buffersize;
  		// should be read only
  		public int KeyLength;
  		public long seekStart = 0;
  		public static byte[] HEADERPREFIX = { 98, 112, 78, 98, 112 };
  		// header consists of 
  		// prefix | version | node size | key size | culture id | buffer number of root | buffer number of free list head
  		int headersize = HEADERPREFIX.Length + 1 + BufferFile.INTSTORAGE*3 + BufferFile.LONGSTORAGE*2;
  		public const byte VERSION = 0;
  		// size of allocated key space in each node (should be a read only property)
  		public int NodeSize;
  		BplusNode root = null;
  		long rootSeek; 
  		long freeHeadSeek;
  		public Hashtable FreeBuffersOnCommit = new Hashtable();
  		public Hashtable FreeBuffersOnAbort = new Hashtable();
  		Hashtable IdToTerminalNode = new Hashtable();
  		Hashtable TerminalNodeToId = new Hashtable();
  		int TerminalNodeCount = 0;
  		int LowerTerminalNodeCount = 0;
  		int FifoLimit = 100;
  		public static int NULLBUFFERNUMBER = -1;
  		public static byte NONLEAF = 0, LEAF = 1, FREE = 2;
  
  		public BplusTreeLong(System.IO.Stream fromfile, int NodeSize, int KeyLength, long StartSeek, int CultureId)
  		{
  			this.cultureContext = new System.Globalization.CultureInfo(CultureId);
  			this.cmp = this.cultureContext.CompareInfo;
  			this.fromfile = fromfile;
  			this.NodeSize = NodeSize;
  			this.seekStart = StartSeek;
  			// add in key prefix overhead
  			this.KeyLength = KeyLength + BufferFile.SHORTSTORAGE;
  			this.rootSeek = NULLBUFFERNUMBER;
  			this.root = null;
  			this.freeHeadSeek = NULLBUFFERNUMBER;
  			this.SanityCheck();
  		}
  		
  		public int MaxKeyLength() 
  		{
  			return this.KeyLength-BufferFile.SHORTSTORAGE;
  		}
  		public void Shutdown()
  		{
  			this.fromfile.Flush();
  			this.fromfile.Close();
  		}
  		public int Compare(string left, string right) 
  		{
  			//System.Globalization.CompareInfo cmp = this.cultureContext.CompareInfo;
  			if (this.cultureContext==null || this.DontUseCulture) 
  			{
  				// no culture context: use miscellaneous total ordering on unicode strings
  				int i = 0;
  				while (i<left.Length && i<right.Length) 
  				{
  					int leftOrd = Convert.ToInt32(left[i]);
  					int rightOrd = Convert.ToInt32(right[i]);
  					if (leftOrd<rightOrd) 
  					{
  						return -1;
  					}
  					if (leftOrd>rightOrd)
  					{
  						return 1;
  					}
  					i++;
  				}
  				if (left.Length<right.Length) 
  				{
  					return -1;
  				}
  				if (left.Length>right.Length) 
  				{
  					return 1;
  				}
  				return 0;
  			}
  			if (this.cmp==null) 
  			{
  				this.cmp = this.cultureContext.CompareInfo;
  			}
  			return this.cmp.Compare(left, right);
  		}
  		public void SanityCheck(bool strong) 
  		{
  			this.SanityCheck();
  			if (strong) 
  			{
  				this.Recover(false);
  				// look at all deferred deallocations -- they should not be free
  				byte[] buffer = new byte[1];
  				foreach (DictionaryEntry thing in this.FreeBuffersOnAbort) 
  				{
  					long buffernumber = (long) thing.Key;
  					this.buffers.getBuffer(buffernumber, buffer, 0, 1);
  					if (buffer[0]==FREE) 
  					{
  						throw new BplusTreeException("free on abort buffer already marked free "+buffernumber);
  					}
  				}
  				foreach (DictionaryEntry thing in this.FreeBuffersOnCommit) 
  				{
  					long buffernumber = (long) thing.Key;
  					this.buffers.getBuffer(buffernumber, buffer, 0, 1);
  					if (buffer[0]==FREE) 
  					{
  						throw new BplusTreeException("free on commit buffer already marked free "+buffernumber);
  					}
  				}
  			}
  		}
  		public void Recover(bool CorrectErrors) 
  		{
  			Hashtable visited = new Hashtable();
  			if (this.root!=null) 
  			{
  				// find all reachable nodes
  				this.root.SanityCheck(visited);
  			}
  			// traverse the free list
  			long freebuffernumber = this.freeHeadSeek;
  			while (freebuffernumber!=NULLBUFFERNUMBER) 
  			{
  				if (visited.ContainsKey(freebuffernumber) ) 
  				{
  					throw new BplusTreeException("free buffer visited twice "+freebuffernumber);
  				}
  				visited[freebuffernumber] = FREE;
  				freebuffernumber = this.parseFreeBuffer(freebuffernumber);
  			}
  			// find out what is missing
  			Hashtable Missing = new Hashtable();
  			long maxbuffer = this.buffers.nextBufferNumber();
  			for (long i=0; i<maxbuffer; i++) 
  			{
  				if (!visited.ContainsKey(i)) 
  				{
  					Missing[i] = i;
  				}
  			}
  			// remove from missing any free-on-commit blocks
  			foreach (DictionaryEntry thing in this.FreeBuffersOnCommit) 
  			{
  				long tobefreed = (long) thing.Key;
  				Missing.Remove(tobefreed);
  			}
  			// add the missing values to the free list
  			if (CorrectErrors) 
  			{
  				if (Missing.Count>0) 
  				{
  					System.Diagnostics.Debug.WriteLine("correcting "+Missing.Count+" unreachable buffers");
  				}
  				ArrayList missingL = new ArrayList();
  				foreach (DictionaryEntry d in Missing) 
  				{
  					missingL.Add(d.Key);
  				}
  				missingL.Sort();
  				missingL.Reverse();
  				foreach (object thing in missingL) 
  				{
  					long buffernumber = (long) thing;
  					this.deallocateBuffer(buffernumber);
  				}
  				//this.ResetBookkeeping();
  			} 
  			else if (Missing.Count>0)
  			{
  				string buffers = "";
  				foreach (DictionaryEntry thing in Missing) 
  				{
  					buffers += " "+thing.Key;
  				}
  				throw new BplusTreeException("found "+Missing.Count+" unreachable buffers."+buffers);
  			}
  		}
  		public void SerializationCheck()  
  		{
  			if (this.root==null) 
  			{
  				throw new BplusTreeException("serialization check requires initialized root, sorry");
  			}
  			this.root.SerializationCheck();
  		}
  		void SanityCheck() 
  		{
  			if (this.NodeSize<2) 
  			{
  				throw new BplusTreeException("node size must be larger than 2");
  			}
  			if (this.KeyLength<5) 
  			{
  				throw new BplusTreeException("Key length must be larger than 5");
  			}
  			if (this.seekStart<0) 
  			{
  				throw new BplusTreeException("start seek may not be negative");
  			}
  			// compute the buffer size
  			// indicator | seek position | [ key storage | seek position ]*
  			int keystorage = this.KeyLength + BufferFile.SHORTSTORAGE;
  			this.buffersize = 1 + BufferFile.LONGSTORAGE + (keystorage + BufferFile.LONGSTORAGE)*this.NodeSize;
  		}
  		public string toHtml() 
  		{
  			System.Text.StringBuilder sb = new System.Text.StringBuilder();
  			sb.Append("<h1>BplusTree</h1>\r\n");
  			sb.Append("\r\n<br> nodesize="+this.NodeSize);
  			sb.Append("\r\n<br> seekstart="+this.seekStart);
  			sb.Append("\r\n<br> rootseek="+this.rootSeek);
  			sb.Append("\r\n<br> free on commit "+this.FreeBuffersOnCommit.Count+" ::");
  			foreach (DictionaryEntry thing in this.FreeBuffersOnCommit) 
  			{
  				sb.Append(" "+thing.Key);
  			}
  			sb.Append("\r\n<br> Freebuffers : ");
  			Hashtable freevisit = new Hashtable();
  			long free = this.freeHeadSeek;
  			string allfree = "freehead="+free+" :: ";
  			while (free!=NULLBUFFERNUMBER) 
  			{
  				allfree = allfree+" "+free;
  				if (freevisit.ContainsKey(free)) 
  				{
  					throw new BplusTreeException("cycle in freelist "+free);
  				}
  				freevisit[free] = free;
  				free = this.parseFreeBuffer(free);
  			}
  			if (allfree.Length==0) 
  			{
  				sb.Append("empty list");
  			} 
  			else 
  			{
  				sb.Append(allfree);
  			}
  			foreach (DictionaryEntry thing in this.FreeBuffersOnCommit) 
  			{
  				sb.Append(" "+thing.Key);
  			}
  			sb.Append("\r\n<br> free on abort "+this.FreeBuffersOnAbort.Count+" ::");
  			foreach (DictionaryEntry thing in this.FreeBuffersOnAbort) 
  			{
  				sb.Append(" "+thing.Key);
  			}
  			sb.Append("\r\n<br>\r\n");
  
  			//... add more
  			if (this.root==null) 
  			{
  				sb.Append("<br><b>NULL ROOT</b>\r\n");
  			} 
  			else 
  			{
  				this.root.AsHtml(sb);
  			}
  			return sb.ToString();
  		}
  		public BplusTreeLong(System.IO.Stream fromfile, int KeyLength, int NodeSize, int CultureId):
  			this(fromfile, NodeSize, KeyLength, (long)0, CultureId) 
  		{
  			// just start seek at 0
  		}
  		public static BplusTreeLong SetupFromExistingStream(System.IO.Stream fromfile) 
  		{
  			return SetupFromExistingStream(fromfile, (long)0);
  		}
  		public static BplusTreeLong SetupFromExistingStream(System.IO.Stream fromfile, long StartSeek) 
  		{
  			int dummyId = System.Globalization.CultureInfo.InvariantCulture.LCID;
  			BplusTreeLong result = new BplusTreeLong(fromfile, 7, 100, StartSeek, dummyId); // dummy values for nodesize, keysize
  			result.readHeader();
  			result.buffers = BufferFile.SetupFromExistingStream(fromfile, StartSeek+result.headersize);
  			if (result.buffers.buffersize != result.buffersize) 
  			{
  				throw new BplusTreeException("inner and outer buffer sizes should match");
  			}
  			if (result.rootSeek!=NULLBUFFERNUMBER) 
  			{
  				result.root = new BplusNode(result, null, -1, true);
  				result.root.LoadFromBuffer(result.rootSeek);
  			}
  			return result;
  		}
  		public static BplusTreeLong InitializeInStream(System.IO.Stream fromfile, int KeyLength, int NodeSize) 
  		{
  			int dummyId = System.Globalization.CultureInfo.InvariantCulture.LCID;
  			return InitializeInStream(fromfile, KeyLength, NodeSize, dummyId);
  		}
  		public static BplusTreeLong InitializeInStream(System.IO.Stream fromfile, int KeyLength, int NodeSize, int CultureId) 
  		{
  			return InitializeInStream(fromfile, KeyLength, NodeSize, CultureId, (long)0);
  		}
  		public static BplusTreeLong InitializeInStream(System.IO.Stream fromfile, int KeyLength, int NodeSize, int CultureId, long StartSeek) 
  		{
  			if (fromfile.Length>StartSeek) 
  			{
  				throw new BplusTreeException("can't initialize bplus tree inside written area of stream");
  			}
  			BplusTreeLong result = new BplusTreeLong(fromfile, NodeSize, KeyLength, StartSeek, CultureId);
  			result.setHeader();
  			result.buffers = BufferFile.InitializeBufferFileInStream(fromfile, result.buffersize, StartSeek+result.headersize);
  			return result;
  		}
  		public void SetFootPrintLimit(int limit) 
  		{
  			if (limit<5) 
  			{
  				throw new BplusTreeException("foot print limit less than 5 is too small");
  			}
  			this.FifoLimit = limit;
  		}
  		public void RemoveKey(string key) 
  		{
  			if (this.root==null) 
  			{
  				throw new BplusTreeKeyMissing("tree is empty: cannot delete");
  			}
  			bool MergeMe;
  			BplusNode theroot = this.root;
  			theroot.Delete(key, out MergeMe);
  			// if the root is not a leaf and contains only one child (no key), reroot
  			if (MergeMe && !this.root.isLeaf && this.root.SizeInUse()==0) 
  			{
  				this.root = this.root.FirstChild();
  				this.rootSeek = this.root.makeRoot();
  				theroot.Free();
  			}
  		}
  		public long this[string key] 
  		{
  			get 
  			{
  				long valueFound;
  				bool test = this.ContainsKey(key, out valueFound);
  				if (!test) 
  				{
  					throw new BplusTreeKeyMissing("no such key found: "+key);
  				}
  				return valueFound;
  			}
  			set 
  			{
  				if (!BplusNode.KeyOK(key, this)) 
  				{
  					throw new BplusTreeBadKeyValue("null or too large key cannot be inserted into tree: "+key);
  				}
  				bool rootinit = false;
  				if (this.root==null) 
  				{
  					// allocate root
  					this.root = new BplusNode(this, null, -1, true);
  					rootinit = true;
  					//this.rootSeek = root.DumpToFreshBuffer();
  				}
  				// insert into root...
  				string splitString;
  				BplusNode splitNode;
  				root.Insert(key, value, out splitString, out splitNode);
  				if (splitNode!=null) 
  				{
  					// split of root: make a new root.
  					rootinit = true;
  					BplusNode oldRoot = this.root;
  					this.root = BplusNode.BinaryRoot(oldRoot, splitString, splitNode, this);
  				}
  				if (rootinit) 
  				{
  					this.rootSeek = root.DumpToFreshBuffer();
  				}
  				// check size in memory
  				this.ShrinkFootprint();
  			}
  		}
  		public string FirstKey() 
  		{
  			string result = null;
  			if (this.root!=null) 
  			{
  				// empty string is smallest possible tree
  				if (this.ContainsKey("")) 
  				{
  					result = "";
  				} 
  				else 
  				{
  					return this.root.FindNextKey("");
  				}
  				this.ShrinkFootprint();
  			}
  			return result;
  		}
  		public string NextKey(string AfterThisKey) 
  		{
  			if (AfterThisKey==null) 
  			{
  				throw new BplusTreeBadKeyValue("cannot search for null string");
  			}
  			string result = this.root.FindNextKey(AfterThisKey);
  			this.ShrinkFootprint();
  			return result;
  		}
  		public bool ContainsKey(string key) 
  		{
  			long valueFound;
  			return this.ContainsKey(key, out valueFound);
  		} 
  		public bool ContainsKey(string key, out long valueFound) 
  		{
  			if (key==null)
  			{
  				throw new BplusTreeBadKeyValue("cannot search for null string");
  			}
  			bool result = false;
  			valueFound = (long) 0;
  			if (this.root!=null) 
  			{
  				result = this.root.FindMatch(key, out valueFound);
  			}
  			this.ShrinkFootprint();
  			return result;
  		}
  		public long Get(string key, long defaultValue) 
  		{
  			long result = defaultValue;
  			long valueFound;
  			if (this.ContainsKey(key, out valueFound))
  			{
  				result = valueFound;
  			}
  			return result;
  		}
  		public void Set(string key, object map) 
  		{
  			if (!(map is long)) 
  			{
  				throw new BplusTreeBadKeyValue("only longs may be used as values in a BplusTreeLong: "+map);
  			}
  			this[key] = (long) map;
  		}
  		public object Get(string key, object defaultValue) 
  		{
  			long valueFound;
  			if (this.ContainsKey(key, out valueFound)) 
  			{
  				return (object) valueFound;
  			}
  			return defaultValue;
  		}
  		/// <summary>
  		/// Store off any changed buffers, clear the fifo, free invalid buffers
  		/// </summary>
  		public void Commit() 
  		{
  			// store all modifications
  			if (this.root!=null) 
  			{
  				this.rootSeek = this.root.Invalidate(false);
  			}
  			this.fromfile.Flush();
  			// commit the new root
  			this.setHeader();
  			this.fromfile.Flush();
  			// at this point the changes are committed, but some space is unreachable.
  			// now free all unfreed buffers no longer in use
  			ArrayList toFree = new ArrayList();
  			foreach (DictionaryEntry d in this.FreeBuffersOnCommit) 
  			{
  				toFree.Add(d.Key);
  			}
  			toFree.Sort();
  			toFree.Reverse();
  			foreach (object thing in toFree) 
  			{
  				long buffernumber = (long) thing;
  				this.deallocateBuffer(buffernumber);
  			}
  			// store the free list head
  			this.setHeader();
  			this.fromfile.Flush();
  			this.ResetBookkeeping();
  		}
  		/// <summary>
  		/// Forget all changes since last commit
  		/// </summary>
  		public void Abort() 
  		{
  			// deallocate allocated blocks
  			ArrayList toFree = new ArrayList();
  			foreach (DictionaryEntry d in this.FreeBuffersOnAbort) 
  			{
  				toFree.Add(d.Key);
  			}
  			toFree.Sort();
  			toFree.Reverse();
  			foreach (object thing in toFree) 
  			{
  				long buffernumber = (long) thing;
  				this.deallocateBuffer(buffernumber);
  			}
  			long freehead = this.freeHeadSeek;
  			// reread the header (except for freelist head)
  			this.readHeader();
  			// restore the root
  			if (this.rootSeek==NULLBUFFERNUMBER) 
  			{
  				this.root = null; // nothing was committed
  			} 
  			else 
  			{
  				this.root.LoadFromBuffer(this.rootSeek);
  			}
  			this.ResetBookkeeping();
  			this.freeHeadSeek = freehead;
  			this.setHeader(); // store new freelist head
  			this.fromfile.Flush();
  		}
  		void ResetBookkeeping() 
  		{
  			this.FreeBuffersOnCommit.Clear();
  			this.FreeBuffersOnAbort.Clear();
  			this.IdToTerminalNode.Clear();
  			this.TerminalNodeToId.Clear();
  		}
  		public long allocateBuffer() 
  		{
  			long allocated = -1;
  			if (this.freeHeadSeek==NULLBUFFERNUMBER) 
  			{
  				// should be written immediately after allocation
  				allocated = this.buffers.nextBufferNumber();
  				//System.Diagnostics.Debug.WriteLine("<br> allocating fresh buffer "+allocated);
  				return allocated;
  			}
  			// get the free head data
  			allocated = this.freeHeadSeek;
  			this.freeHeadSeek = this.parseFreeBuffer(allocated);
  			//System.Diagnostics.Debug.WriteLine("<br> recycling free buffer "+allocated);
  			return allocated;
  		}
  		long parseFreeBuffer(long buffernumber) 
  		{
  			int freesize = 1+BufferFile.LONGSTORAGE;
  			byte[] buffer = new byte[freesize];
  			this.buffers.getBuffer(buffernumber, buffer, 0, freesize);
  			if (buffer[0]!=FREE) 
  			{
  				throw new BplusTreeException("free buffer not marked free");
  			}
  			long result = BufferFile.RetrieveLong(buffer, 1);
  			return result;
  		}
  		public void deallocateBuffer(long buffernumber) 
  		{
  			//System.Diagnostics.Debug.WriteLine("<br> deallocating "+buffernumber);
  			int freesize = 1+BufferFile.LONGSTORAGE;
  			byte[] buffer = new byte[freesize];
  			// it better not already be marked free
  			this.buffers.getBuffer(buffernumber, buffer, 0, 1);
  			if (buffer[0]==FREE) 
  			{
  				throw new BplusTreeException("attempt to re-free free buffer not allowed");
  			}
  			buffer[0] = FREE;
  			BufferFile.Store(this.freeHeadSeek, buffer, 1);
  			this.buffers.setBuffer(buffernumber, buffer, 0, freesize);
  			this.freeHeadSeek = buffernumber;
  		}
  		void setHeader() 
  		{
  			byte[] header = this.makeHeader();
  			this.fromfile.Seek(this.seekStart, System.IO.SeekOrigin.Begin);
  			this.fromfile.Write(header, 0, header.Length);
  		}
  		public void RecordTerminalNode(BplusNode terminalNode) 
  		{
  			if (terminalNode==this.root) 
  			{
  				return; // never record the root node
  			}
  			if (this.TerminalNodeToId.ContainsKey(terminalNode) )
  			{
  				return; // don't record it again
  			}
  			int id = this.TerminalNodeCount;
  			this.TerminalNodeCount++;
  			this.TerminalNodeToId[terminalNode] = id;
  			this.IdToTerminalNode[id] = terminalNode;
  		}
  		public void ForgetTerminalNode(BplusNode nonterminalNode) 
  		{
  			if (!this.TerminalNodeToId.ContainsKey(nonterminalNode)) 
  			{
  				// silently ignore (?)
  				return;
  			}
  			int id = (int) this.TerminalNodeToId[nonterminalNode];
  
gt: 			if (id == this.LowerTerminalNodeCount) 