SHARE
TWEET

Untitled

a guest Dec 11th, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma once
  2.  
  3. template<class T>
  4. class LinkedList
  5. {
  6. public:
  7.  
  8.     LinkedList() : head_(new Node()), rhead_(head_), size_(0) {}
  9.  
  10.     void insert(const T& val)
  11.     {
  12.         Node* now = head_;
  13.         while (now->next_ != nullptr && now->next_->val_ < val)
  14.         {
  15.             now = now->next_;
  16.         }
  17.         now = new Node(val, now, now->next_);
  18.         now->previous_->next_ = now;
  19.         if (now->next_ != nullptr)
  20.         {
  21.             now->next_->previous_ = now;
  22.         }
  23.         if (rhead_->next_ != nullptr)
  24.         {
  25.             rhead_ = rhead_->next_;
  26.         }
  27.         ++size_;
  28.     }
  29.  
  30.     const unsigned& size() const
  31.     {
  32.         return size_;
  33.     }
  34.  
  35.     struct Node;
  36.     class reverse_iterator;
  37.  
  38.     class iterator
  39.     {
  40.     public:
  41.  
  42.         iterator(Node* ptr, Node* left, Node* right) : current_(ptr), left_(left), right_(right) {}
  43.  
  44.         iterator(const iterator& copy) : current_(copy.current_), left_(copy.left_), right_(copy.right_) {}
  45.  
  46.         reverse_iterator getReversible() const
  47.         {
  48.             return reverse_iterator(current_, left_, right_);
  49.         }
  50.  
  51.         iterator& operator=(const iterator& right)
  52.         {
  53.             current_ = right.current_;
  54.             return *this;
  55.         }
  56.  
  57.         T* operator->() const
  58.         {
  59.             return current_;
  60.         }
  61.  
  62.         iterator operator++(int)
  63.         {
  64.             assert(current_ != nullptr);
  65.             iterator res(current_);
  66.             current_ = current_->next_;
  67.             return res;
  68.         }
  69.  
  70.         iterator operator--(int)
  71.         {
  72.             assert(current_ != left_);
  73.             iterator res(current_);
  74.             current_ = current_->previous;
  75.             return res;
  76.         }
  77.  
  78.         iterator& operator++()
  79.         {
  80.             assert(current_ != nullptr);
  81.             current_ = current_->next_;
  82.             return *this;
  83.         }
  84.  
  85.         iterator& operator--()
  86.         {
  87.             assert(current_ != left_);
  88.             current_ = current_->previous_;
  89.             return *this;
  90.         }
  91.  
  92.         const T& operator*()
  93.         {
  94.             assert(current_ != nullptr);
  95.             return current_->val_;
  96.         }
  97.  
  98.         const T& operator*() const
  99.         {
  100.             assert(current_ != nullptr);
  101.             return current_->val_;
  102.         }
  103.  
  104.         bool operator==(const iterator& right)
  105.         {
  106.             return current_ == right.current_;
  107.         }
  108.  
  109.         bool operator!=(const iterator& right)
  110.         {
  111.             return current_ != right.current_;
  112.         }
  113.  
  114.     private:
  115.         Node* left_;
  116.         Node* current_;
  117.         Node* right_;
  118.     };
  119.  
  120.     class reverse_iterator
  121.     {
  122.     public:
  123.  
  124.         reverse_iterator(Node* ptr, Node* left, Node* right) : current_(ptr), left_(left), right_(right) {}
  125.  
  126.         reverse_iterator(const reverse_iterator& copy) : current_(copy.current_), left_(copy.left_), right_(copy.right_) {}
  127.  
  128.         iterator getStraight() const
  129.         {
  130.             return iterator(current_, left_, right_);
  131.         }
  132.  
  133.         reverse_iterator& operator=(const reverse_iterator& right)
  134.         {
  135.             current_ = right.current_;
  136.             return *this;
  137.         }
  138.  
  139.         T* operator->() const
  140.         {
  141.             return current_;
  142.         }
  143.  
  144.         reverse_iterator operator++(int)
  145.         {
  146.             assert(current_ != nullptr);
  147.             reverse_iterator res(current_);
  148.             current_ = current_->previous_;
  149.             return res;
  150.         }
  151.  
  152.         reverse_iterator operator--(int)
  153.         {
  154.             assert(current_ != right_);
  155.             reverse_iterator res(current_);
  156.             current_ = current_->next_;
  157.             return res;
  158.         }
  159.  
  160.         reverse_iterator& operator++()
  161.         {
  162.             assert(current_ != nullptr);
  163.             current_ = current_->previous_;
  164.             return *this;
  165.         }
  166.  
  167.         reverse_iterator& operator--()
  168.         {
  169.             assert(current_ != right_);
  170.             current_ = current_->next_;
  171.             return *this;
  172.         }
  173.  
  174.         const T& operator*()
  175.         {
  176.             assert(current_ != nullptr);
  177.             return current_->val_;
  178.         }
  179.  
  180.         const T& operator*() const
  181.         {
  182.             assert(current_ != nullptr);
  183.             return current_->val_;
  184.         }
  185.  
  186.         bool operator==(const reverse_iterator& right)
  187.         {
  188.             return current_ == right.current_;
  189.         }
  190.  
  191.         bool operator!=(const reverse_iterator& right)
  192.         {
  193.             return current_ != right.current_;
  194.         }
  195.  
  196.     private:
  197.         Node* left_;
  198.         Node* current_;
  199.         Node* right_;
  200.     };
  201.  
  202.     iterator begin() const
  203.     {
  204.         return iterator(head_->next_, head_, (!size_ ? nullptr : rhead_));
  205.     }
  206.  
  207.     iterator end() const
  208.     {
  209.         return iterator(rhead_->next_, head_, (!size_ ? nullptr : rhead_));
  210.     }
  211.  
  212.     reverse_iterator rbegin() const
  213.     {
  214.         return reverse_iterator((!size_ ? nullptr : rhead_), head_, (!size_ ? nullptr : rhead_));
  215.     }
  216.  
  217.     reverse_iterator rend() const
  218.     {
  219.         return reverse_iterator(head_, head_, (!size_ ? nullptr : rhead_));
  220.     }
  221.  
  222. private:
  223.  
  224.     Node* head_;
  225.     Node* rhead_;
  226.     unsigned size_;
  227.  
  228.     struct Node
  229.     {
  230.         Node() : next_(nullptr), previous_(nullptr) {}
  231.  
  232.         Node(const T& val, Node* previous, Node* next) : val_(val), next_(next), previous_(previous) {}
  233.  
  234.         T val_;
  235.         Node* previous_;
  236.         Node* next_;
  237.     };
  238. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top