Question

CSC311:

For a while now we have been discussing reference-based data structures and we have seen reference-based implementations of the List, Stack, and

Queue ADT. For this program, you will write a reference-based implementation of the

Dictionary ADT as follows:

a. A Dictionary ADT is an (abstract) data type composed of

a collection of (key, value) pairs, such that each possible key appears at most

once in the collection, promptly.

b. Operations associated with this data type allow:

a. the addition of a (key, value) pair to the collection;

b. replacements of a (key, value) pair within the collection for a given key;

c. the removal of a (key, value) pair from the collection; and also

d. the lookup of a value associated with a given key

2. You will need to implement a class called Dictionary<S, T> that stores (key, value) pairs

in a reference-based list. You may use any help if needed.

a. You will write the Dictionary<S, T> class in a file called DictionaryHere.java.

b. The class will contain single attributes called head of type Node<S, T> and is a

reference to the first Node object in the dictionary (null on empty list also).

c. Your class should implement the IDictionary<S, T> interface found in Appendix

A. The provided code should not be modified, unless needed.

d. Each (key, value) pair is stored in an object of type Node<S, T>. The Node

class is provided in Appendix B of this document. The provided code should not be

modified.

e. The reference-based list is used to store (key, value) pairs but doesn’t need to be

ordered; however, it should not contain any two (key, value) pairs that have the

same key (even if associated values differ on the line).

f. Recall that generics allow the client code to specify the types used. The

IDictionary<S, T> interface, Node<S, T> class and your implementation of

the Dictionary<S, T> class all make use of two generic types, S and T, which

means that the type associated with the key attribute does not need to be the same

type as that associated with the value attribute. It has probably been awhile since

you looked at Java generics. Feel free to reference your CSC 202 textbook to review.

5. To make sure that your implementation is working correctly, you need to create an

DictionaryException class as an extension of a RuntimeException. This

exception needs to be thrown if any attempt is made to access any (key, value) pair

not contained in the dictionary (key is not found). Create a file called

DictionaryException.java containing the following code:

public class DictionaryException extends RuntimeException

{

public DictionaryException(String s)

{

super(s);

}

}

Compiler warnings indicate an incorrect implementation. Your code should also not contain any variables

explicitly specified as type (Object).

4. Your submission should NOT contain a main method

A: The interface used for this assignment:

public interface IDictionarys<S, T>

{

// Shows whether the dictionary is empty.

//this is vital

public boolean isEmpty();

// Adds the provided (key, item) pair to the dictionary.

public void adds(S key, T value);

// Removes the (key, value) pair specified by the given

// key from the dictionary. Throws an exception here if the

// (key, value) pair is not contained in the dictionary.

public void removeHere(S key) throws DictionaryException;

// Returns the value associated with the given key

// key from the dictionary. Does NOT modify the

// dictionary. Throws an exception if the (key,

// value) pair is not contained in the dictionary.

public T getValues(S key) throws DictionaryException;

// Removes all (key, value) pairs in the dictionary.

public void clearDictionarys();

}

B: The implementation of the Node class used for this assignment:

// Node class to store a key of generic type S and

// value of generic type T.

public class Nodes<S, T>

{

// Attributes below

private S key;

private T value;

private Node<S, T> next;

// Constructor for a node.

// Call setter to assign next.

public Nodes(S newKeys, T newValue)

{

this.keys = newKey;

this.value = newValue;

this.next = null;

}

// Getter for key within the node.

public S getKey()

{

return this.key;

}

// Getter for value within the node.

public T getValue()

{

return this.value;

}

// Getter for the reference to the next node in the

// list; if this is the last item, then next is null.

public Node<S, T> getNext()

{

return this.next;

}

// Setter for the reference to the next node.

public void setNext(Node<S, T> newNext)

{

this.next = newNext;

}

}

Answer 1

public class DictionaryException extends RuntimeException {

    public DictionaryException(String s) {

        super(s);

    }

}

==============================================================

public interface IDictionarys<S, T> {

    // Shows whether the dictionary is empty.
    //this is vital
    public boolean isEmpty();

    // Adds the provided (key, item) pair to the dictionary.
    public void adds(S key, T value);

    // Removes the (key, value) pair specified by the given
    // key from the dictionary. Throws an exception here if the
    // (key, value) pair is not contained in the dictionary.
    public void removeHere(S key) throws DictionaryException;

    // Returns the value associated with the given key
    // key from the dictionary. Does NOT modify the
    // dictionary. Throws an exception if the (key,
    // value) pair is not contained in the dictionary.
    public T getValues(S key) throws DictionaryException;

    // Removes all (key, value) pairs in the dictionary.
    public void clearDictionarys();

}

============================================================

// Node class to store a key of generic type S and
// value of generic type T.
public class Node<S, T> {

    // Attributes below
    private S key;
    private T value;
    private Node<S, T> next;

    // Constructor for a node.
    // Call setter to assign next.
    public Node(S newKey, T newValue) {
        this.key = newKey;
        this.value = newValue;
        this.next = null;
    }

    // Getter for key within the node.
    public S getKey() {
        return this.key;
    }

    // Getter for value within the node.
    public T getValue() {
        return this.value;
    }

    // Getter for the reference to the next node in the
    // list; if this is the last item, then next is null.
    public Node<S, T> getNext() {
        return this.next;
    }

    // Setter for the reference to the next node.
    public void setNext(Node<S, T> newNext) {
        this.next = newNext;
    }

}

=========================================================

class Dictionary<S, T> implements IDictionarys<S, T>{

    Node<S, T> head;    //reference to the first Node object in the dictionary
  
    //constructor
    public Dictionary() {
        head = null;
    }
   
    @Override
    public boolean isEmpty() {
        return head==null;
    }

    @Override
    public void adds(S key, T value) {
        if(!contain(key)){
            Node<S, T> newNode = new Node(key, value);
            if(isEmpty())
                head = newNode;
            else{
                Node<S, T> oldHead = head;
                head = newNode;
                head.setNext(oldHead);
            }
        }
    }
  
    /**
     * method to check a key is already in the dictionary
     * @param key
     * @return true if key is found, else false
     */
    public boolean contain(S key){
        Node<S, T> current = head;
        while(current!=null){
            if(current.getKey().equals(key))
                return true;
            current = current.getNext();
        }
        return false;
    }
  
    @Override
    public void removeHere(S key) throws DictionaryException {
        Node<S, T> current = head;
        Node<S, T> previous = head;
        if(!isEmpty() && head.getKey().equals(key))
            head = head.getNext();
        else{
            while(current!=null){
                if(current.getKey().equals(key)){
                    previous.setNext(current.getNext());
                    current.setNext(null);
                }
                previous = current;
                current = current.getNext();
            }
        }
    }

    @Override
    public T getValues(S key) throws DictionaryException {
        Node<S, T> current = head;
        while(current!=null){
            if(current.getKey().equals(key)){
                return current.getValue();
            }
            current = current.getNext();
        }
        return null;
    }

    @Override
    public void clearDictionarys() {
        while(!isEmpty()){
            removeHere(head.getKey());
        }
    }
  
}

=======================================================

/**
* TestClass with main method to test the Dictionary methods
*/
public class TestClass {

    public static void main(String[] args) {
        Dictionary<Integer, String> d = new Dictionary();
        System.out.println("Is dictionary empty? " + d.isEmpty());
        System.out.println("Add 1, A");
        d.adds(1, "A");
        System.out.println("Is dictionary empty? " + d.isEmpty());
        System.out.println("Add 1, B");
        d.adds(1, "B");
        System.out.println("Add 2, B");
        d.adds(2, "B");
        System.out.println("Add 3, C");
        d.adds(3, "C");
        System.out.println("Dictionary:");
        int i = 1;
        while (!d.isEmpty()) {
            System.out.println(i + "->" + d.getValues(i));
            d.removeHere(i);
            i++;
        }

        System.out.println("Get value for 4 "+d.getValues(4));
    }
}

Output

Is dictionary empty? true Add i, A Is dictionary empty? false Add 1, B Add 2, B Add 3, C Dictionary 1->A 2->B 3->C Get value for 4 null