Implementing a Map in Java

Question

I'm currently working on an assignment that has me creating a Map class in Java, and I've run into an error while working with the 'put' method that I cannot seem to fix. Essentially, when the test is run, the new Node within the Map will not be created, and I cannot seem to figure out why. Thank you in advance!

Class:

public class MyMap<K extends Comparable<K>, V> {
private class MapNode {
    private K key;
    private V value;
    private MapNode left;
    private MapNode right;

    public MapNode(K theKey, V theValue) {
        key = theKey;
        value = theValue;
        left = null;
        right = null;
    }
}

private MapNode root;

public MyMap() {
    root = null;
}

/**
 * Associates key to value and stores mapping If key exists, replaces value
 * with a new value
 * 
 * @param key
 * @param value
 * @return value replaced; null if no value
 */

public V put(K key, V value) {
    return put(key, value, root);
}

private V put(K key, V value, MapNode ref) {
    V temp;
    if (ref == null) {
        ref = new MapNode(key, value);
        return null;
    } else {
        if (ref.key.compareTo(key) == 0) {
            temp = ref.value;
            ref.value = value;
            return temp;
        } else if (key.compareTo(ref.key) < 0)
            return put(key, value, ref.left);
        else
            return put(key, value, ref.right);
    }
}

/**
 * Return value to which key is mapped
 * 
 * @param key
 * @return value of key; null
 */

public V get(K key) {
    return get(key, root);
}

private V get(K key, MapNode ref) {
    if (ref == null) {
        return null;
    } else {
        if (ref.key.compareTo(key) == 0)
            return ref.value;
        else if (key.compareTo(ref.key) < 0)
            return get(key, ref.left);
        else if (key.compareTo(ref.key) > 0)
            return get(key, ref.right);
        else
            return null;
    }
}

/**
 * Returns true if Map already uses the key
 * 
 * @param key
 * @return true; false
 */

public boolean containsKey(K key) {
    return containsKey(key, root);
}

private boolean containsKey(K key, MapNode ref) {
    if (ref == null) {
        return false;
    } else {
        if (ref.key.compareTo(key) == 0)
            return true;
        else if (key.compareTo(ref.key) < 0)
            return containsKey(key, ref.left);
        else if (key.compareTo(ref.key) > 0)
            return containsKey(key, ref.right);
        else
            return false;
    }
}
}

Test:

import org.junit.Test;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class MyMapTest {
@Test
public void testMyMap(){
    MyMap<String, Integer> m = new MyMap<String, Integer>();

    assertFalse(m.containsKey("one"));
    assertEquals(null, m.get("one"));
    assertEquals(null, m.put("one", 1));
    assertTrue(m.containsKey("one"));
}
}

When you step through your code in a debugger what do you see? — Peter Lawrey
– Peter Lawrey, Commented Apr 19, 2012 at 20:15
Yes, a Binary tree that stores both a Key and a Value at each location. — Weasler
– Weasler, Commented Apr 19, 2012 at 20:16
When I step through the Debugger and into the creation of the new Node (ref = new MapNode(key, value); I get a Class Not Found error. — Weasler
– Weasler, Commented Apr 19, 2012 at 20:17

Sam DeHaan · Accepted Answer · 2012-04-19 20:17:34Z

2

Inside your put(K key, V value, MapNode ref) method, you assign a new MapNode to ref containing the node you want to add.

I see that you call that method by passing root. This stores the same reference as stored in root in ref. What this means, is that they would point to the same Object, if root were not null. However, as root is null, they both point to null.

When you assign ref = new MapNode(key, value);, you point ref to the new node, but root still points to null.

You need to point root to the new MapNode, pointing ref to it does not do it for you.

answered Apr 19, 2012 at 20:17

Sam DeHaan

10.4k2 gold badges42 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Weasler Over a year ago

Thank you very much, I'd vote you up if I could; very concise and well explained!

Peter Lawrey · Accepted Answer · 2012-04-19 20:17:50Z

0

The problem you have is that you don't change the root anywhere so you Map won't have anything in it. You are passing by value, not by reference so when you do ref = new MapNode() this changes you local variable, not the callers value.

answered Apr 19, 2012 at 20:17

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

Comments

Louis Wasserman · Accepted Answer · 2012-04-19 20:18:04Z

0

Your problem is that you're losing track of the fact that Java isn't pass-by-reference -- it passes references by value. When you say ref = new MapNode(...), you're not actually changing anything. You'll need to explicitly make the parent node point to the newly created node.

answered Apr 19, 2012 at 20:18

Louis Wasserman

200k26 gold badges367 silver badges437 bronze badges

Collectives™ on Stack Overflow

Implementing a Map in Java

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related