Question

write program that develop a Java class Dictionary to support the following public methods of an abstract data type:

public class Dictionary {

// insert a (key, value) pair into the Dictionary, key value must be unique, the value is associated with the key; only the last value inserted for a key will be kept public void insert(String key, String value);

// return the value associated with the key value public String lookup(String key);

// delete the (key, value) pair public void delete (String key);

}

You will declare a class Pair to represent the (key, value) pair, and use an array of the Pair objects to keep the values in the dictionary. Your array of Pair objects should be able to be sorted by java.util.Arrays.sort(). You can decide whether to store the Pair values in the array sorted or not according to the key values.

Write the main() method to create an instance of the Dictionary object, insert 50 random (key, value) pairs, update some values behind the same key, and delete some (key, value) pairs.

2. Rewrite Your class Dictionary so it can support values of any data type, and show that it works with different value data types.

3. Discuss advantages and disadvantages for storing the Pair objects sorted or not in the Dictionary class.

4. What is running time for each method of your Dictionary class in terms of Big-O notation?

5. Trace method heapSort(T[] w) with sequence of diagrams with both heap tree view and 1-D array view how to sort integers 8, 4, 1, 2, 5, 3, 10, 7, 5, 9, 1, 12, and 5.

Answer 1

import java.util.ArrayList;

public class Dictionary {
    ArrayList<Pair> dict = new ArrayList<>();

    public String key,value;

    // ArrayList<String> keysInt = new ArrayList<String>();
    // ArrayList<String> valuesInt = new ArrayList<String>();

    void insert(String key, String value){
        this.dict.add(new Pair(key, value));

        this.key = key;
        this.value = value;
    }
    void insert(int key, int value){
        this.dict.add(new Pair(key, value));
    }
  
    void insert(double key, double value){
        this.dict.add(new Pair(key, value));
    }

    public String lookup(String key){
        for( int i =0; i < this.dict.size(); i++){
            if (dict.get(i).keyString.equals(key))
                return dict.get(i).valueString;
        }
        return "Key Pair Not Found!!";
    }
    public int lookup(int key){
        for (int i =0; i < this.dict.size(); i++){
            if(dict.get(i).keyInt == key){
                return dict.get(i).valueInt;
            }
        }
        return -1;
    }

    public double lookup(double key){
        for (int i =0; i < this.dict.size(); i++){
            if(dict.get(i).keyDouble == key){
                return dict.get(i).valueDouble;
            }
        }
        return -1;
    }
    public void detele(String key){
        int counter = 0;
        for (int i = 0; i < this.dict.size(); i++){
            if (this.dict.get(i).keyString.equals(key)){
                this.dict.remove(i);
                counter++;
            }
        }

        if (counter == 0) System.out.println("Key Pair not found!!");
    }
}

import java.util.Comparator;

public class Pair {
    String keyString;
    String valueString;

    int keyInt;
    int valueInt;

    double keyDouble, valueDouble;

    public Pair(String key, String value){
        this.keyString = key;
        this.valueString = value;
    }

    public Pair(int key, int value){
        this.keyInt = key;
        this.valueInt = value;
    }

    public Pair(double key, double value){
        this.keyDouble = key;
        this.valueDouble = value;
    }

    public double getkeyDouble(){
        return this.keyDouble;
    }

    public double getValueDouble(){
        return this.valueDouble;
    }

    public void setKeyDouble(double key){
        this.keyDouble = key;
    }
    public void setValueDouble(double value){
        this.valueDouble = value;
    }
    public String getKey(){
        return this.keyString;
    }
    public String getValue(){
        return this.valueString;
    }

    public void setKey(String key) {
        this.keyString = key;
    }

    public void setValue(String value) {
        this.valueString = value;
    }

    public int getKeyInt(){
        return this.keyInt;
    }
    public int getValueInt(){
        return this.valueInt;
    }

    public void setKeyInt(int keyInt){
        this.keyInt = keyInt;
    }

    public void setValueInt(int valueInt){
        this.valueInt = valueInt;
    }

    public double compareToDouble(Pair pair){
        double key;
        key = ((Pair)pair).getkeyDouble();
        return this.keyDouble - key;
    }

    public int compareToInt(Pair pair){
        int key;
        key = ((Pair)pair).getKeyInt();
        return this.keyInt - key;
    }
    public static Comparator<Pair> keyComp = new Comparator<Pair>() {
        @Override
        public int compare(Pair o1, Pair o2) {

            String key1 = o1.keyString.toUpperCase();
            String key2 = o2.keyString.toUpperCase();

            return key1.compareTo(key2);
        }
    };

}

import java.util.Random;
public class Main {

    public static void main(){
        Dictionary dict = new Dictionary();
        for (int i = 0; i < 50; i++){
            Random rand = new Random();
            String key = " " + rand.nextInt() ;
            String value = " " + rand.nextInt();
            dict.insert(key, value);
        }

    }
}