/** * 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 * */

** Takes two lists (calling object and a parameter) and constructs their "pruned union" as a new list. Returns new TravelOptions object as a pointer.

preconditions: both calling object and parameter must be pareto and sorted (returns null if not)

postcondition: returned object must also be pareto and sorted. In general, it will be a subset of the traditional set-union of the two lists.

Runtime: Linear. 

public:

enum Relationship { better, worse, equal, incomparable};

private:

struct Node {

double price;

double time;

Node *next;

Node(double _price=0, double _time=0, Node* _next=nullptr){

price = _price; time = _time; next = _next;

}

};

/* TravelOptions private data members */

Node *front; // pointer for first node in linked list (or null if list is empty)

int _size;

public:

// constructors

TravelOptions() {

front = nullptr;

_size=0;

}

~TravelOptions( ) {

clear();

}

TravelOptions * union_pareto_sorted(const TravelOptions &other)const{

if(!is_pareto_sorted() || !other.is_pareto_sorted())

// CODE GOES HERE

return nullptr;