Summary: 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 #de fine TRVLOPTNS. H TRVLOPTNSH - - #include #include #include
price, a->time, b->price, b->time) public: func: push_tront * desc: Adds a option to the front of the list (simple primitive for building lists) * status DONE vold push tront (double price. double time front new Node (price, time, front); size+t *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 TraveLOptions Traveloptions *options-new TravelOptions ) from-vec(std::vector { * static > &vec) for (int i=vec . size()-1; options->push_front (vec[i].first, vec[i].second) i>=0; i-- 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> * vec() { to *vec const - sta: : ve ct r> new std:: vector> () ; while (p !- nullptr vec->push_back (std: :pair (p->price, p p->next; p->time)); 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 ANID - time is used as a tie-breaker for options with identical price. the OPtlons are h hon-decreas1ng oraesO Price AND - time is used as a tie-breaker for options with identical price. For example, using the notation to represent an option: must be before must be AFTER (price is less, so time ignored) (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 1t sorted by the rules above talse otherwise. *Examples: *The option list below is sorted by our rules: *The option list below is NOT sorted by our rules: AAAAA must be before *The option list below is also NOT sorted by our rules: AAAAA must be before * 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 ther option Y such that Y dominates X). There are several eguivalent ways of stating this property. . . * status: TODO REQUIREMENTS: - the list must be unaltered - no memory allocation, arrays, etc. allowed -RUNTIME: quadratic in numberf options n (1 - RUNTIMEquadratic 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) constt 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., 0(n)). * status TODO COMMENTS:notice that because of the runtime requirement, you cannot simply do this: return is_sorted) && is_pareto) R/ bool is_pareto_sorted) constf return false s k * 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 easierRmber, 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 fer this test given) desc: (assuming the list is sorted and pareto): Lf the option given by the parameters price and time is NOT dominated by already existing options, the following results: new option sprice,time> 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 REQUREMENT: 1.near in the length of the list -- 0(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_sortedeturn false // your code here! return true: *func: union_pareto_sorted * precondition: calling object and parameter collections must both be sorted and pareto (if not, nullptr is returned) * preconditio calling object and parameter collections must both be sorted and pareto (i not, nullptr is returned) * desc: constructs "the sorea, pare:o" union (as in set-union excluding dominated options) of tne two collections and returns it as a newly created object * RUNTIME: linear in the length ofhe two lists (suppose one list is of length n and the other is of length m, then the overall runtime must ce 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 acout what is the candidate for the 2nd option f any Remember: a pareto-sorted list must be strictly increasing and price and strictly decreasing in tinie *status: TODO TravelOptions union pareto sorted (const TravelOptions &other) const if (!is_pareto_sorted) other.is_pareto_sorted)) return nullpt.r; return nullptr; func: prune_sorced *preconaition: given collection must be sorted (it not, false is returned) * desc: takes sorted 1ist of options and removes dominated entries (and eliminates any duplicates). * RJNT TME : 1:near in the length of the list (O(n)) COMMENTS:the resulting list will be sorted AND pareto * satus : TODO bool prune sorted) iis sorted) return false; return true: func: join plus plus *preconditions oneboth the calling object and parameter are just TravelOptions objects not necessarily sorted or paretol * paran: other; a reference to another to a 11st of TravelCptions (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 t* city Y (this is part of your plan - you need to stop in city Y then you continue from city Y to city 2 Let the calling object be the options for the X-to-Y leg and the parameter be the options for the Y-to-2 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 pa ird with any option for the Y-co-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 funcion's joD is to de-ermine the sorted-pareto list of options for the entire trip and retrn it as a pointer to the object t returns: a pointer to a TravelOptions object capturing al1 non-dominated options or the entire trip from x-to-z (i.e., even hough the given lis:s may not be sorted or pareto, the resulting list will be both). * stat.us TODO RUNTIME: no runtime requirement t TIPS: Start by chinking 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 night be especially useful! (probably ought to implement any functions you plan on using first!) Don't overthink this one - there is no runtime requirement aiter al.1 BOUNDARY CONDITIONS: it is possile that one of both of the given option lists is empty The result is still *a pointer to a new Traveloptions object-- that object just happens to have an empty list TravelOptions* join plus plus (const Traveloptions &other) const i well-defined also empzy). An empty option list is NOT the same as a null pointer thoughyou should still return return nullptr; placeholder to make the compiler happy * func: join_plus_max t preconditions: both the calling object and the para * desc: imagine a different scenario (vs. join plus pl 1 -pareto 1ists (if not, nullptr is returned) parent with two chiidren one living in city A and the other living irn city C-and they are both coming home for the holidays (et'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 1ist for the B-to-C trip Consider a particular optlon for the A-to-c trip and a particular option for the B-to-c trip Clearly, the cota. price for selecting these two options is p1+p2 However (unlike in the plus_plus case), adding the t and t.2 doesn't make gense 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(tl, 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 ooth children one The resulting TravelOptions object is ret rned as a pointer (recall if the preconditions are not met, nullptr is recurned) * RUNTZME .et N and M be the lengths o the respective lists given ; your runtime nust e linear in NH (0 (N+M)) *status: TODO *TIPS: This one will take some thought! If the specified runtime is possible, he resulting option list cannot be too large righ (at most. K+M in length)? But there NXM possible pa iring of options. So enumme rating 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 1ist MUST be Remember that a sortea-pareto list must be strictly increasing in price and strictly decreasing in time Now think about what might be the 2nd option in the 1ist you are building. It must cost more than the first AND take less time. To be nore concrete, suppose your first option has total price of $100 and results in child A traveling for 12 hours and child B traveling for hours. Does it make sense to spend more money on child B so they can get home in say 7 hours? Think about it! Th MAX function is important! Traveloptions join plus_max (const Traveloptions other) const f if(!is pareto!(other.is_pareto ))) return nullptr; return nullpcr; func: : sorted clon *desc: returns a sorted TravelOptions object which contains the same elements as the current object * status DONE [out relies on to do ite insert sorted] Traveloptions *sorted_clone t Travel0ptions sortednew Traveloptions ) Node *pfront: while(p != nullptr) { sorted->insert_sorted (p->price, p->time); returri sorted ns Open with 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 (1.e., the expensive options are returned) .. *returns: pointer to expensive options or nullptr if the calling object is not pareto-sorted *RUNTIME: 1inear in the length of the given list (0 () * ADDITIONAL RagUIREMENI": for full credit. you MAY NOT ALLOCATE ANY NEW NODES! Th ink about it-- suppose your given ist has 100 options and 40 of them are below the max_price threshold; the other 60 options end up in the returnd ist. 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 Trave 10ptions splitsortedpareto (double maxprice) { - - - it(is pareto_sorted)) return nullptr; retur nullptr; / placeholder to make compiler happy with skeleton func: display * desc: prins a string representation of the current Trave!Options object *status DONE void display printf(" PRICE printf ("; Node * p = front; TIME n") while (p!llptr) printf(" %5.2f p = p->next; 5.2f ", p->price, p>time)i *func: display *desc: prints a string representation of the current TravelOptions object *status:DONE void display ) printf("PRICE printf (" Node * p = front; TIME " while (p!-nullptr) printf(" %5.2f p- p->next; %5.2f ", p->price, p->time); t x *func: checks um * desc: Performs and XOR of all node pointers and returns result as an unsigned int * status: DONE *NOTES: YOU MAY NOT TOUCH OR MODIFYTHIS FUNCTION!! unsigned long int checksum ) const unsigned long int s0; Node pfront; while (p!-nullptr) s-s A ((unsigned long int)p); pp->next return s; #endif #ifndef #de fine TRVLOPTNS. H TRVLOPTNSH - - #include #include #include price, a->time, b->price, b->time) public: func: push_tront * desc: Adds a option to the front of the list (simple primitive for building lists) * status DONE vold push tront (double price. double time front new Node (price, time, front); size+t *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 TraveLOptions Traveloptions *options-new TravelOptions ) from-vec(std::vector { * static > &vec) for (int i=vec . size()-1; options->push_front (vec[i].first, vec[i].second) i>=0; i-- 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> * vec() { to *vec const - sta: : ve ct r> new std:: vector> () ; while (p !- nullptr vec->push_back (std: :pair (p->price, p p->next; p->time)); 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 ANID - time is used as a tie-breaker for options with identical price. the OPtlons are h hon-decreas1ng oraesO Price AND - time is used as a tie-breaker for options with identical price. For example, using the notation to represent an option: must be before must be AFTER (price is less, so time ignored) (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 1t sorted by the rules above talse otherwise. *Examples: *The option list below is sorted by our rules: *The option list below is NOT sorted by our rules: AAAAA must be before *The option list below is also NOT sorted by our rules: AAAAA must be before * 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 ther option Y such that Y dominates X). There are several eguivalent ways of stating this property. . . * status: TODO REQUIREMENTS: - the list must be unaltered - no memory allocation, arrays, etc. allowed -RUNTIME: quadratic in numberf options n (1 - RUNTIMEquadratic 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) constt 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., 0(n)). * status TODO COMMENTS:notice that because of the runtime requirement, you cannot simply do this: return is_sorted) && is_pareto) R/ bool is_pareto_sorted) constf return false s k * 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 easierRmber, 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 fer this test given) desc: (assuming the list is sorted and pareto): Lf the option given by the parameters price and time is NOT dominated by already existing options, the following results: new option sprice,time> 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 REQUREMENT: 1.near in the length of the list -- 0(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_sortedeturn false // your code here! return true: *func: union_pareto_sorted * precondition: calling object and parameter collections must both be sorted and pareto (if not, nullptr is returned) * preconditio calling object and parameter collections must both be sorted and pareto (i not, nullptr is returned) * desc: constructs "the sorea, pare:o" union (as in set-union excluding dominated options) of tne two collections and returns it as a newly created object * RUNTIME: linear in the length ofhe two lists (suppose one list is of length n and the other is of length m, then the overall runtime must ce 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 acout what is the candidate for the 2nd option f any Remember: a pareto-sorted list must be strictly increasing and price and strictly decreasing in tinie *status: TODO TravelOptions union pareto sorted (const TravelOptions &other) const if (!is_pareto_sorted) other.is_pareto_sorted)) return nullpt.r; return nullptr; func: prune_sorced *preconaition: given collection must be sorted (it not, false is returned) * desc: takes sorted 1ist of options and removes dominated entries (and eliminates any duplicates). * RJNT TME : 1:near in the length of the list (O(n)) COMMENTS:the resulting list will be sorted AND pareto * satus : TODO bool prune sorted) iis sorted) return false; return true: func: join plus plus *preconditions oneboth the calling object and parameter are just TravelOptions objects not necessarily sorted or paretol * paran: other; a reference to another to a 11st of TravelCptions (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 t* city Y (this is part of your plan - you need to stop in city Y then you continue from city Y to city 2 Let the calling object be the options for the X-to-Y leg and the parameter be the options for the Y-to-2 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 pa ird with any option for the Y-co-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 funcion's joD is to de-ermine the sorted-pareto list of options for the entire trip and retrn it as a pointer to the object t returns: a pointer to a TravelOptions object capturing al1 non-dominated options or the entire trip from x-to-z (i.e., even hough the given lis:s may not be sorted or pareto, the resulting list will be both). * stat.us TODO RUNTIME: no runtime requirement t TIPS: Start by chinking 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 night be especially useful! (probably ought to implement any functions you plan on using first!) Don't overthink this one - there is no runtime requirement aiter al.1 BOUNDARY CONDITIONS: it is possile that one of both of the given option lists is empty The result is still *a pointer to a new Traveloptions object-- that object just happens to have an empty list TravelOptions* join plus plus (const Traveloptions &other) const i well-defined also empzy). An empty option list is NOT the same as a null pointer thoughyou should still return return nullptr; placeholder to make the compiler happy * func: join_plus_max t preconditions: both the calling object and the para * desc: imagine a different scenario (vs. join plus pl 1 -pareto 1ists (if not, nullptr is returned) parent with two chiidren one living in city A and the other living irn city C-and they are both coming home for the holidays (et'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 1ist for the B-to-C trip Consider a particular optlon for the A-to-c trip and a particular option for the B-to-c trip Clearly, the cota. price for selecting these two options is p1+p2 However (unlike in the plus_plus case), adding the t and t.2 doesn't make gense 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(tl, 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 ooth children one The resulting TravelOptions object is ret rned as a pointer (recall if the preconditions are not met, nullptr is recurned) * RUNTZME .et N and M be the lengths o the respective lists given ; your runtime nust e linear in NH (0 (N+M)) *status: TODO *TIPS: This one will take some thought! If the specified runtime is possible, he resulting option list cannot be too large righ (at most. K+M in length)? But there NXM possible pa iring of options. So enumme rating 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 1ist MUST be Remember that a sortea-pareto list must be strictly increasing in price and strictly decreasing in time Now think about what might be the 2nd option in the 1ist you are building. It must cost more than the first AND take less time. To be nore concrete, suppose your first option has total price of $100 and results in child A traveling for 12 hours and child B traveling for hours. Does it make sense to spend more money on child B so they can get home in say 7 hours? Think about it! Th MAX function is important! Traveloptions join plus_max (const Traveloptions other) const f if(!is pareto!(other.is_pareto ))) return nullptr; return nullpcr; func: : sorted clon *desc: returns a sorted TravelOptions object which contains the same elements as the current object * status DONE [out relies on to do ite insert sorted] Traveloptions *sorted_clone t Travel0ptions sortednew Traveloptions ) Node *pfront: while(p != nullptr) { sorted->insert_sorted (p->price, p->time); returri sorted ns Open with 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 (1.e., the expensive options are returned) .. *returns: pointer to expensive options or nullptr if the calling object is not pareto-sorted *RUNTIME: 1inear in the length of the given list (0 () * ADDITIONAL RagUIREMENI": for full credit. you MAY NOT ALLOCATE ANY NEW NODES! Th ink about it-- suppose your given ist has 100 options and 40 of them are below the max_price threshold; the other 60 options end up in the returnd ist. 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 Trave 10ptions splitsortedpareto (double maxprice) { - - - it(is pareto_sorted)) return nullptr; retur nullptr; / placeholder to make compiler happy with skeleton func: display * desc: prins a string representation of the current Trave!Options object *status DONE void display printf(" PRICE printf ("; Node * p = front; TIME n") while (p!llptr) printf(" %5.2f p = p->next; 5.2f ", p->price, p>time)i *func: display *desc: prints a string representation of the current TravelOptions object *status:DONE void display ) printf("PRICE printf (" Node * p = front; TIME " while (p!-nullptr) printf(" %5.2f p- p->next; %5.2f ", p->price, p->time); t x *func: checks um * desc: Performs and XOR of all node pointers and returns result as an unsigned int * status: DONE *NOTES: YOU MAY NOT TOUCH OR MODIFYTHIS FUNCTION!! unsigned long int checksum ) const unsigned long int s0; Node pfront; while (p!-nullptr) s-s A ((unsigned long int)p); pp->next return s; #endif
