/** * used by the Cellphone * to locate a list of predictive words for a series of keys * * Each tree node */public class MultiwayTree { /** * Root node of the tree, having a null parent. */ protected MultiwayTreeNode root; //(use but) DO NOT ALTER THIS FIELD /** * Create a MultiwayTree consisting of MultiwayTreeNodes with the given maximum * number of children. */ public MultiwayTree(int maxNumChildren) { root = new MultiwayTreeNode(maxNumChildren); } /** * Insert the given Comparable object into this MultiwayTree * at a node with the given indices. * * @param indices An array used to locate the path leading * to the MultiwayTreeNode where insertion occurs. * * Each array element is the child index of each node * on the path (excluding the root node) with respect to its parent. * * For example, childIndices[0] is the * index of the root node's child that is the * top-level ancestor of the node at which insertion occurs, * childIndices[1] is the index of the next-level ancestor, etc ... * * @param word The word to be inserted. * */ public void insert(int[] indices, Object word) { MultiwayTreeNode tempNode = root; for(int i = 0; i < indices.length; i++){ tempNode = tempNode.getChild(indices[i]); } tempNode.setData(word); /* * traverse from the root node * down through the children nodes indicated * by each child index in the indices array. * * e.g [2,4,4] * would traverse from the root node * to the child in position 2 * then to the child in position 4 of node 2 * then to the child in position 4 of node 2->4 * (the final node being root->2->4->4) * * at each level traversed, insert the word at the end of the list. * this builds up at each position an ordered list of words. * The first in the list being the most frequently used word. * (taking care with the first time things are accessed). * * these lists can then be used to cycle through. the most probable * predicted word being first at the head of the list. * * the list used is a doubly-linked list. in the analysis section, * you will think about and (maybe) answer why this data structure * is being used here. also what would be the result if the word * wasn't inserted at each level during the traversal. */ } /** * Get the node of a path from the root node. * * @param indices Each array element is the child index * of each node on the path (excluding the root node) * with respect to its parent. * * @return The node matching the indices or null if not found */ public MultiwayTreeNode getNode(int[] indices) { MultiwayTreeNode tempNode = root; for(int i = 0; i < indices.length - 1; i++){ tempNode = tempNode.getChild(indices[i]); } if(tempNode.getChild(indices[indices.length - 1]) != null){ return tempNode.getChild(indices[indices.length - 1]); } else return null; } /** * Returns a new iterator for the tree. * * Used to keep current position in the tree. */ public MultiwayTreeIterator getIterator() { MultiwayTreeIterator returnIterator = new MultiwayTreeIterator(this); return returnIterator; }}// csse 2006.jul.20 MultiwayTree // csse 2006.aug.03