Problem1:

The file UnsortedLinkedDictionary.java contains unimplemented methods for a dictionary based

on an unsorted linked list. Implement all these methods.

------------------------------------------------------------------------

Unsorted Array Dictionary Driver

------------------------------------------------------------------------

import java.util.Iterator;

public class UnsortedArrayDictionaryDriver {

public static void main(String[] args) {

testDictionary();

} // end main

public static void display(UnsortedArrayDictionary dictionary) {

Iterator keyIterator = dictionary.getKeyIterator();

Iterator valueIterator = dictionary.getValueIterator();

while (keyIterator.hasNext() && valueIterator.hasNext())

System.out.println(keyIterator.next() + " : " + valueIterator.next());

System.out.println();

} // end display

public static void testDictionary() {

String dirk = "Dirk";

String abel = "Abel";

String miguel = "Miguel";

String tabbie = "Tabatha";

String tom = "Tom";

String sam = "Sam";

String reiss = "Reiss";

String bette = "Bette";

String carole = "Carole";

String derek = "Derek";

String nancy = "Nancy";

String bogus = "Bo";

// create a dictionary

System.out.println("Creating dictionary: ");

UnsortedArrayDictionary nameList = new UnsortedArrayDictionary();

System.out.println(" Testing isEmpty(): ");

if(nameList.isEmpty() == true)

System.out.println("OK");

else

System.out.println("ERROR");

// test add

System.out.println(" Testing add(): ");

nameList.add(dirk, "555-1234");

nameList.add(abel, "555-5678");

nameList.add(miguel, "555-9012");

nameList.add(tabbie, "555-3456");

nameList.add(tom, "555-5555");

nameList.add(sam, "555-7890");

nameList.add(reiss, "555-2345");

nameList.add(bette, "555-7891");

nameList.add(carole, "555-7892");

nameList.add(derek, "555-7893");

nameList.add(nancy, "555-7894");

System.out.println(" Testing getSize(): ");

if(nameList.getSize() == 11)

System.out.println("OK");

else

System.out.println("ERROR");

display(nameList);

// test getValue

System.out.println(" Testing getValue(): ");

System.out.println(" Sam: " + nameList.getValue(sam) + " should be 555-7890");

System.out.println(" Tom: " + nameList.getValue(tom) + " should be 555-5555");

System.out.println(" Reiss: " + nameList.getValue(reiss) + " should be 555-2345");

// test contains

System.out.println(" Testing contains(): ");

if ( nameList.contains(sam) )

System.out.println(" Sam is in dictionary - OK");

else

System.out.println("Error in contains()");

if ( nameList.contains(abel) )

System.out.println(" Abel is in dictionary - OK");

else

System.out.println("Error in contains()");

if ( nameList.contains(miguel) )

System.out.println(" Miguel is in dictionary - OK");

else

System.out.println("Error in contains()");

if ( nameList.contains(tom) )

System.out.println(" Tom is in dictionary - OK");

else

System.out.println("Error in contains()");

if (!nameList.contains(bogus))

System.out.println(" Bo is not in dictionary - OK");

else

System.out.println("Error in contains()");

// remove first item

System.out.println(" Removing first item Dirk - Dirk's number is " +

nameList.remove(dirk) + " should be 555-1234");

// test replacing value

System.out.println("Replacing phone number of Reiss and Miguel: ");

String oldNumber = nameList.add(reiss, "555-5432");

System.out.println("Reiss's old number " + oldNumber + " is replaced by 555-5432");

oldNumber = nameList.add(miguel, "555-2109");

System.out.println("Miguel's old number " + oldNumber + " is replaced by 555-2109");

System.out.println(" " + nameList.getSize() +

" (should be 10) items in dictionary, as follows: ");

display(nameList);

// remove interior and last items

System.out.println(" Removing interior item Reiss and last item Nancy: ");

nameList.remove(reiss);

nameList.remove(nancy);

// remove Bo (not in dictionary)

System.out.println(" Removing Bo (not in dictionary): ");

String result = nameList.remove(bogus);

if (result == null)

System.out.println("Bo was not found in the dictionary.");

else

System.out.println("Error in remove().");

System.out.println(" " + nameList.getSize() +

" (should be 8) items in dictionary, as follows: ");

display(nameList);

// test clear

System.out.println(" Testing clear(): ");

nameList.clear();

System.out.println("Dictionary should be empty; isEmpty() returns " +

nameList.isEmpty());

} // testDictionary

} // end Driver

------------------------------------------------------------------------

import java.util.Arrays;

import java.util.Iterator;

import java.util.NoSuchElementException;

public class UnsortedArrayDictionary

{

private Entry[] dictionary; // array of unsorted entries

private int numberOfEntries;

private final static int DEFAULT_INITIAL_CAPACITY = 6;

public UnsortedArrayDictionary() {

this(DEFAULT_INITIAL_CAPACITY);

} // end default constructor

public UnsortedArrayDictionary(int initialCapacity) {

// the cast is safe because the new array contains null entries

@SuppressWarnings("unchecked")

Entry[] tempDictionary = (Entry[])new Entry[initialCapacity];

dictionary = tempDictionary;

numberOfEntries = 0;

} // end constructor

public V add(K key, V value) {

V result = null;

int keyIndex = locateIndex(key);

if (keyIndex < numberOfEntries) {

// key found, return and replace old value

result = dictionary[keyIndex].getValue(); // old value

dictionary[keyIndex].setValue(value); // replace value

}

else {

ensureCapacity();

// add at end of array

dictionary[numberOfEntries] = new Entry(key, value);

numberOfEntries++;

} // end if

return result;

} // end add

public V remove(K key) {

V result = null;

int keyIndex = locateIndex(key);

if (keyIndex < numberOfEntries) {

result = dictionary[keyIndex].getValue();

dictionary[keyIndex] = dictionary[numberOfEntries - 1]; // replace removed entry with last entry

numberOfEntries--;

} // end if

// else result is null

return result;

} // end remove

public V getValue(K key) {

V result = null;

int keyIndex = locateIndex(key);

if (keyIndex < numberOfEntries) {

result = dictionary[keyIndex].getValue();

} // end if

return result;

} // end getValue

public boolean contains(K key) {

return getValue(key) != null;

} // end contains

public boolean isEmpty() {

return numberOfEntries == 0;

} // end isEmpty

public int getSize() {

return numberOfEntries;

} // end getSize

public final void clear() {

numberOfEntries = 0;

} // end clear

public Iterator getKeyIterator() {

return new KeyIterator();

} // end getKeyIterator

public Iterator getValueIterator() {

return new ValueIterator();

} // end getValueIterator

// Returns the index of the entry that contains the given search key, or

// numberOfEntries if no such entry exists.

private int locateIndex(K key) {

// sequential search

int index = 0;

while ( (index < numberOfEntries) && !key.equals(dictionary[index].getKey()) )

index++;

return index;

} // end locateIndex

// Doubles the size of the array dictionary if it is full

private void ensureCapacity() {

if (numberOfEntries == dictionary.length)

dictionary = Arrays.copyOf(dictionary, 2 * dictionary.length);

} // end ensureCapacity

// Same as SortedArrayDictionary

private class KeyIterator implements Iterator {

private int currentIndex;

private KeyIterator() {

currentIndex = 0;

} // end default constructor

public boolean hasNext() {

return currentIndex < numberOfEntries;

} // end hasNext

public K next() {

K result = null;

if (hasNext()) {

Entry currentEntry = dictionary[currentIndex];

result = currentEntry.getKey();

currentIndex++;

}

else

throw new NoSuchElementException();

return result;

} // end next

public void remove(){

throw new UnsupportedOperationException();

} // end remove

} // end KeyIterator

private class ValueIterator implements Iterator {

private int currentIndex;

private ValueIterator() {

currentIndex = 0;

} // end default constructor

public boolean hasNext() {

return currentIndex < numberOfEntries;

} // end hasNext

public V next() {

V result = null;

if (hasNext()) {

Entry currentEntry = dictionary[currentIndex];

result = currentEntry.getValue();

currentIndex++;

}

else

throw new NoSuchElementException();

return result;

} // end next

public void remove() {

throw new UnsupportedOperationException();

} // end remove

} // end getValueIterator

private class Entry {

private S key;

private T value;

private Entry(S searchKey, T dataValue) {

key = searchKey;

value = dataValue;

} // end constructor

private S getKey() {

return key;

} // end getKey

private T getValue() {

return value;

} // end getValue

private void setValue(T dataValue) {

value = dataValue;

} // end setValue

} // end Entry

} // end UnsortedArrayDictionary

------------------------------------------------------------------------

import java.util.Iterator;

import java.util.Scanner;

import java.io.File;

import java.io.FileNotFoundException;

/**

A driver that demonstrates the class TelephoneDirectory.

@author Frank M. Carrano

@author Timothy M. Henry

@version 4.0

*/

public class TelephoneDirectoryDriver

{

private static final Name INPUT_ERROR = new Name("error", "error");

private static final Name QUIT = new Name("quit", "quit");

public static void main(String[] args)

{

TelephoneDirectory directory = new TelephoneDirectory();

String fileName = "data.txt"; // Or file name could be read

try

{

Scanner data = new Scanner(new File(fileName));

directory.readFile(data);

}

catch (FileNotFoundException e)

{

System.out.println("File not found: " + e.getMessage());

}

//=======================

// This part is not in the book

System.out.println("The directory contains " + directory.getSize() + " names, as follows: ");

Iterator nameTraverser = directory.getKeyIterator();

Iterator numberTraverser = directory.getValueIterator();

while (nameTraverser.hasNext() && numberTraverser.hasNext())

System.out.println(nameTraverser.next() + " " + numberTraverser.next());

Name joey = new Name("Joey", "Jones");

Name jude = new Name("Jude", "Jones");

Name jim = new Name("Jimmy", "Jones");

Name jamie = new Name("Jamie", "Smith");

Name june = new Name("June", "Jones");

Name judy = new Name("Judy", "Jones");

Name bogus = new Name("Bo", "Gus"); // not in directory

System.out.println(" Looking up phone numbers:");

System.out.println("Joey's number is " + directory.getPhoneNumber(joey) + " (should be 401-555-1234)");

System.out.println("Jude's number is " + directory.getPhoneNumber(jude) + " (should be 401-555-2345)");

System.out.println("Jimmy's number is " + directory.getPhoneNumber(jim) + " (should be 401-555-3456)");

System.out.println("Jamie's number is " + directory.getPhoneNumber(jamie) + " (should be 401-555-4567)");

System.out.println("June's number is " + directory.getPhoneNumber(june) + " (should be 401-555-5678)");

System.out.println("Judy's number is " + directory.getPhoneNumber(judy) + " (should be 401-555-6789)");

System.out.println("Bo's number is " + directory.getPhoneNumber(bogus) + " (should be null");

//=======================

Name nextName = getName(); // Get name for search from user

while (!nextName.equals(QUIT))

{

if (nextName.equals(INPUT_ERROR))

System.out.println("Error in entering name. Try again.");

else

{

String phoneNumber = directory.getPhoneNumber(nextName);

if (phoneNumber == null)

System.out.println(nextName + " is not in the directory.");

else

System.out.println("The phone number for " + nextName +

" is " + phoneNumber);

} // end if

nextName = getName();

} // end while

System.out.println("Bye!");

} // end main

// Returns either the name read from user, INPUT_ERROR, or QUIT.

private static Name getName()

{

Name result = null;

Scanner keyboard = new Scanner(System.in);

System.out.print("Enter first name and last name, " +

"or quit to end: ");

String line = keyboard.nextLine();

if (line.trim().toLowerCase().equals("quit"))

result = QUIT;

else

{

String firstName = null;

String lastName = null;

Scanner scan = new Scanner(line);

if (scan.hasNext())

{

firstName = scan.next();

if (scan.hasNext())

lastName = scan.next();

else

result = INPUT_ERROR;

}

else

result = INPUT_ERROR;

if (result == null)

{

// First and last names have been read

result = new Name(firstName, lastName);

} // end if

} // end if

return result;

} // end getName

} // end Driver

/*

The directory contains 6 names, as follows:

Jimmy Jones 401-555-3456

Joey Jones 401-555-1234

Jude Jones 401-555-2345

Judy Jones 401-555-6789

June Jones 401-555-1111

Jamie Smith 401-555-4567

Looking up phone numbers:

Joey's number is 401-555-1234 (should be 401-555-1234)

Jude's number is 401-555-2345 (should be 401-555-2345)

Jimmy's number is 401-555-3456 (should be 401-555-3456)

Jamie's number is null (should be 401-555-4567)

June's number is 401-555-1111 (should be 401-555-5678)

Judy's number is 401-555-6789 (should be 401-555-6789)

Bo's number is null (should be null

Enter first name and last name, or quit to end: Jude Jones

The phone number for Jude Jones is 401-555-2345

Enter first name and last name, or quit to end: Jude Smith

Jude Smith is not in the directory.

Enter first name and last name, or quit to end: quit

Bye!

*/

------------------------------------------------------------------------

import java.util.Scanner;

class Name implements Comparable

{

private String first;

private String last;

public Name() {

first = last = null;

}

public Name(String firstName, String lastName) {

first = firstName;

last = lastName;

}

public int compareTo(Name n) {

int c = first.compareTo(n.first);

if(c == 0)

c = last.compareTo(n.last);

return c;

}

}

public class TelephoneDirectory

{

private BSTDictionary< Name, String > phoneBook;

public TelephoneDirectory () {

phoneBook = new BSTDictionary < Name, String > ();

} // end default constructor

public void readFile (Scanner data) {

while (data.hasNext ()) {

String firstName = data.next ();

String lastName = data.next ();

String phoneNumber = data.next ();

Name fullName = new Name (firstName, lastName);

phoneBook.add (fullName, phoneNumber);

} // end while

data.close ();

} // end readFile

public String getPhoneNumber (Name personName)

{

return phoneBook.getValue (personName);

} // end getPhoneNumber

public String getPhoneNumber (String firstName, String lastName)

{

Name fullName = new Name (firstName, lastName);

return phoneBook.getValue (fullName);

} // end getPhoneNumber

} // end TelephoneDirectory

------------------------------------------------------------------------

import java.util.Scanner;

import java.io.File;

import java.io.FileNotFoundException;

import java.io.IOException;

public class FrequencyCounterDriver

{

public static void main (String [] args) {

FrequencyCounter wordCounter = new FrequencyCounter ();

String fileName = "Data.txt"; // or file name could be read

try {

Scanner data = new Scanner (new File (fileName));

wordCounter.readFile (data);

}

catch (FileNotFoundException e) {

System.out.println ("File not found: " + e.getMessage ());

}

catch (IOException e) {

System.out.println ("I/O error " + e.getMessage ());

}

wordCounter.display ();

} // end main

} // end Driver

------------------------------------------------------------------------

import java.util.Iterator;

import java.util.Scanner;

public class FrequencyCounter

{

private BSTDictionary< String, Integer > wordTable;

public FrequencyCounter ()

{

wordTable = new BSTDictionary < String, Integer > ();

} // end default constructor

public void readFile (Scanner data)

{

data.useDelimiter ("\\W+");

while (data.hasNext ()) {

String nextWord = data.next ();

nextWord = nextWord.toLowerCase ();

Integer frequency = wordTable.getValue (nextWord);

if (frequency == null) { // add new word to table

wordTable.add (nextWord, new Integer (1));

}

else { // increment count of existing word; replace wordTable entry

frequency++;

wordTable.add (nextWord, frequency);

} // end if

} // end while

data.close ();

} // end readFile

public void display ()

{

Iterator < String > keyIterator = wordTable.getKeyIterator ();

Iterator < Integer > valueIterator = wordTable.getValueIterator ();

while (keyIterator.hasNext ()) {

System.out.println (keyIterator.next () + " " +

valueIterator.next ());

} // end while

} // end display

} // end FrequencyCounter

------------------------------------------------------------------------

import java.util.Iterator;

import java.util.Scanner;

import java.io.File;

import java.io.FileNotFoundException;

/**

A driver that demonstrates the class Concordance.

@author Frank M. Carrano

@author Timothy M. Henry

@version 4.0

*/

public class ConcordanceDriver

{

public static void main(String[] args)

{

Concordance wordIndex = new Concordance();

String fileName = "Data.txt"; // could be read

try

{

Scanner textReader = new Scanner(new File(fileName));

wordIndex.readFile(textReader);

}

catch (FileNotFoundException e)

{

System.out.println("File not found: " + e.getMessage());

}

System.out.println("Here is the concordance for the text read from the data file:");

wordIndex.display();

// Test Question 9 (getLineNumbers)

System.out.println(" Test getLineNumbers(\"learning\")");

ListWithIteratorInterface lineList = wordIndex.getLineNumbers("learning");

Iterator listIterator = lineList.getIterator();

while (listIterator.hasNext())

{

System.out.print(listIterator.next() + " ");

} // end while

System.out.println();

System.out.println(" Done!");

} // end main

} // end Driver

/*

Here is the concordance for the text read from the data file:

is 1 2

labor 1

learning 1 2

lost 1

perilous 2

thought 1 2

without 1 2

Test getLineNumbers("learning")

1 2

Done!

*/

------------------------------------------------------------------------

import java.util.Iterator;

import java.util.Scanner;

/**

A class that represents a concordance.

@author Frank M. Carrano

@author Timothy M. Henry

@version 4.0

*/

public class Concordance

{

private DictionaryInterface> wordTable;

public Concordance()

{

// Using SortedVectorDictionary instead of SortedDictionary

wordTable = new SortedVectorDictionary<>();

} // end default constructor

/** Reads a text file of words and creates a concordance.

@param data A text scanner for the text file of data. */

public void readFile(Scanner data)

{

int lineNumber = 1;

while (data.hasNext())

{

String line = data.nextLine();

line = line.toLowerCase();

Scanner lineProcessor = new Scanner(line);

lineProcessor.useDelimiter("\\W+");

while (lineProcessor.hasNext())

{

String nextWord = lineProcessor.next();

ListWithIteratorInterface lineList = wordTable.getValue(nextWord);

if (lineList == null)

{ // Create new list for new word; add list and word to index

lineList = new LinkedListWithIterator<>();

wordTable.add(nextWord, lineList);

} // end if

// Add line number to end of list so list is sorted

lineList.add(lineNumber);

} // end while

lineNumber++;

} // end while

data.close();

} // end readFile

/** Displays words and the lines in which they occur. */

public void display()

{

Iterator keyIterator = wordTable.getKeyIterator();

Iterator> valueIterator = wordTable.getValueIterator();

while (keyIterator.hasNext())

{

// Display the word

System.out.print(keyIterator.next() + " ");

// Get line numbers and iterator

ListWithIteratorInterface lineList = valueIterator.next();

Iterator listIterator = lineList.getIterator();

// Display line numbers

while (listIterator.hasNext())

{

System.out.print(listIterator.next() + " ");

} // end while

System.out.println();

} // end while

} // end display

// Question 9, Chapter 19

public ListWithIteratorInterface getLineNumbers(String word)

{

return wordTable.getValue(word);

} // end getLineNumbers

} // end Concordance

------------------------------------------------------------------------