Advertisement
Guest User

Untitled

a guest
Apr 8th, 2020
201
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.87 KB | None | 0 0
  1. #include <cstddef>
  2. #include <iostream>
  3.  
  4. template <class U>
  5. void Copy(const U* buffer_from, size_t count, U* buffer_to) {
  6.     for (size_t i = 0; i < count; ++i) {
  7.         buffer_to[i] = buffer_from[i];
  8.     }
  9. }
  10.  
  11. template <class U>
  12. void Swap(U& a, U& b) {
  13.     U c = a;
  14.     a = b;
  15.     b = c;
  16. }
  17.  
  18. template <class U>
  19. class CircularBuffer {
  20.     U* buffer_;
  21.     size_t capacity_;
  22.     size_t begin_;
  23.     size_t end_;
  24.     size_t size_;
  25.  
  26.     const static int kIncreaseFactor = 2;
  27.  
  28.     void BufferReallocation(size_t new_cap) {
  29.         U* new_buffer = new U[new_cap];
  30.         for (size_t i = 0; i < Size(); ++i) {
  31.             new_buffer[i] = buffer_[(begin_ + i) % Capacity()];
  32.         }
  33.         delete[] buffer_;
  34.         buffer_ = new_buffer;
  35.         capacity_ = new_cap;
  36.     }
  37.  
  38. public:
  39.     CircularBuffer()
  40.         : buffer_(nullptr),
  41.           capacity_(0),
  42.           begin_(0),
  43.           end_(0),
  44.           size_(0) {
  45.     }
  46.  
  47.     explicit CircularBuffer(size_t count) : CircularBuffer() {
  48.         capacity_ = count;
  49.         if (count != 0) {
  50.             buffer_ = new U[count];
  51.         }
  52.     }
  53.  
  54.     CircularBuffer(const CircularBuffer& other)
  55.         : CircularBuffer() {
  56.         Clear();
  57.         for (size_t i = 0; i < other.Size(); ++i) {
  58.             PushBack(other[i]);
  59.         }
  60.     }
  61.  
  62.     CircularBuffer& operator=(const CircularBuffer& other) {
  63.         if (this == &other) {
  64.             return *this;
  65.         }
  66.        
  67.         Clear();
  68.         for (size_t i = 0; i < other.Size(); ++i) {
  69.             PushBack(other[i]);
  70.         }
  71.     }
  72.  
  73.     ~CircularBuffer() {
  74.         delete[] buffer_;
  75.     }
  76.  
  77.     U& operator[](size_t idx) {
  78.         return buffer_[(begin_ + idx) % Capacity()];
  79.     }
  80.  
  81.     const U& operator[](size_t idx) const {
  82.         return buffer_[(begin_ + idx) % Capacity()];
  83.     }
  84.  
  85.     const U& Front() const {
  86.         return buffer_[begin_];
  87.     }
  88.  
  89.     U& Front() {
  90.         return buffer_[begin_];
  91.     }
  92.  
  93.     const U& Back() const {
  94.         return buffer_[end_];
  95.     }
  96.  
  97.     U& Back() {
  98.         return buffer_[end_];
  99.     }
  100.  
  101.     size_t Size() const {
  102.         return size_;
  103.     }
  104.  
  105.     size_t Capacity() const {
  106.         return capacity_;
  107.     }
  108.  
  109.     bool Empty() const {
  110.         return Size() == 0;
  111.     }
  112.  
  113.     void PushFront(const U& val) {
  114.         if (Empty()) {
  115.             if (Capacity() == 0) {
  116.                 Reserve(1);
  117.             }
  118.             begin_ = 0;
  119.             end_ = 0;
  120.         } else {
  121.             if (Size() == Capacity()) {
  122.                 Reserve(Capacity() * kIncreaseFactor);
  123.             }
  124.             begin_ = (begin_ - 1 + Capacity()) % Capacity();
  125.         }
  126.  
  127.         buffer_[begin_] = val;
  128.         ++size_;
  129.     }
  130.  
  131.     void PushBack(const U& val) {
  132.         if (Empty()) {
  133.             if (Capacity() == 0) {
  134.                 Reserve(1);
  135.             }
  136.             begin_ = 0;
  137.             end_ = 0;
  138.         } else {
  139.             if (Size() == Capacity()) {
  140.                 Reserve(Capacity() * kIncreaseFactor);
  141.             }
  142.             end_ = (end_ + 1) % Capacity();
  143.         }
  144.  
  145.         buffer_[end_] = val;
  146.         ++size_;
  147.     }
  148.  
  149.     void PopBack() {
  150.         if (!Empty()) {
  151.             end_ = (end_ - 1 + Capacity()) % Capacity();
  152.             --size_;
  153.         }
  154.     }
  155.  
  156.     void PopFront() {
  157.         if (!Empty()) {
  158.             begin_ = (begin_ + 1) % Capacity();
  159.             --size_;
  160.         }
  161.     }
  162.  
  163.     void Clear() {
  164.         size_ = 0;
  165.         end_ = begin_;
  166.     }
  167.  
  168.     void Reserve(size_t new_cap) {
  169.         if (new_cap <= Capacity()) {
  170.             return;
  171.         }
  172.  
  173.         U* new_buffer = new U[new_cap];
  174.         for (size_t i = 0; i < Size(); ++i) {
  175.             new_buffer[i] = buffer_[(begin_ + i) % Capacity()];
  176.         }
  177.  
  178.         capacity_ = new_cap;
  179.         begin_ = 0;
  180.         end_ = begin_ + Size() - 1;
  181.  
  182.         delete[] buffer_;
  183.         buffer_ = new_buffer;
  184.     }
  185.  
  186.     void Swap(CircularBuffer<U>& other) {
  187.         ::Swap(buffer_, other.buffer_);
  188.         ::Swap(capacity_, other.capacity_);
  189.         ::Swap(begin_, other.begin_);
  190.         ::Swap(end_, other.end_);
  191.         ::Swap(size_, other.size_);
  192.     }
  193. };
  194.  
  195. #include <cstddef>
  196.  
  197. template <class T, size_t N>
  198. class Page {
  199.     T buffer_[N];
  200.     size_t size_;
  201.     size_t begin_;
  202.  
  203. public:
  204.     Page() : size_(0), begin_(0) {
  205.     }
  206.  
  207.     Page(const Page& other) = default;
  208.     Page& operator=(const Page& other) = default;
  209.     ~Page() = default;
  210.  
  211.     T& operator[](size_t idx) {
  212.         return buffer_[begin_ + idx];
  213.     }
  214.  
  215.     const T& operator[](size_t idx) const {
  216.         return buffer_[begin_ + idx];
  217.     }
  218.  
  219.     const T& Front() const {
  220.         return buffer_[begin_];
  221.     }
  222.  
  223.     T& Front() {
  224.         return buffer_[begin_];
  225.     }
  226.  
  227.     const T& Back() const {
  228.         return buffer_[begin_ + size_ - 1];
  229.     }
  230.  
  231.     T& Back() {
  232.         return buffer_[begin_ + size_ - 1];
  233.     }
  234.  
  235.     bool Empty() const {
  236.         return Size() == 0;
  237.     }
  238.  
  239.     size_t Size() const {
  240.         return size_;
  241.     }
  242.  
  243.     bool Full() const {
  244.         return Size() == N;
  245.     }
  246.  
  247.     bool IsBack() const {
  248.         return Empty() || (begin_ == 0 && !Full());
  249.     }
  250.  
  251.     bool IsFront() const {
  252.         return Empty() || (begin_ != 0 && !Full());
  253.     }
  254.  
  255.     void PushBack(const T& val) {
  256.         if (!IsBack()) {
  257.             return;
  258.         }
  259.  
  260.         if (Empty()) {
  261.             begin_ = 0;
  262.         }
  263.  
  264.         buffer_[size_++] = val;
  265.     }
  266.  
  267.     void PushFront(const T& val) {
  268.         if (!IsFront()) {
  269.             return;
  270.         }
  271.  
  272.         if (Empty()) {
  273.             begin_ = N;
  274.         }
  275.  
  276.         buffer_[--begin_] = val;
  277.         ++size_;
  278.     }
  279.  
  280.     void PopBack() {
  281.         if (Empty()) {
  282.             return;
  283.         }
  284.  
  285.         --size_;
  286.     }
  287.  
  288.     void PopFront() {
  289.         if (Empty()) {
  290.             return;
  291.         }
  292.  
  293.         --size_;
  294.         ++begin_;
  295.     }
  296.  
  297.     void Clear() {
  298.         size_ = 0;
  299.     }
  300. };
  301.  
  302.  
  303. //deque
  304.  
  305.  
  306. template <class T>
  307. void swap(T& a, T& b) {
  308.     T tmp = a;
  309.     a = b;
  310.     b = tmp;
  311. }
  312.  
  313. template <class T>
  314. class Deque {
  315.     const static size_t kPageSize = 100;
  316.  
  317.     CircularBuffer<Page<T, kPageSize>*> cb_;
  318.  
  319. public:
  320.     Deque() : cb_() {
  321.     }
  322.  
  323.     Deque(const Deque& other) : Deque() {
  324.         size_t size_deque = other.Size();
  325.         for (size_t i = 0; i < size_deque; ++i) {
  326.             PushBack(other[i]);
  327.         }
  328.     }
  329.  
  330.     Deque& operator=(const Deque& other) {
  331.         if (&other == this) {
  332.             return *this;
  333.         }
  334.  
  335.         cb_.Clear();
  336.        
  337.         size_t size_deque = other.Size();
  338.         for (size_t i = 0; i < size_deque; ++i) {
  339.             PushBack(other[i]);
  340.         }
  341.     }
  342.  
  343.     ~Deque() {
  344.         for (size_t i = 0; i < cb_.Size(); ++i) {
  345.             delete cb_[i];
  346.         }
  347.     }
  348.  
  349.     T& operator[](size_t idx) {
  350.         if (idx < cb_.Front()->Size()) {
  351.             return (*cb_.Front())[idx];
  352.         }
  353.  
  354.         size_t page_idx = (idx - cb_.Front()->Size()) / kPageSize;
  355.         return (*cb_[page_idx + 1])[(idx - cb_.Front()->Size()) % kPageSize];
  356.     }
  357.  
  358.     const T& operator[](size_t idx) const {
  359.         if (idx < cb_.Front()->Size()) {
  360.             return (*cb_.Front())[idx];
  361.         } else {
  362.             size_t page_idx = (idx - cb_.Front()->Size()) / kPageSize;
  363.             return (*cb_[page_idx + 1])[(idx - cb_.Front()->Size()) % kPageSize];
  364.         }
  365.     }
  366.  
  367.     size_t Size() const {
  368.         size_t res = 0;
  369.         for (size_t i = 0; i < cb_.Size(); ++i) {
  370.             res += cb_[i]->Size();
  371.         }
  372.  
  373.         return res;
  374.     }
  375.  
  376.     void Swap(Deque& other) {
  377.         swap(cb_, other.cb_);
  378.     }
  379.  
  380.     void PushBack(const T& value) {
  381.         if (cb_.Empty() || !(cb_.Back()->IsBack())) {
  382.             cb_.PushBack(new Page<T, kPageSize>);
  383.         }
  384.  
  385.         cb_.Back()->PushBack(value);
  386.     }
  387.  
  388.     void PushFront(const T& value) {
  389.         if (cb_.Empty() || !(cb_.Front()->IsFront())) {
  390.             cb_.PushFront(new Page<T, kPageSize>);
  391.         }
  392.  
  393.         cb_.Front()->PushFront(value);
  394.     }
  395.  
  396.     void PopBack() {
  397.         if (cb_.Empty()) {
  398.             return;
  399.         }
  400.  
  401.         cb_.Back()->PopBack();
  402.         if (cb_.Back->Empty()) {
  403.             delete cb_.Back();
  404.             cb_.PopBack();
  405.         }
  406.     }
  407.  
  408.     void PopFront() {
  409.         if (cb_.Empty()) {
  410.             return;
  411.         }
  412.  
  413.         cb_.Front()->PopFront();
  414.         if (cb_.Front()->Empty()) {
  415.             delete cb_.Front();
  416.             cb_.PopFront();
  417.         }
  418.     }
  419.  
  420.     void Clear() {
  421.         for (size_t i = 0; i < Size(); ++i) {
  422.             delete cb_[i];
  423.         }
  424.  
  425.         cb_.Clear();
  426.     }
  427. };
  428.  
  429. #include <iostream>
  430.  
  431. using namespace std;
  432.  
  433. int main()
  434. {
  435.     Deque<int> x;
  436.    
  437.     x.PushFront(2);
  438.     x.PushFront(1);
  439.     x.PushBack(3);
  440.    
  441.     Deque<int> a(x);
  442.    
  443.     cout << a[0] << " " << a[1] << " " << a[2];
  444.    
  445.     return 0;
  446. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement