Understand Priority Queue and Hash Table Data Structures in Java

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; } }