CODEWITHSUNDEEP
javasymbol-table
yenyen
yenyen

Reputation: 35

Rank for symbol table

How would I return the number of keys that is less than the given key? I just don't know where to start. I have the base start but other than that I dont know where to begin

public class LinkedListST<Key extends Comparable<Key>, Value> {
    private Node first;      // the linked list of key-value pairs

    // a helper linked list data type
    private class Node {
        private Key key;
        private Value val;
        private Node next;

        public Node(Key key, Value val, Node next)  {
            this.key  = key;
            this.val  = val;
            this.next = next;
        }
    }

public int rank (Key key) {
        if(key == null) return 0;
        //TODO
    }

EDIT: This is what I have so far but my for loop is wrong and is giving me errors

public int rank (Key key) {
    int count = 0;
    for(Node x = first; x != null; x = x.next){
        if(x.next < key){
            count++;
        }
    return count;
    }
}

Upvotes: 0

Views: 948

Answers (2)

AJNeufeld
AJNeufeld

Reputation: 8695

Pseudo code:

initialize counter to zero
loop over all nodes, starting at first:
   if node's key < key:
       increment count
return count

That should get you started.

EDIT

Ok, so you've actually posted a real attempt at writing the code, which is the secret to getting real help on Stack Overflow.

Your code, with proper indentation, ...

public int rank (Key key) {
    int count = 0;
    for(Node x = first; x != null; x = x.next){
        if (x.next < key){
            count++;
        }
        return count;  // <-- Note!
    }
}

... shows a return statement inside the loop. Not exactly what you wanted.

The if (x.next < key) is also giving you grief, because you need to compare Key with Key, not Node with Key.

Finally, the Comparable interface requires the the Key to implement the compareTo(Key other) method. Used like:

key.compareTo(x.key)

This returns a -1, 0, or 1 depending on which is larger or if they are the same. So you really want:

if (key.compareTo(x.key) < 0) {

or

if (key.compareTo(x.key) > 0) {

Exercise left to student.

Upvotes: 0

Andreas
Andreas

Reputation: 159165

Your code is almost there, but you have three issues:

  • The return statement is inside the for loop. If you corrected the indentation, you'd see that. Move it outside.
  • You don't want to compare x.next to key. You want to compare x.key to the key parameter.
  • You cannot compare using the < operator. Since Key is Comparable, you can compare by calling compareTo().

Here is the updated code:

public int rank (Key key) {
    int count = 0;
    for (Node x = first; x != null; x = x.next) {
        if (x.key.compareTo(key) < 0){
            count++;
        }
    }
    return count;
}

Upvotes: 1

Related Questions