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)
 
(Deque in C++)
Line 1: Line 1:
Below is a C++ implementation of a Deque.
#pragma once
#include <cstddef>
#include <utility>
#include <iostream>


It uses a Circular Doubly Linked Unrolled Linked List of Circular Arrays as its underlying data structure to increase pushing and popping performance. Insertions and erasures, while are both constant time in circular arrays and linked lists, they are noticeably faster (at least without optimizations) in arrays.
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;
}
}

Revision as of 03:10, 5 March 2019

Below is a C++ implementation of a Deque.

It uses a Circular Doubly Linked Unrolled Linked List of Circular Arrays as its underlying data structure to increase pushing and popping performance. Insertions and erasures, while are both constant time in circular arrays and linked lists, they are noticeably faster (at least without optimizations) in arrays.

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