C++ Data Structure programming assignment. Simulate a grocery delivery service.
Lab 4 - Order, She Wrote Introduction In the dot-com boom and bust, several big-name ecommerce companies promised that they would deliver anything to anyone in less than hour. They (https://en.wikipedia.org/wiki/Kozmo.com) went spectacularly bankrupt (https://en.wikipedia.org/wiki/Webvan) spectacularly quickly! Just two decades later, Instacart, Uber Eats, Grubhub, Gopuff, and many others are trying again. We’ll see how well they do this time (https://www.wsj.com/articles/losses-mount-for-startups- racing-to-deliver-groceries-fast-and-cheap-11643544004? st=ax88qjtbxz7e6lg&reflink=desktopwebshare_permalink) . Although we aren’t getting part of their VC money (https://news.crunchbase.com/news/most-active- vc-startup-investors-tiger-global-softbank-y-combinator/) , attrac++d (pronounced attracted) is paying us to write an order management system. They want a system that will allow them to calculate when a particular courier can handle delivering a particular order. There are two types of orders that attrac++d users can place: 1. A buy-one-get-something-free (Bogo) order: The Bogo order always contains two items. Once the user selects the item they are going to buy (the “paid” item) and the item they want for free (the “free” item), they cannot change their order. 2. A flexible order: The flexible order allows users to purchase as many items as they want. However, attrac++d customers are not allowed to hoard – no duplicate items are allowed in any of the orders. attrac++d users can add and remove items from their order as often as they want. Couriers are defined by the number of items they can store in their vehicle. If a courier’s vehicle can hold more items than are in an order, they can take that order. Otherwise, they cannot. https://en.wikipedia.org/wiki/Kozmo.com https://en.wikipedia.org/wiki/Webvan https://www.wsj.com/articles/losses-mount-for-startups-racing-to-deliver-groceries-fast-and-cheap-11643544004?st=ax88qjtbxz7e6lg&reflink=desktopwebshare_permalink https://news.crunchbase.com/news/most-active-vc-startup-investors-tiger-global-softbank-y-combinator/ We get paid by the job and not by the hour – let’s get started. Attrac++d ADTs Recall our discussion in class about abstract data types (ADTs). ADTs are “a collection of data and a set of operations on that data”. As the textbook author is at pains to remind us, an ADT is not a data structure. In a sense, the ADT precedes the data structure. A data structure is a means of implementing an ADT. Based on the description of the problem, it seems like we need two ADTs: 1. The item that the user wants to buy. 2. The order that the user wants delivered. As for the collection of data for each ADT, 1. the item contains a string that names the item, and 2. the order contains a number of items. We can refine the order ADT into further: 1. The Bogo order 2. The flexible order These refined order ADTs contain the same data as their parent, the generic order. As for the operations for each ADT, 1. the item has a single operation, getItemName, that allows its user to query for the item’s name, and 2. the order has several operations, defined below. Based on the preceding description, a Bogo order does not need any mutators. It does however, need an accessor, size: 1. Bogo size: Return the number of items in a Bogo order – always 2. The flexible order, on the other hand, needs two mutators: 1. Flexible order remove: Remove a single item, given as a parameter, from the order. 2. Flexible order add: Add a single item, given as a parameter, to the order. The flexible order also needs an accessor: 1. Flexible order size: Return the number of items in a flexible order. Both the Bogo- and the flexible-order ADT specify a size operation. It makes sense to define that operation on the base class, then, and let each of the refined order types override the implementation to customize their specific behavior. Attrac++d Courier Algorithm The courier calculation system is relatively straightforward. Again, each courier can handle a certain number of items in their car. If the software system we build for attrac++d assigns a courier to deliver an order that contains too many items, that courier will have to smash them in their trunk! Needless to say, attrac++d’s ratings on Yelp! will suffer. To make sure that orders are assigned to compatible couriers, we will implement a Boolean-valued function that takes two parameters: 1. The size of the courier’s car 2. An order. The function will return true if the size of the order is less than or equal to the size of the courier’s car. Attrac++d Implementation The staff engineers at attrac++d have given us an implementation of the Item ADT as a C++ class named Item . Their implementation is in include/ordershewrote/item.hpp . It has several important features: 1. Two objects of the Item type can be compared for equality ( == ) and inequality ( != ). This feature will help us prevent hoarders placing a flexible order with more than one of the same item. It will also make it easier for us to find the item a user asks to remove from their order. 2. The name of the Item is represented as a std::string which can be accessed using the getItemName() member function. After presenting our order ADT design to attrac++d’s devops team, we were given an interface to which to adhere so that our code integrates with their workflow. We cannot deviate from their specification if they have any hope of maintaining their system’s 0-9s reliability. Order (Base Class) The Order base class contains only one function, size , a pure-virtual function that returns an int that holds the size of the order. A pure-virtual function is a function in a base class that has no definition and, therefore, must be implemented by a derived class. An object cannot be instantiated from a class that contains one or more pure-virtual functions. A class with one or more pure-virtual functions is known as an abstract class. A derived class must implement an abstract class’ pure- virtual function before it can be instantiated. The Bogo and FlexibleOrder derived classes will do just that, and more. The Bogo Derived Class The Bogo class is derived from Order . It must implement size . The Bogo class should also have a constructor that takes two Item s by “const reference”: 1. The Item the user is paying for; and 2. The Item that the user is getting for free. The Bogo class should store those in private member variables in case we need to add additional member functions later to support additions to the Bogo-order ADT. For more information on "const reference" (member) function parameters, see Walls and Mirrors pp. 724 - 726 or the C++ Core Guidelines discussion on the topic (https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rf-in) . The FlexibleOrder Derived Class The FlexibleOrder class is also derived from Order . It, too, must implement size . The FlexibleOrder class should also contain implementations of member functions that match the flexible-order ADT’s operations: 1. add : add takes a parameter of type Item by “const reference”. The object of type Item passed as a parameter to the add member function should be added to the FlexibleOrder only as long as it is not already in the order. Remember, two Item s can be compared using the == and != operators. 2. remove : remove takes a parameter of type Item by “const reference”. The object of type Item passed as a parameter to the remove member function is removed from the FlexibleOrder if it is present. Note: In order to game the system, some users may try to remove items from an order that don’t exist. In this case, the member function should not make any changes to the order. Remember, two Item s can be compared using the == and != operators. The FlexibleOrder class must store the objects of type Item that comprise the order in a dynamically allocated array. This requirements means that you cannot store the Item s that make up a flexible order using a std::vector . When an object of type FlexibleOrder is destroyed, all of its dynamically allocated memory must be properly released. canCourierTake Implementation The final implementation task is to define a canCourierTake function. canCourierTake returns a bool . canCourierTake accepts two parameters: 1. An object of type Order by “const reference” that is the order to be delivered. Because we are using inheritance and the parameter is of type Order , the actual argument passed by “const reference” can be either an instance of a Bogo or FlexibleOrder . It is vital that canCourierTake takes this parameter by “const reference”. Remember earlier we discussed how the Order class was abstract? You cannot use abstract classes as the type of a pass-by-value parameter to a function because the mechanism by which the compiler affects a pass-by-value function call https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rf-in requires that the class be constructed – something we said earlier was impossible! There is no such requirement if you define the parameter as a reference and use pass-by-reference semantics. 2. An int value that indicates the number of items that can fit in the courier’s car. The canCourierTake function returns true if the number of items in the order is less than or equal to the number of items that can fit in the courier’s car and false otherwise. Programming Task and Requirements Your programming task for this lab is to implement the classes, member functions and functions described above. Your implementation must precisely follow the specifications defined in the preceding section. Start with this skeleton (https://uc.instructure.com/courses/1519734/files/152735095?wrap=1) (https://uc.instructure.com/courses/1519734/files/152735095/download?download_frd=1) ! Because there are no class templates to define, you should separate your interface from your implementation – the best practice in C++ (see Walls and Mirrors p. 32). A file named order.cpp has been provided for you in the skeleton for this reason. (You can define the Order , Bogo and FlexibleOrder classes all in the same implementation file!) Place the implementation of the canCourierTake function in include/ordershewrote/cancouriertake.hpp . Examples Assuming that you have properly defined all the classes, member functions and functions, the code in the main function of main.cpp from the skeleton should print Courier can take the Bogo order! Critical-Thinking Task and Requirements We spent a significant amount of time in class discussing the difference between automatic and dynamic variables, and the heap and the stack. With respect to the description above, consider this code: int main() { FlexibleOrder forder{}; Item item1{"banana"}, item2{"natural peanut butter"}; forder.add(item1); forder.add(item2); ... return 0; } Assume that this program is paused during execution at the ... . Your critical-thinking task is to describe how forder is arranged in memory at that moment