Object oriented design for a Restaurant

Let we start to design Object Oriented architecture of restaurant. Before start the design, we need to understand how a restaurant works.

Components required:

Customer

            Name

            Contact

selectDish(): Dish

Selects the dish from the menu.

callWaiter(): call upon a waiter.

placeOrder(d:Dish): Places the order and enjoy his meal once the dish is served on his table.

requestBill(): Ask for the bill to the waiter.

makePayment(): Pays for the services.

Waiter

            Name

            EmpId

            TableToWait

respondToCustomer(): Response to the customer’s calls on the tables he is waiting.

takeOrder(): Take the customer's order.

placeOrderToQueue(o:Order): Place the order in PendingOrderQueue.

handleOrderPreparedNotification(): Observer design pattern for notification

Wait for the order ready notifications.

serveDishToCustomer(d:Dish): Once notification is received, collects the dish and serves the dish to the corresponding customer.

takeBillRequest(): Receive the bill request from the customer.

acceptPayment(): Ask the Cashier to prepare the bill.

payMoneyToCashier(): Gives the bill to the customer and accepts the payment.

Chef

            EmpId

prepareDish(d:Dish): Get the next order from the PendingOrderQueue.

placeOrderInFinishedQueue(): Prepares the dish and push the order to finished order queue.

notifyOrderComplete(): Observer design pattern for notification

Send a notification that the order is ready.

Cashier

            Name

            EmpId

prepareBill(o:Order): Accepts the prepare bill request from the waiter for the given order details. Prepares the bills and hands it over to the waiter.

acceptPayment(): Accept the cash from the waiter towards the order.

Order (DTO)

            id

            Dish

Data structure used:

PendingOrderQueue

addOrder(o:Order): Waiter will place the order in the PendingOrderQueue.

getNextOrder(): Chef gets the next order from the PendingOrderQueue.

FinishedOrderQueue

getFinishedOrder(o:Order): Chef will prepare the dish and push the order to FinishedOrderQueue. 

poll(), peek() and remove() Method in the Queue

String java.util.PriorityQueue.poll()

Retrieves and removes the head of this queue, or returns null if this queue is empty.

Specified by: poll() in Queue

Returns: the head of this queue, or null if this queue is empty

String java.util.PriorityQueue.peek()

Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

Specified by: peek() in Queue

Returns: the head of this queue, or null if this queue is empty

String java.util.AbstractQueue.remove()

Retrieves and removes the head of this queue. This method differs from poll only in that it throws an exception if this queue is empty.

Specified by: remove() in Queue

Returns: the head of this queue

Throws: NoSuchElementException - if this queue is empty

poll() vs remove() Method in the Queue

String java.util.PriorityQueue.poll()

Retrieves and removes the head of this queue, or returns null if this queue is empty.

Specified by: poll() in Queue

Returns: the head of this queue, or null if this queue is empty

String java.util.AbstractQueue.remove()

Retrieves and removes the head of this queue. This method differs from poll only in that it throws an exception if this queue is empty.

Specified by: remove() in Queue

Returns: the head of this queue

Throws: NoSuchElementException - if this queue is empty.

PiorityQueue in Java

PiorityQueue(=belongs to the Java Collections Framework) is an unbounded Queue, which is based on  priority heap and it is an implementation of Queue interface. It can be used to keep elements in a particular order, according to their natural order (=Comparable) or custom order defined by Comparator interface based on each element’s priority.

PriorityQueue is not synchronized i.e. it cannot be safely shared between multiple threads. To avoid the Concurrent Modification Exception, PriorityBlockingQueue(= thread-safe) can be used in multithreaded environment.

Priority queue provides O(log(n)) time performance for common enqueing and dequeing methods e.g. offer(), poll() and add(), but constant time for retrieval methods e.g. peek() and element().

It was introduced in JDK 1.5.

Java PriorityQueue key points:

1. A Comparator can be provided in the constructor when instantiating a PriorityQueue. Then the order of the items in the Queue will be decided based on the Comparator provided.

public PriorityQueue(intinitialCapacity,

                         Comparator<? super E> comparator)

If a Comparator is not provided, then the natural order (Comparable) of the Collection will be used to order the elements.

2. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

3. null is not allowed in this Collection. It will throw the NullPointerException.

4. The head of this queue is the least element with respect to the specified ordering.

5. Ordering ties between the PriorityQueue elements are decided arbitrarily (=on the basis of random choice).

5. PriorityQueue is not synchronized. PriorityBlockingQueue is the thread-safe counterpart of PriorityQueue.

6. PriorityQueue is unbounded and it grows dynamically based on the number of elements in the Queue. It has internal capacity at any given time and it is increased as the elements are added. The policy for this internal capacity and increment is not specified or standardized.

7. The iterator() of this PriorityQueue does not guarantee for traversal of the Queue elements in any particular order.

PriorityQueueTest.java

import java.util.PriorityQueue;

import java.util.Queue;

public classPriorityQueueTest {

      public static void main(String args[]) {

            Queue<MobilePhone> items = new PriorityQueue<MobilePhone>();

            items.add(new MobilePhone("Samsung", 100));

            items.add(new MobilePhone("Iphone", 400));

            items.add(new MobilePhone("Blackberry", 200));

            items.add(new MobilePhone("HTC", 300));

            System.out.println("Mobiles phones list: ");

            System.out.println(items);

      }

}

class MobilePhone implementsComparable<MobilePhone> {

     

      private String name;

      private int price;

      public MobilePhone(String name, int price) {

            this.name = name;

            this.price = price;

      }

      public String getName() {

            return name;

      }

      @Override

      public int compareTo(MobilePhone phone) {

            return this.price - phone.price;

      }

      @Override

      public String toString() {

            return String.format("Brand:%s Price: $%d", name, price);

      }     

}

References:

https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

Maximum Subarray Sum: Kadane's algorithm

Kadane's algorithm

Kadane's algorithm consists of a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position.

Usage of Kadane's algorithm         

It is used to obtain the maximum subarray sum from an array of integers.

Pseudo code:

Initialize: max_so_far = 0

max_ending_here = 0

Loop for each element of the array

               max_ending_here = max_ending_here + a[i]

               if(max_ending_here < 0)

                              max_ending_here = 0

               if(max_so_far < max_ending_here)

                              max_so_far = max_ending_here

return max_so_far

Code in Java:

import java.util.Scanner;

/* Class kadane */

public class KadaneAlgorithm {

      /* Function to largest continuous sum */

      public static intmaxSequenceSum(int[] arr) {       

            int maxSoFar = arr[0], maxEndingHere = arr[0];

            for (inti= 1; i< arr.length; i++) {

                 

                  /* calculate maxEndingHere */

                  if (maxEndingHere < 0) {

                        maxEndingHere = arr[i];

                  } else {

                        maxEndingHere += arr[i];

                  }

                  /* calculate maxSoFar */

                  if (maxEndingHere >= maxSoFar) {

                        maxSoFar= maxEndingHere;

                  }

            }

            return maxSoFar;

      }

      public static void main (String[] args) {

            int[] arr = {8,6,5,-19,-24,2,8,9,14,-1,7};

            int sum = KadaneAlgorithm.maxSequenceSum(arr);

            System.out.println("Maximum Sequence sum is: "+ sum);

      }

}

Output: Maximum Sequence sum is: 39