[ACE] Maps

ADT: Maps

A map models a collection of key-value entries that is searchable ‘by the key’.

Multiple entries with the same key are not allowed.

Map ADT over Key and Value

The difference between Map and Priority Queue

Both insert entries based on a key but:

• Map: can access any key using “get(K k)”
• PQ: access only the minimum key using “RemoveMin()”

Implement Map

We can implement a map using an doubly-linked list. Every Node in the linked list is a K,V pair.

So first, we need to implement doubly-linked list

What we have in doubly linked list?

• We need a new class node to represent every element
• We also need a header and a trailer, header is previous to the first node and trailer is after the last node
• Because it is a doubly linked list, the node should linked with previous node and next node
  Ok, let’s started to build doublylinked list

Here, we define the bullet point above, then we need to specify the operations.

So what operations to perform?

We need a getNode() to get the node on some index.

There must be insert(), which insert element to some index, this will takes us O(n) time
If we have insert, we also can insert element to the first or last, which just takes us O(1) time

Also, delete is similar.

And we need a print() or iterator the whole linkedlist to prove its correctness.

Then we need to do actual map

First thing, and the most important thing we need to consider is the generic.
We have generic in DLL, here the generic should be the Entry(I write my own entry called MyEntry, but it is the similar with Maps.Entry)

so, what we actually store in Map is DLL, then we need to make it as the member variable.

The other operation is based on this DLL

get

    @Override
    public V get(K k) {
        for(int i = 0; i < size(); i++){
            if(dll.getNode(i).getElement().getKey().equals(k)){
                return dll.getNode(i).getElement().getValue();
            }
        }
        return null;
    }

put

    @Override
    public V put(K k, V v) {
        if(get(k)==null){
            dll.addLast(new MyEntry<K,V>(k, v));
            return null;
        }else{
            V temp = get(k);
            dll.addLast(new MyEntry<K,V>(k, v));
            return temp;
        }
    }

remove

    @Override
    public V remove(K k) {
        for(int i = 0; i < size(); i++){
            if(dll.getNode(i).getElement().getKey().equals(k)){
                dll.delete(i);
            }
        }
        return null;
    }

Keys

    @Override
    public Set<K> Keys() {
        Set<K> set = new HashSet<K>();
        for(int i = 0; i < size(); i++){
            set.add(dll.getNode(i).getElement().getKey());
        }
        return set;
    }

A little test about map