Win a copy of Learn Spring Security (video course) this week in the Spring forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Please critique my countOccurrence method for IntTreeBag class

 
Dubravko Zubavich
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have written the countOccurrence method for the IntTreeBag class which returns the count of number of occurrences of a particular element in the bag.

public class IntTreeBag implements Cloneable
{

private IntBTNode root;

public void treeInsert(int newItem)
{

if ( root == null ) {

root = new IntBTNode(newItem, null,null );
return;
}

IntBTNode runner;
runner = root;
boolean done = false;

while (!done) {
if ( newItem < runner.getData() ) {

if ( runner.getLeft() == null ) {
runner.setLeft(new IntBTNode( newItem, null,null ));
return;
}
else
runner = runner.getLeft();
}
else {

if ( runner.getRight() == null )
{
runner.setRight(new IntBTNode( newItem, null,null ));
return;
}
else
runner = runner.getRight();
}
}
}

public int countOccurrences(int target)
{
int count = 0;
IntBTNode cursor = root;


while(cursor != null)
{
if(cursor.getData() > target)
cursor=cursor.getRight();

else if (cursor.getData() < target)
cursor = cursor.getLeft();

else if(cursor.getData() == target)
{
++count;
cursor = cursor.getLeft();
}

}
return count;
}

}

I have tested this method with varying tree size and to check to the occurrence of each element. Only one element at any time reports occurrence of 1 and the rest report zero. For example, I have added following ten integers to the tree bag.

84
Count is 1
90
Count is 0
97
Count is 0
67
Count is 0
57
Count is 0
17
Count is 0
13
Count is 0
64
Count is 0
67
Count is 0
46
Count is 0

My question is why the count occurrence method return zero for every other item. I check for the occurrence of each element as soon as I add it to the int tree bag. Please critique.
 
Rosco Duncan
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Dubravko,

Its difficult to understand this code without the rest of your IntTreeBag class implementation. It could be that the rest of the class is not implemented correctly. Also the method that you have posted seems to be incomplete as it is missing a return statement.
 
Dubravko Zubavich
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rosco Duncan wrote:Hi Dubravko,

Its difficult to understand this code without the rest of your IntTreeBag class implementation. It could be that the rest of the class is not implemented correctly. Also the method that you have posted seems to be incomplete as it is missing a return statement.


I have updated the code and added the rest of the class that I have written. It includes adding the node and counting occurrences.

 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I suspect you want that "return count;" to be outside the while loop, not inside!
 
Dubravko Zubavich
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ernest Friedman-Hill wrote:I suspect you want that "return count;" to be outside the while loop, not inside!


Actually, the return count is outside the while loop. I just mistyped it in the thread. Now i has been corrected.
 
Moojid Hamid
Ranch Hand
Posts: 120
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
you have your getLeft and get right backwards.
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dubravko Zubavich wrote:
Ernest Friedman-Hill wrote:I suspect you want that "return count;" to be outside the while loop, not inside!


Actually, the return count is outside the while loop. I just mistyped it in the thread. Now i has been corrected.


You typed your code to post it? Are you familiar with "cut and paste?"

See here for a discussion of why doing this is not just a lot of unneeded work, but a bad idea besides.
 
Dubravko Zubavich
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ernest Friedman-Hill wrote:
Dubravko Zubavich wrote:
Ernest Friedman-Hill wrote:I suspect you want that "return count;" to be outside the while loop, not inside!


Actually, the return count is outside the while loop. I just mistyped it in the thread. Now i has been corrected.


You typed your code to post it? Are you familiar with "cut and paste?"

See here for a discussion of why doing this is not just a lot of unneeded work, but a bad idea besides.


yes, I am familiar with cut and paste and that's what I did.

The last part is where I had to retype it in the thread, not the entire code.

Thanks for pointing that out.
 
Dubravko Zubavich
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Moojid Hamid wrote:you have your getLeft and get right backwards.


I have fixed that and now every element's count is 1. My question is that in cases where I have more than one occurrence of the same element shouldn't the count occurrence method return a value greater than one for that specific element.

 
Moojid Hamid
Ranch Hand
Posts: 120
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dubravko Zubavich wrote:
Moojid Hamid wrote:you have your getLeft and get right backwards.


I have fixed that and now every element's count is 1. My question is that in cases where I have more than one occurrence of the same element shouldn't the count occurrence method return a value greater than one for that specific element.



Did you fix the last case where cursor.getData() == target? It should also be getRight.
 
Dubravko Zubavich
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Moojid Hamid wrote:
Dubravko Zubavich wrote:
Moojid Hamid wrote:you have your getLeft and get right backwards.


I have fixed that and now every element's count is 1. My question is that in cases where I have more than one occurrence of the same element shouldn't the count occurrence method return a value greater than one for that specific element.



Did you fix the last case where cursor.getData() == target? It should also be getRight.


Yes, I did it now and I can get more than one count in case there are duplicates.

But shouldn't it be getLeft since elements to the left are less or equal to the element at cursor node. This is exactly what the text book says.

 
Moojid Hamid
Ranch Hand
Posts: 120
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dubravko Zubavich wrote:
Moojid Hamid wrote:
Dubravko Zubavich wrote:
Moojid Hamid wrote:you have your getLeft and get right backwards.


I have fixed that and now every element's count is 1. My question is that in cases where I have more than one occurrence of the same element shouldn't the count occurrence method return a value greater than one for that specific element.



Did you fix the last case where cursor.getData() == target? It should also be getRight.


Yes, I did it now and I can get more than one count in case there are duplicates.

But shouldn't it be getLeft since elements to the left are less or equal to the element at cursor node. This is exactly what the text book says.



In that case your insert method is incorrect. look at the if statement in the insert method, you are inserting on left only if the value is less than the node. if it is equal or greater it goes on right.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic