To do: Implement put when not a leaf node (section labeled todo near bottom) package hw3;

import java.util.LinkedList;

public class TwoThreeIntSet {

private class Node { int[] items; // the keys/items in the node Node[] subtrees; // the children of this node int nodeType; // the node type (2, 3, or 4)

/** * Create a new node with item as the key and two subtrees * * @param item the key/item for the node * @param left the root of the subtree less than the item * @param right the root of the subtree greater than the item */ public Node(int item, Node left, Node right) { items = new int[3]; subtrees = new Node[4]; subtrees[0] = left; subtrees[1] = right; nodeType = 2; items[0] = item; }

/** * Creates a new leaf with item as the key. * * @param item the key/item for the leaf. */ public Node(int item) { this(item, null, null); }

/** * Returns true if this node is a leaf * * @return true if this node is a leaf. */ public boolean isLeaf() { return subtrees[0] == null; } }

private Node root;

public TwoThreeIntSet() { } public void put(int item) { /* * If the tree is empty, create a new leaf node for the item. It is also the * root of the tree. */ if (root == null) root = new Node(item);

/* * Otherwise, we will be inserting the item in a pre-existing leaf using a * recursive helper function. */ else { root = put(root, item); /* * The recursive helper function returns a 2-3 tree where the root might be a * 4-node. Check for this and split if necessary. */ if (root.nodeType == 4) { Node left = new Node(root.items[0], root.subtrees[0], root.subtrees[1]); Node right = new Node(root.items[2], root.subtrees[2], root.subtrees[3]); root = new Node(root.items[1], left, right); } } }

private Node put(Node n, int item) { /* * First check if n contains item. If it does, there is nothing to do and we can * return the root of this subtree unchanged */ int itemCount = n.nodeType - 1; for (int i = 0; i < itemCount; i++) { if (n.items[i] == item) return n; }

/* * Because we always insert into a pre-existing leaf, the base case here is a * tree with one node (the root is a leaf). */ if (n.isLeaf()) {

// If the node is a 2-node, insert the new item to its left or right. if (n.nodeType == 2) { if (item < n.items[0]) { n.items[1] = n.items[0]; n.items[0] = item; } else { n.items[1] = item; } n.nodeType = 3; }

else if (n.nodeType == 3) { // Turn this into a 4-node and return it since you are allowed // to temporarily have a 4-node as a the root. if (item < n.items[0]) { n.items[2] = n.items[1]; n.items[1] = n.items[0]; n.items[0] = item; } else if(item > n.items[0] && item < n.items[1]){ n.items[2] = n.items[1]; n.items[1] = item; } else if(item > n.items[1]) { n.items[2] = item; } n.nodeType = 4; }

else throw new RuntimeException("ERROR: " + n.nodeType + "-node found while inserting");

return n; }

// If not a leaf node, we will need to insert in one of our subtrees. else { if (n.nodeType == 2) { if (item < n.items[0]) { Node result = put(n.subtrees[0], item); // if the resulting root is not a 4-node, we can insert it as our new left. if (result.nodeType != 4) { n.subtrees[0] = result; } // otherwise, we need to fix it by splitting it else { Node newLeft = new Node(result.items[0], result.subtrees[0], result.subtrees[1]); Node newMiddle = new Node(result.items[2], result.subtrees[2], result.subtrees[3]); n.items[1] = n.items[0]; n.items[0] = result.items[1]; n.subtrees[2] = n.subtrees[1]; n.subtrees[1] = newMiddle; n.subtrees[0] = newLeft; n.nodeType = 3; } } else { Node result = put(n.subtrees[1], item); // if the resulting root is not a 4-node, we can insert it as our new right. if (result.nodeType != 4) { n.subtrees[1] = result; } // otherwise, we need to fix it by splitting it else { Node newMiddle = new Node(result.items[0], result.subtrees[0], result.subtrees[1]); Node newRight = new Node(result.items[2], result.subtrees[2], result.subtrees[3]); n.items[1] = result.items[1]; n.subtrees[2] = newRight; n.subtrees[1] = newMiddle; n.nodeType = 3; } } return n;

}

else if (n.nodeType == 3) { // TODO Make this work } else throw new RuntimeException("ERROR: " + n.nodeType + "-node found while inserting");

} }