Evening Folks,

Having a bit of a problem with somthing i am trying to code, wondering if anyone here can help....

The basic idea is that i am trying to build a Priority Queue of binary tree nodes so that they are stored in ascending order by a number stored in each of the tree nodes.

Each binary tree node is constructed from a CharNode and are definately being constructed properly. The problem seems to be in the BinaryNode's compareTo method as the Priority Queue is using this to sort the elements.

BinaryNode.java

public class BinaryNode implements Comparable<BinaryNode>{
	
	private BinaryNode left;
	private BinaryNode right;
	private int frequency;
	private char character;
	
	public BinaryNode(int f, char c){
		this.left = null;
		this.right = null;
		this.frequency = f;
		this.character = c;
	}
	
	public BinaryNode getLeft() {
		return left;
	}
	
	public void setLeft(BinaryNode left) {
		this.left = left;
	}
	
	public BinaryNode getRight() {
		return right;
	}
	
	public void setRight(BinaryNode right) {
		this.right = right;
	}
	
	public int getFrequency() {
		return frequency;
	}
	
	public void setFrequency(int frequency) {
		this.frequency = frequency;
	}
	
	public char getCharacter() {
		return character;
	}
	
	public void setCharacter(char character) {
		this.character = character;
	}	
	
	public int compareTo(BinaryNode x) {
    	
        // Assume neither string is null. Real code should
        // probably be more robust
        if (x.getFrequency() > this.getFrequency())
        {
            return -1;
        }
        else if (x.getFrequency() < this.getFrequency())
        {
            return 1;
        }
        else if (this.equals(x))
        	return 0;
        else {
        	System.out.println("ERROR");
        	return 0;
        }        
        }	
	public String toString(){
		//String s = "";
		return this.character + "/" + this.frequency;
	}
	
	public boolean equals(BinaryNode x){
		
		if (this.frequency == x.frequency && this.character == x.character){
			return true;
		}
		return false;
		
	}
}

The code that uses the PriorityQueue to

public void buildTree(){

		PriorityQueue<BinaryNode> queue = new PriorityQueue<BinaryNode>();
		
		for (CharNode element : this.frequencyList.getFreqList()){
			BinaryNode node = new BinaryNode(element.getFrequency(), element.getCharacter());
			System.out.println("Adding Node " + node + " to queue.");
			queue.add(node);
			System.out.println("Queue is now :" + queue);
			
		}
		
		System.out.println(queue);
	}

Ive tried using compartors but i come up against the same problem, the above code gives the following output:

Adding Node t/4 to queue.
Queue is now :[t/4]
Adding Node h/3 to queue.
Queue is now :[h/3, t/4]
Adding Node e/2 to queue.
Queue is now :[e/2, t/4, h/3]
Adding Node /4 to queue.
ERROR
Queue is now :[e/2, t/4, h/3, /4]
Adding Node c/1 to queue.
Queue is now :[c/1, e/2, h/3, /4, t/4]
Adding Node a/2 to queue.
Queue is now :[c/1, e/2, a/2, /4, t/4, h/3]
Adding Node i/1 to queue.
ERROR
Queue is now :[c/1, e/2, i/1, /4, t/4, h/3, a/2]
Adding Node n/1 to queue.
ERROR
Queue is now :[c/1, n/1, i/1, e/2, t/4, h/3, a/2, /4]
[c/1, n/1, i/1, e/2, t/4, h/3, a/2, /4]

I realise this might be a complicatedly worded etc, but if anyones willing to help ill glady explain any code etc...

Cheers,

Logi.

About L63:
L42 and L72 methods do not cover all cases, comparisons.
character GT LT ?

About L63:
L42 and L72 methods do not cover all cases, comparisons.
character GT LT ?

Are you saying my compareTo and equals methods should cover ALL cases?

The character in the binary node is pretty much irrelevant as far as the queue is concerned, im only interested in the number associated with each node.

Cheers,

Logi.

I'm confused - you said you're creating some sort of "binary tree priority queue" but your code looks like it's just intended to be a sorted list of Objects, which are different. Which is it supposed to be?

Also, in your sample run, you added a /4 but it doesn't have a character with it. Don't you have to say a/4 or something similar? Otherwise what happens to the character?

Edited 7 Years Ago by BestJewSinceJC: n/a

About

System.out.println("Queue is now :" + queue);

You are using default method toString(), which not reflect the order.
Try print in loop

queue.remove()

method

I've changed my compareTo method to the below code:

public int compareTo(BinaryNode x)
    {
    	
        if (this.character > x.character){
        	
        	if (x.getFrequency() > this.getFrequency())
            {
                return -1;
            }
            else if (x.getFrequency() < this.getFrequency())
            {
                return 1;
            }
            else {
            	return 0;
            }
        	
        }
        
        else if (this.character < x.character){
        	
        	if (x.getFrequency() > this.getFrequency())
            {
                return -1;
            }
            else if (x.getFrequency() < this.getFrequency())
            {
                return 1;
            }
            else {
            	return 0;
            }
        }
        
        else if (this.character == x.character){
        	
        	if (x.getFrequency() > this.getFrequency())
            {
                return -1;
            }
            else if (x.getFrequency() < this.getFrequency())
            {
                return 1;
            }
            else {
            	return 0;
            }
        	
        }
        else {
        	System.out.println("ERROR");
        	return 0;
        }        
    }

But it still outputs the queue as:

[c/1, n/1, i/1, e/2, t/4, h/3, a/2, /4]

Except this time there were no errors printed as pbviously all the cases are taken care of....

About
You are using default method toString(), which not reflect the order.
Try print in loopmethod

Nice one.

That worked fine, seems they were in order after all :D

Cheers,

Logi.

#6 too long
9 posibilities 10 returns

public int compareTo(Somthing with two things _1 and _2 to compare) {
        // _1 comparation higher priority
        if (GT_1) {
            return -1;
        } else if (LT_1) {
            return 1;
        } else { //here only EQ_1: 
            if (GT_2) {
                return -1;
            } else if (LT_2) {
                return 1;
            } //here only EQ2:
            return 0;
        }
        // here nothing -- impossible
    }
This article has been dead for over six months. Start a new discussion instead.