Subversion Repositories Code-Repo

import java.util.ArrayList;

// Generic BST implementation
public class BSTree<K extends Comparable<? super K>, E> implements Dictionary<K, E> {
        private BSTreeNode<K,E> root;   // Root of the BST
        NodeSerializer serializer;
        
        // Constructor
        public BSTree(MemManager mem) {
                serializer = new NodeSerializer(mem);
                this.root = null;
        }
        
        // Inserts a node into the BST
        public void insert(K key, E element) {
                // Set the BST root as the returned node
                this.root = insertRecursive(root, key, element);
        }
        
        // Removes a node from the BST given the key
        public void remove(K key) {
                // Adds invalid coordinates if none are specified
                this.remove(key, -1, -1);
        }
        
        public void remove(K key, int x, int y) {
                // Check if node exists
                E temp = findRecursive(root, key);
                if (temp != null) {
                        // Remove the node
                        this.root = removeRecursive(root, key, x, y);
                }
        }
        
        // Returns a node from the BST given the key
        public E find(K key) {
                return findRecursive(root, key);
        }
        
        // Returns a list of all nodes with the given key
        public ArrayList<E> findAll(K key) {
                ArrayList<E> elementList = new ArrayList<E>();
                findAllRecursive(root, key, elementList);
                return elementList;
        }
        
        // Removes all nodes from the BST
        public void clear() {
                this.root = null;
        }
        
        // Recursively inserts a node into the BST
        private BSTreeNode<K,E> insertRecursive(BSTreeNode<K,E> root, K key, E element) {
                if (root == null)
                        // If there are no nodes in the BST, create and return a new node
                        return new BSTreeNode<K,E>(key, element);
                if (root.getKey().compareTo(key) > 0)
                        // If passed key is smaller, insert into left child
                        root.setLeft(insertRecursive(root.getLeft(), key, element));
                else
                        // If passed key is greater, insert into right child
                        root.setRight(insertRecursive(root.getRight(), key, element));
                return root;
        }
                
        // Recursively searches minimal nodes for matches to the given key
        private E findRecursive(BSTreeNode<K,E> root, K key) {
                if (root == null)
                        return null;
                
                if (root.getKey().compareTo(key) > 0)
                        // If passed key is smaller, search the left child
                        return findRecursive(root.getLeft(), key);
                else if (root.getKey().compareTo(key) == 0)
                        // If key is found, return with the found element
                        return root.getElement();
                else
                        // If key is not found, search the right child
                        return findRecursive(root.getRight(), key);
        }
        
        // Recursively searches all nodes for matches to the given key
        private void findAllRecursive(BSTreeNode<K,E> root, K key, ArrayList<E> elementList) {
                if (root == null)
                        return;
                
                // If key matches, save to list
                if (root.getKey().compareTo(key) == 0)
                        elementList.add(root.getElement());
                
                // Recursively call search on all possible nodes
                if (root.getKey().compareTo(key) > 0)
                        findAllRecursive(root.getLeft(), key, elementList);
                else
                        findAllRecursive(root.getRight(), key, elementList);
        }
        
        // Recursively removes a node from the BST given a key
        private BSTreeNode<K,E> removeRecursive(BSTreeNode<K,E> root, K key, int x, int y) {
                if (root == null)
                        return null;
                // Find the node to remove
                if (root.getKey().compareTo(key) > 0)
                        root.setLeft(removeRecursive(root.getLeft(), key, x, y));
                else if (root.getKey().compareTo(key) < 0)
                        root.setRight(removeRecursive(root.getRight(), key, x, y));
                // Node's key matches
                else {
                        // If we want to narrow it down by coordinates as well
                        if (x >= 0 && y >= 0) {
                                CityRecord record = serializer.handleToCityRecord((Handle)root.getElement());
                                // If coordinates do not match, keep searching from the right child
//                              if (((Record)root.getElement()).getX() != x || ((Record)root.getElement()).getY() != y) {
                                if (record.getX() != x || record.getY() != y) {
                                        root.setRight(removeRecursive(root.getRight(), key, x, y));
                                } else {
                                        // If one of the leaves is null, just return the other leaf
                                        if (root.getLeft() == null) {
                                                serializer.removeCityRecordHandle((Handle)root.getElement());
                                                return root.getRight();
                                        } else if (root.getRight() == null) {
                                                serializer.removeCityRecordHandle((Handle)root.getElement());
                                                return root.getLeft();
                                        } else {
                                                serializer.removeCityRecordHandle((Handle)root.getElement());
                                                // Otherwise create a new node with the smallest value on the right leaf
                                                BSTreeNode<K,E> temp = getMin(root.getRight());
                                                root.setElement(temp.getElement());
                                                root.setKey(temp.getKey());
                                                root.setRight(deleteMin(root.getRight()));
                                        }
                                }
                        // Otherwise just remove the node
                        } else {
                                // If one of the leaves is null, just return the other leaf
                                if (root.getLeft() == null) {
                                        serializer.removeCityRecordHandle((Handle)root.getElement());
                                        return root.getRight();
                                } else if (root.getRight() == null) {
                                        serializer.removeCityRecordHandle((Handle)root.getElement());
                                        return root.getLeft();
                                } else {
                                        serializer.removeCityRecordHandle((Handle)root.getElement());
                                        // Otherwise create a new node with the smallest value on the right leaf
                                        BSTreeNode<K,E> temp = getMin(root.getRight());
                                        root.setElement(temp.getElement());
                                        root.setKey(temp.getKey());
                                        root.setRight(deleteMin(root.getRight()));
                                }
                        }
                }
                return root;
        }
        
        // Recursively returns the minimum key node
        private BSTreeNode<K,E> getMin(BSTreeNode<K,E> root) {
                if (root.getLeft() == null)
                        return root;
                else
                        return getMin(root.getLeft());
        }
        
        // Recursively deletes the minimum key node
        private BSTreeNode<K,E> deleteMin(BSTreeNode<K,E> root) {
                if (root.getLeft() == null)
                        return root.getRight();
                else {
                        root.setLeft(deleteMin(root.getLeft()));
                        return root;
                }
        }
}