User:Alf3xs: Difference between revisions

From Rosetta Code
Content added Content deleted
(Deque Implmentation Using a Circular Doubly Linked Unrolled Linked List of Circular Arrays)
 
(Blanked the page)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
#pragma once
#include <cstddef>
#include <utility>
#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;
}
}

Latest revision as of 03:11, 5 March 2019

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