Advertisement
Guest User

Untitled

a guest
May 26th, 2017
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.98 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. //
  5. // Created by noname on 25.05.2017.
  6. //
  7. template <typename T>
  8. class List {
  9. public:
  10.     List();
  11.     List(const List&);
  12.     List(const List& , const List&);//collide them
  13.     ~List();
  14.     bool is_empty() const;//obv
  15.     void push_back(const T&);//adds an element to the start of the sequence
  16.     void push_front(const T&);//adds an element to the end of sequence
  17.     bool is_zeroed() const;
  18.     void sort() const;
  19.     void reset();
  20.     T sum_of_greater_than(const T&) const;
  21.     T sum() const;
  22.     bool find_and_delete(const T&);
  23.     T find_minimum();//check is_empty before calling this!!!!!!!!!!!
  24.  
  25.     template <typename callable>
  26.     void for_each(callable&&);
  27.  
  28.     template <typename callable>
  29.     void for_each(callable&&) const;
  30.  
  31. private:
  32.     struct Node {
  33.         Node(const T& in) : value(in){}
  34.         T value;
  35.         Node* next = nullptr;
  36.     };
  37.     Node* head = nullptr;
  38.     Node* last = nullptr;
  39. };
  40.  
  41. template<typename  T>
  42. List<T>::List() { }
  43.  
  44. template<typename  T>
  45. List<T>::List(const List& in) {
  46.     auto p = this;
  47.     //in lambdas "this" will not be defined the way its needed
  48.     in.for_each([&p](T i){
  49.        p->push_back(i);
  50.     });
  51.  
  52. }
  53.  
  54. template<typename  T>
  55. List<T>::List(const List& first, const List& second) {
  56.     auto p = this;
  57.     first.for_each([&p](auto i){
  58.         p->push_back(i);
  59.     });
  60.     second.for_each([&p](auto i){
  61.         p->push_back(i);
  62.     });
  63. }
  64.  
  65. template<typename  T>
  66. List<T>::~List() {
  67.     reset();
  68. }
  69.  
  70. template <typename T>
  71. void List<T>::reset(){
  72.     while (head != nullptr){
  73.         auto temp = head;
  74.         head = head->next;
  75.         delete temp;
  76.     }
  77.     last = head;
  78. }
  79.  
  80. template <typename T>
  81. bool List<T>::is_empty() const {
  82.     return head == nullptr;
  83. };
  84.  
  85. template <typename T>
  86. void List<T>::push_back(const T& in){
  87.     auto temp = new Node(in);
  88.     if (this->is_empty()){
  89.         last = head = temp;
  90.     } else {
  91.         last = last->next = temp;
  92.     }
  93. };
  94.  
  95. template <typename T>
  96. void List<T>::sort() const {
  97.     auto item = head;
  98.     bool done = false;
  99.     while (!done){
  100.         done = true;
  101.         auto i = head;
  102.         while (i != nullptr){
  103.             if ((i->next != nullptr ) && (i->value < i->next->value)){
  104.                 done = false;
  105.                 //swap them
  106.                 auto temp = i->value;
  107.                 i->value = i->next->value;
  108.                 i->next->value = temp;
  109.             }
  110.             i = i->next;
  111.         }
  112.     }
  113. }; //the worst sort method i have ever written
  114.  
  115. template <typename T>
  116. T List<T>::sum_of_greater_than(const T & in) const {
  117.     T sum = 0;
  118.     for_each([&sum , in](auto item){
  119.         if (item > in)
  120.             sum += item;
  121.     });
  122.     return sum;
  123. };
  124.  
  125. template <typename T>
  126. T List<T>::sum() const {
  127.     T sum = 0;
  128.     for_each([&sum](auto item){
  129.         sum += item;
  130.     });
  131.     return sum;
  132. };
  133.  
  134. template <typename T>
  135. bool List<T>::find_and_delete(const T & in) {
  136.     auto tempPointer = head;
  137.     auto tempValue = head->value;
  138.     //dont wanna break the whole list
  139.     if (head->value == in){
  140.         if (head->next == nullptr){
  141.             //only one and it matches. Delete it!
  142.             delete head;
  143.             head = last = nullptr;
  144.         } else {
  145.             //matches and there's something left, so the  next one should be the head
  146.             head = head->next;
  147.             delete tempPointer;
  148.         }
  149.         return true;
  150.     }
  151.     //head is not the key, os we can simply skip it
  152.     tempPointer = tempPointer->next;
  153.     while (tempPointer != nullptr){
  154.         if (tempPointer->value == in) {
  155.             Node* previous = head;
  156.             while (previous->next != tempPointer)
  157.                 previous = previous->next;
  158.             if (tempPointer == last) {
  159.                 last = previous;
  160.                 last->next = nullptr;
  161.             }
  162.             else {
  163.                 previous->next = tempPointer->next;
  164.             }
  165.             delete tempPointer;
  166.             return true;
  167.         } else
  168.             tempPointer = tempPointer->next;
  169.     }
  170.     return false;
  171. };
  172.  
  173. template <typename T>
  174. void List<T>::push_front(const T& in) {
  175.     auto temp = new Node(in);
  176.     if (this->is_empty()){
  177.         last = head = temp;
  178.     } else {
  179.         temp->next = head;
  180.         head = temp;
  181.     }
  182. };
  183.  
  184. template <typename T>
  185. T List<T>::find_minimum() {
  186.     T res = head->value;// NOT EMPTY-SAFE!
  187.     for_each([&res](auto item){
  188.        if (item < res)
  189.            res = item;
  190.     });
  191.     return res;
  192. }
  193.  
  194. template <typename T>
  195. template <typename callable>
  196. void List<T>::for_each(callable&& f) {
  197.     auto item = head;
  198.     while (item != nullptr){
  199.         auto next = item->next;
  200.         f(item->value);
  201.         item = next;
  202.     }
  203.     return;
  204. };
  205.  
  206. template <typename T>
  207. template <typename callable>
  208. void List<T>::for_each(callable&& f) const {
  209.     auto item = head;
  210.     while (item != nullptr){
  211.         auto next = item->next;
  212.         f(item->value);
  213.         item = next;
  214.     }
  215.     return;
  216. };
  217.  
  218. template <typename T>
  219. bool List<T>::is_zeroed() const {
  220.     try{
  221.         for_each([](T& i) {
  222.             if (i != 0)
  223.                 throw 0;
  224.         });
  225.     } catch (...){
  226.         return false;
  227.     }
  228.     return true;
  229. };
  230.  
  231. template <>
  232. bool List<List<int>>::is_zeroed() const{
  233.     try {
  234.         for_each([](List<int> &i) {
  235.             if (!i.is_zeroed())
  236.                 throw 0;
  237.         });
  238.     } catch (...){
  239.         return false;
  240.     }
  241.     return true;
  242. };
  243.  
  244. uint32_t inputPositiveNumber(){
  245.     int64_t temp;
  246.     std::cin >> temp;
  247.     if (temp <= 0){
  248.         std::cout <<"\nPlease input positive numbers only:";
  249.         return inputPositiveNumber();
  250.     }
  251.     return static_cast<uint32_t>(temp);
  252. }
  253.  
  254.  
  255. void test(){
  256.     List<int> a;
  257.     int sum = 0;
  258.     a.push_front(-10);
  259.     a.push_front(-30);
  260.     for (int i = -1 ; i < 2 ; i++)
  261.         a.push_back(7*i);
  262.     a.sort();
  263.     a.find_and_delete(4);
  264.  
  265.     return;
  266. }
  267.  
  268. int main(){
  269.     test();
  270.     List<List<int>> islands;
  271.     uint32_t islandCount = 0;
  272.     std::cout << "Input the number of islands:";
  273.     islandCount = inputPositiveNumber();
  274.     for (uint32_t i = 0; i < islandCount; ++i){
  275.         std::cout << "\nFilling island number " << i + 1;
  276.         List<int> tempIsland;
  277.         std::cout << "\nInput the number of rabbits here:";
  278.         auto rabbitsCount = inputPositiveNumber();
  279.         for (uint32_t j = 0; j < rabbitsCount; ++j){
  280.             std::cout << "Input the weight of rabbit number " << j + 1 << ":";
  281.             tempIsland.push_back(inputPositiveNumber());
  282.         }
  283.         //little trick here.
  284.         //push front coz we need to go backwards c;
  285.         islands.push_front(tempIsland);
  286.     }
  287.     List<int> boat;
  288.     std::cout << "Input the boat capacity:";
  289.     auto boatCapacity = inputPositiveNumber();
  290.     //end of input
  291.     while (!islands.is_zeroed()){//while the islands are not tottaly empty
  292.         //lets try so save them
  293.         islands.for_each([&boat, &boatCapacity](List<int>& currIsland){
  294.             List<int> buffer(boat , currIsland);
  295.             boat.reset(); currIsland.reset();
  296.             buffer.sort();
  297.             List<int> currIslandCopy(currIsland);
  298.             buffer.for_each([&boat , &boatCapacity , &currIslandCopy](int i){
  299.                if  (i + boat.sum() <= boatCapacity){
  300.                    //able to grab this guy
  301.                    boat.push_back(i);
  302.                } else {
  303.                    //unable to grab him
  304.                    currIslandCopy.push_back(i);
  305.                }
  306.             });
  307.             currIsland = currIslandCopy;
  308.         });
  309.  
  310.         std::cout << "\nThe result of another swimming adventure:\n";
  311.         islands.for_each([](auto island){
  312.             island.for_each([](auto weight){
  313.                 std::cout << weight << ' ';
  314.             });
  315.             std::cout << "< - - - >\n";
  316.         });
  317.         std::cout << "Press any key to continue the cycle";
  318.         std::cin.ignore();
  319.     }
  320.     return 0;
  321. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement