MoveToFrontDictionary.java

package edu.caltech.cs2.datastructures;

import edu.caltech.cs2.interfaces.ICollection;
import edu.caltech.cs2.interfaces.IDictionary;

import java.util.Iterator;

public class MoveToFrontDictionary<K, V> implements IDictionary<K,V> {
    //keep track global head <Node <K, V>
    //dictionary nodes have K key, V value
    //Node<K,V> next
    private Node<K, V> head;
    private int size;

    public MoveToFrontDictionary() {
        this.head = null;
        this.size = 0;
    }

    private static class Node<K, V> {
        public K key;
        public V value;
        public Node<K, V> next;

        public Node(K key, V value) {

            this(key, value, null);
        }

        public Node(K key, V value, Node<K, V> next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    @Override
    public V remove(K key) {
        //call get() on key
        //head = head.next
        if (this.head == null){
            return null;
        }
        if (!this.containsKey(key)){
            return null;
        }
        if (this.head.key.equals(key)){
            V value = this.head.value;
            this.head = this.head.next;
            this.size --;
            return value;
        }
        Node<K, V> current = this.head;
        Node<K, V> prev = null;
        while (current != null && !current.key.equals(key)){
            prev = current;
            current = current.next;
        }
        if (current == null) {
            return null;
        }
        prev.next = current.next;
        this.size--;
        return current.value;
    }

    @Override
    public V put(K key, V value) {
        //save head node as oldHead
        //Head = new Node(key, val)
        //head.next = old.head (???)
        V oldHead = this.remove(key);
        Node<K, V> node = new Node<K, V>(key, value);
        if (this.head != null){
            node.next = this.head;
        }
        this.head = node;
        this.size++;
        return oldHead;
    }

    @Override
    public boolean containsKey(K key) {
        return this.keys().contains(key);
    }

    @Override
    public boolean containsValue(V value) {
        return this.values().contains(value);
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public ICollection<K> keys() {
        ICollection<K> deq = new ArrayDeque<>();

        if (this.head == null) {
            return deq;
        }

        Node<K, V> current = this.head;

        while (current != null) {
            deq.add(current.key);

            current = current.next;
        }

        return deq;
    }

    @Override
    public ICollection<V> values() {

        ICollection<V> deq = new ArrayDeque<>();

        if (this.head == null){
            return deq;
        }
        Node<K, V> current = this.head;
        while (current != null) {
            deq.add(current.value);

            current = current.next;
        }

        return deq;

    }

    public V get(K key) {
        if (this.head == key){
            return this.head.value;
        }
        else {
            Node<K, V> curr = this.head;
            while (curr != null) {
                if (curr.key.equals(key)){
                    V val = curr.value;
                   /*
                   //rather than use put, directly change the pointers of the node being accessed
                   Node<K, V> nxtNode = curr.next;
                   nxtNode.next = this.head;
                   this.head = nxtNode;
                   //previous node
                   //create a new node at front of list with the node that is being accessed
                   */
                    this.put(key, val);
                    return val;
                }
                curr = curr.next;
            }
        }
        return null;
    }

    @Override
    public Iterator<K> iterator() {
        return new MoveToFrontIterator(this);
    }

    private class MoveToFrontIterator implements Iterator<K>{
        //take linkeddeque iterator
        private Node<K, V> currNode = null;

        public MoveToFrontIterator(MoveToFrontDictionary dict){
            this.currNode = dict.head;
        }

        @Override
        public boolean hasNext() {
            return this.currNode != null;
        }

        @Override
        public K next() {
            K element = currNode.key;
            this.currNode = currNode.next;
            return element;
        }
    }
}