/** * Assume there is a private field called _fac that is an IListFactory. * The constructor should have an IListFactory as a parameter. */ public IList removeRange(Comparable keyLo, Comparable keyHi) { if (keyLo.compareTo(keyHi) > 0) { throw new IllegalArgumentException(keyLo + " > " + keyHi); } final DictionaryPair low = new DictionaryPair(keyLo, null); final DictionaryPair hi = new DictionaryPair(keyHi, null); /** * Uses an anonymous BiTree visitor with a list accumulator to store the * elements that are being removed as the tree _bt is being traversed. * There are three cases to consider: * root < keyLo: because of BST, the left subtree of _bt is out of range; * thus only the right subtree of _bt need to be considered * keyHi < root: because of BST, the right subtree of _bt is out of range; * thus only the left subtree of _bt need to be considered * keyLo <= root <= keyHi: recur on both the left and right subtree of * _bt and remove the root node as well. */ return (IList)_bt.execute(new IVisitor() { public Object emptyCase(BiTree h, Object accList) { return accList; } public Object nonEmptyCase(BiTree h, Object accList) { if (((Comparable)h.getRootDat()).compareTo(low) < 0) { return h.getRightSubTree().execute(this, accList); } else if (((Comparable)h.getRootDat()).compareTo(hi) > 0) { return h.getLeftSubTree().execute(this, accList); } else { accList = h.getLeftSubTree().execute(this, accList); accList = h.getRightSubTree().execute(this, accList); accList = _fac.makeNEList(h.getRootDat(), (IList)accList); h.execute(_deleter, h.getRootDat()); return accList; } } }, _fac.makeEmptyList()); }