Tournament Tree help

[Christopher Beech]

Greetings, Java Ranch

I'm trying to type up a program that will generate sorted runs that are greater than the size of memory. The momory can hold a tournament tree with 4 elements. I have 16 elements to put in. It's suppose to take the 4 ints, do a min winner tree, toss the winner into an array, remove the winner from the tree, then insert a new given element. Program compares tree elements to the last int in the winner array. If the tree element is smaller than the last array in winner, it is ignored. Whenever all the tree elements are smaller than the last int in the winner array, the winner array is printed. The entire winner array is then erased.

Sorry if my code is a little funny. I've done most of the typing while sick.

 import java.util.*;
 
public class Tournament
{
  private Node[] tree;
  private int topSize;
  private int size;
  private Node[] anArray;
  private int sizeOfArray;
  
  public Tournament(int tp)
  {
    topSize = tp;
    size = 0;
    tree = new Node[topSize];
    sizeOfArray = size;
    anArray= new Node[sizeOfArray];
  }
  
  public boolean insert(int number)
  {
    Node newNode = new Node(number);
    tree[size] = newNode;
    up(size++);
    return true;
  }
  
  public void up(int index)
  {
    int parent = (index - 1) / 2;
    Node bottom = tree[index];
    
    while (index > 0 && tree[parent].getNumber() < bottom.getNumber())
    {
      tree[index] = tree[parent];
      index = parent;
      parent = (parent - 1) / 2;
    }
    tree[index] = bottom;
  }
  
  public void remove(int number)
  {
    Node root = tree[number];
    tree[number] = tree[--size];
  }
  
  public int compare()
  {
    int smaller;
    int left = tNode.getLeft();
    int right = tNode.getRight();
    
    if(tree[left].getNumber() > smaller && tree[right].getNumber() > smaller)
    {
      if (tree[left].getNumber() < tree[right].getNumber())
      {
        smaller = left;
        up(left);
        return(smaller);
      }
      else
      {
        smaller = right;
        up(right);
        remove(smaller);
        return(smaller);
      }
    }
    if (tree[left].getNumber() > smaller && tree[right].getNumber() < smaller)
    {
      smaller = left;
      up(left);
      return(smaller);
    }
    if (tree[left].getNumber() < smaller && tree[right].getNumber() > smaller)
    {
      smaller = right;
      up(right);
      return(smaller);
    }
    else
    {
      print(anArray);
    }
  }
  
  public void print()
  {
    System.out.print("Array: ");
    for (int i = 0; i < size; i++)
      if (anArray[i] != null)
      System.out.print(tree[i].getNumber() + " ");
    System.out.println();
  }
  
  public static void main(String[] args)
  {
    int collection, first, group, number, numberOfInts, size;
    
    first = 4;
    size = 16;
    Tournament h = new Tournament(size);
    Scanner console = new Scanner(System.in);
    System.out.println("Enter number of ints to insert.");
    numberOfInts = console.nextInt();
    
    while(numberOfInts > 0)
    {
      while (first != 0)
      {
        first = first - 1;
        numberOfInts = numberOfInts - 1;
        System.out.println("Enter number to insert.");
        collection = console.nextInt();
        h.insert(collection);
      }
      numberOfInts = numberOfInts - 1;
      System.out.println("Enter number to insert.");
      number = console.nextInt();
      h.insert(number);
      h.compare();
    }
  }
}
 
class Node
{
  private int info; //Makes an int variable named info.
  private Node leftChild;
  private Node rightChild;
  
  // Method to initialize variable.
  
  public Node(int key)
  {
    info = key;
    leftChild = null;
    rightChild = null;
  }
  
  //Method to get number from torunament tree.
  
  public int getNumber()
  {
    return info;
  }
  
  public Node getLeft()
  {
    return leftChild;
  }
  
  public Node getRight()
  {
    return rightChild;
  }
  
  //Method to set number to tournament tree
  
  public void setNumber(int number)
  {
    info = number;
  }
}   

Also, these three lines are giving the complier a fit:

  int left = tNode.getLeft();
        int right = tNode.getRight();
        else
        {
         print(anArray);
         }  

[ March 27, 2007: Message edited by: Christopher Beech ]
[ March 27, 2007: Message edited by: Christopher Beech ]

[Mike Mc Afee]

 
  public Node getLeft()
  {
    return leftChild;
  }
 
  public Node getRight()
  {
    return rightChild;
  }

Also, these three lines are giving the complier a fit:

  int left = tNode.getLeft();
        int right = tNode.getRight();
        else
        {
         print(anArray);
         }  

Although no description of the kind of fit that the compiler was having is provided, I've taken a stab at what the problem is. In the future, the more description of the problem, the better.

getLeft and getRight appear to be returning type Node. Change left and right to type Node.

[ March 27, 2007: Message edited by: Mike Mc Afee ]
[ March 27, 2007: Message edited by: Mike Mc Afee ]

[Christopher Beech]

Ok, did a little changing. Here's what I changed:

 public int compare(Node tNode)
  {
    int smaller = 0;
    Node left = tNode.getLeft();
    Node right = tNode.getRight();
    int leftNumber = left.getNumber();
    int rightNumber = right.getNumber();
 
    if(tree[leftNumber].getNumber() > smaller && tree[rightNumber].getNumber() > smaller)
    {
      if (tree[leftNumber].getNumber() < tree[rightNumber].getNumber())
      {
        smaller = leftNumber;
        up(leftNumber);
        return(smaller);
      }
      else
      {
        smaller = rightNumber;
        up(rightNumber);
        remove(smaller);
        return(smaller);
      }
    }
    if (tree[leftNumber].getNumber() > smaller && tree[rightNumber].getNumber() < smaller)
    {
      smaller = leftNumber;
      up(leftNumber);
      return(smaller);
    }
    if (tree[leftNumber].getNumber() < smaller && tree[rightNumber].getNumber() > smaller)
    {
      smaller = rightNumber;
      up(rightNumber);
      return(smaller);
    }
    else
    {
      print(anArray);
    }
  }   
public void print(Node[] anArray)
  {
    System.out.print("Array: ");
    for (int i = 0; i < size; i++)
      if (anArray[i] != null)
      System.out.print(tree[i].getNumber() + " ");
    System.out.println();
  }

The compiler is having a fit over the following line:

h.compare();
Error: compare(Node) in Tournament cannot be applied to ();
[ March 27, 2007: Message edited by: Christopher Beech ]

[David McCombs]

h.compare(); This is how you tried to call compare. This is the method:

public int compare(Node tNode)

You need to pass a Node as an argument.

[Christopher Beech]

New error found.

  else
    {
      print(anArray);
    }
  }  

Missing return statement

[David McCombs]

Look at the method header again. Then look at the end of the method, anything missing?

[Christopher Beech]

It's expecting an int to be returned. But I'm not sure what int to return. I could put return smaller at the very end. That'll make the compiler happy, but I doubt it'll do any more than that.

[Christopher Beech]

I've made some changes. I know that it will, at the very least, insert numbers in the correct order. If I could just get that compare to work.

 /* Author: Chris Beech
 *
 * Purpose:
 *
 * Created:  March 23, 2007
 * Modified: March 23, 2007
 */
 
import java.util.*;
 
public class Tournament
{
  private Node[] tree;
  private int topSize;
  private int size;
  private Node[] anArray;
  private int sizeOfArray;
  private Node root;
 
  public Tournament(int tp)
  {
    topSize = tp;
    size = 0;
    tree = new Node[topSize];
    sizeOfArray = size;
    anArray= new Node[sizeOfArray];
  }
 
  public boolean insert(int number)
  {
    Node newNode = new Node(number);
    tree[size] = newNode;
    up(size++);
    return true;
  }
 
  public void up(int index)
  {
    Node bottom = tree[index];
    
    tree[index] = bottom;
  }
 
  public void remove(int number)
  {
    Node root = tree[number];
    tree[number] = tree[--size];
  }
 
  public int compare(Node tNode)
  {
    int smaller = 0;
    Node left = tNode.getLeft();
    Node right = tNode.getRight();
    int leftNumber = left.getNumber();
    int rightNumber = right.getNumber();
 
    if(tree[leftNumber].getNumber() > smaller && tree[rightNumber].getNumber() > smaller)
    {
      if (tree[leftNumber].getNumber() < tree[rightNumber].getNumber())
      {
        smaller = leftNumber;
        up(leftNumber);
        return smaller;
      }
      else
      {
        smaller = rightNumber;
        up(rightNumber);
        return smaller;
      }
    }
    if (tree[leftNumber].getNumber() > smaller && tree[rightNumber].getNumber() < smaller)
    {
      smaller = leftNumber;
      up(leftNumber);
      return smaller;
    }
    if (tree[leftNumber].getNumber() < smaller && tree[rightNumber].getNumber() > smaller)
    {
      smaller = rightNumber;
      up(rightNumber);
      return smaller;
    }
    else
    {
      //print(anArray);
    }
    return smaller;
  }
 
  public void print()
  {
    System.out.print("Array: ");
    for (int i = 0; i < size; i++)
      if (tree[i] != null)
      System.out.print(tree[i].getNumber() + " ");
    System.out.println();
  }
 
  public static void main(String[] args)
  {
    int collection, first, group, number, numberOfInts, size;
 
    first = 4;
    size = 16;
    Tournament h = new Tournament(size);
    Scanner console = new Scanner(System.in);
    System.out.println("Enter number of ints to insert.");
    numberOfInts = console.nextInt();
 
    while(numberOfInts > 0)
    {
      while (first != 0)
      {
        first = first - 1;
        numberOfInts = numberOfInts - 1;
        System.out.println("Enter number to insert.");
        collection = console.nextInt();
        h.insert(collection);
      }
      numberOfInts = numberOfInts - 1;
      System.out.println("Enter number to insert.");
      number = console.nextInt();
      h.insert(number);
      h.print();
      //h.compare();
    }
  }
}
 
class Node
{
  private int info;
  private Node leftChild;
  private Node rightChild;
 
  public Node(int key)
  {
    info = key;
    leftChild = null;
    rightChild = null;
  }
 
  public int getNumber()
  {
    return info;
  }
 
  public Node getLeft()
  {
    return leftChild;
  }
 
  public Node getRight()
  {
    return rightChild;
  }
 
  public void setNumber(int number)
  {
    info = number;
  }
}   

[Christopher Beech]

Anybody got an idea how to get the min-winner??? I've been at it all night but I've haven't gotten it yet.

[Christopher Beech]

Wow. Almost no replies. I guess I should have known better than to expect help from an internet forum.

Thanks to the few that bother to help.

[Joanne Neal]

If a method is not doing what you expect, then you need to debug it. At the very least put some print statements in which will show you the path it is taking thru the code.

Once you know what it is doing, if you can't see why it is doing this, come back and ask. Show us the test data you're using and describe which route thru the code you expect it to take and which route it is actually taking.

You say you've been at it all night. Well, tell us what you've found during this time, so we don't have to repeat all your tests. Debugging is time consuming. The less people have to do to help you, the more likely it is you'll get help.