Understand Priority Queue and Hash Table Data Structures in Java
- Instructions
- Requirements and Specifications
Instructions
Objective
Write a java assignment to understand and implement priority queue and hash table data structures.
Requirements and Specifications
Source Code
ADD PRODUCT
package warehouse;
/*
* Use this class to test to addProduct method.
*/
public class AddProduct {
public static void main(String[] args) {
StdIn.setFile(args[0]);
StdOut.setFile(args[1]);
// Use this file to test addProduct
Warehouse warehouse = new Warehouse();
int n = Integer.parseInt(StdIn.readLine());
for (int i = 0; i
String[] parts = StdIn.readLine().split("\\s+");
warehouse.addProduct(Integer.parseInt(parts[1]), parts[2], Integer.parseInt(parts[3]),
Integer.parseInt(parts[0]), Integer.parseInt(parts[4]));
}
StdOut.println(warehouse);
}
}
DELETE PRODUCT
package warehouse;
/*
* Use this class to test the deleteProduct method.
*/
public class DeleteProduct {
public static void main(String[] args) {
StdIn.setFile(args[0]);
StdOut.setFile(args[1]);
// Use this file to test deleteProduct
Warehouse warehouse = new Warehouse();
int n = Integer.parseInt(StdIn.readLine());
for (int i = 0; i
String[] parts = StdIn.readLine().split("\\s+");
if (parts[0].equals("add")) {
warehouse.addProduct(Integer.parseInt(parts[2]), parts[3], Integer.parseInt(parts[4]),
Integer.parseInt(parts[1]), Integer.parseInt(parts[5]));
}
else {
warehouse.deleteProduct(Integer.parseInt(parts[1]));
}
}
StdOut.println(warehouse);
}
}
EVERYTHING
package warehouse;
/*
* Use this class to put it all together.
*/
public class Everything {
public static void main(String[] args) {
StdIn.setFile(args[0]);
StdOut.setFile(args[1]);
// Use this file to test all methods
Warehouse warehouse = new Warehouse();
int n = Integer.parseInt(StdIn.readLine());
for (int i = 0; i
String[] parts = StdIn.readLine().split("\\s+");
if (parts[0].equals("add")) {
warehouse.addProduct(Integer.parseInt(parts[2]), parts[3], Integer.parseInt(parts[4]),
Integer.parseInt(parts[1]), Integer.parseInt(parts[5]));
}
else if (parts[0].equals("purchase")){
warehouse.purchaseProduct(Integer.parseInt(parts[2]), Integer.parseInt(parts[1]), Integer.parseInt(parts[3]));
}
else if (parts[0].equals("restock")){
warehouse.restockProduct(Integer.parseInt(parts[1]), Integer.parseInt(parts[2]));
}
else if (parts[0].equals("delete")){
warehouse.deleteProduct(Integer.parseInt(parts[1]));
}
}
StdOut.println(warehouse);
}
}
PRODUCT
package warehouse;
/*
* This class represents a warehouse Product.
*
* @author Ishaan Ivaturi
*
*/
public class Product {
private int id; // product identification
private String name; // product name
private int stock; // number of items in stock
private int lastPurchaseDay; // the number of days since the store opening that the item was last purchased
private int demand; // initial demand is obtained from a survey prior to product release
private int popularity; // Initial Demand + Total Amount Purchased + Date of Last Purchase
public Product(int i, String n, int s, int l, int d) {
id = i;
name = n;
stock = s;
lastPurchaseDay = l;
demand = d;
popularity = l + d;
}
public Product(int i, String n, int s, int l) {
this(i, n, s, l, 0);
}
public Product(int i, String n) {
this(i, n, 0, 0);
}
public int getId() {
return id;
}
public String getName() { return name; }
public int getStock() { return stock; }
public int getLastPurchaseDay() { return lastPurchaseDay; }
public int getDemand() { return demand; }
public int getPopularity() { return popularity; }
public void setId(int i) { id = i; }
public void setName(String n) { name = n; }
public void updateStock(int s) { stock += s; }
public void setStock(int s) { stock = s; }
public void setLastPurchaseDay(int l) {
lastPurchaseDay = l;
popularity = lastPurchaseDay + demand;
}
public void updateDemand(int d) {
demand += d;
popularity = lastPurchaseDay + demand;
}
public void setDemand(int d) {
demand = d;
popularity = lastPurchaseDay + demand;
}
/*
* Returns true if this object equals other
*/
public boolean equals (Object other) {
if ( !(other instanceof Product) ) {
return false;
}
Product o = (Product) other;
return this.getId() == o.getId();
}
public String toString() {
return String.format("(%s: %d, %d)", name, stock, popularity);
}
}
PURCHASE PRODUCT
package warehouse;
public class PurchaseProduct {
public static void main(String[] args) {
StdIn.setFile(args[0]);
StdOut.setFile(args[1]);
// Use this file to test purchaseProduct
Warehouse warehouse = new Warehouse();
int n = Integer.parseInt(StdIn.readLine());
for (int i = 0; i
String[] parts = StdIn.readLine().split("\\s+");
if (parts[0].equals("add")) {
warehouse.addProduct(Integer.parseInt(parts[2]), parts[3], Integer.parseInt(parts[4]),
Integer.parseInt(parts[1]), Integer.parseInt(parts[5]));
}
else {
warehouse.purchaseProduct(Integer.parseInt(parts[2]), Integer.parseInt(parts[1]), Integer.parseInt(parts[3]));
}
}
StdOut.println(warehouse);
}
}
RESTOCK
package warehouse;
public class Restock {
public static void main(String[] args) {
StdIn.setFile(args[0]);
StdOut.setFile(args[1]);
// Uset his file to test restock
Warehouse warehouse = new Warehouse();
int n = Integer.parseInt(StdIn.readLine());
for (int i = 0; i
String[] parts = StdIn.readLine().split("\\s+");
if (parts[0].equals("add")) {
warehouse.addProduct(Integer.parseInt(parts[2]), parts[3], Integer.parseInt(parts[4]),
Integer.parseInt(parts[1]), Integer.parseInt(parts[5]));
}
else {
warehouse.restockProduct(Integer.parseInt(parts[1]), Integer.parseInt(parts[2]));
}
}
StdOut.println(warehouse);
}
}
SECTOR
package warehouse;
public class Sector {
private Product[] products;
private int currentSize;
public Sector() {
products = new Product[6];
currentSize = 0;
}
// Add an item to the end of the sector, index 0 is ignored
public void add(Product prod) {
products[currentSize+1] = prod;
currentSize++;
}
// Set some index, valid indices are from 1 to currentSize inclusive
public void set(int index, Product prod) {
products[index] = prod;
}
// Delete the last element currently stored
public void deleteLast() {
products[currentSize] = null;
currentSize--;
}
// Get the product at some index
public Product get(int index) {
return products[index];
}
// Get the current size
public int getSize() {
return currentSize;
}
// Swap the items at 2 indices
public void swap(int index1, int index2) {
Product temp = products[index1];
products[index1] = products[index2];
products[index2] = temp;
}
// Apply the swim algorithm from class on some index
public void swim(int index) {
while (index > 1 && products[index].getPopularity() < products[index/2].getPopularity()) {
swap(index, index/2);
index /= 2;
}
}
// Apply the sink algorithm from class on some index
public void sink(int index) {
while (index*2 <= currentSize) {
int smallestChild;
if (index*2 + 1 > currentSize
|| products[index*2].getPopularity() < products[index*2 + 1].getPopularity()) {
smallestChild = index*2;
}
else smallestChild = index*2 + 1;
if (products[index].getPopularity() > products[smallestChild].getPopularity()) {
swap(index, smallestChild);
index = smallestChild;
}
else break;
}
}
public String toString() {
String sectorString = "{";
sectorString += "null";
for (int i = 1; i <= currentSize; i++) {
sectorString += "; " + products[i].toString();
}
return sectorString + "}";
}
}
WAREHOUSE
package warehouse;
/*
*
* This class implements a warehouse on a Hash Table like structure,
* where each entry of the table stores a priority queue.
* Due to your limited space, you are unable to simply rehash to get more space.
* However, you can use your priority queue structure to delete less popular items
* and keep the space constant.
*
* @author Ishaan Ivaturi
*/
public class Warehouse {
private Sector[] sectors;
// Initializes every sector to an empty sector
public Warehouse() {
sectors = new Sector[10];
for (int i = 0; i < 10; i++) {
sectors[i] = new Sector();
}
}
/**
* Provided method, code the parts to add their behavior
* @param id The id of the item to add
* @param name The name of the item to add
* @param stock The stock of the item to add
* @param day The day of the item to add
* @param demand Initial demand of the item to add
*/
public void addProduct(int id, String name, int stock, int day, int demand) {
evictIfNeeded(id);
addToEnd(id, name, stock, day, demand);
fixHeap(id);
}
/**
* Add a new product to the end of the correct sector
* Requires proper use of the .add() method in the Sector class
* @param id The id of the item to add
* @param name The name of the item to add
* @param stock The stock of the item to add
* @param day The day of the item to add
* @param demand Initial demand of the item to add
*/
private void addToEnd(int id, String name, int stock, int day, int demand) {
Product newProduct = new Product(id, name, stock, day, demand);
Sector sector = sectors[id % 10];
sector.add(newProduct);
}
/**
* Fix the heap structure of the sector, assuming the item was already added
* Requires proper use of the .swim() and .getSize() methods in the Sector class
* @param id The id of the item which was added
*/
private void fixHeap(int id) {
Sector sector = sectors[id % 10];
sector.swim(sector.getSize());
}
/**
* Delete the least popular item in the correct sector, only if its size is 5 while maintaining heap
* Requires proper use of the .swap(), .deleteLast(), and .sink() methods in the Sector class
* @param id The id of the item which is about to be added
*/
private void evictIfNeeded(int id) {
Sector sector = sectors[id % 10];
if (sector.getSize() >= 5) {
sector.swap(1, sector.getSize());
sector.deleteLast();
sector.sink(1);
}
}
/**
* Update the stock of some item by some amount
* Requires proper use of the .getSize() and .get() methods in the Sector class
* Requires proper use of the .updateStock() method in the Product class
* @param id The id of the item to restock
* @param amount The amount by which to update the stock
*/
public void restockProduct(int id, int amount) {
Sector sector = sectors[id % 10];
for (int i = 1; i<=sector.getSize(); i++) {
if (sector.get(i).getId() == id) {
sector.get(i).updateStock(amount);
return;
}
}
}
/**
* Delete some arbitrary product while maintaining the heap structure in O(logn)
* Requires proper use of the .getSize(), .get(), .swap(), .deleteLast(), .sink() and/or .swim() methods
* Requires proper use of the .getId() method from the Product class
* @param id The id of the product to delete
*/
public void deleteProduct(int id) {
Sector sector = sectors[id % 10];
for (int i = 1; i<=sector.getSize(); i++) {
if (sector.get(i).getId() == id) {
sector.swap(i, sector.getSize());
sector.deleteLast();
Product p = sector.get(i);
if (p != null) {
sector.swim(i);
if (sector.get(i) == p) {
sector.sink(i);
}
}
return;
}
}
}
/**
* Simulate a purchase order for some product
* Requires proper use of the getSize(), sink(), get() methods in the Sector class
* Requires proper use of the getId(), getStock(), setLastPurchaseDay(), updateStock(), updateDemand() methods
* @param id The id of the purchased product
* @param day The current day
* @param amount The amount purchased
*/
public void purchaseProduct(int id, int day, int amount) {
Sector sector = sectors[id % 10];
for (int i = 1; i<= sector.getSize(); i++) {
if (sector.get(i).getId() == id) {
Product p = sector.get(i);
if (p.getStock() >= amount) {
p.setLastPurchaseDay(day);
p.updateStock(-amount);
p.updateDemand(amount);
sector.sink(i);
}
}
}
}
/**
* Construct a better scheme to add a product, where empty spaces are always filled
* @param id The id of the item to add
* @param name The name of the item to add
* @param stock The stock of the item to add
* @param day The day of the item to add
* @param demand Initial demand of the item to add
*/
public void betterAddProduct(int id, String name, int stock, int day, int demand) {
int startSector = id % 10;
for (int i = 0; i<10; i++) {
Sector currSector = sectors[(startSector + i) % 10];
if (currSector.getSize() < 5) {
currSector.add(new Product(id, name, stock, day, demand));
currSector.swim(currSector.getSize());
return;
}
}
addProduct(id, name, stock, day, demand);
}
/*
* Returns the string representation of the warehouse
*/
public String toString() {
String warehouseString = "[\n";
for (int i = 0; i < 10; i++) {
warehouseString += "\t" + sectors[i].toString() + "\n";
}
return warehouseString + "]";
}
/*
* Do not remove this method, it is used by Autolab
*/
public Sector[] getSectors () {
return sectors;
}
}
Similar Samples
At ProgrammingHomeworkHelp.com, we offer expert assistance with a wide range of programming assignments. Our skilled professionals are dedicated to delivering high-quality, timely solutions tailored to your academic needs. Trust us to help you excel in your programming courses.
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java