Programming Assignment 1: Representing, Managing and Manipulating Travel Options

You may NOT do any of the following:

• change any of the function names or signatures (parameter lists and types and return type)

• introduce any global or static variables

• use any arrays or vectors inside the TravelOptions class! Not for this assignment!! (You may use them as you see fit in any driver/tester programs you write)

You MAY do any of the following as you see fit:

• Introduce helper functions. But you should make them private.

Reminders: Some functions eliminate list entries (e.g., prune_sorted). Don't forget to deallocate the associated nodes (using the delete operator).

Please read the below code and complete the missing parts.

/**

* func: prune_sorted

* precondition: given collection must be sorted (if not, false is returned).

* desc: takes sorted list of options and removes dominated entries

* (and eliminates any duplicates).

* RUNTIME: linear in the length of the list (O(n))

* COMMENTS: the resulting list will be sorted AND pareto.

* status: TODO

*

*/

bool prune_sorted(){

if(!is_sorted()) return false;

return true;

}

/**

* func: join_plus_plus

* preconditions: none -- both the calling object and parameter are just TravelOptions objects (not necessarily

* sorted or pareto).

* param: other; a reference to another to a list of TravelOptions (thus, there are two option lists: the calling

* object and the parameter).

* desc: suppose you are planning a trip composed of two "legs":

*

* first you travel from city X to city Y (this is part of your plan - you need to stop in city Y)

* then you continue from city Y to city Z

*

* Let the calling object be the options for the X-to-Y leg and the parameter be the options for the

* Y-to-Z leg.

*

* Your job is to construct a pareto-sorted set of options for the entire trip and return the resulting

* TravelOptions object as a pointer.

*

* In principle, any option for the X-to-Y leg can be paird with any option for the Y-to-Z leg.

* In such a pairing, the total price will be p1+p2 and the total time will be t1+t2, (i.e., option ).

* (This is why the operation is called join_plus_plus)

*

* This function's job is to determine the sorted-pareto list of options for the entire trip and return it

* as a pointer to the object.

* returns: a pointer to a TravelOptions object capturing all non-dominated options for the entire trip from X-to-Z

* (i.e., even though the given lists may not be sorted or pareto, the resulting list will be both).

*

* status: TODO

* RUNTIME: no runtime requirement

*

* TIPS:

* Start by thinking about the "cross-product" of the two option lists (i.e., enumerating all pairs).

* Leverage some of the other operations in this assignment -- insert_pareto_sorted might be especially useful!

* (probably ought to implement any functions you plan on using first!).

* Don't overthink this one -- there is no runtime requirement after all.

*

* BOUNDARY CONDITIONS: it is possible that one of both of the given option lists is empty! The result is still

* well-defined (also empty). An empty option list is NOT the same as a null pointer though -- you should still return

* a pointer to a new TravelOptions object -- that object just happens to have an empty list.

*/

TravelOptions * join_plus_plus(const TravelOptions &other) const {

return nullptr; // placeholder to make the compiler happy

}

/**

* func: join_plus_max

* preconditions: both the calling object and the parameter are sorted-pareto lists (if not, nullptr is returned).

* desc: imagine a different scenario (vs. join_plus_plus): you are a parent with two children -- one living in city A and

* the other living in city C -- and they are both coming home for the holidays (let's call your home C).

* You have a pareto-sorted option list for the A-to-C trip (this is the calling object) and a pareto-sorted option list

* for the B-to-C trip.

* Consider a particular option for the A-to-C trip and a particular option for the B-to-C trip .

* Clearly, the total price for selecting these two options is p1+p2.

* However (unlike in the plus_plus case), adding the t1 and t2 doesn't make sense right (the trips are in "parallel").

* What you care about as a parent is when BOTH of your children are home. This is determine by MAX(t1,t2).

* Thus, the resulting "composite" option in this case would be (hence the name join_plus_max).

*

* Your job is to construct the sorted-pareto "composite" option list capturing the options for getting both children home.

* The resulting TravelOptions object is returned as a pointer (recall if the preconditions are not met,

* nullptr is returned).

*

* RUNTIME: let N and M be the lengths of the respective lists given; your runtime must be linear in N+M (O(N+M)).

*

* status: TODO

*

* TIPS:

* This one will take some thought! If the specified runtime is possible, the resulting option list cannot be too

* large right (at most N+M in length)? But there NxM possible pairing of options. So enummerating all pairs

* of options cannot be an option (as was suggested for the _plus_plus case).

*

* Start by figuring out what the FIRST (cheapest) option in the resulting list MUST be.

* Remember that a sorted-pareto list must be strictly increasing in price and strictly decreasing in time.

* Now think about what might be the 2nd option in the list you are building. It must cost more than the first AND

* take less time. To be more concrete, suppose your first option has total price of $100 and results in child A

* traveling for 12 hours and child B traveling for 8 hours. Does it make sense to spend more money on child B

* so they can get home in say 7 hours? Think about it! The MAX function is important!

*/

TravelOptions * join_plus_max(const TravelOptions &other) const {

if(!is_pareto() || !(other.is_pareto()))

return nullptr;

return nullptr;

}

/**

* func: sorted_clone

* desc: returns a sorted TravelOptions object which contains the same elements as the current object

* status: DONE [but relies on to do item insert_sorted]

*/

TravelOptions * sorted_clone() {

TravelOptions *sorted = new TravelOptions();

Node *p = front;

while(p != nullptr) {

sorted->insert_sorted(p->price, p->time);

p = p->next;

}

return sorted;

}

/**

* func: split_sorted_pareto

* precondition: given list must be both sorted and pareto (if not, nullptr is returned;

* code already given).

* desc: This function takes a sorted-pareto option list and splits into two option lists:

*

* - the options with price less than or equal to max_price (if any) are retained in the calling

* object (and only those are retained in the calling object).

* - the other, more expensive options are used to populate a new TravelOptions object which

* is returned as a pointer (i.e., the expensive options are returned)..

*

* returns: pointer to expensive options or nullptr if the calling object is not pareto-sorted.

* RUNTIME: linear in the length of the given list (O(n)).

* ADDITIONAL REQUIREMENT: for full credit you MAY NOT ALLOCATE ANY NEW NODES! Think about it --

* suppose your given list has 100 options and 40 of them are below the max_price threshold;

* the other 60 options end up in the returnd list. Still a grand total of 100 options and

* therefore 100 nodes. So... there should be no reason to delete or allocate any nodes.

* status: TODO

*/

TravelOptions * split_sorted_pareto(double max_price) {

if(!is_pareto_sorted())

return nullptr;

return nullptr; // placeholder to make compiler happy with skeleton

}

/**

* func: display

* desc: prints a string representation of the current TravelOptions object

* status: DONE

*/

void display(){

printf(" PRICE TIME ");

printf("--------------------- ");

Node * p = front;

while(p!=nullptr) {

printf(" %5.2f %5.2f ", p->price, p->time);

p = p->next;

}

}

/**

* func: checksum

* desc: Performs and XOR of all node pointers and returns result as

* an unsigned int.

*

* status: DONE

*

* NOTES: YOU MAY NOT TOUCH OR MODIFY THIS FUNCTION!!

*/

unsigned long int checksum() const {

unsigned long int s = 0;

Node *p = front;

while (p != nullptr)

{

s = s ^ ((unsigned long int)p);

p = p->next;

}

return s;

}

};

#endif