Write a program called ComputeARR to compute the average rating a restaurant is currently getting. The ratings are in sequences of stars, from 0 to 8. Write the program so that it:

Declares and creates a symbol table using the algs31.BinarySearchST class;

Fills that symbol table with the following key-value pairs:

Key	Value
********	4
*******	3.5
******	3
*****	2.5
****	2
***	1.5
**	1
*	0.5

Reads a sequence of star ratings from a file called a1ratings.txt using StdIn where the ratings are separated from each other by one or more whitespace characters. Read these ratings by directing StdIn to the file with the fromFile method and then, to make reading in the strings easier, there is a method called StdIn.readAllStrings() that returns an array of Strings that automatically reads in all of the strings and divides them properly.

Iterates through the array just filled using a for-each loop and accumulates a total score based on the ratings. For each rating, look up its value in the symbol table and add it to the accumulator variable.

Computes and prints the average value.

Create your own test file called a1ratings.txt and place it in the data directory. Remember that your program will open it using the pathname data/a1grades.txt. Do not submit your test file.

PLEASE NOTE: Do not copy any code from the algs31.BinarySearchST class. You will have a single line in your program that declares and creates an empty symbol table and then you will need to call the instance methods put and get.

// Exercise 3.1.16 3.1.17 3.1.30 (Solution published at http://algs4.cs.princeton.edu/)

package algs31;

import stdlib.*;

import algs13.Queue;

/* ***********************************************************************

* Compilation: javac BinarySearchST.java

* Execution: java BinarySearchST

* Dependencies: StdIn.java StdOut.java

* Data files: http://algs4.cs.princeton.edu/31elementary/tinyST.txt

*

* Symbol table implementation with binary search in an ordered array.

*

* % more tinyST.txt

* S E A R C H E X A M P L E

*

* % java BinarySearchST < tinyST.txt

* A 8

* C 4

* E 12

* H 5

* L 11

* M 9

* P 10

* R 3

* S 0

* X 7

*

*************************************************************************/

public class BinarySearchST, V> {

private static final int INIT_CAPACITY = 2;

private K[] keys;

private V[] vals;

private int N = 0;

// create an empty symbol table with default initial capacity

public BinarySearchST() { this(INIT_CAPACITY); }

// create an empty symbol table with given initial capacity

@SuppressWarnings("unchecked")

public BinarySearchST(int capacity) {

keys = (K[]) new Comparable[capacity];

vals = (V[]) new Object[capacity];

}

// resize the underlying arrays

@SuppressWarnings("unchecked")

private void resize(int capacity) {

if (capacity <= N) throw new IllegalArgumentException ();

K[] tempk = (K[]) new Comparable[capacity];

V[] tempv = (V[]) new Object[capacity];

for (int i = 0; i < N; i++) {

tempk[i] = keys[i];

tempv[i] = vals[i];

}

vals = tempv;

keys = tempk;

}

// is the key in the table?

public boolean contains(K key) { return get(key) != null; }

// number of key-value pairs in the table

public int size() { return N; }

// is the symbol table empty?

public boolean isEmpty() { return size() == 0; }

// return the value associated with the given key, or null if no such key

public V get(K key) {

if (isEmpty()) return null;

int i = rank(key);

if (i < N && keys[i].compareTo(key) == 0) return vals[i];

return null;

}

// return the number of keys in the table that are smaller than given key

public int rank(K key) {

int lo = 0, hi = N-1;

while (lo <= hi) {

int m = lo + (hi - lo) / 2;

int cmp = key.compareTo(keys[m]);

if (cmp < 0) hi = m - 1;

else if (cmp > 0) lo = m + 1;

else return m;

}

return lo;

}

// Search for key. Update value if found; grow table if new.

public void put(K key, V val) {

if (val == null) { delete(key); return; }

int i = rank(key);

// key is already in table

if (i < N && keys[i].compareTo(key) == 0) {

vals[i] = val;

return;

}

// insert new key-value pair

if (N == keys.length) resize(2*keys.length);

for (int j = N; j > i; j--) {

keys[j] = keys[j-1];

vals[j] = vals[j-1];

}

keys[i] = key;

vals[i] = val;

N++;

//assert check();

}

// Remove the key-value pair if present

public void delete(K key) {

if (isEmpty()) return;

// compute rank

int i = rank(key);

// key not in table

if (i == N || keys[i].compareTo(key) != 0) {

return;

}

for (int j = i; j < N-1; j++) {

keys[j] = keys[j+1];

vals[j] = vals[j+1];

}

N--;

keys[N] = null; // to avoid loitering

vals[N] = null;

// resize if 1/4 full

if (N > 0 && N == keys.length/4) resize(keys.length/2);

//assert check();

}

// delete the minimum key and its associated value

public void deleteMin() {

if (isEmpty()) throw new Error("Symbol table underflow error");

delete(min());

}

// delete the maximum key and its associated value

public void deleteMax() {

if (isEmpty()) throw new Error("Symbol table underflow error");

delete(max());

}

/* ***************************************************************************

* Ordered symbol table methods

*****************************************************************************/

public K min() {

if (isEmpty()) return null;

return keys[0];

}

public K max() {

if (isEmpty()) return null;

return keys[N-1];

}

public K select(int k) {

if (k < 0 || k >= N) return null;

return keys[k];

}

public K floor(K key) {

int i = rank(key);

if (i < N && key.compareTo(keys[i]) == 0) return keys[i];

if (i == 0) return null;

else return keys[i-1];

}

public K ceiling(K key) {

int i = rank(key);

if (i == N) return null;

else return keys[i];

}

public int size(K lo, K hi) {

if (lo.compareTo(hi) > 0) return 0;

if (contains(hi)) return rank(hi) - rank(lo) + 1;

else return rank(hi) - rank(lo);

}

public Iterable keys() {

return keys(min(), max());

}

public Iterable keys(K lo, K hi) {

Queue queue = new Queue<>();

if (lo == null && hi == null) return queue;

if (lo == null) throw new Error("lo is null in keys()");

if (hi == null) throw new Error("hi is null in keys()");

if (lo.compareTo(hi) > 0) return queue;

for (int i = rank(lo); i < rank(hi); i++)

queue.enqueue(keys[i]);

if (contains(hi)) queue.enqueue(keys[rank(hi)]);

return queue;

}

/* ***************************************************************************

* Check internal invariants

*****************************************************************************/

private boolean check() {

return isSorted() && rankCheck();

}

// are the items in the array in ascending order?

private boolean isSorted() {

for (int i = 1; i < size(); i++)

if (keys[i].compareTo(keys[i-1]) < 0) return false;

return true;

}

// check that rank(select(i)) = i

private boolean rankCheck() {

for (int i = 0; i < size(); i++)

if (i != rank(select(i))) return false;

for (int i = 0; i < size(); i++)

if (keys[i].compareTo(select(rank(keys[i]))) != 0) return false;

return true;

}

/* ***************************************************************************

* Test client

*****************************************************************************/

public static void main(String[] args) {

StdIn.fromFile("data/tiny.txt");

BinarySearchST st = new BinarySearchST<>();

for (int i = 0; !StdIn.isEmpty(); i++) {

String key = StdIn.readString();

st.put(key, i);

}

for (String s : st.keys())

StdOut.println(s + " " + st.get(s));

}

}