CODEWITHSUNDEEP
javavariable-assignment
Weasler
Weasler

Reputation: 247

Implementing a Map in Java

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"));
}
}

Upvotes: 1

Views: 234

Answers (3)

Louis Wasserman
Louis Wasserman

Reputation: 198221

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.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533680

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.

Upvotes: 0

Sam DeHaan
Sam DeHaan

Reputation: 10325

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.

Upvotes: 2

Related Questions