/** By Kristi Thompson and Sean McLaughlin * * April 10 & 11, 1997 * * CISC 235 - Information Structures (Winter 1997) taught by David Alex Lamb * * Dept of Computer Science * Queen's University, Kingston * * kristi@merlan.ca , seanster@merlan.ca * * http://qlink.queensu.ca/~3sm79/BplusTree * * Feel free to copy and modify this applet, but please give credit * to the original author where appropriate * * This applet was inspired by and partly based upon the BST Search Tree Applet * by James Stewart. * * http://www.dgp.toronto.edu/people/JamesStewart/applets/bst/bst-property.html * */ /** * * Version 1.1, April 12-13, 1997 * */ Added cool animation and annoying sounds. Revamped Code in a major way after another insight into 'The One True Way'. (It sure helps to read the Java FAQ :) Code is cleaner and information hiding is improved. Insertion takes place in a thread mainly just because a single thread applett won't repaint() our animated objects. Everything is in place for adding Arrows and more animation. A few new classes were created, although they are not fully implemented yet. Key - The key value and it's on-screen representation Pointer - A box with an arrow that points to other Sprites Data - A box that contains and displays data values that we are storing/retrieving. Record - A Box Containing a Key and Data. This is what will be a bucket's element. Sprite - Moveable animated object. -Tree Layout is no longer a kludge and works they way we think it should. 0 Kludges! -More stuff Animated -Forgot to mention last time that graphics are double-buffered for smooth animation.. -Code is still not terribly careful about freeing objects. (delete? free? what the HECK is it?) Java to the rescue! -New buttons! -Repaint button. We could make the tree resize in an animated manner, but it's our belief that this may look confusing because you want to see the insertion, not a bunch of other nodes shifting around -Clear button for obvious purposes. Reload the page if you want the default parameters read back in again. The road has been paved for version 1.2: A 'Record' is on the screen and you type your key and data into it. On insert, record 'Glides' Down the tree, pausing at each inode to compare values and eventually 'Squeeze' into the Bucket. A key and a pointer slide out of the Record from it's top and 'Glide' up to the Inner Node and Squeeze in. Process repeats until key fits or root splits. During this time Arrows redraw as things move. It's all too easy now :) We will likely expand this code to implement the rest of the useful tree operations. -Kristi & Sean /** * * Version 1.0, April 11, 1997 * */ We were unable to make the applett work as initially planned. If you're interested in the notes, here they are: Negatives: - Node layout is a hack and can overlap nodes The java Layout Manager mechanism should be used to keep the nodes in a proper tree shape, but the nature of the node insertions and tree structure are more complex than the simplistic layout manager interface will allow. It would actually be easier and more straighforward to build our own layer management into the Tree class than subclass the Layabout Manager - No connecting lines are drawn Until a real layout mechanism is determined, drawing connecting lines is a waste of time. - Possible that one or two objects aren't explicitly disposed of. We know about it, but don't really care since java cleans it all up. Isn't that the point of Java anyway? For losers that can't use pointers properly? - No actual animation Lack of time is the only excuse here. There is indeed a small amount of animation if there was a way to sleep() between steps. It seems that only threads can sleep(). Well, if there was time to add threads, we would have the actual animation anyway. Java classes are like a 'Sesame Street' version. Sure it's nice and simple, but as soon as you have to go against the grain, it's an uphill battle. Positives: - Tree and Nodes are actual objects, with their own associated methods. The other Applet cut corners here in a big way. One main difference is that we have recursive methods. ie Tree tells root Node to draw itself, root node then tells it's children to draw themselves, etc. The other applet's method had the tree class doing all the work in one big 'for' loop. ie. iterate through the nodes, call a method to draw the node, etc. While it may be preferential to not use recursion in some cases, the actual coding and testing of the recursive model is perfectly natural and IMHO much easier to comprehend and maintain. - Insertion of nodes is bug free :) - Inserting data with an existing key simply updates the data. - Form follows function. It's easy to animate because it works that way. - The Order of the Tree is variable, and can be changed at compile time. If we enjoy the overhead of vector arrays, we could make it a runtime parameter. In fact that's likely to be implemented shortly. -This code is heavily commented. Somebody whack that other applet making guy for us. -Other stuff we have forgotten but which we're sure would impress nerdy people. -Net searches reveal there's no other applet like it. :) Sean and Kristi April 11, 1997 //EOF