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 (or already exists), keep going
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.right);
findAnagrams(subtree.left);
}
} catch (NullPointerException ignore) {
/*
This exception exists as a kludge for any time
subtree is null. The program does bad things (crash)
if this is not present.
*/
}
}
private int compareSummaries(byte[] left, byte[] right) {
for (int i = 0; i < 26; 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();
}
}
|
