Implementation: Pick one of the two following applications to implement. (SPELL
ID: 3755725 • Letter: I
Question
Implementation: Pick one of the two following applications to implement. (SPELL CHECKER)
Test your application with the supplied Bag ADT implementation. You may want to declare your reference variables as type BagInterface<> rather than ResizableArrayBag<> to simplify switching implementations. Optionally, test your application with your own Bag ADT implementation to make sure that your code works with multiple Bag implementations.
Spell Checker Write a spell checker that goes through the following steps:
1. Fill a bag with words from a dictionary file
2. Read in words from another text file
3. Check if those words are in the dictionary (ignoring upper/lower case differences)
4. Store misspelled words in a second bag
5. Print all misspelled words to the console Example output: corde beganning szpring Two files are supplied in the data directory for the spell checker: the dictionary sowpods.txt and a file to test called the-lancashire-cotton-famine.txt. You should test your program using that dictionary and test file.
You should also test additional files to make sure that your code works with a variety of inputs. Start with some smaller dictionary/test files as you are first writing the code and then build up to the supplied files.
package edu.wit.cs.comp2000;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class SpellChecker {
// An example method to open a file
private static void exampleOpenFile(String fName) {
try (Scanner s = new Scanner(new File(fName))) {
// loop over all words in file
} catch (FileNotFoundException e) {
System.err.println("Cannot open file " + fName + ". Exiting.");
System.exit(0);
}
}
public static void main(String[] args) {
exampleOpenFile("data/sowpods.txt");
}
}
___________________________________________________________________________
package edu.wit.cs.comp2000;
/**
A class of bags whose entries are stored in a fixed-size array.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
public final class ArrayBag<T> implements BagInterface<T>
{
private final T[] bag;
private int numberOfEntries;
private boolean initialized = false;
private static final int DEFAULT_CAPACITY = 25;
private static final int MAX_CAPACITY = 10000;
/** Creates an empty bag whose initial capacity is 25. */
public ArrayBag()
{
this(DEFAULT_CAPACITY);
} // end default constructor
/** Creates an empty bag having a given capacity.
@param desiredCapacity The integer capacity desired. */
public ArrayBag(int desiredCapacity)
{
if (desiredCapacity <= MAX_CAPACITY)
{
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempBag = (T[])new Object[desiredCapacity]; // Unchecked cast
bag = tempBag;
numberOfEntries = 0;
initialized = true;
}
else
throw new IllegalStateException("Attempt to create a bag " +
"whose capacity exceeds " +
"allowed maximum.");
} // end constructor
/** Adds a new entry to this bag.
@param newEntry The object to be added as a new entry.
@return True if the addition is successful, or false if not. */
public boolean add(T newEntry)
{
checkInitialization();
boolean result = true;
if (isArrayFull())
{
result = false;
}
else
{ // Assertion: result is true here
bag[numberOfEntries] = newEntry;
numberOfEntries++;
} // end if
return result;
} // end add
/** Retrieves all entries that are in this bag.
@return A newly allocated array of all the entries in this bag. */
public T[] toArray()
{
checkInitialization();
// The cast is safe because the new array contains null entries.
@SuppressWarnings("unchecked")
T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast
for (int index = 0; index < numberOfEntries; index++)
{
result[index] = bag[index];
} // end for
return result;
// Note: The body of this method could consist of one return statement,
// if you call Arrays.copyOf
} // end toArray
/** Sees whether this bag is empty.
@return True if this bag is empty, or false if not. */
public boolean isEmpty()
{
return numberOfEntries == 0;
} // end isEmpty
/** Gets the current number of entries in this bag.
@return The integer number of entries currently in this bag. */
public int getCurrentSize()
{
return numberOfEntries;
} // end getCurrentSize
/** Counts the number of times a given entry appears in this bag.
@param anEntry The entry to be counted.
@return The number of times anEntry appears in this ba. */
public int getFrequencyOf(T anEntry)
{
checkInitialization();
int counter = 0;
for (int index = 0; index < numberOfEntries; index++)
{
if (anEntry.equals(bag[index]))
{
counter++;
} // end if
} // end for
return counter;
} // end getFrequencyOf
/** Tests whether this bag contains a given entry.
@param anEntry The entry to locate.
@return True if this bag contains anEntry, or false otherwise. */
public boolean contains(T anEntry)
{
checkInitialization();
return getIndexOf(anEntry) > -1; // or >= 0
} // end contains
/** Removes all entries from this bag. */
public void clear()
{
while (!isEmpty())
remove();
} // end clear
/** Removes one unspecified entry from this bag, if possible.
@return Either the removed entry, if the removal
was successful, or null. */
public T remove()
{
checkInitialization();
T result = removeEntry(numberOfEntries - 1);
return result;
} // end remove
/** Removes one occurrence of a given entry from this bag.
@param anEntry The entry to be removed.
@return True if the removal was successful, or false if not. */
public boolean remove(T anEntry)
{
checkInitialization();
int index = getIndexOf(anEntry);
T result = removeEntry(index);
return anEntry.equals(result);
} // end remove
// Returns true if the array bag is full, or false if not.
private boolean isArrayFull()
{
return numberOfEntries >= bag.length;
} // end isArrayFull
// Locates a given entry within the array bag.
// Returns the index of the entry, if located,
// or -1 otherwise.
// Precondition: checkInitialization has been called.
private int getIndexOf(T anEntry)
{
int where = -1;
boolean found = false;
int index = 0;
while (!found && (index < numberOfEntries))
{
if (anEntry.equals(bag[index]))
{
found = true;
where = index;
} // end if
index++;
} // end while
// Assertion: If where > -1, anEntry is in the array bag, and it
// equals bag[where]; otherwise, anEntry is not in the array.
return where;
} // end getIndexOf
// Removes and returns the entry at a given index within the array.
// If no such entry exists, returns null.
// Precondition: 0 <= givenIndex < numberOfEntries.
// Precondition: checkInitialization has been called.
private T removeEntry(int givenIndex)
{
T result = null;
if (!isEmpty() && (givenIndex >= 0))
{
result = bag[givenIndex]; // Entry to remove
int lastIndex = numberOfEntries - 1;
bag[givenIndex] = bag[lastIndex]; // Replace entry to remove with last entry
bag[lastIndex] = null; // Remove reference to last entry
numberOfEntries--;
} // end if
return result;
} // end removeEntry
// Throws an exception if this object is not initialized.
private void checkInitialization()
{
if (!initialized)
throw new SecurityException("ArrayBag object is not initialized properly.");
} // end checkInitialization
} // end ArrayBag
package edu.wit.cs.comp2000;
import java.util.Arrays;
/**
A class that implements a bag of objects by using an array.
The bag is never full.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
_______________________________________________________________________
public final class ResizableArrayBag<T> implements BagInterface<T>
{
private T[] bag; // Cannot be final due to doubling
private int numberOfEntries;
private boolean initialized = false;
private static final int DEFAULT_CAPACITY = 25; // Initial capacity of bag
private static final int MAX_CAPACITY = 250000;
// DMR - extended to hold entire dictionary
/** Creates an empty bag whose initial capacity is 25. */
public ResizableArrayBag()
{
this(DEFAULT_CAPACITY);
} // end default constructor
/** Creates an empty bag having a given initial capacity.
@param initialCapacity The integer capacity desired. */
public ResizableArrayBag(int initialCapacity)
{
checkCapacity(initialCapacity);
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempBag = (T[])new Object[initialCapacity]; // Unchecked cast
bag = tempBag;
numberOfEntries = 0;
initialized = true;
} // end constructor
/** Creates a bag containing given entries.
@param contents An array of objects. */
public ResizableArrayBag(T[] contents)
{
checkCapacity(contents.length);
bag = Arrays.copyOf(contents, contents.length);
numberOfEntries = contents.length;
initialized = true;
} // end constructor
/** Adds a new entry to this bag.
@param newEntry The object to be added as a new entry.
@return True. */
public boolean add(T newEntry)
{
checkInitialization();
if (isArrayFull())
{
doubleCapacity();
} // end if
bag[numberOfEntries] = newEntry;
numberOfEntries++;
return true;
} // end add
/** Retrieves all entries that are in this bag.
@return A newly allocated array of all the entries in this bag. */
public T[] toArray()
{
checkInitialization();
// The cast is safe because the new array contains null entries.
@SuppressWarnings("unchecked")
T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast
for (int index = 0; index < numberOfEntries; index++)
{
result[index] = bag[index];
} // end for
return result;
} // end toArray
/** Sees whether this bag is empty.
@return True if this bag is empty, or false if not. */
public boolean isEmpty()
{
return numberOfEntries == 0;
} // end isEmpty
/** Gets the current number of entries in this bag.
@return The integer number of entries currently in this bag. */
public int getCurrentSize()
{
return numberOfEntries;
} // end getCurrentSize
/** Counts the number of times a given entry appears in this bag.
@param anEntry The entry to be counted.
@return The number of times anEntry appears in this ba. */
public int getFrequencyOf(T anEntry)
{
checkInitialization();
int counter = 0;
for (int index = 0; index < numberOfEntries; index++)
{
if (anEntry.equals(bag[index]))
{
counter++;
} // end if
} // end for
return counter;
} // end getFrequencyOf
/** Tests whether this bag contains a given entry.
@param anEntry The entry to locate.
@return True if this bag contains anEntry, or false otherwise. */
public boolean contains(T anEntry)
{
checkInitialization();
return getIndexOf(anEntry) > -1; // or >= 0
} // end contains
/** Removes all entries from this bag. */
public void clear()
{
while (!isEmpty())
remove();
} // end clear
/** Removes one unspecified entry from this bag, if possible.
@return Either the removed entry, if the removal
was successful, or null. */
public T remove()
{
checkInitialization();
T result = removeEntry(numberOfEntries - 1);
return result;
} // end remove
/** Removes one occurrence of a given entry from this bag.
@param anEntry The entry to be removed.
@return True if the removal was successful, or false if not. */
public boolean remove(T anEntry)
{
checkInitialization();
int index = getIndexOf(anEntry);
T result = removeEntry(index);
return anEntry.equals(result);
} // end remove
// Locates a given entry within the array bag.
// Returns the index of the entry, if located,
// or -1 otherwise.
// Precondition: checkInitialization has been called.
private int getIndexOf(T anEntry)
{
int where = -1;
boolean found = false;
int index = 0;
while (!found && (index < numberOfEntries))
{
if (anEntry.equals(bag[index]))
{
found = true;
where = index;
} // end if
index++;
} // end while
// Assertion: If where > -1, anEntry is in the array bag, and it
// equals bag[where]; otherwise, anEntry is not in the array.
return where;
} // end getIndexOf
// Removes and returns the entry at a given index within the array.
// If no such entry exists, returns null.
// Precondition: 0 <= givenIndex < numberOfEntries.
// Precondition: checkInitialization has been called.
private T removeEntry(int givenIndex)
{
T result = null;
if (!isEmpty() && (givenIndex >= 0))
{
result = bag[givenIndex]; // Entry to remove
int lastIndex = numberOfEntries - 1;
bag[givenIndex] = bag[lastIndex]; // Replace entry to remove with last entry
bag[lastIndex] = null; // Remove reference to last entry
numberOfEntries--;
} // end if
return result;
} // end removeEntry
// Returns true if the array bag is full, or false if not.
private boolean isArrayFull()
{
return numberOfEntries >= bag.length;
} // end isArrayFull
// Doubles the size of the array bag.
// Precondition: checkInitialization has been called.
private void doubleCapacity()
{
int newLength = 2 * bag.length;
checkCapacity(newLength);
bag = Arrays.copyOf(bag, newLength);
} // end doubleCapacity
// Throws an exception if the client requests a capacity that is too large.
private void checkCapacity(int capacity)
{
if (capacity > MAX_CAPACITY)
throw new IllegalStateException("Attempt to create a bag whose capacity exceeds " +
"allowed maximum of " + MAX_CAPACITY);
} // end checkCapacity
// Throws an exception if receiving object is not initialized.
private void checkInitialization()
{
if (!initialized)
throw new SecurityException ("Uninitialized object used " +
"to call an ArrayBag method.");
} // end checkInitialization
} // end ResizableArrayBag
package edu.wit.cs.comp2000;
/**
An interface that describes the operations of a bag of objects.
@author Frank M. Carrano
@version 4.0
*/
_____________________________________________________________
public interface BagInterface<T>
{
/** Gets the current number of entries in this bag.
@return The integer number of entries currently in the bag. */
public int getCurrentSize();
/** Sees whether this bag is empty.
@return True if the bag is empty, or false if not. */
public boolean isEmpty();
/** Adds a new entry to this bag.
@param newEntry The object to be added as a new entry.
@return True if the addition is successful, or false if not. */
public boolean add(T newEntry);
/** Removes one unspecified entry from this bag, if possible.
@return Either the removed entry, if the removal.
was successful, or null. */
public T remove();
/** Removes one occurrence of a given entry from this bag.
@param anEntry The entry to be removed.
@return True if the removal was successful, or false if not. */
public boolean remove(T anEntry);
/** Removes all entries from this bag. */
public void clear();
/** Counts the number of times a given entry appears in this bag.
@param anEntry The entry to be counted.
@return The number of times anEntry appears in the bag. */
public int getFrequencyOf(T anEntry);
/** Tests whether this bag contains a given entry.
@param anEntry The entry to locate.
@return True if the bag contains anEntry, or false if not. */
public boolean contains(T anEntry);
/** Retrieves all entries that are in this bag.
@return A newly allocated array of all the entries in the bag.
Note: If the bag is empty, the returned array is empty. */
public T[] toArray();
} // end BagInterface
________________________________________________________________
package edu.wit.cs.comp2000;
/**
A class of bags whose entries are stored in a chain of linked nodes.
The bag is never full.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.1
*/
public final class LinkedBag<T> implements BagInterface<T>
{
private Node firstNode; // Reference to first node
private int numberOfEntries;
public LinkedBag()
{
firstNode = null;
numberOfEntries = 0;
} // end default constructor
/** Sees whether this bag is empty.
@return True if this bag is empty, or false if not. */
public boolean isEmpty()
{
return numberOfEntries == 0;
} // end isEmpty
/** Gets the number of entries currently in this bag.
@return The integer number of entries currently in this bag. */
public int getCurrentSize()
{
return numberOfEntries;
} // end getCurrentSize
/** Adds a new entry to this bag.
@param newEntry The object to be added as a new entry
@return True if the addition is successful, or false if not. */
public boolean add(T newEntry) // OutOfMemoryError possible
{
// Add to beginning of chain:
Node newNode = new Node(newEntry);
newNode.next = firstNode; // Make new node reference rest of chain
// (firstNode is null if chain is empty)
firstNode = newNode; // New node is at beginning of chain
numberOfEntries++;
return true;
} // end add
/** Retrieves all entries that are in this bag.
@return A newly allocated array of all the entries in this bag. */
public T[] toArray()
{
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast
int index = 0;
Node currentNode = firstNode;
while ((index < numberOfEntries) && (currentNode != null))
{
result[index] = currentNode.data;
index++;
currentNode = currentNode.next;
} // end while
return result;
} // end toArray
/** Counts the number of times a given entry appears in this bag.
@param anEntry The entry to be counted.
@return The number of times anEntry appears in this bag. */
public int getFrequencyOf(T anEntry)
{
int frequency = 0;
int counter = 0;
Node currentNode = firstNode;
while ((counter < numberOfEntries) && (currentNode != null))
{
if (anEntry.equals(currentNode.data))
{
frequency++;
} // end if
counter++;
currentNode = currentNode.next;
} // end while
return frequency;
} // end getFrequencyOf
/** Tests whether this bag contains a given entry.
@param anEntry The entry to locate.
@return True if the bag contains anEntry, or false otherwise. */
public boolean contains(T anEntry)
{
boolean found = false;
Node currentNode = firstNode;
while (!found && (currentNode != null))
{
if (anEntry.equals(currentNode.data))
found = true;
else
currentNode = currentNode.next;
} // end while
return found;
} // end contains
// Locates a given entry within this bag.
// Returns a reference to the node containing the entry, if located,
// or null otherwise.
private Node getReferenceTo(T anEntry)
{
boolean found = false;
Node currentNode = firstNode;
while (!found && (currentNode != null))
{
if (anEntry.equals(currentNode.data))
found = true;
else
currentNode = currentNode.next;
} // end while
return currentNode;
} // end getReferenceTo
/** Removes all entries from this bag. */
public void clear()
{
while (!isEmpty())
remove();
} // end clear
/** Removes one unspecified entry from this bag, if possible.
@return Either the removed entry, if the removal
was successful, or null. */
public T remove()
{
T result = null;
if (firstNode != null)
{
result = firstNode.data;
firstNode = firstNode.next; // Remove first node from chain
numberOfEntries--;
} // end if
return result;
} // end remove
/** Removes one occurrence of a given entry from this bag, if possible.
@param anEntry The entry to be removed.
@return True if the removal was successful, or false otherwise. */
public boolean remove(T anEntry)
{
boolean result = false;
Node nodeN = getReferenceTo(anEntry);
if (nodeN != null)
{
nodeN.data = firstNode.data; // Replace located entry with entry in first node
firstNode = firstNode.next; // Remove first node
numberOfEntries--;
result = true;
} // end if
return result;
} // end remove
private class Node
{
private T data; // Entry in bag
private Node next; // Link to next node
private Node(T dataPortion)
{
this(dataPortion, null);
} // end constructor
private Node(T dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode;
} // end constructor
} // end Node
} // end LinkedBag
Explanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. If you are satisfied with the solution, please upvote the answer. Thanks
// SpellChecker.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
public class SpellChecker {
//defining required Bags
static BagInterface<String> bag1, bag2;
/**
* method to load words from a dictionary file, and fill the first bag
* @param filename name of dictionary file
* @throws FileNotFoundException if the file is not found
*/
static void loadDictionary(String filename) throws FileNotFoundException {
//initializing bag
bag1 = new ResizableArrayBag<String>();
//creating scanner to read the file
Scanner scanner = new Scanner(new File(filename));
//adding all words to bag1
while (scanner.hasNext()) {
bag1.add(scanner.next().toLowerCase());
}
}
/**
* method to check a file for spelling errors and fill the mispelt words in bag2
* @param filename name of file
* @throws FileNotFoundException if file not found
* assuming bag1 is not null
*/
static void performSpellCheck(String filename) throws FileNotFoundException {
//initializing second bag
bag2 = new ResizableArrayBag<String>();
Scanner scanner = new Scanner(new File(filename));
// using regex pattern to split words by all possible punctuation
// symbols
scanner.useDelimiter("\W+");
while (scanner.hasNext()) {
//getting word
String word = scanner.next();
//if the word is not found in bag1, adding to bag2
if (!bag1.contains(word.toLowerCase())) {
bag2.add(word);
}
}
}
public static void main(String[] args) {
//scanner to read user input
Scanner scanner = new Scanner(System.in);
try {
//getting dictionary file name
System.out.println("Enter dictionary file name: ");
String dictionaryFileName = scanner.nextLine();
//loading dictionary, filling bag1
loadDictionary(dictionaryFileName);
//getting name of file to be tested
System.out.println("Enter name of file to be spell checked: ");
String inputFileName = scanner.nextLine();
//performing spell check
performSpellCheck(inputFileName);
if (bag2 != null) {
//displaying the mispelt words
System.out.println("Mispelt words count: "
+ bag2.getCurrentSize());
System.out.println("Mispelt words: ");
System.out.println(Arrays.toString(bag2.toArray()));
}
} catch (FileNotFoundException e) {
System.out.println(e);
}
}
}
/*input1.txt*/
This is an example file tp testt the spel checkker program. Hope everything is working properly
Some randomm text is enterred.
/*OUTPUT*/
Enter dictionary file name:
dictionary.txt
Enter name of file to be spell checked:
input1.txt
Mispelt words count: 6
Mispelt words:
[tp, testt, spel, checkker, randomm, enterred]