Splay trees and compareTo

Three questions. 1 and 3 should be very simple, and that's why i am not breaking them up into three q's.

//QUESTION 1 (Line marked below)
I get this error:
The method compareTo(Object) is undefined for the type Object

why? _root.getKey returns the key value in the root (type TreeNode), which is type Object, the same as key, and the value that compareTo expects.

//QUESTION 2 (Line marked below)
I have a splay method which must have the contract splay(TreeNode t), not splay(Object t).  So, assuming the TreeNode with the _key value == key, how do I get this TreeNode so that I can pass it to the splay method? As I am writing this, I realize I have also created a find(Object key) method which looks like this:
        public Object find(Object key){
            if (_root == null) return null;
            splay(key);
              if(_root.getKey().compareTo(key) != 0) return null;
              return _root.getKey();
      }
but I am unable to make the mental connection as to how I might use find (if possible) to get a TreeNode existing in my splayTree that I could pass to my splay(TreeNode t) method.  Suggestions??


//QUESTION 3
What does this mean as a for loop?
for (;;){//THIS LINE
//Loop contents here
}

The Code:

      public Object remove(Object key){
            TreeNode x;
            splay(key);                   //QUESTION 2
            if (key.compareTo(_root.getKey()) == 0) {   //QUESTION 1
            // Now delete the root
            if (_root.getLeft() == null) {
                _root = _root.getRight();
            } else {
                x = _root.getRight();
                _root = _root.getLeft();
                splay(key);                  //QUESTION 2
                _root.setRight(x);
            }
            }
      }
LVL 9
D4LyAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

objectsCommented:
compareTo() is a method of Comparable, *not* Object.
The object needs to be an instance of Comparable.
0
D4LyAuthor Commented:
This does not work.  I am assuming this is what you were telling me to do.

                Comparable cKey = (Comparable)key;
            Comparable tKey = (Comparable) _root.getKey();
            if ((c = key.compareTo(tKey)) == 0) {      
                  _root.setItem(item);
                return;
            }
0
objectsCommented:
Does the key implement Comparable?
How exactly is it not working?
0
Cloud Class® Course: MCSA MCSE Windows Server 2012

This course teaches how to install and configure Windows Server 2012 R2.  It is the first step on your path to becoming a Microsoft Certified Solutions Expert (MCSE).

D4LyAuthor Commented:
my bad.
0
D4LyAuthor Commented:
I forgot to replace key.comareTo with cKey.compareTo

spoke to soon.
0
D4LyAuthor Commented:
tips on 2 or 3?
0
objectsCommented:
> for (;;){//THIS LINE
> //Loop contents here
> }

same as:

while (true) {
//Loop contents here
}
0
objectsCommented:
What class is _root?
0
D4LyAuthor Commented:
excelent. thanks very much

one left!!
0
D4LyAuthor Commented:
wait...while WHAT is true?
0
D4LyAuthor Commented:
_root is class TreeNode
0
D4LyAuthor Commented:
and out of curiosity, what program do you edit your Java with?
0
objectsCommented:
> wait...while WHAT is true?

while 'true' is true :)
ie. loop forever
0
D4LyAuthor Commented:
ah, hence the break; statements inside this mock while loop.
0
objectsCommented:
public TreeNode getNode(Object key)
{
   return getNode(_root, key);
}

public TreeNode getNode(TreeNode parent, Object key)
{
   TreeNode result = null;
   // compare parent with key for a match
   // if is the required node then do:
   if (match)
   {
     result = parent;
   }
   else
   {
     Enumeration i = parent.children();
     while (result==null && i.hasMoreElements())
     {
        TreeNode child = (TreeNode) i.nextElement();
        result = getNode(child, key);
     }
   }
   return result;
}
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
D4LyAuthor Commented:
so when i want to call splay, i will now splay(getNode(key));, correct?

Can you explain what type Enumeration is? and where children comes from?
0
objectsCommented:
Yes, Enumeration is an interface from java.util package
children() is a method of TreeNode.
0
D4LyAuthor Commented:
I've created my own TreeNode class....which doesnt contain a children() method....must I include java.util.*?

I do have a method that I could possibly use instead of the enumeration that traverses a tree...let me check.
0
D4LyAuthor Commented:
I could possibly manipulate this computeSize class to traverse the tree searching, instead of increasing the count:

children() here comes from an iterator interface.

public class ComputeSize {
      int i;
      
      public ComputeSize(){
            i = 0;
      }
      
      private int doIt(Tree t,Position root) {
      if (t.isExternal(root))
            i=i+1;
      else {
            i=i+1;

            Iterator it = t.children(root);
            while(it.more()) {
                  Position kid = (Position)it.get();
                  doIt(t,kid);
                  it.next();
            }
            }
            return i;
      }
      public int doIt(Tree t) {
            return doIt(t,t.root());
      }
}
0
objectsCommented:
> which doesnt contain a children() method

ok then you need to whatever methods it provides to loop thru all the child nodes.
0
D4LyAuthor Commented:
Thanks very much for all your help.

What program do you use to edit your Java code?
0
objectsCommented:
used to use ultraedit, but have been trialling jedit more recently.
0
D4LyAuthor Commented:
what are your thoughts on eclipse?
0
objectsCommented:
Have never actually used it, but would like to find the time.
0
D4LyAuthor Commented:
objects, because I have a splay tree, I could use this logic I think, to find my node:

say I have this tree:
i want to splay 5 in this tree, I simply grab
my root, compare if 5 is greater (YES), now move to the right, test greater
again (YES), move right, test (NO), move left, test (NO), move left, and now
return my node? just trying to think out loud...this seems about
right. Let me know, and thanks for your help.

       3
      /  \
    2    4
  /         \
1           7
            /  \
          6    8
         /        \
       5          10
                  /
                9
0
objectsCommented:
yes that sounds correct.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.