avr39ripe

cppQueueOverListFw

Aug 17th, 2021 (edited)
753
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. template <typename ElemT>
  4. class ListFw
  5. {
  6.     class Node
  7.     {
  8.         ElemT data;
  9.         Node* next;
  10.     public:
  11.         Node(const ElemT& dataP, Node* nextP = nullptr) : data{ dataP }, next{ nextP }{}
  12.         friend ListFw;
  13.         template <typename ElemT>
  14.         friend std::ostream& operator<<(std::ostream& out, const ListFw<ElemT>& list);
  15.     };
  16.  
  17.     Node* head;
  18.     Node* tail;
  19.     size_t size;
  20.     Node* getNode(size_t idx);
  21. public:
  22.     ListFw() : head{ nullptr }, tail{ nullptr }, size{ 0 } {}
  23.     bool empty()const { return size == 0; }
  24.     size_t get_size()const { return size; }
  25.     ElemT& front() { return head->data; }
  26.     const ElemT& front()const { return head->data; }
  27.     ElemT& back() { return tail->data; }
  28.     const ElemT& back()const { return tail->data; }
  29.     void push_front(const ElemT& data);
  30.     void push_back(const ElemT& data);
  31.     bool pop_front();
  32.     bool pop_back();
  33.  
  34.     void insert_at(size_t idx, const ElemT& data);
  35.     bool delete_at(size_t idx);
  36.  
  37.     void print()
  38.     {
  39.         if (!head) { std::cout << "[empty]"; }
  40.         else
  41.         {
  42.             for (auto curr{ head }; curr; curr = curr->next)
  43.             {
  44.                 std::cout << curr->data << ' ';
  45.             }
  46.         }
  47.         std::cout << '\n';
  48.     }
  49.  
  50.     void clear();
  51.     ~ListFw();
  52.     template <typename ElemT>
  53.     friend std::ostream& operator<<(std::ostream& out, const ListFw<ElemT>& list);
  54. };
  55.  
  56. template <typename ElemT>
  57. std::ostream& operator<<(std::ostream& out, const ListFw<ElemT>& list)
  58. {
  59.     if (!list.head) { out << "[empty]"; }
  60.     else
  61.     {
  62.         for (auto curr{ list.head }; curr; curr = curr->next)
  63.         {
  64.             out << curr->data << ' ';
  65.         }
  66.     }
  67.     return out;
  68. }
  69.  
  70. template <typename ElemT>
  71. void ListFw<ElemT>::push_front(const ElemT& data)
  72. {
  73.     head = new Node{ data, head };
  74.  
  75.     if (!tail) { tail = head; }
  76.     ++size;
  77. }
  78.  
  79. template <typename ElemT>
  80. void ListFw<ElemT>::push_back(const ElemT& data)
  81. {
  82.     if (!head)
  83.     {
  84.         head = new Node{ data, head };
  85.         tail = head;
  86.     }
  87.     else
  88.     {
  89.         tail->next = new Node{ data, nullptr };
  90.         tail = tail->next;
  91.     }
  92.     ++size;
  93. }
  94.  
  95. template <typename ElemT>
  96. bool ListFw<ElemT>::pop_front()
  97. {
  98.     if (head)
  99.     {
  100.         Node* oldHead{ head };
  101.         head = head->next;
  102.         delete oldHead;
  103.         --size;
  104.         if (!size) { tail = nullptr; }
  105.         return true;
  106.     }
  107.     return false;
  108. }
  109.  
  110. template <typename ElemT>
  111. bool ListFw<ElemT>::pop_back()
  112. {
  113.     if (tail)
  114.     {
  115.         if (tail == head)
  116.         {
  117.             delete tail;
  118.             head = nullptr;
  119.             tail = nullptr;
  120.             size = 0;
  121.             return true;
  122.         }
  123.  
  124.         Node* curr{ head };
  125.         for (; !(curr->next == tail); curr = curr->next);
  126.  
  127.         delete tail;
  128.         curr->next = nullptr;
  129.         tail = curr;
  130.         --size;
  131.         return true;
  132.     }
  133.     return false;
  134. }
  135.  
  136. template <typename ElemT>
  137. void ListFw<ElemT>::clear()
  138. {
  139.     while (head)
  140.     {
  141.         std::cout << "Clear for: " << front() << '\n';
  142.         pop_front();
  143.     }
  144. }
  145.  
  146. template <typename ElemT>
  147. ListFw<ElemT>::~ListFw()
  148. {
  149.     while (tail)
  150.     {
  151.         std::cout << "Destruct for: " << back() << '\n';
  152.         pop_back();
  153.     }
  154. }
  155.  
  156. template <typename ElemT>
  157. void printListState(const ListFw<ElemT>& l)
  158. {
  159.     std::cout << "Size: " << l.get_size() << '\n';
  160.     std::cout << "Front: " << l.front() << '\n';
  161.     std::cout << "Back: " << l.back() << '\n';
  162. }
  163.  
  164. template <typename ElemT>
  165. typename ListFw<ElemT>::Node* ListFw<ElemT>::getNode(size_t idx)
  166. {
  167.     Node* curr{ nullptr };
  168.     size_t currIdx;
  169.  
  170.     if (idx >= 0 and idx < size)
  171.     {
  172.         for (curr = head, currIdx = 0; currIdx < idx; curr = curr->next, ++currIdx);
  173.     }
  174.     return curr;
  175. }
  176.  
  177. template <typename ElemT>
  178. void ListFw<ElemT>::insert_at(size_t idx, const ElemT& data)
  179. {
  180.     Node* prev{ getNode(idx - 1) };
  181.     Node* curr{ prev ? prev->next : nullptr };
  182.  
  183.     if (!curr or curr == head) { push_front(data); return; }
  184.     else
  185.     {
  186.         prev->next = new Node{ data, curr };
  187.     }
  188.     ++size;
  189. }
  190.  
  191. template <typename ElemT>
  192. bool ListFw<ElemT>::delete_at(size_t idx)
  193. {
  194.     if (idx == 0) { pop_front(); return true; }
  195.     Node* prev{ getNode(idx - 1) };
  196.     Node* curr{ prev ? prev->next : nullptr };
  197.  
  198.     if (curr)
  199.     {
  200.         if (curr == head) { head = curr->next; }
  201.         else
  202.         {
  203.             if (curr->next) { prev->next = curr->next; }
  204.             else { tail = prev; prev->next = nullptr; }
  205.         }
  206.         --size;
  207.         delete curr;
  208.         return true;
  209.     }
  210.     return false;
  211. }
  212.  
  213. template <typename ElemT>
  214. class Queue
  215. {
  216.     ListFw<ElemT> storage;
  217.     size_t capacity; // if capUnlimit unlimited elements in queue
  218.     static const uint8_t capUnlimit{ 0 };
  219. public:
  220.     Queue(size_t capacityP = capUnlimit) : capacity{ capacityP }{}
  221.     size_t getSize()const { return storage.get_size(); }
  222.     size_t getCapacity()const { return capacity; }
  223.     Queue& setCapacity(size_t capacityP)
  224.     {
  225.         while (storage.get_size() > capacityP) { storage.pop_back(); } // remove extra elements if neded
  226.         capacity = capacityP;
  227.         return *this;
  228.     }
  229.     bool empty()const { return storage.empty(); }
  230.     bool full()const { return capacity == capUnlimit ? false : storage.get_size() == capacity; }
  231.     ElemT& front() { return storage.front(); }
  232.     const ElemT& front()const { return storage.front(); }
  233.  
  234.     bool push(const ElemT& elem)
  235.     {
  236.         if (!full())
  237.         {
  238.             storage.push_back(elem);
  239.             return true;
  240.         }
  241.         return false;
  242.     }
  243.  
  244.     bool pop()
  245.     {
  246.         if (!empty())
  247.         {
  248.             storage.pop_front();
  249.             return true;
  250.         }
  251.         return false;
  252.     }
  253.  
  254.     template <typename ElemT>
  255.     friend std::ostream& operator<<(std::ostream& out, const Queue<ElemT> list);
  256. };
  257.  
  258. template <typename ElemT>
  259. std::ostream& operator<<(std::ostream& out, const Queue<ElemT> list)
  260. {
  261.     return out << list.storage;
  262. }
  263.  
  264. int main()
  265. {
  266.     Queue<int> queue{10};
  267.     std::cout << queue << '\n';
  268.  
  269.     std::cout << "Enqueue...\n";
  270.     for (size_t i{ 0 }; !queue.full(); ++i)
  271.     {
  272.         queue.push(i);
  273.         std::cout << i << '\n';
  274.     }
  275.  
  276.     std::cout << "\nFront of queue is: " << queue.front() << "\n\n";
  277.     std::cout << "Size of queue is: " << queue.getSize() << "\n\n";
  278.  
  279.     queue.setCapacity(5);
  280.  
  281.     std::cout << "\nFront of queue is: " << queue.front() << "\n\n";
  282.     std::cout << "Size of queue is: " << queue.getSize() << "\n\n";
  283.  
  284.  
  285.     std::cout << "Dequeue...\n";
  286.     for (; !queue.empty(); queue.pop())
  287.     {
  288.         std::cout << queue.front() << '\n';
  289.     }
  290.     queue.pop();
  291.     std::cout << queue << '\n';
  292.  
  293.     return 0;
  294. }
  295.  
RAW Paste Data