5 Replies - 972 Views - Last Post: 26 March 2011 - 01:05 PM Rate Topic: -----

#1 FoggyPhysics  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 26-March 11

Getting Trees into a priority queue / error

Posted 26 March 2011 - 09:09 AM

Hello,
I am having a trouble understanding why I am not able to insert the the trees I have made into a priority queue. The PriorityQ, Node and Tree classes are from Lafore's Data Structures text. I am trying to build a Huffman algorithm and am hung up on this step. I believe it is because the are incompatible types, inorder to insert a Tree object into the PriorityQ, the PriorityQ should be declared with "private Tree[] queArray;" instead of "private int[] queArray;" Is this assumption correct?

Error Message is as follows:

----jGRASP exec: javac -g Assignment5.java
HuffmanTesting.java:377: insert(int) in PriorityQ cannot be applied to (Tree)
thePQ.insert(theTree);
^
Note: HuffmanTesting.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error

----jGRASP wedge: exit code for process is 1.
----jGRASP: operation complete.




import java.util.*;
import java.io.*;
import java.util.*;               // for Stack class

////////////////////////////////////////////////////////////////
   class PriorityQ
   
   {
   // array in sorted order, from max at 0 to min at size-1
      private int maxSize;
      private int[] queArray;
      private int nItems;
   //-------------------------------------------------------------
      public PriorityQ(int s)                  // constructor
      {
         maxSize = s;
         queArray = new int[maxSize];
         nItems = 0;
      }
   //-------------------------------------------------------------
      public void insert(int item)            // insert item
      {
         int j;
      
         if(nItems==0)                         // if no items,
            queArray[nItems++] = item;         // insert at 0
         else                                  // if items,
         {
            for(j=nItems-1; j>=0; j--)         // start at end,
            {
               if( item > queArray[j] )        // if new item larger,
                  queArray[j+1] = queArray[j]; // shift upward
               else                            // if smaller,
                  break;                       // done shifting
            }  // end for
            queArray[j+1] = item;              // insert it
            nItems++;
         }                                     // end else (nItems > 0)
      }                                        // end insert()
   //-------------------------------------------------------------
      public int remove()                     // remove minimum item
      { 
         return queArray[--nItems]; }
   //-------------------------------------------------------------
      public int peekMin()                    // peek at minimum item
      { 
         return queArray[nItems-1]; }
   //-------------------------------------------------------------
      public boolean isEmpty()                 // true if queue is empty
      { 
         return (nItems==0); }
   //-------------------------------------------------------------
      public boolean isFull()                  // true if queue is full
      { 
         return (nItems == maxSize); }
   //-------------------------------------------------------------
   }                                           // end class PriorityQ

/**************************************************************/

/**************************************************************/
   class Node
   {
      public int iData;              // data item (key)
      public double dData;           // data item
      public Node leftChild;         // this node's left child
      public Node rightChild;        // this node's right child
   
      public void displayNode()      // display ourself
      {
         System.out.print('{');
         System.out.print(iData);
         System.out.print(", ");
         System.out.print(dData);
         System.out.print("} ");
      }
   }  // end class Node
/**************************************************************/
   class Tree
   {
      private Node root;             // first node of tree
   
   // -------------------------------------------------------------
      public Tree()                  // constructor
      { root = null; }            // no nodes in tree yet
   // -------------------------------------------------------------
      public Node find(int key)      // find node with given key
      {                           // (assumes non-empty tree)
         Node current = root;               // start at root
         while(current.iData != key)        // while no match,
         {
            if(key < current.iData)         // go left?
               current = current.leftChild;
            else                            // or go right?
               current = current.rightChild;
            if(current == null)             // if no child,
               return null;                 // didn't find it
         }
         return current;                    // found it
      }  // end find()
   // -------------------------------------------------------------
      public void insert(int id, double dd)
      {
         Node newNode = new Node();    // make new node
         newNode.iData = id;           // insert data
         newNode.dData = dd;
         if(root==null)                // no node in root
            root = newNode;
         else                          // root occupied
         {
            Node current = root;       // start at root
            Node parent;
            while(true)                // (exits internally)
            {
               parent = current;
               if(id < current.iData)  // go left?
               {
                  current = current.leftChild;
                  if(current == null)  // if end of the line,
                  {                 // insert on left
                     parent.leftChild = newNode;
                     return;
                  }
               }  // end if go left
               else                    // or go right?
               {
                  current = current.rightChild;
                  if(current == null)  // if end of the line
                  {                 // insert on right
                     parent.rightChild = newNode;
                     return;
                  }
               }  // end else go right
            }  // end while
         }  // end else not root
      }  // end insert()
   // -------------------------------------------------------------
      public boolean delete(int key) // delete node with given key
      {                           // (assumes non-empty list)
         Node current = root;
         Node parent = root;
         boolean isLeftChild = true;
      
         while(current.iData != key)        // search for node
         {
            parent = current;
            if(key < current.iData)         // go left?
            {
               isLeftChild = true;
               current = current.leftChild;
            }
            else                            // or go right?
            {
               isLeftChild = false;
               current = current.rightChild;
            }
            if(current == null)             // end of the line,
               return false;                // didn't find it
         }  // end while
      // found node to delete
      
      // if no children, simply delete it
         if(current.leftChild==null &&
                                   current.rightChild==null)
         {
            if(current == root)             // if root,
               root = null;                 // tree is empty
            else if(isLeftChild)
               parent.leftChild = null;     // disconnect
            else                            // from parent
               parent.rightChild = null;
         }
         
         // if no right child, replace with left subtree
         else if(current.rightChild==null)
            if(current == root)
               root = current.leftChild;
            else if(isLeftChild)
               parent.leftChild = current.leftChild;
            else
               parent.rightChild = current.leftChild;
         
         // if no left child, replace with right subtree
         else if(current.leftChild==null)
            if(current == root)
               root = current.rightChild;
            else if(isLeftChild)
               parent.leftChild = current.rightChild;
            else
               parent.rightChild = current.rightChild;
         
         else  // two children, so replace with inorder successor
         {
         // get successor of node to delete (current)
            Node successor = getSuccessor(current);
         
         // connect parent of current to successor instead
            if(current == root)
               root = successor;
            else if(isLeftChild)
               parent.leftChild = successor;
            else
               parent.rightChild = successor;
         
         // connect successor to current's left child
            successor.leftChild = current.leftChild;
         }  // end else two children
      // (successor cannot have a left child)
         return true;                                // success
      }  // end delete()
   // -------------------------------------------------------------
   // returns node with next-highest value after delNode
   // goes to right child, then right child's left descendents
      private Node getSuccessor(Node delNode)
      {
         Node successorParent = delNode;
         Node successor = delNode;
         Node current = delNode.rightChild;   // go to right child
         while(current != null)               // until no more
         {                                 // left children,
            successorParent = successor;
            successor = current;
            current = current.leftChild;      // go to left child
         }
                                           // if successor not
         if(successor != delNode.rightChild)  // right child,
         {                                 // make connections
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
         }
         return successor;
      }
   // -------------------------------------------------------------
      public void traverse(int traverseType)
      {
         switch(traverseType)
         {
            case 1: System.out.print("\nPreorder traversal: ");
               preOrder(root);
               break;
            case 2: System.out.print("\nInorder traversal:  ");
               inOrder(root);
               break;
            case 3: System.out.print("\nPostorder traversal: ");
               postOrder(root);
               break;
         }
         System.out.println();
      }
   // -------------------------------------------------------------
      private void preOrder(Node localRoot)
      {
         if(localRoot != null)
         {
            System.out.print(localRoot.iData + " ");
            preOrder(localRoot.leftChild);
            preOrder(localRoot.rightChild);
         }
      }
   // -------------------------------------------------------------
      private void inOrder(Node localRoot)
      {
         if(localRoot != null)
         {
            inOrder(localRoot.leftChild);
            System.out.print(localRoot.iData + " ");
            inOrder(localRoot.rightChild);
         }
      }
   // -------------------------------------------------------------
      private void postOrder(Node localRoot)
      {
         if(localRoot != null)
         {
            postOrder(localRoot.leftChild);
            postOrder(localRoot.rightChild);
            System.out.print(localRoot.iData + " ");
         }
      }
   // -------------------------------------------------------------
      public void displayTree()
      {
         Stack globalStack = new Stack();
         globalStack.push(root);
         int nBlanks = 32;
         boolean isRowEmpty = false;
         System.out.println(
            "......................................................");
         while(isRowEmpty==false)
         {
            Stack localStack = new Stack();
            isRowEmpty = true;
         
            for(int j=0; j<nBlanks; j++)
               System.out.print(' ');
         
            while(globalStack.isEmpty()==false)
            {
               Node temp = (Node)globalStack.pop();
               if(temp != null)
               {
                  System.out.print(temp.iData);
                  localStack.push(temp.leftChild);
                  localStack.push(temp.rightChild);
               
                  if(temp.leftChild != null ||
                                   temp.rightChild != null)
                     isRowEmpty = false;
               }
               else
               {
                  System.out.print("--");
                  localStack.push(null);
                  localStack.push(null);
               }
               for(int j=0; j<nBlanks*2-2; j++)
                  System.out.print(' ');
            }  // end while globalStack not empty
            System.out.println();
            nBlanks /= 2;
            while(localStack.isEmpty()==false)
               globalStack.push( localStack.pop() );
         }  // end while isRowEmpty is false
         System.out.println(
            "......................................................");
      }  // end displayTree()
   // -------------------------------------------------------------
   }  // end class Tree
////////////////////////////////////////////////////////////////
/**************************************************************/
/**************************************************************/
/**************************************************************/
/**************************************************************/
////////////////////////////////////////////////////////////////


   public class HuffmanTesting {
   /** Main method */
      public static void main(String[] args) throws Exception {
      // Create a File instance
         java.io.File file = new java.io.File("Huffmantext.txt");
      
      // Create a Scanner for the file
         java.util.Scanner input = new java.util.Scanner(file);
      
         String s = input.next();
      
      // Invoke the countLetters method to count each letter
         int[] counts = countLetters(s);
			
	    	Tree theTreeA = new Tree();
			theTreeA.insert(counts[0], 65);  
			theTreeA.displayTree();      
	    	Tree theTreeB = new Tree();
			theTreeB.insert(counts[1], 66);  
			theTreeB.displayTree();  
			Tree theTreeC = new Tree();
			theTreeC.insert(counts[2], 67);  
			theTreeC.displayTree();   
			Tree theTreeD = new Tree();
			theTreeD.insert(counts[3], 68);  
			theTreeD.displayTree();     
			Tree theTreeE = new Tree();
			theTreeE.insert(counts[4], 69);  
			theTreeE.displayTree();       
			Tree theTreeF = new Tree();
			theTreeF.insert(counts[5], 70);  
			theTreeF.displayTree();
			Tree theTreeG = new Tree();
			theTreeG.insert(counts[6], 71);  
			theTreeG.displayTree();		
			
			Tree theTree = new Tree();
			
			PriorityQ thePQ = new PriorityQ(7);
			thePQ.insert(theTree);											
			
			
      
               }                                                  //End main
   
   
   
   // Count each letter in the string
      public static int[] countLetters(String s) {
         int[] counts = new int[7];
      
         for (int i = 0; i < s.length(); i++) {
            if (Character.isLetter(s.charAt(i)))
               counts[s.charAt(i) - 'A']++;
         }
      
         return counts;
      }
   }





Is This A Good Question/Topic? 0
  • +

Replies To: Getting Trees into a priority queue / error

#2 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Getting Trees into a priority queue / error

Posted 26 March 2011 - 10:09 AM

The error message is self-explanatory:

you have a PriorityQ which consists primarily of an array of elements of datatype int and a method for placing new data elements of type int into that array

you have a Tree datatype which you created, consisting primarily of a Node datatype which you also created (which in turn consists of an int, a double, and references to two other Nodes)

and you are trying to push the Tree into the PriorityQ.

You can't park a truck in a bike rack.

You have to rewrite your PriorityQ to contain an array of Tree elements instead of ints, and rewrite its methods accordingly.

This post has been edited by r.stiltskin: 26 March 2011 - 10:25 AM

Was This Post Helpful? 1
  • +
  • -

#3 FoggyPhysics  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 26-March 11

Re: Getting Trees into a priority queue / error

Posted 26 March 2011 - 10:32 AM

View Postr.stiltskin, on 26 March 2011 - 10:09 AM, said:

The error message is self-explanatory:

you have a PriorityQ which consists primarily of an array of elements of datatype int and a method for placing new data elements of type int into that array

you have a Tree datatype which you created, consisting primarily of a Node datatype which you also created (which in turn consists of an int, a double, and references to two other Nodes)

and you are trying to push the Tree into the PriorityQ.

You can't park a truck in a bike rack.

You have to rewrite your PriorityQ to contain an array of Node elements instead of ints, and rewrite its methods accordingly.


Thank you for the quick response.

I assumed this was the idea but am very unsure on how to modify the PriorityQ class and its methods. For example, if I change the array from int to Node will i need to change nItems to iData?



   class PriorityQ
   
   {
   // array in sorted order, from max at 0 to min at size-1
      private int maxSize;
      private Node[] queArray;
      private int nItems;
   //-------------------------------------------------------------
      public PriorityQ(int s)                  // constructor
      {
         maxSize = s;
         queArray = new Node[maxSize];
         nItems = 0;
      }
   //-------------------------------------------------------------
      public void insert(int item)            // insert item
      {
         int j;
      
         if(nItems==0)                         // if no items,
            queArray[nItems++] = item;         // insert at 0
         else                                  // if items,
         {
            for(j=nItems-1; j>=0; j--)         // start at end,
            {
               if( item > queArray[j] )        // if new item larger,
                  queArray[j+1] = queArray[j]; // shift upward
               else                            // if smaller,
                  break;                       // done shifting
            }  // end for
            queArray[j+1] = item;              // insert it
            nItems++;
         }                                     // end else (nItems > 0)
      }                                        // end insert()
   //-------------------------------------------------------------
      public Node remove()                     // remove minimum item
      { 
         return queArray[--nItems]; }
   //-------------------------------------------------------------
      public Node peekMin()                    // peek at minimum item
      { 
         return queArray[nItems-1]; }
   //-------------------------------------------------------------
      public boolean isEmpty()                 // true if queue is empty
      { 
         return (nItems==0); }
   //-------------------------------------------------------------
      public boolean isFull()                  // true if queue is full
      { 
         return (nItems == maxSize); }
   //-------------------------------------------------------------
   }                                           // end class PriorityQ

////////////////////////////////////////////////////////////////
   class Node
   {
      public int iData;              // data item (key)
      public double dData;           // data item
      public Node leftChild;         // this node's left child
      public Node rightChild;        // this node's right child
   
      public void displayNode()      // display ourself
      {
         System.out.print('{');
         System.out.print(iData);
         System.out.print(", ");
         System.out.print(dData);
         System.out.print("} ");
      }
   }  // end class Node
////////////////////////////////////////////////////////////////



Was This Post Helpful? 0
  • +
  • -

#4 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Getting Trees into a priority queue / error

Posted 26 March 2011 - 10:50 AM

View PostFoggyPhysics, on 26 March 2011 - 12:32 PM, said:

u for the quick response.

... if I change the array from int to Node will i need to change nItems to iData?


That doesn't really make sense. No matter what kind of items are in the queue, it still wants to know how many there are, and how many will always be an int, right? But that's the least of your troubles.

Looking over your code again, it seems like you are trying to piece together code that was written for different purposes. You'll have trouble using that Tree class without modification -- because it wasn't designed for adding Nodes, it was designed for adding ints (and creates its own nodes). You'll either have to rewrite the Tree class, or work with Nodes directly (without the tree), or at every step of the Huffman algorithm you'll have to retrieve all the ints out of one subtree and add them one by one to another subtree.
Was This Post Helpful? 1
  • +
  • -

#5 FoggyPhysics  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 26-March 11

Re: Getting Trees into a priority queue / error

Posted 26 March 2011 - 11:49 AM

How about this approach:
Make a Node for each letter
Make a tree for each Nodes
Insert Node into Trees into PriorityQ

I still do not understand how to modify the priority queue so that it will accept something other than ints. I am reading Liang's "Introduction to Java" now and see that he uses generics for priority queue's (Trees, Heaps and everything else).

View Postr.stiltskin, on 26 March 2011 - 10:50 AM, said:

View PostFoggyPhysics, on 26 March 2011 - 12:32 PM, said:

u for the quick response.

... if I change the array from int to Node will i need to change nItems to iData?


That doesn't really make sense. No matter what kind of items are in the queue, it still wants to know how many there are, and how many will always be an int, right? But that's the least of your troubles.

Looking over your code again, it seems like you are trying to piece together code that was written for different purposes. You'll have trouble using that Tree class without modification -- because it wasn't designed for adding Nodes, it was designed for adding ints (and creates its own nodes). You'll either have to rewrite the Tree class, or work with Nodes directly (without the tree), or at every step of the Huffman algorithm you'll have to retrieve all the ints out of one subtree and add them one by one to another subtree.


View PostFoggyPhysics, on 26 March 2011 - 11:45 AM, said:

Correction on steps in last post:

1.) Make a Node for each letter
2.) Make a tree for each Nodes
3.) Insert Nodes into Tree
4.) Insert Trees into PriorityQ

View Postr.stiltskin, on 26 March 2011 - 10:50 AM, said:

View PostFoggyPhysics, on 26 March 2011 - 12:32 PM, said:

u for the quick response.

... if I change the array from int to Node will i need to change nItems to iData?


That doesn't really make sense. No matter what kind of items are in the queue, it still wants to know how many there are, and how many will always be an int, right? But that's the least of your troubles.

Looking over your code again, it seems like you are trying to piece together code that was written for different purposes. You'll have trouble using that Tree class without modification -- because it wasn't designed for adding Nodes, it was designed for adding ints (and creates its own nodes). You'll either have to rewrite the Tree class, or work with Nodes directly (without the tree), or at every step of the Huffman algorithm you'll have to retrieve all the ints out of one subtree and add them one by one to another subtree.

Was This Post Helpful? 0
  • +
  • -

#6 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Getting Trees into a priority queue / error

Posted 26 March 2011 - 01:05 PM

Think about how the Huffman algorithm works.

I think you should have a constructor that lets you create a Tree by supplying a "key" (int, char, whatever data type you are encoding) to be the contents of the root Node, and another constructor that takes a Tree to be the root, a Tree to be the leftChild, and another Tree to be the rightChild.

So your Tree class will need:
Tree( Datatype dat ); // this creates the single-node trees to begin
Tree( Tree root, Tree left, Tree right ); // this creates multi-node trees

And your PriorityQ will need:
void insert( Tree t );
Tree remove();

And the PriorityQ has to be able to order its elements based on the value of the data member of the Node at the root of the Tree being inserted.

This post has been edited by r.stiltskin: 26 March 2011 - 01:05 PM

Was This Post Helpful? 2
  • +
  • -

Page 1 of 1