辅导Java编程、讲解Store Checkout System
- 首页 >> Java编程Store Checkout System
For this assignment, you will create a portion of a retail store checkout system. For this assignment you have both data structures and an application to develope. The application provides fast lookup for product information. A clerk (or customer) inputs a product stock number and the system returns the record for that item. The system is designed to provide facilities to add, remove and look up items, along with certain other utility functions. Your data structures portion of the project will use the DictionaryADT interface (provided) to support your application program. The dictionary takes key=value pairs. Each key must be distinct; no duplicates are allowed. There may be duplicate values.
Due Date/Time:
Your project is due on Friday, May 4th at 3:30 PM. Do not submit any printouts, just place all of your program files in your handin/prog4/ folder.
As we are at the end of the semester, I am allowing as much time as I can for you to complete the assignment. Therefore,the May 4th deadline is final, and no late programs will be accepted.
The Project:
This program consists of the ProductLookup application program, which allows the user to interact with the dictionary. You will implement the DictionaryADT iterface in three ways:
•A Hashtable
•A BinarySearchTree
•A Red/Black Tree
Your project will consist of the following files:
•ProductLookup.java The application program (methods below).
•StockItem.java The items that are stored in the dictionary.
•DictionaryADT.java The Dictionary interface. (Provided)
•Hashtable.java A hash table implementation of the DictionaryADT interface. Using chaining.
•BinarySearchTree.java The BST implementation of the DictionaryADT.
•BalancedTree.java A red/black tree implementation of the DictionaryADT, which uses the Java API class java.util.TreeMap.
You will write all of the above classes with the exception that the DictionaryADT interface which is provided.
You may not make any modifications to the DictionaryADT interface; the instructor's copy of this file will be used to grade your project.
All of the above classes except ProductLookup.java and StockItem.java must be in a package named data_structures.
ProductLookup.java
import data_structures.*;
import java.util.Iterator;
public class ProductLookup {
// Constructor. There is no argument-less constructor, or default size
public ProductLookup(int maxSize)
// Adds a new StockItem to the dictionary
public void addItem(String SKU, StockItem item)
// Returns the StockItem associated with the given SKU, if it is
// in the ProductLookup, null if it is not.
public StockItem getItem(String SKU)
// Returns the retail price associated with the given SKU value.
// -.01 if the item is not in the dictionary
public float getRetail(String SKU)
// Returns the cost price associated with the given SKU value.
// -.01 if the item is not in the dictionary
public float getCost(String SKU)
// Returns the description of the item, null if not in the dictionary.
public String getDescription(String SKU)
// Deletes the StockItem associated with the SKU if it is
// in the ProductLookup. Returns true if it was found and
// deleted, otherwise false.
public boolean deleteItem(String SKU)
// Prints a directory of all StockItems with their associated
// price, in sorted order (ordered by SKU).
public void printAll()
// Prints a directory of all StockItems from the given vendor,
// in sorted order (ordered by SKU).
public void print(String vendor)
// An iterator of the SKU keys.
public Iterator<String> keys()
// An iterator of the StockItem values.
public Iterator<StockItem> values()
}
________________________________________
StockItem.java
import java.util.Iterator;
import data_structures.*;
public class StockItem implements Comparable<StockItem> {
String SKU;
String description;
String vendor;
float cost;
float retail;
// Constructor. Creates a new StockItem instance.
public StockItem(String SKU, String description, String vendor,
float cost, float retail)
// Follows the specifications of the Comparable Interface.
// The SKU is always used for comparisons, in dictionary order.
public int compareTo(StockItem n)
// Returns an int representing the hashCode of the SKU.
public int hashCode()
// standard get methods
public string getDescription()
public String getVendor()
public float getCost()
public float getRetail()
// All fields in one line, in order
public String toString()
}
________________________________________
DictionaryADT
/* DictionaryADT.java
Dictionary interface.
*/
package data_structures;
import java.util.Iterator;
import java.util.NoSuchElementException;
public interface DictionaryADT<K extends Comparable<K>,V> {
// Returns true if the dictionary has an object identified by
// key in it, otherwise false.
public boolean contains(K key);
// Adds the given key/value pair to the dictionary. Returns
// false if the dictionary is full, or if the key is a duplicate.
// Returns true if addition succeeded.
public boolean add(K key, V value);
// Deletes the key/value pair identified by the key parameter.
// Returns true if the key/value pair was found and removed,
// otherwise false.
public boolean delete(K key);
// Returns the value associated with the parameter key. Returns
// null if the key is not found or the dictionary is empty.
public V getValue(K key);
// Returns the key associated with the parameter value. Returns
// null if the value is not found in the dictionary. If more
// than one key exists that matches the given value, returns the
// first one found.
public K getKey(V value);
// Returns the number of key/value pairs currently stored
// in the dictionary
public int size();
// Returns true if the dictionary is at max capacity
public boolean isFull();
// Returns true if the dictionary is empty
public boolean isEmpty();
// Returns the Dictionary object to an empty state.
public void clear();
// Returns an Iterator of the keys in the dictionary, in ascending
// sorted order. The iterator must be fail-fast.
public Iterator<K> keys();
// Returns an Iterator of the values in the dictionary. The
// order of the values must match the order of the keys.
// The iterator must be fail-fast.
public Iterator<V> values();
}
Additional Details:
•Your project will consist of exactly the files/classes named in this assignment. You may not have any additional classes or public methods. (Inner classes and private methods are OK).
•The ProductLookup class must have a variable of type DictionaryADT which will be instantiated using your Hashtable class. You must insure that your ProductLookup class works with all three implementations, but turn it in hardcoded to use the Hashtable class. Your ProductLookup class, and all three implementations will be tested with driver programs not available to you.
•For the BinarySearchTree and Hashtable implementations, you must write your own code; you may import only java.util.Iterator, java.util.NoSuchElementException, and java.util.ConcurrentModificationException;
•Your DictionaryADT implementation methods should be as efficient as possible.
•Your iterators must be fail-fast.
•For the red/black tree implementation, you should use the Java API class java.util.TreeMap. For this implementation only, you may use any classes in the Java API.
•Each source code file must begin with your name and class account number (commented out of course). This is a gradable issue.
•Your class names and methods and method signatures must match the specifications exactly.
•Projects that fail to compile will receive very little or no credit.
•Here is DictionaryTester.java a test program for program #4.
/* DictionaryTester.java
Class for testing your DictionaryADT implementation.
NOTE: Not all public methods in the interface are tested.
You are responsible for testing your classes. A test program
not available to you will be used for grading your project.
If your BST class crashes with ordered data, then try setting
a larger stack size with the -Xss switch. ie
java -Xss128M DictionaryTester
*/
import data_structures.*;
public class DictionaryTester {
public static void main(String [] args) {
int DICTIONARY_SIZE = 10000;
String [] testArray = getRandomStrings(DICTIONARY_SIZE);
long start, stop;
DictionaryADT<String,Integer> dictionary;
System.out.println("Testing the Hashtable with randomly ordered data...\n");
dictionary = new Hashtable<String,Integer>(DICTIONARY_SIZE);
for(int i=0; i < DICTIONARY_SIZE; i++)
dictionary.add(testArray[i], new Integer(i));
System.out.println("Now performing " + (DICTIONARY_SIZE*10) +
" searches.");
start = System.currentTimeMillis();
for(int i=0; i < DICTIONARY_SIZE*10; i++) {
int index = ( (int) (DICTIONARY_SIZE*Math.random()));
Integer val = (Integer) dictionary.getValue(testArray[index]);
if(val == null)
throw new RuntimeException(
"ERROR, key " + testArray[index] + " was not found");
if(val.intValue() !=index)
throw new RuntimeException(
"ERROR, wrong value returned, expected " + index +
" but got " + val);
}
stop = System.currentTimeMillis();
System.out.println("TIME: " + (stop-start) + "\n");
System.out.println("Reverse lookups...");
System.out.println("Now performing " + (DICTIONARY_SIZE/10) +
" searches.");
start = System.currentTimeMillis();
for(int i=0; i < DICTIONARY_SIZE/10; i++) {
int index = ( (int) (DICTIONARY_SIZE*Math.random()));
String key = (String) dictionary.getKey(new Integer(index));
if(key == null)
throw new RuntimeException(
"ERROR, key " + testArray[index] + " was not found");
if(!testArray[index].equals(key))
throw new RuntimeException(
"ERROR, wrong key returned, expected " + testArray[index] +
" but got " + key);
}
stop = System.currentTimeMillis();
System.out.println("TIME: " + (stop-start) + "\n");
System.out.println("\nNow testing with ORDERED data...\n");
testArray = getOrderedStrings(DICTIONARY_SIZE);
System.out.println("***************Testing the Hashtable...");
dictionary = new Hashtable<String,Integer>(DICTIONARY_SIZE);
for(int i=0; i < DICTIONARY_SIZE; i++)
dictionary.add(testArray[i], new Integer(i));
System.out.println("Now performing " + (DICTIONARY_SIZE*10) +
" searches.");
start = System.currentTimeMillis();
for(int i=0; i < DICTIONARY_SIZE*10; i++) {
int index = ( (int) (DICTIONARY_SIZE*Math.random()));
Integer val = (Integer) dictionary.getValue(testArray[index]);
if(val == null)
throw new RuntimeException(
"ERROR, key " + testArray[index] + " was not found");
if(val.intValue() !=index)
throw new RuntimeException(
"ERROR, wrong value returned, expected " + index +
" but got " + val);
}
stop = System.currentTimeMillis();
System.out.println("TIME: " + (stop-start) + "\n");
System.out.println("Reverse lookups...");
System.out.println("Now performing " + (DICTIONARY_SIZE/10) +
" searches.");
start = System.currentTimeMillis();
for(int i=0; i < DICTIONARY_SIZE/10; i++) {
int index = ( (int) (DICTIONARY_SIZE*Math.random()));
String key = (String) dictionary.getKey(new Integer(index));
if(key == null)
throw new RuntimeException(
"ERROR, key " + testArray[index] + " was not found");
if(!testArray[index].equals(key))
throw new RuntimeException(
"ERROR, wrong key returned, expected " + testArray[index] +
" but got " + key);
}
stop = System.currentTimeMillis();
System.out.println("TIME: " + (stop-start) + "\n");
}
private static String[] getOrderedStrings(int size) {
String [] array = getRandomStrings(size);
array = shellSort(array);
return array;
}
//This method generates a random string of the form:
// ABC123. The digits on the end will be mostly zero.
private static String[] getRandomStrings(int size) {
String [] str = new String[size];
String temp = "";
int where=0;
byte [] b = {0x41,0x41,0x41,0x30,0x30,0x30};
for(int i=0; i < 10; i++)
for(int j=0; j < 10; j+=(int)2*Math.random()+1)
for(int k=0; k < 10; k+=(int)2*Math.random()+1)
for(int l=0; l < 26; l+=(int)2*Math.random()+1)
for(int m=0; m < 26; m+=(int) 2*Math.random()+1)
for(int n=0; n < 26; n++) {
if(where >= size) break;
str[where++] = ""+
((char)(b[0]+n)) +
((char)(b[1]+m)) +
((char)(b[2]+l)) +
((char)(b[3]+k)) +
((char)(b[4]+j)) +
((char)(b[5]+i));
}
for(int i=0; i < size; i++) {
int index = ( (int) (size*Math.random()));
String tmp = str[index];
str[index] = str[i];
str[i] = tmp;
}
return str;
}
private static String[] shellSort(String n[]) {
if(n.length < 2)
return n;
int in=0, out=0, h=1;
String temp=null;
int size = n.length;
while(h <= size/3)
h = h*3+1;
while(h > 0) {
for(out=h; out < size; out++) {
temp = n[out];
in = out;
while(in > h-1 &&
((Comparable)n[in-h]).compareTo(temp) >= 0) {
n[in] = n[in-h];
in -= h;
}
n[in] = temp;
} // end for
h = (h-1)/3;
} // end while
return n;
}
}
•Here is ProductTester.java, a sample test program for your ProductLookup class.
public class ProductTester {
private ProductLookup lookup;
public ProductTester(int maxSize) {
lookup = new ProductLookup(maxSize);
runTests();
lookup.printAll();
}
private void runTests() {
StockItem item = new StockItem("AGT-1234","Runner","Nike",37.15f,79.95f);
lookup.addItem("AGT-1234",item);
}
public static void main(String [] args) {
new ProductTester(1000);
}
}