Aidan Johansson

Yeah. You know what, I may not write the correct add() method as well.

Anagram trees. Because of the K and R algorithm, summaries are totally ordered, so we can use them as keys in a binary search tree. We will call it an anagram tree. The anagram tree’s keys are summaries, and its values are linear singly linked lists of strings, in which each string represents a word. The anagram tree is the basis for our efficient anagram finding program.
Here is my idea. We start with an empty anagram tree. Then we read words as strings from a text file. Every time we read a word, we construct its summary. Then we search for a node in the tree that has the summary as its key, using the "K-and-R" algorithm to control the search. If we find the node, then we add the word to the node’s list (if it’s not already there). If we do not find the node, then we add a new node to the list. The new node’s key is the summary, and its value is a list that contains the word.

Hello everyone,
I am trying to read in a text from a file and then using an algorithm to find the anagrams by using the concept of summaries. Suppose that a word is a string of one or more lower case Roman letters a through z, without accents, blanks, or punctuation marks. Also suppose that the letter a corresponds to 0, that b corresponds to 1, etc., up to z that corresponds to 25. (These are not the A SCII or Unicode codes for those letters!) For each word, we make an array of 26 integers, called a summary of that word. In the summary, the element at index k tells how many times the letter corresponding to k appears in the word. For example, if we have the word present, then its summary looks like this, where the large numbers are array elements, and the small numbe

After we have read all the words, there will be many nodes in the anagram tree, each with a list of one or more words. The words in each list are anagrams of each other, because they all have the same summary. We then traverse the tree, visiting each node. If we find a node whose list has only one word, then we ignore it, because that word is an anagram of only itself. However, if we find a node whose list has two or more words, then we print those words, because they are anagrams of each other.
import java.io.FileReader;   //  Read Unicode chars from a file. import java.io.IOException;  //  In case there's IO trouble. //  WORDS. Iterator. Read words, represented as STRINGs, from a text file. Each //  word is the longest possible contiguous series of alphabetic ASCII CHARs. class Words {    private int           ch;      //  Last CHAR from READER, as an INT.    private FileReader    reader;  //  Read CHARs from here.    private StringBuilder word;    //  Last word read from READER. //  Constructor. Initialize an instance of WORDS, so it reads words from a file //  whose pathname is PATH. Throw an exception if we cannot open PATH.    public Words(String path)    {        try        {            reader = new FileReader(path);            ch = reader.read();        }        catch (IOException ignore)        {            throw new IllegalArgumentException("Cannot open '" + path + "'.");        }    } //  HAS NEXT. Try to read a WORD from READER, converting it to lower case as we //  go. Test if we were successful.    public boolean hasNext()    {        word = new StringBuilder();        while (ch > 0 && ! isAlphabetic((char) ch))        {            read();        }        while (ch > 0 && isAlphabetic((char) ch))        {            word.append(toLower((char) ch));            read();        }        return word.length() > 0;    } //  IS ALPHABETIC. Test if CH is an ASCII letter.    private boolean isAlphabetic(char ch)    {        return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z';    } //  NEXT. If HAS NEXT is true, then return a WORD read from READER as a STRING. //  Otherwise, return an undefined STRING.    public String next()    {        return word.toString();    } //  READ. Read the next CHAR from READER. Set CH to the CHAR, represented as an //  INT. If there are no more CHARs to be read from READER, then set CH to -1.    private void read()    {        try        {            ch = reader.read();        }        catch (IOException ignore)        {            ch = -1;        }    } //  TO LOWER. Return the lower case ASCII letter which corresponds to the ASCII //  letter CH.    private char toLower(char ch)    {        if ('a' <= ch && ch <= 'z')        {            return ch;        }        else        {            return (char) (ch - 'A' + 'a');        }    } //  MAIN. For testing. Open a text file whose pathname is the 0th argument from //  the command line. Read words from the file, and print them one per line.    public static void main(String [] args)    {        Words words = new Words(args[0]);        while (words.hasNext())        {            System.out.println("'" + words.next() + "'");        }    } } class AnagramTree {    private class TreeNode    {        private byte[] summary;        private WordNode words ;        private TreeNode left;        private TreeNode right;        private TreeNode(WordNode words)        {            this.summary = summary;            this.words = words;            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;        }    }    private TreeNode head;    public AnagramTree()    {        head = new TreeNode(null);    }    public void add(String word)    {        TreeNode temp = head;        WordNode wordnode = new WordNode(word, null);        TreeNode new_tree_node = new TreeNode(wordnode);        while(temp != null)        {            if(temp.left == null && (compareSummaries(new_tree_node.summary, temp.summary) <= 0))            {                temp.left = new_tree_node;            }            else            {                temp = temp.left;            }            if(temp.right == null && (compareSummaries(new_tree_node.summary, temp.summary) >= 0))            {                temp.right = new_tree_node;            }            else            {                temp = temp.right;            }        }    }    public void anagrams()    {        TreeNode temp = head;        while(temp != null)        {            if(temp.words.next != null)            {                printInOrder_anagrams(temp);                System.out.print(" ");            }        }    }    private void printInOrder_anagrams(TreeNode currNode)    {        if(currNode == null)        {            return;        }        printInOrder_anagrams(currNode.left);        System.out.print(currNode.words.next + " ");        printInOrder_anagrams(currNode.right);    }    private int compareSummaries(byte[] left, byte[] right)    {        for(int i = 0; i < 26; i++)        {            System.out.print(left[i]);            if(left[i] != right[i])            {                System.out.print(left[i]);                return left[i] - right[i];            }        }        return 0;    }    private byte[] stringToSummary(String word)    {        byte[] summary = new byte[26];        for(int i = 0; i < word.length(); i++)        {            int index = word.charAt(i) - 'a';            summary[index] += 1;            System.out.print(summary[index]);        }        return summary;    } } class Anagrammer {    public static void main(String[] args)    {        Words words = new Words(args[0]);        AnagramTree tree = new AnagramTree();        while (words.hasNext())        {            tree.add(words.next());        }        tree.anagrams();    } }
I have error messages:
Exception in thread "main" java.lang.NullPointerException at AnagramTree.compareSummaries(nguy2952_Project3.java:188) at AnagramTree.add(nguy2952_Project3.java:142) at Anagrammer.main(nguy2952_Project3.java:220)
I need help. Thank you.

It is my honor. Thank you for doing that.

I think what you have said helps me a lot. Even though I may not fully understand what you are saying, I will keep in mind for future practice.
Thank you.

I am sorry I have been working all day. I just saw the comments. Is everything alright? Are we cool?
Thanks for helping out me.

I think it is confusing when I made a class called stack but it is implemented as a singly linked list.
I attached a drawing.

Stephan van Hulst wrote:Hugh, don't use names like Base for generic type parameters. Use single capital letters, such as T.

Thank you kindly.

Hello,
I am supposed to compare the top two elements without changing the nature of the stack, i.e I am not supposed to use peek(), pop(), or push() as the way we implement those methods in class will change the date structures. We can define stack differently and it all depends on how we use it, so the method of implementation is different. This is what I think. Thank you for sharing your thoughts.

Thank you.

I apologize. I forgot to inform you that I made a class call Stack but it actually works as a node. I define a node to have two slots: the first one is object and the next slots points to the next node. This class Stack implements a stack using a singly linked list. So I guess for my second comparison, I have to use:
class Stack<Base> {    private class Node    {        private Base object;        private Node next;        private Node(Base object,Node next)        {            this.object = object;            this.next = next;        }    }    private Node top;
Then:
else if (top.object == top.next.object) {return true;}
Am I still right? Thanks.

Hello,
I would to write a method that accepts no arguments. This method has the following content:
1. If the top two elements on the stack are equal, then return true.
2. If the stack is null or has one element, return false.
3. Otherwise, if the top two elements are not equal, return false. Assume no element is null.

Here is my code.
public boolean aretheyEqual() { if(top.next == null || top == null) { return false;} else if(top == top.next) {return true;} return else; }
Is this true?
Thank you.

That was all I could think of.

Step 1: To half into two lists: left and right and add the nodes to the front of these lists.
while (true) {            if (unsorted != null) {                currNode = unsorted.next;                unsorted.next = left;                left = unsorted;                unsorted = currNode;            } else {                break;            }            if (unsorted != null) {                currNode = unsorted.next;                unsorted.next = right;                right = unsorted;                unsorted = currNode;            } else {                break;            }        }

It works now. Thanks everyone.