bplustest.java

R树与B树的混合树

package NET.sourceforge.BplusJ.testing;

import java.util.*;
import NET.sourceforge.BplusJ.BplusJ.*;


	/// <summary>
	/// tests main entry point for BplusJ.  Throws exception on failure.
	/// </summary>
	public class bplusTest
	{
		static String tempdirectory = null; //"c:\\tmp"; // set to a directory to test storing to/from files
		static Hashtable allinserts = new Hashtable();
		static Hashtable lastcommittedinserts = new Hashtable();
		static boolean full = true;
		static int keylength = 20;
		static int prefixlength = 6;
		static int nodesize = 6;
		static int buffersize = 100;
		static int bucketsizelimit = 100; // sanity check
		static boolean DoAllTests = true;
		public static void main(String argv[]) 
			throws Exception
		{
			if (DoAllTests) 
			{
				//byteStringTest();
				intTests();
				longTests();
				shortTests();
				testBufferFile();
				LinkedFileTest();
				BplusTreeLongTest();
				Test();
				xTest();
				hTest();
				//sTest(); -- not implemented in java yet
			}
			//hTest();
			CompatTest();
		}
		public static String CompatKey(int i, int j, int k, int l) 
		{
			String seed = "i="+i+" j="+j+" k="+k+" ";
			String result = seed;
//			for (int ii=0; ii<l; ii++) 
//			{
//				result += seed;
//			}
			return ""+l+result;
		}
		public static String CompatValue(int i, int j, int k, int l) 
		{
			String result = CompatKey(k,j,l,i)+CompatKey(l,k,j,i);
			return result+result;
		}
		public static void CompatTest() throws Exception
		{
			if (tempdirectory==null) 
			{
				System.out.println(" compatibility test requires temp directory to be defined: please edit test source file");
				return;
			}
			String otherTreeFileName = tempdirectory+"/CsharpTree.dat";
			String otherBlocksFileName = tempdirectory+"/CsharpBlocks.dat";
			String myTreeFileName = tempdirectory+"/JavaTree.dat";
			String myBlocksFileName = tempdirectory+"/JavaBlocks.dat";
			Hashtable map = new Hashtable();
			System.out.println(" creating "+myTreeFileName+" and "+myBlocksFileName);
			if ((new java.io.File(myTreeFileName)).exists())  
			{
				System.out.println(" deleting existing files");
				(new java.io.File(myTreeFileName)).delete(); 
				(new java.io.File(myBlocksFileName)).delete(); 
			}
			BplusTree myTree = hBplusTree.Initialize(myTreeFileName, myBlocksFileName, 6);
			for (int i=0; i<10; i++) 
			{
				
				System.out.println(" "+i);
				for (int j=0; j<10; j++) 
				{
					for (int k=0; k<10; k++) 
					{
						for (int l=0; l<10; l++) 
						{
							String TheKey = CompatKey(i,j,k,l);
							String TheValue = CompatValue(i,j,k,l);
							//map[TheKey] = TheValue;
							map.put(TheKey, TheValue);
							//myTree[TheKey] = TheValue;
							myTree.set(TheKey, TheValue);
						}
					}
				}
			}
			myTree.Commit();
			myTree.Shutdown();
			System.out.println(" trying to test "+otherTreeFileName+" and "+otherBlocksFileName);
			if (!(new java.io.File(otherTreeFileName)).exists())  
			{
				System.out.println(" file not created yet :(");
				return;
			}
			int count = 0;
			BplusTree otherTree = hBplusTree.ReadOnly(otherTreeFileName, otherBlocksFileName);
			//foreach (DictionaryEntry D in map) 
			for (Enumeration e=map.keys(); e.hasMoreElements(); )
			{
				if ( (count%1000)==1) 
				{
					System.out.println(" ... "+count);
				}
				String TheKey = (String) e.nextElement();
				String TheValue = (String) map.get(TheKey);
				String OtherValue = otherTree.get(TheKey);
				if (!OtherValue.equals(TheValue) )
				{
					throw new Exception(" Values don't match "+TheValue+" "+OtherValue);
				}
				count++;
			}
			System.out.println(" compatibility test ok");
		}
		public static java.io.RandomAccessFile makeFile(String name) throws Exception
		{
			if (tempdirectory==null) 
			{
				System.out.println("to run these tests you need to edit the source file, adding a String definition for tempdirectory");
				throw new Exception("to run these tests you need to edit the source file, adding a String definition for tempdirectory");
			}
			String path = tempdirectory + "/" + name;
			// delete it if it exists
			java.io.File f = new java.io.File(path);
			if (f.exists()) 
			{
				System.out.println("<br>				DELETING FILE "+path);
				f.delete();
			}
			return new java.io.RandomAccessFile(path, "rw");
		}
		
		static String keyMaker(int i, int j, int k) 
		{
			int selector = (i+j+k)%3;
			String result = ""+i+"."+j+"."+k;
			if (selector==0) 
			{
				result = ""+k+"."+(j%5)+"."+i;
			} 
			else if (selector==1) 
			{
				result = ""+k+"."+j+"."+i;
			}
			return result;
		}
		
		static String xkeyMaker(int i, int j, int k) 
		{
			String result = keyMaker(i,j,k);
			result = result+result+result;
			result = result + keyMaker(k,i,j);
			return result;
		}
		
		static String ValueMaker(int i, int j, int k)
		{
			if ( ((i+j+k)%5) == 3 )
			{
				return "";
			}
			//System.Text.StringBuilder sb = new System.Text.StringBuilder();
			String result = "";
			//sb.Append("value");
			result += "value";
			for (int x=0; x<i+k*5; x++) 
			{
				//sb.Append(j);
				result += j;
				//sb.Append(k);
				result += k;
			}
			return result;
		}
		
		
		public static void Test() 
			throws Exception
		{
			System.out.println("TESTING BPLUSTREE");
			//System.IO.Stream treefile=null, blockfile=null;
			java.io.RandomAccessFile treefile = makeFile("bptTree.dat");
			java.io.RandomAccessFile blockfile = makeFile("bptBlock.dat");
			BplusTree bpt = BplusTree.Initialize(treefile, blockfile, keylength);
			//BplusTree bpt = getTree(treefile, blockfile);
			Hashtable allmaps = new Hashtable();
			for (int i=0; i<10; i++) 
			{
				System.out.println("Pass "+i+" of 10");
				bpt.SetFootPrintLimit(16-i);
				for (int j=0; j<30; j++) 
				{
					exercise(bpt, i, j, allmaps, false);
					if ((j%4)==2) 
					{
						bpt = BplusTree.ReOpen(treefile, blockfile);
					}
					// now check the structure
					checkStructure(allmaps, bpt, true);
				}
			}
		}
		public static void xTest() 
			throws Exception
		{
			System.out.println("TESTING BPLUSTREE");
			//System.IO.Stream treefile=null, blockfile=null;
			java.io.RandomAccessFile treefile = makeFile("bptTreeX.dat");
			java.io.RandomAccessFile blockfile = makeFile("bptBlockX.dat");
			BplusTree bpt = xBplusTree.Initialize(treefile, blockfile, keylength);
			//BplusTree bpt = getTree(treefile, blockfile);
			Hashtable allmaps = new Hashtable();
			for (int i=0; i<10; i++) 
			{
				System.out.println("Pass "+i+" of 10");
				bpt.SetFootPrintLimit(16-i);
				for (int j=0; j<30; j++) 
				{
					exercise(bpt, i, j, allmaps, true);
					if ((j%4)==2) 
					{
						bpt = xBplusTree.ReOpen(treefile, blockfile);
					}
					// now check the structure
					checkStructure(allmaps, bpt, true);
				}
			}
		}
		public static void hTest() 
			throws Exception
		{
			System.out.println("TESTING BPLUSTREE");
			//System.IO.Stream treefile=null, blockfile=null;
			java.io.RandomAccessFile treefile = makeFile("bptTreeH.dat");
			java.io.RandomAccessFile blockfile = makeFile("bptBlockH.dat");
			BplusTree bpt = hBplusTree.Initialize(treefile, blockfile, keylength);
			//BplusTree bpt = getTree(treefile, blockfile);
			Hashtable allmaps = new Hashtable();
			for (int i=0; i<10; i++) 
			{
				System.out.println("Pass "+i+" of 10");
				bpt.SetFootPrintLimit(16-i);
				for (int j=0; j<30; j++) 
				{
					exercise(bpt, i, j, allmaps, true);
					if ((j%4)==2) 
					{
						bpt = hBplusTree.ReOpen(treefile, blockfile);
					}
					// now check the structure
					checkStructure(allmaps, bpt, false);
				}
			}
		}
		public static void exercise(IStringTree bpt, int i, int j, Hashtable allmaps, boolean extended) 
			throws Exception
		{
			Hashtable record = new Hashtable();
			for (int k=0; k<30; k++) 
			{
				String thiskey;
				if (extended) 
				{
					thiskey = xkeyMaker(i,j,k);
				} 
				else 
				{
					thiskey = keyMaker(i,j,k);
				}
				String thisvalue =ValueMaker(j,k,i);
				//record[thiskey] = thisvalue;
				record.put(thiskey, thisvalue);
				//bpt[thiskey] = thisvalue;
				bpt.set(thiskey, thisvalue);
			}
			if ((j%3)==1) 
			{
				bpt.Recover(false);
			}
			if ( ((i+j)%2) == 1 ) 
			{
				bpt.Commit();
				bpt.Abort();  // should have no effect
				bpt.Commit();  // ditto
				if ( (i+j)%5 < 2) 
				{
					//System.out.println(bpt.toHtml());
					//foreach (DictionaryEntry d in record) 
					for (Enumeration e=record.keys(); e.hasMoreElements(); )
					{
						String thiskey = (String) e.nextElement();
						bpt.RemoveKey(thiskey);
						if (allmaps.containsKey(thiskey)) 
						{
							allmaps.remove(thiskey);
						}
					}
					//System.out.println(bpt.toHtml());
					bpt.Commit();
					//return;
				} 
				else 
				{
					//foreach (DictionaryEntry d in record) 
					for (Enumeration e=record.keys(); e.hasMoreElements(); )
					{
						//allmaps[d.Key] = d.Value;
						String key = (String) e.nextElement();
						String value = (String) record.get(key);
						allmaps.put(key, value);
					}
				}
			} 
			else 
			{
				bpt.Abort();
			}
		}
		public static void checkStructure(Hashtable allmaps, IStringTree bpt, boolean ordered) 
			throws Exception
		{
			TreeSet allkeys = new TreeSet();
			//ArrayList allkeys = new ArrayList();
			//foreach (DictionaryEntry d in allmaps) 
			for (Enumeration e=allmaps.keys(); e.hasMoreElements(); )
			{
				String thiskey = (String)e.nextElement();
				String thisvalue = (String)allmaps.get(thiskey);
				String treemap = bpt.get(thiskey);
				if (!treemap.equals(thisvalue)) 
				{
					throw new Exception("key "+thiskey+" maps to "+treemap+" but should map to "+thisvalue);
				}
				allkeys.add(thiskey);
			}
			String currentkey = bpt.FirstKey();
			//allkeys.Sort();
			if (ordered) 
			{
				for (Iterator e=allkeys.iterator(); e.hasNext(); )
				{
					Object thing = e.next();					
					String recordedkey = (String) thing;
					if (currentkey==null) 
					{
						throw new Exception("end of keys found when expecting "+recordedkey);
					}
					if (!currentkey.equals(recordedkey)) 
					{
						//System.out.println(bpt.toHtml());
						throw new Exception("key "+currentkey+" found where expecting "+recordedkey);
					}
					currentkey = bpt.NextKey(currentkey);
				}
				if (currentkey!=null) 
				{
					throw new Exception("found "+currentkey+" when expecting end of keys");
				}
			}
			// should add test for unordered case too...
		}
		
		public static void abort(BplusTreeLong bpt) throws Exception
		{
			System.out.println(" <h3>ABORT!</H3>");
			bpt.Abort();
			allinserts = (Hashtable) lastcommittedinserts.clone();
			checkit(bpt);
		}
		public static void commit(BplusTreeLong bpt) throws Exception
		{
			System.out.println(" <h3>COMMIT!</H3>");