#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
#include <iterator>
#include <type_traits>
#include <iostream>
template <typename T>
class List
{
struct Node
{
T data;
Node* prev = nullptr;
Node* next = nullptr;
Node() = default;
Node(const T& d) : data(d), prev(nullptr), next(nullptr) {}
Node(T&& d) : data(d), prev(nullptr), next(nullptr) {}
template<typename... Args> Node(Args&&... args) : data(std::forward<Args>(args)...) {}
};
Node* head = nullptr;
Node *tail = nullptr;
std::size_t l_size = 0;
//SFINAE
template <typename Iter>
using required_input_iterator = std::enable_if<std::is_base_of_v<std::input_iterator_tag,
typename std::iterator_traits<Iter>::iterator_category >>;
public:
using reference = T&;
using const_reference = const T&;
using size_type = std::size_t;
class const_iterator ;
class iterator : public std::input_iterator_tag
{
Node * node = nullptr;
friend class List;
iterator(Node* p) : node(p) {}
public:
iterator(const_iterator x) : node(x.node) {}
using value_type = std::remove_reference_t<T>;
using difference_type = std::ptrdiff_t;
using pointer = value_type*;
using reference = value_type&;
using iterator_category = std::bidirectional_iterator_tag;
public:
iterator () = default;
reference operator*()
{
return node->data;
}
reference operator->()
{
return node->data;
}
// prefix operators
iterator& operator++()
{
node = node->next;
return *this;
}
iterator& operator--()
{
node = node->prev;
return *this;
}
// postfix operators
iterator operator++(int)
{
Node* temp = this->node;
node = node->next;
return temp;
}
iterator operator--(int)
{
Node* temp = this->node;
node = node->prev;
return temp;
}
friend bool operator== (const iterator& lhs, const iterator& rhs) noexcept
{
return lhs.node == rhs.node;
}
friend bool operator!= (const iterator& lhs, const iterator& rhs) noexcept
{
return lhs.node != rhs.node;
}
};
class const_iterator
{
Node* node = nullptr;
friend class List;
const_iterator (Node* p) : node(p) {}
public:
const_iterator (const iterator& x) : node(x.node) {}
using value_type = std::remove_reference_t<T>;
using difference_type = std::ptrdiff_t;
using pointer = value_type*;
using reference = value_type&;
using iterator_category = std::bidirectional_iterator_tag;
public:
const_iterator () = default;
const_iterator(const const_iterator& other) : node(other.node) {}
reference operator*()
{
return node->data;
}
T* operator->()
{
return node->data;
}
// prefix operators
const_iterator& operator++()
{
node = node->next;
return *this;
}
const_iterator& operator--()
{
node = node->prev;
return *this;
}
// postfix operators
const_iterator operator++(int)
{
Node* temp = this->node;
node = node->next;
return temp;
}
const_iterator operator--(int)
{
Node* temp = this->node;
node = node->prev;
return temp;
}
friend bool operator== (const const_iterator& lhs, const const_iterator& rhs) noexcept
{
return lhs.node == rhs.node;
}
friend bool operator!= (const const_iterator& lhs, const const_iterator& rhs) noexcept
{
return lhs.node != rhs.node;
}
};
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
List() = default;
explicit List(size_type n);
List(size_type n, const_reference v);
List(const std::initializer_list<T>& i_list);
template<typename InputIterator, typename = required_input_iterator<InputIterator>> List(InputIterator first, InputIterator last);
List(const List& src);
List& operator=(List src);
List(List&& src);
//~List();
void assign(size_type n, const_reference v);
void assign(const std::initializer_list<T>& i_list);
template<typename InputIterator, typename = required_input_iterator<InputIterator>> void assign(InputIterator first, InputIterator last);
// element acces
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// iterators
iterator begin() noexcept;
const_iterator begin() const noexcept;
iterator end() noexcept;
const_iterator end() const noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend() const;
reverse_iterator rbegin() noexcept;
const_reverse_iterator crbegin() const noexcept;
reverse_iterator rend() noexcept;
const_reverse_iterator crend() const noexcept;
// capacity
size_type size() const noexcept;
bool empty() const noexcept;
// modifiers
void clear() noexcept;
iterator insert(const_iterator pos, const_reference v);
iterator insert(const_iterator pos, T&& v);
iterator insert(const_iterator pos, size_type n, const_reference v);
template<typename InputIterator, typename = required_input_iterator<InputIterator>> iterator insert(const_iterator pos, InputIterator first, InputIterator last);
iterator insert(const_iterator pos, std::initializer_list<T> i_list);
template<typename... Args> iterator emplace(const_iterator pos, Args&&... args );
iterator erase(const_iterator pos);
iterator erase(const_iterator first, const_iterator last);
void push_back(const_reference v);
void push_back(T&& v);
template<typename... Args> reference emplace_back(Args&&...args);
void pop_back();
void push_front(const_reference v);
void push_front(T&& v);
template<typename... Args> reference emplace_front(Args&&...args);
void pop_front();
void resize(size_type new_size);
void resize(size_type new_size, const_reference v);
void swap(List& other) noexcept;
// Operations
void merge( List& other );
void merge( List&& other );
template <class Compare> void merge( List& other, Compare comp );
template <class Compare> void merge( List&& other, Compare comp );
void splice( const_iterator pos, List& other );
void splice( const_iterator pos, List&& other );
void splice( const_iterator pos, List& other, const_iterator it );
void splice( const_iterator pos, List&& other, const_iterator it );
void splice( const_iterator pos, List& other, const_iterator first, const_iterator last);
void splice( const_iterator pos, List&& other, const_iterator first, const_iterator last );
size_type remove(const_reference v);
template<typename UnaryPredicate>size_type remove_if(UnaryPredicate p);
void reverse() noexcept;
size_type unique();
template<typename BinaryPredicate> size_type unique(BinaryPredicate p);
void sort();
template <class Compare> void sort(Compare comp);
// Non-member functions
template<typename H>
friend bool operator==(const List<H>& lhs, const List<H>& rhs);
void display();
};
template<typename T>
void List<T>::display()
{
for(auto e: *this)
std::cout << e << ' ';
std::cout << '\n';
}
template <typename T>
List<T>::List(size_type n)
{
if (n == 0)
return;
resize(n);
}
template <typename T>
List<T>::List(size_type n, const_reference v)
{
if (n == 0)
return;
insert(end(), n, v);
}
template <typename T>
List<T>::List(const std::initializer_list<T>& i_list) : l_size(i_list.size())
{
if(l_size == 0)
return;
insert(end(), i_list.begin(), i_list.end());
}
template<typename T>
template<typename InputIterator, typename SFINAE >
List<T>::List(InputIterator first, InputIterator last)
{
size_type dist = 0;
for(auto it = first; it != last; ++it)
++dist;
if(dist == 0)
return;
insert(end(), first, last);
}
template<typename T>
List<T>::List(const List& other)
{
Node* source = other.head;
while(source)
{
emplace_back(source->data);
source = source->next;
}
}
template<typename T>
List<T>::List(List&& other)
{
this->swap(other);
}
template<typename T>
List<T>& List<T>::operator=(List other)
{
this->swap(other);
return *this;
}
template<typename T>
void List<T>::assign(size_type n, const_reference v)
{
clear();
insert(begin(), n, v);
}
template<typename T>
template<typename InputIterator, typename SFINAE>
void List<T>::assign(InputIterator first, InputIterator last)
{
clear(),
insert(end(), first, last);
}
template<typename T>
void List<T>::assign(const std::initializer_list<T>& i_list)
{
clear();
insert(end(), i_list.begin(), i_list.end());
}
// element acess
template<typename T>
typename List<T>::reference List<T>::front()
{
return *begin();
}
template<typename T>
typename List<T>::const_reference List<T>::front() const
{
return *begin();
}
template<typename T>
typename List<T>::reference List<T>::back()
{
return tail->data;
}
template<typename T>
typename List<T>::const_reference List<T>::back() const
{
return tail->data;
}
// iterators
template<typename T>
typename List<T>::const_iterator List<T>::begin() const noexcept
{
return const_iterator(head);
}
template<typename T>
typename List<T>::iterator List<T>::begin() noexcept
{
return iterator(head);
}
template<typename T>
typename List<T>::iterator List<T>::end() noexcept
{
return nullptr;
}
template<typename T>
typename List<T>::const_iterator List<T>::end() const noexcept
{
return const_iterator(tail);
}
template<typename T>
typename List<T>::const_iterator List<T>::cbegin() const noexcept
{
return begin();
}
template<typename T>
typename List<T>::const_iterator List<T>::cend() const
{
return end();
}
template<typename T>
typename List<T>::reverse_iterator List<T>::rbegin() noexcept
{
return reverse_iterator(tail);
}
template<typename T>
typename List<T>::const_reverse_iterator List<T>::crbegin() const noexcept
{
}
template<typename T>
typename List<T>::reverse_iterator List<T>::rend() noexcept
{
return reverse_iterator(head);
}
template<typename T>
typename List<T>::const_reverse_iterator List<T>::crend() const noexcept
{
}
// capacity
template<typename T>
typename List<T>::size_type List<T>::size() const noexcept
{
return l_size;
}
template<typename T>
bool List<T>::empty() const noexcept
{
return l_size == 0;
}
// modifiers
template<typename T>
void List<T>::clear() noexcept
{
Node* temp;
while(head)
{
temp = head;
head = head->next;
delete temp;
}
tail = head = nullptr;
l_size = 0;
}
template<typename T>
typename List<T>::iterator List<T>::insert(const_iterator pos, const_reference v)
{
return emplace(pos, v);
}
template<typename T>
typename List<T>::iterator List<T>::insert(const_iterator pos, T&& v)
{
return emplace(pos, std::forward<const_reference>(v));
}
template<typename T>
typename List<T>::iterator List<T>::insert(const_iterator pos,
size_type n, const_reference v)
{
if(n == 0)
return iterator(pos);
iterator iter = emplace(pos, std::move(v));
for(int i = 0; i < n - 1; ++i)
emplace(pos, v);
return iter;
}
template<typename T>
template<typename InputIterator, typename SFINAE>
typename List<T>::iterator List<T>::insert(const_iterator pos, InputIterator first, InputIterator last)
{
while(first != last)
emplace(pos, *first++);
}
template<typename T>
template<typename... Args>
typename List<T>::iterator List<T>::emplace(const_iterator pos, Args&&... args )
{
Node* curr = pos.node;
Node* new_node = new Node(std::forward<Args>(args)...);
if( ! head) // if list is empty
{
head = tail = new_node;
head->prev = nullptr;
tail->next = nullptr;
}
else if(curr == nullptr) // to the end of the list
{
tail->next = new_node;
new_node->prev = tail;
tail = new_node;
tail->next = nullptr;
}
else if(curr == head) // to the beginnig of the list
{
curr->prev = new_node;
new_node->next = curr;
head = new_node;
}
else // in the middle
{
Node* temp = head;
while(temp)
{
if(curr == temp)
{
if(curr->prev)
curr->prev->next = new_node;
new_node->prev = curr->prev;
new_node->next = curr;
curr->prev = new_node;
curr = new_node;
break;
}
temp = temp->next;
}
}
++l_size;
return iterator(new_node);
}
template<typename T>
typename List<T>::iterator List<T>::erase(const_iterator pos)
{
Node* curr = pos.node;
Node* temp = head;
while(temp)
{
if(curr == temp)
{
if( curr == head) // meaning that it is the beginning of the list
{
if(temp->next) // if there is more than one element
{
head = temp->next;
head->prev = nullptr;
}
else
head = tail = nullptr;
}
else
{
temp->prev->next = temp->next;
if(temp->next)
temp->next->prev = temp->prev;
}
delete temp;
--l_size;
break;
}
temp = temp->next;
}
if(temp->next)
return iterator(temp->next);
return iterator(temp);
}
template<typename T>
typename List<T>::iterator List<T>::erase(const_iterator first, const_iterator last)
{
if (first == head && last == nullptr)
{
clear();
}
else
{
while(first != last)
{
erase(first++);
}
return iterator(last.node);
}
}
template <typename T>
void List<T>::push_back(const_reference v)
{
emplace_back(v);
}
template <typename T>
void List<T>::push_back(T&& v)
{
emplace_back(std::forward<T>(v));
}
template <typename T>
template<typename... Args>
typename List<T>::reference List<T>::emplace_back(Args&&...args)
{
Node* new_node = new Node(std::forward<Args>(args)...);
if(head == nullptr)
{
head = tail = new_node;
head->prev = nullptr;
tail->next = nullptr;
}
else
{
tail->next = new_node;
new_node->prev = tail;
tail = new_node;
tail->next = nullptr;
}
++l_size;
return new_node->data;
}
template <typename T>
void List<T>::pop_back()
{
Node* temp = tail;
if(temp->prev)
{
tail = temp->prev;
tail->next = nullptr;
delete temp;
}
else // only one element in this list
{
Node* node = head;
head = tail = nullptr;
delete node;
}
--l_size;
}
template <typename T>
void List<T>::push_front(const_reference v)
{
emplace_front(v);
}
template <typename T>
void List<T>::push_front(T&& v)
{
emplace_front(std::forward<T>(v));
}
template <typename T>
template<typename... Args>
typename List<T>::reference List<T>::emplace_front(Args&&...args)
{
Node* new_node = new Node(std::forward<Args>(args)...);
if( ! head)
return emplace_back(std::forward<Args>(args)...);
head->prev = new_node;
new_node->next = head;
head = new_node;
++l_size;
return new_node->data;
}
template <typename T>
void List<T>::pop_front()
{
erase(begin());
}
template <typename T>
void List<T>::resize(size_type n)
{
if(n >= l_size)
{
for(size_type i = l_size; i < n; ++i)
{
emplace_back(std::forward<T>(T()));
}
}
else
{
for(size_type i = l_size; i > n; --i)
pop_back();
}
}
template <typename T>
void List<T>::resize(size_type n, const_reference v)
{
if(n >= l_size)
{
for(size_type i = l_size; i < n; ++i)
{
emplace_back(v);
}
}
else
{
for(size_type i = l_size; i > n; --i)
pop_back();
}
}
template<typename T>
void List<T>::swap(List& other) noexcept
{
using std::swap;
std::swap(head, other.head);
std::swap(tail, other.tail);
std::swap(l_size, other.l_size);
}
// Operations
template<typename T>
void List<T>::merge( List& other )
{
if( ! (*this == other))
merge(std::move(other));
}
template<typename T>
void List<T>::merge( List&& other )
{
if( ! (*this == other))
{
for(auto e: other)
emplace_back(std::forward<T>(e));
// in std::list no elements are copied. The container other becomes empty after the operation.
// I don't know how the std::list::merge is implemented that it empties the 'other' container
// so to mimick std::list I did this, is it correct?
// Also have I achieved the goal of not making any copy in merge method?
other.clear();
}
}
template<typename H>
bool operator==(const List<H>& lhs, const List<H>& rhs)
{
if(lhs.size() != rhs.size())
return false;
auto rtemp = rhs.head;
auto ltemp = lhs.head;
while(rtemp || ltemp )
{
if(rtemp->data != ltemp->data)
return false;
rtemp = rtemp->next;
ltemp = ltemp->next;
}
return true;
}
#endif // LIST_H_INCLUDED
