PLEASE HELP in C++

you have been given a partially implemented C++ class called TravelOptions (file: TravelOptions.h). The class implements an ADT using singly-linked lists for which some functions are already written and some are not. Your job is to complete the unwritten functions.

 #ifndef _TRVL_OPTNS_H #define _TRVL_OPTNS_H #include #include #include // using namespace std; class TravelOptions{ 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(); } /** * func: clear * desc: Deletes all Nodes currently in the list * status: DONE */ void clear(){ Node *p, *pnxt; p = front; while(p != nullptr) { pnxt = p->next; delete p; p = pnxt; } _size = 0; front = nullptr; } /** * func: size * desc: returns the number of elements in the list * status: DONE */ int size( ) const { return _size; } /** * func: compare * desc: compares option A (priceA, timeA) with option B (priceB, timeA) and * returns result (see enum Relationship above): * * There are four possible scenarios: * - A and B are identical: option A and option B have identical price and time: * ACTION: return equal * - A is better than B: option A and B are NOT equal/identical AND * option A is no more expensive than option B AND * option A is no slower than option B * ACTION: return better * - A is worse than B: option A and B are NOT equal/identical AND * option A is at least as expensive as option B AND * option A is no faster than option B * ACTION: return worse * NOTE: this means B is better than A * - A and B are incomparable: everything else: one option is cheaper and * the other is faster. * ACTION: return incomparable * * COMMENTS: since this is a static function, there is no calling object. * To call it from a client program, you would do something like this: * TravelOptions::Relationship r; double pa, ta, pb, tb; // some code to set the four price/time variables r = TravelOptions::compare(pa, ta, pb, tb); if(r == TravelOptions::better) std::cout << "looks like option b is useless!" << std::endl; // etcetera * * status: TODO */ static Relationship compare(double priceA, double timeA, double priceB, double timeB) { return incomparable; // placeholder } private: /** * func: compare(Node*, Node*) * desc: private utilty function for comparing two options given as * Node pointers. * * status: DONE * * COMMENT: depends on public compare(double,double,double,double) being implemented. * You might find this version handy when manipulating lists */ static Relationship compare(Node *a, Node *b) { if(a==nullptr || b==nullptr) { std::cout << "ERR: compare(Node*,Node*); null pointer passed!!! Whoops!" << std::endl; return incomparable; } return compare(a->price, a->time, b->price, b->time); } public: /** * func: push_front * desc: Adds a option to the front of the list (simple primitive for building lists) * status: DONE */ void push_front(double price, double time) { front = new Node(price, time, front); _size++; } /** * func: from_vec * desc: This function accepts a C++ standard libary vector of pair. * Each pair is interpreted as a option and a TravelOptions object * is containing exactly the same options as in the vector (and in the same order). * * returns: a pointer to the resulting TravelOptions object * status: DONE */ static TravelOptions * from_vec(std::vector > &vec) { TravelOptions *options = new TravelOptions(); for(int i=vec.size()-1; i>=0; i--) { options->push_front(vec[i].first, vec[i].second); } return options; } /** * func: to_vec * desc: Utility function which creates a C++ standard libary vector of pair. * and populates it with the options in the calling object (in the same order). * As in from_vec the "first" field of each pair maps to price and the "second" * field maps to time. * * returns: a pointer to the resulting vector * status: DONE */ std::vector> * to_vec() const { std::vector> *vec = new std::vector>(); Node *p = front; while(p != nullptr) { vec->push_back(std::pair(p->price, p->time)); p = p->next; } return vec; } /** * func: is_sorted * desc: we consider an option list sorted under the following conditions: * * - the options are in non-decreasing order of price AND * - time is used as a tie-breaker for options with identical price. * * For example, using the notation to represent an option: * * <5.1, 10.0> must be before <5.6, 9.0> (price is less, so time ignored) * <6.2, 4.1> must be AFTER <6.2, 3.9> (identical price; tie broken by * smaller time (3.9 in this case)). * * If two or more options are identical in BOTH price and time, they are * indistinguishible and must appear as a consecutive "block" if the list is * to be considered sorted. * * returns: true if sorted by the rules above; false otherwise. * * Examples: * * The option list below is sorted by our rules: * [ <1, 7>, <2, 8>, <2, 9>, <3, 5>, <5, 8>, <5, 8>, <5, 9>, <6, 12> ] * * The option list below is NOT sorted by our rules: * [ <1, 7>, <2, 8>, <4, 3>, <3, 7>] * ^^^^^^ must be before <4,3> * * The option list below is also NOT sorted by our rules: * [ <1, 7>, <2, 8>, <2, 5>, <3, 7>] * ^^^^^^ must be before <2,8> * status: TODO */ bool is_sorted()const{ return false; } /** * func: is_pareto * desc: returns true if and only if: * * all options are distinct (no duplicates) AND * none of the options are 'suboptimal' (i.e., for each option X, there DOES NOT EXIST * any other option Y such that Y dominates X). There are several equivalent * ways of stating this property... * * status: TODO * * REQUIREMENTS: * - the list must be unaltered * - no memory allocation, arrays, etc. allowed * - RUNTIME: quadratic in number of options n (i.e., O(n^2)). * * REMEMBER: the list does not need to be sorted in order to be pareto */ bool is_pareto() const{ return false; } /** * func: is_pareto_sorted() * desc: returns true if and only if the list is: * - STRICTLY INCREASING IN price AND * - STRICTLY DECREASING IN time * * REQUIREMENTS: * RUNTIME: linear in length of list n (i.e., O(n)). * * status: TODO * * COMMENTS: notice that because of the runtime requirement, you cannot simply do this: * return is_sorted() && is_pareto(); */ bool is_pareto_sorted() const{ return false; } /** * func: insert_sorted * preconditions: given collection (calling object) must be sorted (but not necessarily * pareto). If this is not the case, false is returned (code provided). * (returns true otherwise, after insertion complete). * * desc: inserts option (given as parameters) into option list (calling object) * while keeping it sorted. Recall: ordering by price; tie-breaker is time. * * RUNTIME: linear in length of list -- O(n). * * status: TODO * * NOTES/TIPS: do this before insert_pareto_sorted; it is easier! Remember, this one * you don't have to think about pruning for this function -- just ordering. */ bool insert_sorted(double price, double time) { if(!is_sorted()) return false; return true; } /** * func: insert_pareto_sorted * preconditions: given collection (calling object) must be sorted AND pareto (pruned). * if this is not the case, false is returned. * (code segment for this test given). * desc: (assuming the list is sorted and pareto): if the option given by the parameters * price and time is NOT dominated by already existing options, the following results: * - new option is inserted maintaining the sorted property of the * list, AND * - any pre-existing options which are now suboptimal (i.e., dominated by the * newly added option) are deleted. * If the new option is suboptimal, the list is simply unchanged. * In either case, true is returned (i.e., as long as the preconditions are met). * * RUNTIME REQUIREMENT: linear in the length of the list -- O(n) * * REMEMBER: * If the new option is useless (dominated by a pre-existing option), the list is unchanged * (but you still return true if preconditions are met). * You must maintain sorted order and don't forget to deallocate memory associated * with any deleted nodes. * status: TODO */ bool insert_pareto_sorted(double price, double time) { if(!is_pareto_sorted()) return false; // your code here! return true; }