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 func: is_sorted

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;

}