// the code is too long so i have posted the first half already and this would be the second half where there would be 5 more todo and each are explained in the comments

/** * func: union_pareto_sorted * precondition: calling object and parameter collections must both be sorted and pareto (if not, nullptr is returned). * desc: constructs "the sorted, pareto" union (as in set-union excluding dominated options) of the two collections and returns * it as a newly created object. * RUNTIME: linear in the length of the two lists (suppose one list is of length n and the other is of length m, * then the overall runtime must be O(n+m)) * COMMENTS: REMEMBER: after this operation, the collection must be both pareto and sorted. * TIPS: Think about what must be the FIRST option in the sorted union (bootstrap) -- then think about what is the * candidate for the 2nd option (if any). * Remember: a pareto-sorted list must be strictly increasing and price and strictly decreasing in time. * * status: TODO * */ TravelOptions * union_pareto_sorted(const TravelOptions &other)const{ if(!is_pareto_sorted() || !other.is_pareto_sorted()) return nullptr;

return nullptr; } /** * 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