User:Alf3xs

From Rosetta Code
Revision as of 02:59, 5 March 2019 by rosettacode>Alf3xs (Deque Implmentation Using a Circular Doubly Linked Unrolled Linked List of Circular Arrays)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
  1. pragma once
  2. include <cstddef>
  3. include <utility>
  4. include <iostream>

namespace afstl { // Deque Made from a Circular // Doubly Linked Unrolled Linked List template <typename T, size_t NodeCapacity> class deque;

namespace deque_utilities { class deque_error { public: explicit deque_error(const char* msg) : msg_(msg) { std::cerr << msg << std::endl; }

const char* what() const { return msg_; }

private: const char* msg_ = ""; };

// Circular Doubly Linked Unrolled Linked List Node // Circular Array Adapted from GeeksForGeeks // https://www.geeksforgeeks.org/implementation-deque-using-circular-array/ template <typename T, size_t Capacity> class node final { // Grant Private Access to Deque Class friend class deque<T, Capacity>; // Front Index size_t front_ = 0; // Back Index size_t back_ = 1; // Number of Elements Stored size_t size_ = 0; // Circular Array Holding Elements T* data_; // Pointer to Next Node node* next_ = this; // Pointer to Previous Node node* prev_ = this; // Check if the Node is the Header constexpr bool is_header() const; // Check if the Node is not the Header constexpr bool is_body() const; // Check if Array is Empty constexpr bool empty() const; // Check if the Array is Full constexpr bool full() const; // Constructor for Header node(); // Constructor for Body node(node* prev, node* next); // Destructor ~node(); // Default Copy Constructor (shallow) node(const node&) = default; // Default Copy Assignment Operator (shallow) node& operator=(const node&) = default; // Deleted Move Constructor node(node&&) noexcept = default; // Deleted Move Assignment Operator node& operator=(node&&) noexcept = default; // Push Front into Array void push_front(const T& item); // Push Back into Array void push_back(const T& item); // Pop Front of Array void pop_front(); // Pop Back of Array void pop_back(); // Reference to Front T& front(); // Constant Reference to Front const T& front() const; // Reference to Back T& back(); // Constant Reference to Back const T& back() const; };

template <typename T, size_t Capacity> node<T, Capacity>::node() : data_(nullptr) { }

template <typename T, size_t Capacity> node<T, Capacity>::node(node* prev, node* next) : data_(new T[Capacity]{}), next_(next), prev_(prev) { }

template <typename T, size_t Capacity> node<T, Capacity>::~node() { delete[] data_; }

template <typename T, size_t Capacity> void node<T, Capacity>::push_front(const T& item) { if (front_ == 0) { front_ = 1; back_ = 1; } else if (front_ == 1) { front_ = Capacity; } else { --front_; } data_[front_ - 1] = item; ++size_; }

template <typename T, size_t Capacity> void node<T, Capacity>::push_back(const T& item) { if (front_ == 0) { front_ = 1; back_ = 1; } else if (back_ == Capacity) { back_ = 1; } else { ++back_; } data_[back_ - 1] = item; ++size_; }

template <typename T, size_t Capacity> void node<T, Capacity>::pop_front() { if (front_ == back_) { front_ = 0; back_ = 0; } else { if (front_ == Capacity) { front_ = 1; } else { ++front_; } } --size_; }

template <typename T, size_t Capacity> void node<T, Capacity>::pop_back() { if (front_ == back_) { front_ = 0; back_ = 0; } else if (back_ == 1) { back_ = Capacity; } else { --back_; } --size_; }

template <typename T, size_t Capacity> T& node<T, Capacity>::front() { return data_[front_ - 1]; }

template <typename T, size_t Capacity> const T& node<T, Capacity>::front() const { return data_[front_ - 1]; }

template <typename T, size_t Capacity> T& node<T, Capacity>::back() { return data_[back_ - 1]; }

template <typename T, size_t Capacity> const T& node<T, Capacity>::back() const { return data_[back_ - 1]; }

template <typename T, size_t Capacity> constexpr bool node<T, Capacity>::empty() const { return front_ == 0; }

template <typename T, size_t Capacity> constexpr bool node<T, Capacity>::full() const { return (front_ == 1 && back_ == Capacity) || front_ == back_ + 1; }

template <typename T, size_t Capacity> constexpr bool node<T, Capacity>::is_header() const { // If data_ is nullptr then it is // the header dummy node return data_ == nullptr; }

template <typename T, size_t Capacity> constexpr bool node<T, Capacity>::is_body() const { // If data_ is not nullptr then it is // a body node that stores something return data_ != nullptr; } }

template <typename T, size_t NodeCapacity = 5> class deque final { // Node Storage Structures Typedef using node = deque_utilities::node<T, NodeCapacity>; // Header Node Declaration node header_ = node(); // Number of Elements Stored size_t size_ = 0; // Copy Other Deque Object void copy(const deque& other); public: // Constructor deque() = default; // Copy Constructor deque(const deque& other) noexcept; // Copy Assignment Operator deque& operator=(const deque& other) noexcept; // Move Constructor deque(deque&& other) noexcept; // Move Assignment Operator deque& operator=(deque&& other) noexcept; // Destructor ~deque(); // Push Front Operation void push_front(const T& item); // Push Back Operation void push_back(const T& item); // Pop Front Operation void pop_front(); // Pop Back Operation void pop_back(); // Reference to Front T& front(); // Const Reference to Front const T& front() const; // Reference to Back T& back(); // Constant Reference to Back const T& back() const; // Size Getter constexpr size_t size() const; // Size Checking constexpr bool empty() const; // Clear the deque void clear(); // Print Deque to std output void print() const; // Memory Allocations of Stack and Heap void print_mem() const; };

template <typename T, size_t NodeCapacity> void deque<T, NodeCapacity>::copy(const deque& other) { node* temp = other.header_.next_; while (temp != &(other.header_)) { node* alloc = new node(header_.prev_, &header_); header_.prev_->next_ = alloc; header_.prev_ = alloc; alloc->front_ = temp->front_; alloc->back_ = temp->back_; alloc->data_ = new T[NodeCapacity]{}; for (size_t i = 0; i < NodeCapacity; ++i) { alloc->data_[i] = temp->data_[i]; } temp = temp->next_; } size_ = other.size_; }

template <typename T, size_t NodeCapacity> deque<T, NodeCapacity>::deque(const deque& other) noexcept { copy(other); }

template <typename T, size_t NodeCapacity> deque<T, NodeCapacity>& deque<T, NodeCapacity>::operator=(const deque& other) noexcept { if (this != &other) { clear(); copy(other); } return *this; }

template <typename T, size_t NodeCapacity> deque<T, NodeCapacity>:: deque(deque&& other) noexcept : header_(std::move(other.header_)), size_(std::move(other.size_)) { }

template <typename T, size_t NodeCapacity> deque<T, NodeCapacity>& deque<T, NodeCapacity>::operator=(deque&& other) noexcept { if (this != &other) { clear(); header_ = std::move(other.header_); size_ = std::move(other.size_); } return *this; }

template <typename T, size_t NodeCapacity> deque<T, NodeCapacity>::~deque() { clear(); }

template <typename T, size_t NodeCapacity> void deque<T, NodeCapacity>::push_front(const T& item) { if (header_.next_->full() || header_.next_->is_header()) { node* temp = new node(&header_, header_.next_); header_.next_->prev_ = temp; header_.next_ = temp; } header_.next_->push_front(item); ++size_; }

template <typename T, size_t NodeCapacity> void deque<T, NodeCapacity>::push_back(const T& item) { if (header_.prev_->full() || header_.prev_->is_header()) { node* temp = new node(header_.prev_, &header_); header_.prev_->next_ = temp; header_.prev_ = temp; } header_.prev_->push_back(item); ++size_; }

template <typename T, size_t NodeCapacity> void deque<T, NodeCapacity>::pop_front() { if (size_ == 0) { throw deque_utilities::deque_error("deque: pop_front(): deque is empty"); } if (header_.next_->size_ == 1) { node* temp = header_.next_; temp->prev_->next_ = temp->next_; temp->next_->prev_ = temp->prev_; delete temp; } else { header_.next_->pop_front(); } --size_; }

template <typename T, size_t NodeCapacity> void deque<T, NodeCapacity>::pop_back() { if (size_ == 0) { throw deque_utilities::deque_error("deque: pop_back(): deque is empty"); } if (header_.prev_->size_ == 1) { node* temp = header_.prev_; temp->prev_->next_ = temp->next_; temp->next_->prev_ = temp->prev_; delete temp; } else { header_.prev_->pop_back(); } --size_; }

template <typename T, size_t NodeCapacity> T& deque<T, NodeCapacity>::front() { if (size_ == 0) { throw deque_utilities::deque_error("deque: front(): deque is empty"); } return header_.next_->front(); }

template <typename T, size_t NodeCapacity> const T& deque<T, NodeCapacity>::front() const { if (size_ == 0) { throw deque_utilities::deque_error("deque: front(): deque is empty"); } return header_.next_->front(); }

template <typename T, size_t NodeCapacity> T& deque<T, NodeCapacity>::back() { if (size_ == 0) { throw deque_utilities::deque_error("deque: back(): deque is empty"); } return header_.prev_->back(); }

template <typename T, size_t NodeCapacity> const T& deque<T, NodeCapacity>::back() const { if (size_ == 0) { throw deque_utilities::deque_error("deque: back(): deque is empty"); } return header_.prev_->back(); }

template <typename T, size_t NodeCapacity> void deque<T, NodeCapacity>::clear() { while (!(header_.next_->is_header())) { node* temp = header_.next_; header_.next_ = header_.next_->next_; delete temp; } }

template <typename T, size_t NodeCapacity> void deque<T, NodeCapacity>::print() const { std::cout << "Deque, size: " << size_ << std::endl; std::cout << "Front: " << front() << std::endl; std::cout << "Back: " << back() << std::endl; }

template <typename T, size_t NodeCapacity> void deque<T, NodeCapacity>::print_mem() const { std::cout << "Deque, size: " << size_ << std::endl; std::cout << "Stack: " << sizeof(header_) + sizeof size_ << " bytes" << std::endl; size_t heap_mem = 0; for (node* tmp = header_.next_; tmp != &header_; tmp = tmp->next_) { heap_mem += sizeof(tmp); } std::cout << "Heap: " << heap_mem << " bytes" << std::endl; }

template <typename T, size_t NodeCapacity> constexpr size_t deque<T, NodeCapacity>::size() const { return size_; }

template <typename T, size_t NodeCapacity> constexpr bool deque<T, NodeCapacity>::empty() const { return size_ == 0; } }

Retrieved from "https://rosettacode.org/wiki/User:Alf3xs?oldid=288478"