Printed by Owen L.
Astrachan Oct 14, 09 8:23
package setstuff100;
75
[Link]
Page 1/3
Oct 14, 09 8:23
}
[Link]
Page 2/3
import [Link].*;
5
/** * Simple binary search tree implementation of a set. Operations are O(log n) * in average case and O(n) in the worst case for unbalanced trees. * @author Owen Astrachan */ public class BSTSet<E extends Comparable<E>> implements ISimpleSet<E> {
80
10 85
15
private class TreeNode { E info; TreeNode left; TreeNode right; TreeNode parent;
90
public boolean remove(E element) { TreeNode root = myRoot; while (root != null) { int comp = [Link](element); if (comp == 0) { mySize; remove(root); return true; } else if (comp > 0) { root = [Link]; } else { root = [Link]; } } return false; } private void remove(TreeNode root) { if ([Link] == null && [Link] == null) { // removing leaf if ([Link] == null) { // removing root? myRoot = null; // tree now empty } else { if ([Link] == root) { [Link] = null; } else { [Link] = null; } } } else if ([Link] == null || [Link] == null) { // one child, not two TreeNode child = [Link]; // only child is left? if ([Link] == null) { // nope, its right child = [Link]; } if ([Link] == null) { // new root myRoot = child; } else if ([Link] == root) { [Link] = child; } else { [Link] = child; } [Link] = [Link]; } else { // removing node with two children TreeNode successor = [Link]; if ([Link] == null) { [Link] = [Link]; [Link] = [Link]; if ([Link] != null) { [Link] = root; } } else { // immediate right child of removed node has a left child while ([Link] != null) { successor = [Link]; } [Link] = [Link]; [Link] = [Link]; if ([Link] != null) { [Link] = [Link]; } } } } private TreeNode successor(TreeNode t) { if (t == null) return null; // no successor else if ([Link] != null) { t = [Link];
20
25
TreeNode(E element, TreeNode lptr, TreeNode rptr, TreeNode p) { info = element; left = lptr; right = rptr; parent = p; } } private int mySize;
95
100
30
private TreeNode myRoot;
105
35
public BSTSet() { mySize = 0; myRoot = null; }
110
40
public int size() { return mySize; } public boolean add(E element) { if (myRoot == null) { myRoot = new TreeNode(element, null, null, null); mySize++; return true; } TreeNode root = myRoot; while (root != null) { int comp = [Link](element); if (comp == 0) return false; if (comp > 0) { if ([Link] == null) { [Link] = new TreeNode(element, null, null, root); mySize++; return true; } else { root = [Link]; } } else { if ([Link] == null) { [Link] = new TreeNode(element, null, null, root); mySize++; return true; } else { root = [Link]; } } } // can never reach here return false;
115
45
120
50
125
55
130
60
135
65
140
70
145
Wednesday October 14, 2009
[Link]
1/5
Printed by Owen L. Astrachan Oct 14, 09 8:23
[Link]
Page 3/3
Oct 14, 09 8:23
package setstuff100;
5
[Link]
Page 1/1
150
155
while ([Link] != null) { t = [Link]; } return t; } else { TreeNode parent = [Link]; while (parent != null && [Link] == t) { t = parent; parent = [Link]; } return parent; } } public boolean contains(E element) { TreeNode root = myRoot; while (root != null) { int comp = [Link](element); if (comp == 0) return true; else if (comp > 0) { root = [Link]; } else { root = [Link]; } } return false; } public Iterator<E> iterator() { return new TreeIterator(myRoot); }
10
/** * This generic class illustrates simple imlementations * of sets for the purposes of understanding and reasoning * about tradeoffs. For example, we consider hashing, search trees, * AVL trees and tries as set implementations. * @author Owen Astrachan * @version 2.0, October 2006 */ import [Link];
160 15
165
20
public interface ISimpleSet<E> extends Iterable<E> { /** * Returns the number of elements in this set. * @return size of set */ public int size(); /** * Adds an element to the set (no duplicates). Returns true if and only if * the element was added, i.e., not already stored in the set. * @param element to be added to set * @return true if element not previously in set, false otherwise */ public boolean add(E element); /** * Removes an element from the set and returns true if removal successful. * @param element to be removed from set * @return true if element removed, false otherwise */ public boolean remove(E element); /** * Returns true if element in set, false otherwise. * @param element is candidate for query in set * @return true if element in set, false otherwise */ public boolean contains(E element); /** * Returns an iterator, necessary for Iterable interface. * @return an iterator over this sets elements */ public Iterator<E> iterator(); }
170
25
175 30
180
private class TreeIterator implements Iterator<E> {
35
private TreeNode myCurrent; private TreeNode myPrevious;
185
190
public TreeIterator(TreeNode root) { while ([Link] != null) { root = [Link]; } myCurrent = root; myPrevious = null; } public boolean hasNext() { return myCurrent != null; } public E next() { E data = [Link]; myPrevious = myCurrent; myCurrent = successor(myCurrent); return data; } public void remove() { if (myPrevious == null) { throw new IllegalStateException( "cannot remove, no valid next call"); } [Link](myPrevious); myPrevious = null; mySize; } } }
40
45
195
200
205
210
215
Wednesday October 14, 2009
[Link], [Link]
2/5
Printed by Owen L. Astrachan Oct 14, 09 8:23
package setstuff100;
75
[Link]
Page 1/3
Oct 14, 09 8:23
[Link]
Page 2/3
import [Link].*;
5
public class TrieSet implements ISimpleSet<String> {
80
Node oldRoot = [Link]; [Link] = null; TrieIterator iter = new TrieIterator(t); while ([Link]()) { [Link](prefix+[Link]()); } [Link] = oldRoot; } public boolean remove(String s) { Node t = myRoot; for (int k = 0; k < [Link](); k++) { char ch = [Link](k); t = [Link](ch); if (t == null) return false; // no path below? done } if ([Link]) { [Link] = false; mySize; return true; } return false; } public boolean contains(String s) { Node t = myRoot; for (int k = 0; k < [Link](); k++) { char ch = [Link](k); t = [Link](ch); if (t == null) return false; // no path below? done } return [Link]; // was this marked as a word? } public Iterator<String> iterator() { return new TrieIterator(myRoot); }
10
public static class Node { char info; boolean isWord; Map<Character,Node> children; Node parent;
85
15
20
Node(char ch, Node p) { info = ch; isWord = false; children = new TreeMap<Character,Node>(); parent = p; } } private Node myRoot; // root of entire trie
90
95
25
private int mySize; public TrieSet() { myRoot = new Node(x, null); mySize = 0; } public int size() { return mySize; }
100
30
105
35
public int getIndex(char ch){ ch = [Link](ch); if ([Link](ch)) return ch a + 1; return 0 ;
40
110
} public boolean add(String s) { Node t = myRoot;
45
115
for (int k = 0; k < [Link](); k++) { char ch = [Link](k); Node child = [Link](ch); if (child == null) { child = new Node(ch, t); [Link](ch,child); } t = child; } if (![Link]) { [Link] = true; // walked down path, mark this as a word mySize++; return true; } return false; // alread in set }
135 120
private class TrieIterator implements Iterator<String> { private Node myCurrent; private Node myPrevious; private IdentityHashMap<Node, Object> mySeen = new IdentityHashMap<Node, Object>(); private Object thing = new Object(); StringBuffer path; public TrieIterator(Node root){ myPrevious = null; path = new StringBuffer(); myCurrent = findWordBelow(root); } private Node findWordBelow(Node root){
50
125
55
130
60
65
public void prefixList(ArrayList<String> list, String prefix){ Node t = myRoot; for (int k = 0; k < [Link](); k++) { char ch = [Link](k); t = [Link](ch); if (t == null) { return; } }
140
70
145
if (root == null){ return null; } if ([Link] && ){ [Link](root,thing); return root; } for(Node n : [Link]()){ [Link]([Link]); Node recur = findWordBelow(n); if (recur != null){ return recur; } [Link]([Link]()1); }
Wednesday October 14, 2009
[Link]
3/5
Printed by Owen L. Astrachan Oct 14, 09 8:23
return null; }
150
[Link]
Page 3/3
Oct 14, 09 8:23
package setstuff100;
5
[Link]
Page 1/1
private Node nextWord(Node root){ Node recur = findWordBelow(root); if (recur != null){ return recur; } while (root != null){ Node last = root; root = [Link]; if (root == null) break; // backed up through global root [Link]([Link]()1); for(Node n : [Link]()) { if (){ [Link]([Link]); n = findWordBelow(n); if (n != null){ return n; } } } } return null; } public boolean hasNext() { return myCurrent != null; } public String next() { String s = new String(path); myPrevious = myCurrent; myCurrent = nextWord(myCurrent); return s; } public void remove() { if (myPrevious != null){ [Link] = false; myPrevious = null; mySize; } else { throw new IllegalStateException("bad remove from Trie iterator"); } } } }
155
10
/** * This generic class illustrates simple imlementations * of sets for the purposes of understanding and reasoning * about tradeoffs. For example, we consider hashing, search trees, * AVL trees and tries as set implementations. * @author Owen Astrachan * @version 2.0, October 2006 */ import [Link];
160
15
165
20
public interface ISimpleSet<E> extends Iterable<E> { /** * Returns the number of elements in this set. * @return size of set */ public int size(); /** * Adds an element to the set (no duplicates). Returns true if and only if * the element was added, i.e., not already stored in the set. * @param element to be added to set * @return true if element not previously in set, false otherwise */ public boolean add(E element); /** * Removes an element from the set and returns true if removal successful. * @param element to be removed from set * @return true if element removed, false otherwise */ public boolean remove(E element); /** * Returns true if element in set, false otherwise. * @param element is candidate for query in set * @return true if element in set, false otherwise */ public boolean contains(E element); /** * Returns an iterator, necessary for Iterable interface. * @return an iterator over this sets elements */ public Iterator<E> iterator(); }
170
25
175
30
180
35
185
40
190
45
195
Wednesday October 14, 2009
[Link], [Link]
4/5
Printed by Owen L. Astrachan Oct 14, 09 8:23
package setstuff100; import [Link].*;
5
[Link]
Page 1/1
public class SortedArraySet<E extends Comparable<E>> extends ArraySet<E> { public boolean add(E element) { int index = [Link](myList,element); if (index < 0){ index = (index+1); [Link](index,element); return true; } return false; } public boolean remove(E element) { int index = [Link](myList,element); if (index < 0){ return false; } [Link](index); return true; } public boolean contains(E element) { return [Link](myList,element) >= 0; }
10
15
20
25
30
public Iterator<E> iterator() { return [Link](); }
35
Wednesday October 14, 2009
[Link]
5/5