Incomplete linked list

linked_list_incomplete.hpp

#ifdef _MSC_VER
#pragma once
#endif

#ifndef LIST_HPP
#define LIST_HPP

#include <cstddef>
#include <iterator>
#include <initializer_list>
#include <memory>

namespace std
{

template <typename T>
class list
{
public:
  using value_type       = T;
  using pointer          = T*;
  using reference        = T&;
  using const_reference  = const T&;
  using size_type        = std::size_t;
  using difference_type  = std::ptrdiff_t;

  class iterator;
  class const_iterator;

  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  explicit list();
  list(const list& _another);
  list(size_type _n);
  list(size_type _n, const value_type& _value);
  template <typename InputIterator>
  list(InputIterator _first, InputIterator _last);
  list(std::initializer_list<value_type> _list);
  ~list();

  size_type size() const;
  bool empty() const;

  iterator insert(const_iterator _position, const value_type& _value);
  iterator insert(const_iterator _position, value_type&& _value);
  iterator insert(const_iterator _position,
                  size_type _n, const value_type &_value);
  template <typename InputIterator>
  iterator insert(const_iterator _position,
                  InputIterator _first, InputIterator _last);
  iterator insert(const_iterator _position,
                  std::initializer_list<value_type> _ilist);

  template <typename... Args>
  iterator emplace(const_iterator _position, Args&& ..._args);
  template <typename... Args>
  iterator emplace_back(Args&& ..._args);
  template <typename... Args>
  iterator emplace_front(Args&& ..._args);

  void push_back(const value_type& _value);
  void push_front(const value_type& _value);

  iterator erase(const_iterator _position);
  iterator erase(const_iterator _first, const_iterator _last);

  void pop_back();
  void pop_front();

  void clear() noexcept;

  void remove(const value_type& _value);
  template <typename UnaryPredicate>
  void remove_if(UnaryPredicate _pred);

  void unique();
  template <typename BinaryPredicate>
  void unique(BinaryPredicate _pred);

  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);

  void swap(list& _another) noexcept;

  iterator begin() noexcept;
  iterator end() noexcept;

  const_iterator begin() const noexcept;
  const_iterator end() const noexcept;

  const_iterator cbegin() const noexcept;
  const_iterator cend() const noexcept;

  reverse_iterator rbegin() noexcept;
  reverse_iterator rend() noexcept;

  const_reverse_iterator rbegin() const noexcept;
  const_reverse_iterator rend() const noexcept;

  const_reverse_iterator crbegin() const noexcept;
  const_reverse_iterator crend() const noexcept;

private:
  struct list_node_base
  {
    list_node_base* prev = nullptr;
    list_node_base* next = nullptr;

    list_node_base() = default;
    ~list_node_base() = default;
  };

  struct list_node : public list_node_base
  {
    T value;
    template <typename... Args>
    list_node(Args&& ..._args) : value(_args...) {}
    ~list_node() = default;
  };

  void register_node(const list_node_base* _node);
  void detach_node(const list_node_base* _node);
  bool search_node(const list_node_base* _node) const;

  template <typename ListIterator>
  void check_iterator(const ListIterator& _iter) const noexcept;

  list_node_base *head;
  std::shared_ptr<bool> validating_ptr;
};

template <typename T>
class list<T>::iterator
{
  friend class list;
public:
  using iterator_category = std::bidirectional_iterator_tag;
  using value_type        = typename list::value_type;
  using difference_type   = typename list::difference_type;
  using pointer           = typename list::pointer;
  using reference         = typename list::reference;
  using const_reference   = typename list::const_reference;

  iterator(void) = default;
  iterator(const iterator& _another) = default;
  // See C++ Defect Report #179
  iterator(const typename list::const_iterator& _const_iterator);
  ~iterator() = default;

  reference operator* (void);
  const_reference operator* (void) const;

  bool operator== (const iterator& _another) const;
  bool operator!= (const iterator& _another) const;

  iterator& operator++ (void);
  iterator& operator-- (void);
  iterator operator++ (int);
  iterator operator-- (int);

private:
  iterator(list *_get_from, typename list::list_node_base *_node);

  list *get_from = nullptr;
  typename list::list_node_base *node = nullptr;
  std::shared_ptr<bool> validating_ptr;
};

template <typename T>
class list<T>::const_iterator
{
  friend class list;
public:
  using iterator_category = std::bidirectional_iterator_tag;
  using value_type        = typename list::value_type;
  using difference_type   = typename list::difference_type;
  using pointer           = typename list::pointer;
  using reference         = typename list::reference;
  using const_reference   = typename list::const_reference;

  const_iterator() = default;
  const_iterator(const const_iterator& _another) = default;
  // See C++ Defect Report #179
  const_iterator(const typename list::iterator& _mutable_iterator);
  ~const_iterator() = default;

  bool operator== (const const_iterator& _another) const;
  bool operator!= (const const_iterator& _another) const;

  const_reference operator* (void) const;
  const_iterator& operator++ (void);
  const_iterator& operator-- (void);
  const_iterator operator++ (int);
  const_iterator operator-- (int);

private:
  const_iterator(const list *_get_from,
                 const typename list::list_node_base *_node);

  void check_initialized(void) const noexcept;
  void check_valid(void) const noexcept;
  void check_dereferencable(void) const noexcept;

  const list *get_from = nullptr;
  const typename list::list_node_base *node = nullptr;
  std::shared_ptr<bool> validating_ptr;
};

template <typename T>
list<T>::list() :
  head(new list_node_base()),
  validating_ptr(new bool(true))
{
  head->prev = head;
  head->next = head;
}

template <typename T>
list<T>::list(const list &_another)
{
  insert(cend(), _another.cbegin(), _another.cend());
}

template <typename T>
list<T>::list(size_type _n, const value_type &_value)
{
  insert(cend(), _n, _value);
}

template <typename T>
list<T>::list(size_type _n) : list(_n, value_type())
{
}

template <typename T>
list<T>::list(std::initializer_list<value_type> _ilist)
{
  insert(cend(), _ilist.begin(), _ilist.end());
}

template <typename T>
template <typename InputIterator>
list<T>::list(InputIterator _first, InputIterator _last)
{
  insert(cend(), _first, _last);
}

template <typename T>
list<T>::~list()
{
  erase(cbegin(), cend());
  delete head;
  *(validating_ptr.get()) = false;
}

template <typename T>
typename list<T>::size_type
list<T>::size() const
{
  return distance(begin(), end());
}

template <typename T>
bool
list<T>::empty() const
{
  return (head->next == head);
}

template <typename T>
typename list<T>::iterator
list<T>::insert(const_iterator _position, const value_type &_value)
{
  return emplace(_position, _value);
}

template <typename T>
typename list<T>::iterator
list<T>::insert(const_iterator _position, value_type &&_value)
{
  return emplace(_position, std::move(_value));
}

template <typename T>
typename list<T>::iterator
list<T>::insert(const_iterator _position, size_type _n,
                const value_type &_value)
{
  for (size_type i = 0; i < _n; ++i)
  {
    insert(_position, _value);
  }
}

template <typename T>
template <typename InputIterator>
typename list<T>::iterator
list<T>::insert(const_iterator _position,
                InputIterator _first, InputIterator _last)
{
  for (; _first != _last; ++_first)
  {
    insert(_position, *_first);
  }

  return iterator(this, const_cast<list_node_base*>(_position.node));
}

template <typename T>
typename list<T>::iterator
list<T>::insert(const_iterator _position,
                std::initializer_list<value_type> _ilist)
{
  return insert(_position, _ilist.begin(), _ilist.end());
}

template <typename T>
template <typename... Args>
typename list<T>::iterator
list<T>::emplace(const_iterator _position, Args&&... _args)
{
  _position.check_valid();
  check_iterator(_position);
  iterator position(this, const_cast<list_node_base*>(_position.node));

  list_node *node = (list_node*)malloc(sizeof(list_node));
  construct(node, std::forward<Args>(_args)...);

  node->prev = position.node->prev;
  node->next = position.node;

  position.node->prev->next = node;
  position.node->prev = node;

  register_node(node);

  return iterator(this, node);
}

template <typename T>
template <typename... Args>
typename list<T>::iterator
list<T>::emplace_back(Args&&... _args)
{
  emplace(cend(), std::forward<Args>(_args)...);
}

template <typename T>
template <typename... Args>
typename list<T>::iterator
list<T>::emplace_front(Args&&... _args)
{
  emplace(cbegin(), std::forward<Args>(_args)...);
}

template <typename T>
void
list<T>::push_back(const value_type &_value)
{
  insert(cend(), _value);
}

template <typename T>
void
list<T>::push_front(const value_type &_value)
{
  insert(cbegin(), _value);
}

template <typename T>
typename list<T>::iterator
list<T>::erase(const_iterator _position)
{
  _position.check_dereferencable();
  check_iterator(_position);
  list_node_base *prev = _position.node->prev,
      *next = _position.node->next;

  prev->next = next;
  next->prev = prev;

  list_node_base *mutable_node =
      const_cast<list_node_base*>(_position.node);
  list_node *converted_node =
      reinterpret_cast<list_node*>(mutable_node);

  detach_node(_position.node);
  destroy_at(converted_node);
  free(converted_node);
  return iterator(this, next);
}

template <typename T>
typename list<T>::iterator
list<T>::erase(const_iterator _first, const_iterator _last)
{
  for  (; _first != _last; _first = erase(_first));
  return iterator(this, const_cast<list_node_base*>(_last.node));
}

template <typename T>
void
list<T>::pop_back()
{
  erase(--cend());
}

template <typename T>
void
list<T>::pop_front()
{
  erase(cbegin());
}

template <typename T>
void
list<T>::clear() noexcept
{
  erase(cbegin(), cend());
}

template <typename T>
void
list<T>::remove(const value_type &_value)
{
  remove_if(
        [&](const value_type& _another) -> bool
  {
    return _another == _value;
  }
  );
}

template <typename T>
template <typename UnaryPredicate>
void
list<T>::remove_if(UnaryPredicate _pred)
{
  for (auto it = begin(); it != end();)
  {
    if (_pred(*it))
    {
      it = erase(it);
    }
    else
    {
      ++it;
    }
  }
}

template <typename T>
void
list<T>::unique()
{
  unique(std::equal_to<T>());
}

template <typename T>
template <typename BinaryPredicate>
void
list<T>::unique(BinaryPredicate _binary_pred)
{
  if (cbegin() == cend()) return;

  auto it = cbegin(),
      it2 = ++cbegin();
  while (it2 != cend())
  {
    if (_binary_pred(*it, *it2))
    {
      it = erase(it);
    }
    else
    {
      ++it;
    }

    it2 = it++;
    std::swap(it2, it);
  }
}

template <typename T>
void
list<T>::splice(const_iterator _pos, list &_other)
{
  splice(_pos, _other, _other.begin(), _other.end());
}

template <typename T>
void
list<T>::splice(const_iterator _pos, list &_other,
                           const_iterator _it)
{
  splice(_pos, _other, _it, _other.cend());
}

template <typename T>
void
list<T>::splice(const_iterator _pos, list &_other,
                           const_iterator _first, const_iterator _last)
{
  _pos.check_valid();
  check_iterator(_pos);
  _first.check_valid();
  _last.check_valid();
  _other.check_iterator(_first);
  _other.check_iterator(_last);

  insert(_pos, _first, _last);
  _other.erase(_first, _last);
}

template <typename T>
void
list<T>::swap(list &_another) noexcept
{
  std::swap(head, _another.head);
}

template <typename T>
typename list<T>::iterator
list<T>::begin() noexcept
{
  return iterator(this, head->next);
}

template <typename T>
typename list<T>::iterator
list<T>::end() noexcept
{
  return iterator(this, head);
}

template <typename T>
typename list<T>::const_iterator
list<T>::begin() const noexcept
{
  return const_iterator(this, head->next);
}

template <typename T>
typename list<T>::const_iterator
list<T>::end() const noexcept
{
  return const_iterator(this, head);
}

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 noexcept
{
  return end();
}

template <typename T>
typename list<T>::reverse_iterator
list<T>::rbegin() noexcept
{
  return reverse_iterator(end());
}

template <typename T>
typename list<T>::reverse_iterator
list<T>::rend() noexcept
{
  return reverse_iterator(begin());
}

template <typename T>
typename list<T>::const_reverse_iterator
list<T>::rbegin() const noexcept
{
  return const_reverse_iterator(cend());
}

template <typename T>
typename list<T>::const_reverse_iterator
list<T>::rend() const noexcept
{
  return const_reverse_iterator(cbegin());
}

template <typename T>
typename list<T>::const_reverse_iterator
list<T>::crbegin() const noexcept
{
  return rbegin();
}

template <typename T>
typename list<T>::const_reverse_iterator
list<T>::crend() const noexcept
{
  return rend();
}

template <typename T>
list<T>::iterator::iterator
(const typename list::const_iterator& _const_iterator) :
  get_from(const_cast<list*>(_const_iterator.get_from)),
  node(const_cast<typename list::list_node_base*>(_const_iterator.node)),
  validating_ptr(_const_iterator.validating_ptr)
{
}

template <typename T>
bool
list<T>::iterator::operator== (const iterator& _another) const
{
  check_valid();
  return node == _another.node;
}

template <typename T>
bool
list<T>::iterator::operator!= (const iterator& _another) const
{
  return ! operator==(_another);
}

template <typename T>
typename list<T>::iterator::reference
list<T>::iterator::operator*()
{
  check_dereferencable();
  return (reinterpret_cast<typename list::list_node*>(node))->value;
}

template <typename T>
typename list<T>::iterator::const_reference
list<T>::iterator::operator*() const
{
  check_dereferencable();
  return (reinterpret_cast<const typename list::list_node*>(node))->value;
}

template <typename T>
typename list<T>::iterator&
list<T>::iterator::operator++()
{
  check_valid();
  node = node->next;
  return *this;
}

template <typename T>
typename list<T>::iterator&
list<T>::iterator::operator--()
{
  check_valid();
  node = node->prev;
  return *this;
}

template <typename T>
typename list<T>::iterator
list<T>::iterator::operator++(int)
{
  check_valid();
  iterator ret(*this);
  node = node->next;
  return ret;
}

template <typename T>
typename list<T>::iterator
list<T>::iterator::operator--(int)
{
  check_valid();
  iterator ret(*this);
  node = node->prev;
  return ret;
}

template <typename T>
list<T>::iterator::iterator(list *_get_from,
                                       typename list::list_node_base *_node) :
  get_from(_get_from),
  node(_node),
  validating_ptr(_get_from->validating_ptr)
{
}


template <typename T>
list<T>::const_iterator::const_iterator(
    const typename list::iterator& _mutable_iterator) :
  get_from(_mutable_iterator.get_from),
  node(_mutable_iterator.node),
  validating_ptr(_mutable_iterator.validating_ptr)
{
}

template <typename T>
bool
list<T>::const_iterator::operator== (
    const const_iterator& _another) const
{
  check_valid();
  return node == _another.node;
}

template <typename T>
bool
list<T>::const_iterator::operator!= (
    const const_iterator& _another) const
{
  return ! operator==(_another);
}

template <typename T>
typename list<T>::const_iterator::const_reference
list<T>::const_iterator::operator*() const
{
  check_dereferencable();
  return reinterpret_cast<const typename list::list_node*>(node)->value;
}

template <typename T>
typename list<T>::const_iterator&
list<T>::const_iterator::operator++()
{
  check_valid();
  node = node->next;
  return *this;
}

template <typename T>
typename list<T>::const_iterator&
list<T>::const_iterator::operator--()
{
  check_valid();
  node = node->prev;
  return *this;
}

template <typename T>
typename list<T>::const_iterator
list<T>::const_iterator::operator++(int)
{
  check_valid();
  const_iterator ret(*this);
  node = node->next;
  return ret;
}

template <typename T>
typename list<T>::const_iterator
list<T>::const_iterator::operator--(int)
{
  check_initialized();
  check_valid();
  const_iterator ret(*this);
  node = node->prev;
  return ret;
}

template <typename T>
list<T>::const_iterator::const_iterator(
    const list *_get_from,
    const typename list::list_node_base *_node) :
  get_from(_get_from),
  node(_node),
  validating_ptr(_get_from->validating_ptr)
{
}

template <typename T>
void
swap(list<T>& _a, list<T>& _b)
{
  _a.swap(_b);
}

} // namespace std

#endif // LIST_HPP

int main() {
}