001: package soot.toolkits.purity;
002:
003: /**
004: * This example is from the article A Combined Pointer and Purity Analysis for
005: * Java Programs" by Alexandru Salcianu and Martin Rinard.
006: * It is supposed to demonstrate the purity analysis (-annot-purity)
007: *
008: * by Antoine Mine, 2005/02/08
009: */
010:
011: import java.util.*;
012:
013: public class BinarySearchTree {
014: Node root;
015: int size;
016:
017: static class Node {
018: Node left;
019: Node right;
020: Comparable info;
021: }
022:
023: static final class Wrapper {
024: Object o;
025:
026: Wrapper(Object o) {
027: this .o = o;
028: }
029:
030: public boolean equals(Object o) {
031: if (!(o instanceof Wrapper))
032: return false;
033: return this .o == ((Wrapper) o).o;
034: }
035:
036: public int hashCode() {
037: return System.identityHashCode(o);
038: }
039: }
040:
041: boolean repOk() {
042: if (root == null)
043: return size == 0;
044: if (!isTree())
045: return false;
046: if (numNodes(root) != size)
047: return false;
048: if (!isOrdered(root, null, null))
049: return false;
050: return true;
051: }
052:
053: boolean isTree() {
054: Set visited = new HashSet();
055: visited.add(new Wrapper(root));
056: LinkedList workList = new LinkedList();
057: workList.add(root);
058: while (!workList.isEmpty()) {
059: Node current = (Node) workList.removeFirst();
060: if (current.left != null) {
061: if (!visited.add(new Wrapper(current.left)))
062: return false;
063: workList.add(current.left);
064: }
065: if (current.right != null) {
066: if (!visited.add(new Wrapper(current.right)))
067: return false;
068: workList.add(current.right);
069: }
070: }
071: return true;
072: }
073:
074: int numNodes(Node n) {
075: if (n == null)
076: return 0;
077: return 1 + numNodes(n.left) + numNodes(n.right);
078: }
079:
080: boolean isOrdered(Node n, Comparable min, Comparable max) {
081: if ((min != null && n.info.compareTo(min) <= 0)
082: || (max != null && n.info.compareTo(max) >= 0))
083: return false;
084: if (n.left != null)
085: if (!isOrdered(n.left, min, n.info))
086: return false;
087: if (n.right != null)
088: if (!isOrdered(n.right, n.info, max))
089: return false;
090: return true;
091: }
092:
093: static Node create(int i) {
094: if (i == 0)
095: return null;
096: Node n = new Node();
097: n.left = create(i - 1);
098: n.right = create(i - 1);
099: return n;
100: }
101:
102: public static void main(String[] args) {
103: BinarySearchTree x = new BinarySearchTree();
104: x.root = create(5);
105: x.repOk();
106: }
107:
108: }
|