aboutsummaryrefslogtreecommitdiffstats
path: root/csci1913/Java/project3/project3_strap012.java
blob: 16290aa51c6aa62ce65810eaf3b30028ce51b1d3 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
//package used to bundle with Words class
package project3;
class AnagramTree {
    private TreeNode head;
    private class TreeNode {
        private byte[] summary;
        private WordNode words;
        private TreeNode left, right;
        private TreeNode(String word, byte[] summary) {
            words = new WordNode(word, null);
            this.summary = summary;
            left = null; right = null;
        }
    }

    private class WordNode {
        private String word;
        private WordNode next;
        private WordNode(String word, WordNode next) {
            this.word = word;
            this.next = next;
        }
    }

    public AnagramTree() {
        head = new TreeNode(null, null);
    }

    public void add (String word) {
        byte [] newSumm = new byte [26];
        newSumm = stringToSummary(word);
        TreeNode top = head, bottom = top.right;
        boolean goLeft = false, addWord = false;
        while (bottom != null) {
            int comp = compareSummaries(bottom.summary, newSumm);
            if (comp > 0) {        // left is greater than right, go left
                top = bottom;
                goLeft = true;
                bottom = bottom.left;
            } else if (comp < 0) { // right is greater, go right
                top = bottom;
                goLeft = false;
                bottom = bottom.right;
            } else {
                WordNode badNode = bottom.words;
                boolean wordExists = false;
                while (badNode != null) {
                //Traverse word list to find already added entries
                    if (badNode.word.equals(word)) 
                        wordExists = true;
                    badNode = badNode.next; 
                }
                if (!wordExists)
                    bottom.words = new WordNode(word, bottom.words);
                addWord = true;
                break;
            }
        }   
        if (!addWord) {     //Word was not added, add it
            if (goLeft)
                top.left = new TreeNode(word, newSumm);
            else
                top.right = new TreeNode(word, newSumm);
        }
    } 

    public void anagrams() {
        findAnagrams(head.right);
    }

    private void findAnagrams(TreeNode subtree) {
        try {
            if (subtree.words.next != null) {
                System.out.println();
                while (subtree.words != null) {
                    System.out.print(subtree.words.word);
                    System.out.print(" ");
                    subtree.words = subtree.words.next;
                }
            }
            if (subtree != null) {
                findAnagrams(subtree.left);
                findAnagrams(subtree.right);
            }
        } catch (NullPointerException ignore) {
            /*
             This exception exists as a kludge for any time
             subtree is null. The program does bad things
             if this is not present.
            */
        }
    }
    
    private int compareSummaries(byte[] left, byte[] right) {
        for (int i = 0; i <= 25; i++) {
            if (left[i] != right[i]) {
                return left[i] - right[i];
            }
        }
        //Summaries are identical here
        return 0;
    }

    private byte[] stringToSummary(String word) {
        byte[] temp = new byte[26];
        for (byte i = 0; i < word.length(); i++) {
            temp[word.charAt(i) - 'a'] += 1;
        }
        return temp;
    }
}

class Anagrammer {
    public static void main(String[] args) {
        Words words = new Words(args[0]);
        AnagramTree anagrams = new AnagramTree();
        while (words.hasNext()) {
            anagrams.add(words.next());
        }
        anagrams.anagrams();
        //Print extra line for neatness
        System.out.println();
    }
}