Question

In: Computer Science

0. Introduction. This laboratory assignment involves implementing a data structure called a map. A map associates...

0. Introduction.

This laboratory assignment involves implementing a data structure called a map. A map associates objects called keys with other objects called values. It is implemented as a Java class that uses arrays internally.

1. Theory.

A map is a set of key-value pairs. Each key is said to be associated with its corresponding value, so there is at most one pair in the set with a given key. You can perform the following operations on maps.

  • You can test if a key has a value in the map.

  • You can add a new key-value pair to the map.

  • You can get the value that is associated with a given key.

  • You can change the value that is associated with a given key.

For example, the keys might be String’s that are the English words for numbers. The values might be Integer’s that are the numbers corresponding to those words. If you give the map an English word (like "ten") then you can get back its corresponding number (like 10).
      The maps for this assignment use arrays, and they work by doing linear search on those arrays. As a result, if a map has n pairs, then its operations may need at most O(n) key comparisons. However, there are better ways to implement maps, using data structures that we have not yet discussed in this course. These require only O(log n) or even O(1) key comparisons.

2. Implementation.

You must write a Java class called Map that implements a map. To simplify grading, your class must use the same names for things that are given here. Your class Map must have two generic class parameters, Key and Value, so it looks like this. Here Key is the type of the map’s keys, and Value is the type of the map’s values.

class Map<Key, Value>
{
  ⋮
}

Within the class Map, you must have two private arrays called keys and values. The array keys must be an array whose base type is the class parameter Key. The array values must be an array whose base type is the class parameter Value. Suppose that a key k is found at the index i in the array keys. Then the value associated with k is found at the same index i in the array values. Do not try to use only one array, because that will not work.
      You must also have a private integer variable called count that records how many elements of the arrays are being used. You may also need other private variables that are not mentioned here.
      Your class must have the following methods. Most of them use count, keys, and values somehow. Some methods are public and others are private. The private methods are helpers for the public methods; they may make your code easier to write. Also, any key may be null, and any value may be null. This will affect how you test if keys are equal.

public Map(int length)

Constructor. If length is less than 0 then you must throw an IllegalArgumentException. Otherwise, initialize an empty Map whose keys and values arrays have length elements. (Recall that you must make arrays of Object’s, then cast them to the appropriate types.)

public Value get(Key key)

Search the array keys for an element that is equal to key. If that element is at some index in keys, then return the element at the same index in the array values. If there is no element equal to key in keys, then throw an IllegalArgumentException.

private boolean isEqual(Key leftKey, Key rightKey)

Test if leftKey is equal to rightKey. Either or both may be null. This method is necessary because you must use == when leftKey or rightKey are null, but you must use the equals method when both are not null. (Recall that null has no methods.)

public boolean isIn(Key key)

Test if there is an element in keys that is equal to key.

public void put(Key key, Value value)

Search the array keys for an element that is equal to key. If that element is at some index in keys, then change the element at the same index in values to value. If there is no element in keys that is equal to key, then add key to keys, and add value at the same index in values. If keys and values are full, so you cannot add key and value, then throw an IllegalStateException.

private int where(Key key)

Search the array keys for an element that is equal to key. Return the index of that element. If there is no element equal to key in keys, then return −1.

When you compile your program, you may see the following ‘‘warning’’ messages from javac. Ignore them. As discussed in the lectures, these messages appear because Java does not implement class parameters (the names between < and >) correctly.

Note: your file name.java uses unchecked or unsafe operations.
Note: recompile with -Xlint:unchecked for details.

The file tests5.java on Canvas contains Java code that performs a series of tests, worth 40 points. Each test calls a public method from your class Map, and prints what the method returns. Each test is also followed by a comment that tells how many points it is worth, and what it must print if it works correctly. You may want to run additional tests, but you don’t get points for those.

Using this code: (test5.java)

class Hogwarts
{
//  MAIN. Make an instance of MAP and test it.

  public static void main(String [] args)
  {
    Map<String, String> map;

    try
    {
      map = new Map<String, String>(-5);
    }
    catch (IllegalArgumentException ignore)
    {
      System.out.println("No negatives");       //  No negatives  2 points.
    }

    map = new Map<String, String>(5);

    map.put("Harry",     "Ginny");
    map.put("Ron",       "Lavender");
    map.put("Voldemort", null);
    map.put(null,        "Wormtail");

    System.out.println(map.isIn("Harry"));      //  true          2 points.
    System.out.println(map.isIn("Ginny"));      //  false         2 points.
    System.out.println(map.isIn("Ron"));        //  true          2 points.
    System.out.println(map.isIn("Voldemort"));  //  true          2 points.
    System.out.println(map.isIn(null));         //  true          2 points.
    System.out.println(map.isIn("Joanne"));     //  false         2 points.

    System.out.println(map.get("Harry"));       //  Ginny         2 points.
    System.out.println(map.get("Ron"));         //  Lavender      2 points.
    System.out.println(map.get("Voldemort"));   //  null          2 points.
    System.out.println(map.get(null));          //  Wormtail      2 points.

    try
    {
      System.out.println(map.get("Joanne"));
    }
    catch (IllegalArgumentException ignore)
    {
      System.out.println("No Joanne");          //  No Joanne     2 points.
    }

    map.put("Ron",   "Hermione");
    map.put("Albus", "Gellert");
    map.put(null,    null);

    System.out.println(map.isIn(null));         //  true          2 points.
    System.out.println(map.isIn("Albus"));      //  true          2 points.

    System.out.println(map.get("Albus"));       //  Gellert       2 points.
    System.out.println(map.get("Harry"));       //  Ginny         2 points.
    System.out.println(map.get("Ron"));         //  Hermione      2 points.
    System.out.println(map.get("Voldemort"));   //  null          2 points.
    System.out.println(map.get(null));          //  null          2 points.

    try
    {
      map.put("Draco", "Pansy"); 
    }
    catch (IllegalStateException minnesota)
    {
      System.out.println("No Draco");           //  No Draco      2 points.
    }
  }
}

Solutions

Expert Solution

## here is the class map with my output , follow comments for better explanation.

MAP CLASS :

import java.lang.reflect.Array;

public class Map<Key,Value> {
   //arrays for kes and values of type Key and Value which will be given by main method
   Key keys[];
   Value values[];
   int count;
  
   public Map(int length) {
       if(length < 0)//when length is less 0 then throwing an exception
           throw new IllegalArgumentException(); //here we are initializing default java exception and directly throwing it
       else {
           keys = (Key[])new Object[length];
           values = (Value[])new Object[length];
           count = 0;
       }
   }
  
   //using this method we can compare two Key value whather its equal or not
   private boolean isEqual(Key leftKey, Key rightKey) {
       if(null == leftKey || null == rightKey) {//here if one of the value is null we can't use equals it wil throw null pointer so we just compare it.
           return leftKey == rightKey;
       }else {
           return leftKey.equals(rightKey);
       }
   }
  
   //In this method we can get whether the given key is in our map or not
   private int where(Key key) {
       for(int i=0;i<keys.length;i++) {
           if(isEqual(keys[i], key)) {//here isEquals method will help to compare two keys.
               return i;
           }
       }
       return -1;
   }
  
   public Value get(Key key)
   {
       int index = where(key);//here we can decide whether we have given key in our map usin where method.
       if(-1 != index) return values[index];// if its not -1 then key is present in the map
       throw new IllegalArgumentException();
   }
  
  
  
   public boolean isIn(Key key) {
       int index = where(key);//again same using where we can decide given key is present or not
       if(-1 != index) return true;
       return false;
   }
  
   public void put(Key key, Value value) {
      
       int index = where(key);
       if(-1 != index) values[index] = value;// if key is present we will change the value
       else{
           if(count == keys.length) throw new IllegalStateException();// or else we will check that count is same as length if equals meaning map is full
           else {
               keys[count] = key;//otherwise we will add elements in array and increment the count
               values[count] = value;
               count++;
           }
       }
   }
  

}

OUTPUT


Related Solutions

This laboratory assignment involves implementing a data structure called a map. A map associates objects called...
This laboratory assignment involves implementing a data structure called a map. A map associates objects called keys with other objects called values. It is implemented as a Java class that uses arrays internally. 1. Theory. A map is a set of key-value pairs. Each key is said to be associated with its corresponding value, so there is at most one pair in the set with a given key. You can perform the following operations on maps. You can test if...
Assignment #2 (JAVA) In assignment 1 you had used the data structure called Stack to evaluate...
Assignment #2 (JAVA) In assignment 1 you had used the data structure called Stack to evaluate arithmetic expressions by first converting the given infixed expressions to postfixed expressions, and then evaluated the post fixed expression. Repeat the exercise for this assignment (assignment 2) by using the data structure called Binary Trees. Your output must display the original expression, the postfixed expression representing the Binary tree, and the evaluated result. Please bear in mind that a given expression could result in...
In assignment 1 you had used the data structure called Stack to evaluate arithmetic expressions by...
In assignment 1 you had used the data structure called Stack to evaluate arithmetic expressions by first converting the given infixed expressions to postfixed expressions, and then evaluated the post fixed expression. Repeat the exercise for this assignment (assignment 2) by using the data structure called Binary Trees. Your output must display the original expression, the postfixed expression representing the Binary tree, and the evaluated result. Please bear in mind that a given expression could result in one of the...
In assignment 1 you had used the data structure called Stack to evaluate arithmetic expressions by...
In assignment 1 you had used the data structure called Stack to evaluate arithmetic expressions by first converting the given infixed expressions to postfixed expressions, and then evaluated the post fixed expression. Repeat the exercise for this assignment (assignment 2) by using the data structure called Binary Trees. Your output must display the original expression, the postfixed expression representing the Binary tree, and the evaluated result. Please bear in mind that a given expression could result in one of the...
0. Introduction. In this assignment you will implement a stack as a Java class, using a...
0. Introduction. In this assignment you will implement a stack as a Java class, using a linked list of nodes. Unlike the stack discussed in the lectures, however, your stack will be designed to efficiently handle repeated pushes of the same element. This shows that there are often many different ways to design the same data structure, and that a data structure should be designed for an anticipated pattern of use. 1. Theory. The most obvious way to represent a...
Essay Assignment Based on the assigned reading article, generate an essay paper following this structure Introduction...
Essay Assignment Based on the assigned reading article, generate an essay paper following this structure Introduction Define the consumer behavior science and talk briefly about the four major contexts that impact consumer behavior under the Covid -19 pandemic. Discussion Answer the following without including the questions in the essay How these contexts apply to yourself or your household consumption behavior since the beginning of the pandemic? Briefly explain the eight immediate effects of Covid-19 pandemic. Which of the eight effect...
In this programming project, you will be implementing the data structure min-heap. You should use the...
In this programming project, you will be implementing the data structure min-heap. You should use the C++ programming language, not any other programming language. Also, your program should be based on the g++ compiler on general.asu.edu. All programs will be compiled and graded on general.asu.edu, a Linux based machine. If you program does not work on that machine, you will receive no credit for this assignment. You will need to submit it electronically at the blackboard, in one zip file,...
In this assignment you are to utilize the Node data structure provided on Blackboard. In this...
In this assignment you are to utilize the Node data structure provided on Blackboard. In this assignment you are to write a main program that implements two methods and a main method as their driver. So, only main and two methods with it. Implementation Details: Method 1: ^^^^^^^^^ Parameters and return type: Takes as parameters an array of integers, the size of the array of integer (.length is acceptable also) and it should return a Node that is supposed to...
In this assignment you are to utilize the Node data structure provided on Blackboard. In this...
In this assignment you are to utilize the Node data structure provided on Blackboard. In this assignment you are to write a main program that implements two methods and a main method as their driver. So, only main and two methods with it. Implementation Details: Method 1: ^^^^^^^^^ Parameters and return type: Takes as parameters an array of integers, the size of the array of integer (.length is acceptable also) and it should return a Node that is supposed to...
Designing and implementing a C++ structure data type - Monthly Budget Remember to use correct code...
Designing and implementing a C++ structure data type - Monthly Budget Remember to use correct code formatting and documentation. A student has established the following monthly budget: Budget Categories       Budgeted amount ----------------------------------------------------- Housing                  $ 580.00 Utilities                   $ 150.00 Household Expenses    $ 65.00 Transportation           $ 50.00 Food                      $ 250.00 Medical                  $ 30.00 Insurance                $ 100.00 Entertainment           $ 150.00 Clothing                  $ 75.00 Miscellaneous           $ 50.00 ---------------------------------------------------- Write a program that declares a MonthlyBudget structure designed with member variables to hold each of these expense categories. The program should define two MonthlyBudget structure variables...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT