Sans Pareil Technologies, Inc.

Key To Your Business

Lab 11 - Doubly Linked List


In this exercise we will implement a doubly linked list using std::unique_ptr to manage dynamically allocated node instances stored in the list. Most of the code is identical to the code we used in Singly Linked List, with just a few changes to manage the previous pointer to the preceding Node in the list.

Node


We will use a Node structure that will store the data for the linked list element, a std::unique_ptr to the next node in the linked list, and a pointer to the previous node in the linked list.

Iterators


We will use a BaseIterator class that inherits from std::iterator and will be aliases to iterator and const_iterator as appropriate for the linked list. Since we have a previous link, this iterator will be bi-directional.

using iterator = BaseIterator<Data>;
using const_iterator = BaseIterator<Data const>;


LinkedList


We will model our list implementation on the interface specified for std::list. We will not implement every function specified in the standard (splice for instance, and a few relational operators). As with an object oriented language, we will totally encapsulate the Node structure and not expose it to callers. Standard list operations will be implemented as instance member functions as these generally require access to the internal (private) members of the list.

DoublyLinkedList.h

The main header file that defines the doubly linked list implementation. Note the nested private Node struct, and the BaseIterator class that implements the iterator for our data structure. We move most of the implementation details into DoubleListImpl.h include file for readability. These types of “private” include files are often given an extension tpp to indicate that these are template implementation include files.

#pragma once

#include <initializer_list>
#include <memory>
#include <type_traits>
#include <utility>
#include <functional>

namespace csc240
{
  template <typename Data>
  class DoublyLinkedList
  {
    struct Node;

    template <typename T>
    using iterator_value_type = typename std::remove_reference<
      decltype( *std::declval<T>() )>::type;

  public:
#include "DLLIterator.h"

    using iterator = BaseIterator<Data>;
    using const_iterator = BaseIterator<Data const>;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    DoublyLinkedList() = default;

    template <typename Iterator>
    DoublyLinkedList( Iterator first, Iterator last ) { assign( first, last ); }

    DoublyLinkedList( const std::initializer_list<Data>& list ) :
      DoublyLinkedList( list.begin(), list.end() )
    {}

    DoublyLinkedList( DoublyLinkedList&& rhs ) noexcept
    {
      swap( rhs );
    }

    DoublyLinkedList( const DoublyLinkedList& ) = delete;
    DoublyLinkedList& operator=( const DoublyLinkedList& ) = delete;

    DoublyLinkedList& operator=( const std::initializer_list<Data>& list );

    DoublyLinkedList& operator=( DoublyLinkedList&& rhs )  noexcept
    {
      rhs.swap( *this );
      return *this;
    }

    Data& front() { return head->data; }
    const Data& front() const { return head->data; }

    const Data& back() { return tail->data; }
    const Data& back() const { return tail->data; }

    void assign( std::size_t number, const Data& data )
    {
      clear();
      for ( std::size_t i = 0; i < number; ++i ) emplace_back( data );
    }

    template<typename InputIterator>
    void assign( InputIterator first, InputIterator last );

    void assign( const std::initializer_list<Data>& list )
    {
      assign( list.begin(), list.end() );
    }

    void push_front( const Data& data ) { emplace_front( data ); }
    void push_front( Data&& data ) { emplace_front( std::forward( data ) ); }

    void push_back( const Data& data ) { emplace_back( data ); }
    void push_back( Data&& data ) { emplace_back( std::forward( data ) ); }

    template <typename... Args>
    void emplace_front( Args&&... args );

    template <typename... Args>
    void emplace_back( Args&&... args );

    template <typename... Args>
    iterator emplace( const_iterator position, Args&&... args );

    iterator insert( const_iterator position, const Data& value )
    {
      return emplace( position, value );
    }

    iterator insert( const_iterator position, Data&& value )
    {
      return emplace( position, std::forward( value ) );
    }

    iterator insert( const_iterator position, std::size_t number, const Data& val );

    template<typename InputIterator>
    iterator insert( const_iterator position, InputIterator first, InputIterator last );

    iterator insert( const_iterator position, std::initializer_list<Data> list )
    {
      return insert( position, list.begin(), list.end() );
    }

    iterator erase( const_iterator position );

    iterator erase( const_iterator first, const_iterator last );

    void pop_front();

    void pop_back();

    void remove( const Data& value )
    {
      auto predicate = [&value] ( const Data& item ) { return value == item; };
      remove_if( predicate );
    }

    template <typename Predicate>
    void remove_if( Predicate predicate );

    void clear();

    template <typename Comparator = std::less_equal<iterator_value_type<BaseIterator<Data>>>>
    void sort( Comparator comparator = Comparator() )
    {
      if ( count < 2 ) return;
      sort( head, comparator );
    }

    void reverse() noexcept;

    iterator begin() noexcept { return iterator{ head.get() }; }
    const_iterator cbegin() const noexcept { return const_iterator{ head.get() }; }

    iterator end() noexcept { return iterator{ nullptr }; }
    const_iterator cend() const noexcept { return const_iterator{ nullptr }; }

    reverse_iterator rbegin() noexcept
    {
      sentinel->previous = tail;
      return std::make_reverse_iterator( iterator{ sentinel.get() } );
    }

    const_reverse_iterator crbegin() const noexcept
    {
      sentinel->previous = tail;
      return std::make_reverse_iterator( const_iterator{ sentinel.get() } );
    }

    reverse_iterator rend() noexcept { return std::make_reverse_iterator( begin() ); }
    const_reverse_iterator crend() const noexcept { return std::make_reverse_iterator( cbegin() ); }

    std::size_t size() noexcept { return count; }
    std::size_t size() const noexcept { return count; }

    bool empty() noexcept { return !head; }
    bool empty() const noexcept { return !head; }

    void swap( DoublyLinkedList& rhs ) noexcept;

  private:
    static Node* getPrevious( Node* node ) noexcept
    {
      return ( node ) ? node->previous : nullptr;
    }

    void addChild( Node* parent, Data&& data ) noexcept
    {
      parent->next = std::make_unique<Node>( std::move( data ),
        std::move( parent->next ), parent );
      if ( parent->next->next )
      {
        parent->next->next->previous = parent->next.get();
      }
    }

    void removeChild( Node* parent ) noexcept
    {
      parent->next = std::move( parent->next->next );
      if ( parent->next ) parent->next->previous = parent;
    }

    using Pair = std::tuple<typename Node::Ptr, typename Node::Ptr>;
    Pair split( typename Node::Ptr& source );

    template <typename Comparator = std::less_equal<iterator_value_type<BaseIterator<Data>>>>
    void sort( typename Node::Ptr& node, Comparator& comparator );

    template <typename Comparator = std::less_equal<iterator_value_type<BaseIterator<Data>>>>
    void merge( typename Node::Ptr& left,
      typename Node::Ptr& right, Comparator& comparator );

    struct Node
    {
      using Ptr = std::unique_ptr<Node>;

      Node( Data&& data, Ptr&& next, Node* previous ) :
        data{ std::move( data ) }, next{ std::move( next ) },
        previous{ previous }
      {}

      Node() = default;
      Node( const Node& ) = delete;
      Node& operator=( const Node& ) = delete;

      Data data;
      Ptr next;
      Node* previous = nullptr;
    };

    typename Node::Ptr head = nullptr;
    mutable typename Node::Ptr sentinel = std::make_unique<Node>( Data{}, nullptr, nullptr );
    Node* tail = nullptr;
    std::size_t count = 0;
  };

  template <typename Data>
  bool operator==( const DoublyLinkedList<Data>& lhs,
    const DoublyLinkedList<Data>& rhs );

  template <typename Data>
  bool operator!=( const DoublyLinkedList<Data>& lhs,
    const DoublyLinkedList<Data>& rhs )
  {
    return !( lhs == rhs );
  }

#include "private/DoubleListImpl.h"
}

DLLIterator.h

The custom iterator used with the DoublyLinkedList implementation. This is a bi-directional iterator.

template <typename T>
struct BaseIterator : std::iterator<std::bidirectional_iterator_tag, T>
{
  BaseIterator() = delete;
  BaseIterator( const BaseIterator& ) = default;

  BaseIterator& operator++()
  {
    node = node->next.get();
    return *this;
  }

  BaseIterator operator++( int )
  {
    BaseIterator temp{ node };
    operator++();
    return temp;
  }

  BaseIterator& operator--()
  {
    if ( node ) node = node->previous;
    return *this;
  }

  BaseIterator operator--( int )
  {
    BaseIterator temp{ node };
    operator--();
    return temp;
  }

  bool operator==( const BaseIterator& rhs ) { return node == rhs.node; }
  bool operator!=( const BaseIterator& rhs ) { return !operator==( rhs ); }

  T& operator*() { return node->data; }
  T* operator->() { return &( node->data ); }

private:
  friend class DoublyLinkedList<Data>;
  explicit BaseIterator( Node* node ) : node{ node } {}
  Node* node;
};

DoubleListImpl.h

Implementation of the more complex linked list member functions.

template <typename Data>
DoublyLinkedList<Data>& DoublyLinkedList<Data>::operator=( const std::initializer_list<Data>& list )
{
  DoublyLinkedList tmp( list );
  tmp.swap( *this );
  return *this;
}

template <typename Data>
template<typename InputIterator>
void DoublyLinkedList<Data>::assign( InputIterator first, InputIterator last )
{
  clear();

  auto data = Data{ *first };
  auto ptr1 = std::make_unique<Node>( std::move( data ), nullptr, nullptr );
  head = std::move( ptr1 );
  tail = head.get();
  ++first;
  ++count;

  for ( ; first != last; ++first )
  {
    data = Data{ *first };
    addChild( tail, std::move( data ) );
    tail = tail->next.get();
    ++count;
  }
}

template <typename Data>
template <typename... Args>
void DoublyLinkedList<Data>::emplace_front( Args&&... args )
{
  Data data{ std::forward<Args>( args )... };
  head = std::make_unique<Node>( std::move( data ), std::move( head ), nullptr );

  if ( head->next ) head->next->previous = head.get();
  else tail = head.get();

  ++count;
}

template <typename Data>
template <typename... Args>
void DoublyLinkedList<Data>::emplace_back( Args&&... args )
{
  Data data{ std::forward<Args>( args )... };
  auto ptr = std::make_unique<Node>( std::move( data ), nullptr, tail );

  if ( tail )
  {
    tail->next = std::move( ptr );
    tail = tail->next.get();
  }
  else
  {
    head = std::move( ptr );
    tail = head.get();
  }

  ++count;
}

template <typename Data>
template <typename... Args>
typename DoublyLinkedList<Data>::iterator DoublyLinkedList<Data>::emplace(
  const_iterator position, Args&&... args )
{
  if ( cbegin() == position )
  {
    emplace_front( std::forward<Args>( args )... );
    return begin();
  }
  else if ( cend() == position )
  {
    iterator iter{ tail };
    emplace_back( std::forward<Args>( args )... );
    if ( !iter.node ) iter.node = tail;
    return iter;
  }

  Node* previous = getPrevious( position.node );

  if ( previous && previous->next )
  {
    auto data{ std::forward<Args>( args )... };
    addChild( previous, std::move( data ) );
    ++count;
    return iterator( previous->next.get() );
  }

  throw std::out_of_range( "Invalid input iterator!" );
}

template <typename Data>
typename DoublyLinkedList<Data>::iterator DoublyLinkedList<Data>::insert(
  const_iterator position, std::size_t number, const Data& value )
{
  Node* previous = getPrevious( position.node );
  iterator iter{ previous };

  for ( std::size_t i = 0; i < number; ++i )
  {
    if ( !previous )
    {
      head = std::make_unique<Node>( Data{ value }, std::move( head ), nullptr );

      if ( head->next ) head->next->previous = head.get();
      else tail = head.get();

      previous = head.get();
      iter.node = head.get();
      ++count;
      continue;
    }

    addChild( previous, Data{ value } );
    if ( i == 0 ) iter.node = previous->next.get();
    previous = previous->next.get();
    ++count;
  }

  return iter;
}

template <typename Data>
template <typename InputIterator>
typename DoublyLinkedList<Data>::iterator DoublyLinkedList<Data>::insert(
  const_iterator position, InputIterator first, InputIterator last )
{
  Node* previous = getPrevious( position.node );
  iterator iter{ previous };
  InputIterator start = first;
  auto updateTail = empty();

  for ( ; first != last; ++first )
  {
    if ( !previous )
    {
      head = std::make_unique<Node>( Data{ *first }, std::move( head ), nullptr );

      if ( head->next ) head->next->previous = head.get();
      else tail = head.get();

      previous = head.get();
      iter.node = head.get();
      ++count;
      continue;
    }

    addChild( previous, Data{ *first } );
    if ( start == first ) iter.node = previous->next.get();
    previous = previous->next.get();
    if ( updateTail ) tail = previous;
    ++count;
  }

  return iter;
}

template <typename Data>
typename DoublyLinkedList<Data>::iterator DoublyLinkedList<Data>::erase(
  const_iterator position )
{
  if ( !head ) throw std::out_of_range( "Empty list!" );
  if ( !position.node ) throw std::out_of_range( "Invalid position!" );

  if ( position.node == head.get() )
  {
    pop_front();
    return begin();
  }

  if ( position.node == tail )
  {
    pop_back();
    return iterator{ tail };
  }

  Node* previous = position.node->previous;
  if ( !previous ) throw std::out_of_range( "No such element!" );

  removeChild( previous );
  if ( tail == position.node ) tail = previous->next.get();
  --count;
  return iterator{ previous->next.get() };
}

template <typename Data>
typename DoublyLinkedList<Data>::iterator DoublyLinkedList<Data>::erase(
  const_iterator first, const_iterator last )
{
  if ( !head ) throw std::out_of_range( "Empty list!" );

  Node* previous = getPrevious( first.node );
  if ( !previous && !( first.node == head.get() ) )
  {
    throw std::out_of_range( "Invalid iterator range" );
  }

  Node* current = first.node;

  while ( current != last.node )
  {
    if ( tail == current ) tail = current->previous;

    if ( head.get() == current )
    {
      head = std::move( head->next );
      if ( head && head->next ) head->next->previous = nullptr;
      previous = current = head.get();
    }
    else
    {
      removeChild( previous );
      current = previous->next.get();
    }

    --count;
  }

  if ( count == 0 ) tail = nullptr;

  return iterator{ last.node };
}

template <typename Data>
void DoublyLinkedList<Data>::pop_front()
{
  if ( !head ) throw std::out_of_range( "Empty list!" );

  head = std::move( head->next );
  if ( head && head->next ) head->next->previous = nullptr;
  if ( count == 1 ) tail = nullptr;

  --count;
}

template <typename Data>
void DoublyLinkedList<Data>::pop_back()
{
  if ( !head ) throw std::out_of_range( "Empty list!" );

  if ( count == 1 )
  {
    head = nullptr;
    tail = nullptr;
  }
  else
  {
    auto previous = tail->previous;
    previous->next = nullptr;
    tail = previous;
  }

  --count;
}

template <typename Data>
template <typename Predicate>
void DoublyLinkedList<Data>::remove_if( Predicate predicate )
{
  if ( !head ) return;

  Node* current = head.get();
  Node *previous = current;

  while ( current )
  {
    if ( !predicate( current->data ) )
    {
      previous = current;
      current = current->next.get();
      continue;
    }

    if ( tail == current ) tail = previous;

    if ( current == head.get() )
    {
      head = std::move( head->next );
      if ( head->next ) head->next->previous = nullptr;
      previous = head.get();
      --count;
      if ( count == 1 ) tail = head.get();
    }
    else
    {
      removeChild( previous );
      --count;
    }

    current = previous->next.get();
  }
}

template <typename Data>
void DoublyLinkedList<Data>::clear()
{
  head.reset();
  tail = nullptr;
  count = 0;
}

template <typename Data>
void DoublyLinkedList<Data>::swap( DoublyLinkedList<Data>& rhs ) noexcept
{
  using std::swap;

  swap( head, rhs.head );
  swap( tail, rhs.tail );
  swap( count, rhs.count );
}

template <typename Data>
void swap( DoublyLinkedList<Data>& lhs, DoublyLinkedList<Data>& rhs ) noexcept
{
  lhs.swap( rhs );
}

template <typename Data>
auto DoublyLinkedList<Data>::split( typename Node::Ptr& source ) -> Pair
{
  if ( !source || !source->next )
  {
    return std::make_tuple( std::move( source ), std::make_unique<Node>() );
  }

  Node* slow = source.get();
  Node* fast = slow->next.get();

  while ( fast )
  {
    fast = fast->next.get();
    if ( fast )
    {
      slow = slow->next.get();
      fast = fast->next.get();
    }
  }

  source->previous = nullptr;
  slow->next->previous = nullptr;

  return std::make_tuple( std::move( source ), std::move( slow->next ) );
}


template <typename Data>
template <typename Comparator>
void DoublyLinkedList<Data>::sort( typename Node::Ptr& node, Comparator& comparator )
{
  if ( !node || !node->next ) return;

  Pair p = split( node );

  sort( std::get<0>( p ), comparator );
  sort( std::get<1>( p ), comparator );

  merge( std::get<0>( p ), std::get<1>( p ), comparator );
}

template<typename Data>
template <typename Comparator>
void DoublyLinkedList<Data>::merge(
  typename Node::Ptr& left, typename Node::Ptr& right, Comparator& comparator )
{
  Node leftHead;
  leftHead.next = std::move( left );

  Node rightHead;
  rightHead.next = std::move( right );

  Node n;
  Node* node = &n;

  while ( leftHead.next && rightHead.next )
  {
    if ( comparator( tail->data, leftHead.next->data ) ) tail = leftHead.next.get();
    if ( comparator( tail->data, rightHead.next->data ) ) tail = rightHead.next.get();

    if ( comparator( leftHead.next->data, rightHead.next->data ) )
    {
      node->next = std::move( leftHead.next );
      leftHead.next = std::move( node->next->next );
    }
    else
    {
      node->next = std::move( rightHead.next );
      rightHead.next = std::move( node->next->next );
    }

    if ( node != &n ) node->next->previous = node;
    node = node->next.get();
  }

  node->next = ( leftHead.next ) ?
    std::move( leftHead.next ) : std::move( rightHead.next );

  if ( head ) merge( head, n.next, comparator );
  else head = std::move( n.next );
}

template<typename Data>
void csc240::DoublyLinkedList<Data>::reverse() noexcept
{
  if ( count < 2 ) return;

  tail = head.get();

  Node node;
  node.next = std::move( head );

  Node target;
  while ( node.next )
  {
    auto temp = std::move( node.next );
    node.next = std::move( temp->next );
    if ( node.next && node.next->next ) node.next->next->previous = node.next.get();

    if ( target.next )
    {
      auto t = std::move( target.next );
      target.next = std::move( temp );
      target.next->next = std::move( t );
      if ( target.next->next ) target.next->next->previous = target.next.get();
    }
    else
    {
      target.next = std::move( temp );
      target.next->previous = nullptr;
    }
  }

  head = std::move( target.next );
}

template<typename Data>
bool operator==( const DoublyLinkedList<Data>& lhs, const DoublyLinkedList<Data>& rhs )
{
  return ( lhs.size() == rhs.size() ) &&
    std::equal( lhs.cbegin(), lhs.cend(), rhs.cbegin() );
}

Person.h

A simple class used to test the linked list implementation with custom objects.

#pragma once
#include <cstdint>
#include <iostream>

namespace csc240
{
  class Person
  {
  public:
    Person( uint32_t id, std::string&& name, std::string&& dateOfBirth,
      bool active = true ) : id{ id }, name{ std::move( name ) },
      dateOfBirth{ std::move( dateOfBirth ) }, active{ active } {}

    uint32_t getId() noexcept { return id; }
    uint32_t getId() const noexcept { return id; }

    const std::string& getName() noexcept { return name; }
    const std::string& getName() const noexcept { return name; }

    const std::string& getDateOfBirth() noexcept { return dateOfBirth; }
    const std::string& getDateOfBirth() const noexcept { return dateOfBirth; }

    bool isActive() noexcept { return active; }
    bool isActive() const noexcept { return active; }

  private:
    uint32_t id;
    std::string name;
    std::string dateOfBirth;
    bool active = true;
  };

  inline bool operator==( const Person& lhs, const Person& rhs )
  {
    return ( lhs.getId() == rhs.getId() ) &&
      ( lhs.getName() == rhs.getName() ) &&
      ( lhs.getDateOfBirth() == rhs.getDateOfBirth() ) &&
      ( lhs.isActive() == rhs.isActive() );
  }

  inline bool operator!=( const Person& lhs, const Person& rhs )
  {
    return !( lhs == rhs );
  }

  inline std::ostream& operator<<( std::ostream& os, const Person& person )
  {
    os << "csc240::Person - id: " << person.getId() <<
      ", name: " << person.getName() <<
      ", dateOfBirth: " << person.getDateOfBirth() <<
      ", active: " << person.isActive() << std::endl;
    return os;
  }
}

DoublyLinkedList.cpp

Unit test suite for the linked list implementation.

#include "catch.hpp"
#include "DoublyLinkedList.h"
#include "Person.h"

#include <vector>

SCENARIO( "DoublyLinkedList can work with integer data" )
{
  csc240::DoublyLinkedList<uint32_t> list;

  WHEN( "Adding items at the back" )
  {
    THEN( "Operations at back of list works" )
    {
      const uint32_t value = 1;
      REQUIRE( list.empty() );
      list.emplace_back( value );
      REQUIRE( value == *list.cbegin() );
      REQUIRE( ++( list.cbegin() ) == list.cend() );
      REQUIRE( ++( list.begin() ) == list.end() );
      REQUIRE( value == list.front() );
      REQUIRE( value == list.back() );
      REQUIRE( 1 == list.size() );

      list.emplace_back( value );
      REQUIRE( value == list.front() );
      REQUIRE( value == list.back() );
      REQUIRE( value == *( ++( list.cbegin() ) ) );
      REQUIRE( 2 == list.size() );

      list.pop_back();
      REQUIRE( 1 == list.size() );
      REQUIRE( value == *list.cbegin() );

      list.pop_back();
      REQUIRE( 0 == list.size() );
      REQUIRE_THROWS( list.pop_back() );

      list.push_back( value );
      REQUIRE( 1 == list.size() );
      REQUIRE( value == *list.cbegin() );

      list.clear();
      list.clear();
      REQUIRE( list.empty() );
      REQUIRE( 0 == list.size() );
    }

    AND_THEN( "Operations at front of list works" )
    {
      const uint32_t value = 10;
      list.emplace_front( value );
      REQUIRE( value == *list.cbegin() );
      REQUIRE( value == list.front() );
      REQUIRE( value == list.back() );
      REQUIRE( 1 == list.size() );

      list.emplace_front( value );
      REQUIRE( value == *( ++( list.cbegin() ) ) );
      REQUIRE( value == list.front() );
      REQUIRE( value == list.back() );
      REQUIRE( 2 == list.size() );

      list.pop_front();
      REQUIRE( 1 == list.size() );
      REQUIRE( value == *list.cbegin() );

      list.pop_front();
      REQUIRE( 0 == list.size() );
      REQUIRE_THROWS( list.pop_front() );

      list.push_front( value );
      REQUIRE( 1 == list.size() );
      REQUIRE( value == *list.cbegin() );

      list.clear();
      list.clear();
      REQUIRE( list.empty() );
      REQUIRE( 0 == list.size() );
      REQUIRE_THROWS( list.pop_front() );
      REQUIRE_THROWS( list.pop_back() );
    }
  }
}

SCENARIO( "DoublyLinked list can be used with strings" )
{
  using List = csc240::DoublyLinkedList<std::string>;
  List list;
#define STRING_VALUES { "Some", "random", "text", "values" }

  WHEN( "Using initialiser lists" )
  {
    list.assign( STRING_VALUES );
    REQUIRE( 4 == list.size() );
    REQUIRE( "Some" == *( list.cbegin() ) );

    THEN( "Iterator is compatible with std::advance" )
    {
      auto first = list.cbegin();
      std::advance( first, 1 );
      REQUIRE( "random" == *first );
      
      auto second = list.cbegin();
      std::advance( second, 2 );
      REQUIRE( "text" == *second );
      
      auto third = list.cbegin();
      std::advance( third, 3 );
      REQUIRE( "values" == *third );
    }
  }

  AND_WHEN( "Using a container of strings" )
  {
    const std::vector<std::string> vector STRING_VALUES;
    list.assign( vector.cbegin(), vector.cend() );
    REQUIRE( 4 == list.size() );

    THEN( "Iterator is accessible through std::begin" )
    {
      REQUIRE( "Some" == *( std::begin( list ) ) );
    }

    REQUIRE( "random" == *( ++( list.cbegin() ) ) );
    REQUIRE( "text" == *( ++( ++( list.cbegin() ) ) ) );
    REQUIRE( "values" == *( ++( ++( ++( list.cbegin() ) ) ) ) );
  }

  AND_WHEN( "emplacing data into list" )
  {
    THEN( "emplacing with valid iterator" )
    {
      list.emplace( list.cbegin(), "values" );
      list.emplace( list.cbegin(), "Some" );
      auto citer = ++( list.cbegin() );
      list.emplace( citer, "text" );
      citer = ++( list.cbegin() );
      list.emplace( citer, "random" );

      REQUIRE( 4 == list.size() );
      REQUIRE( "Some" == *( list.cbegin() ) );
      REQUIRE( "Some" == list.front() );
      REQUIRE( "random" == *( ++( list.cbegin() ) ) );
      REQUIRE( "text" == *( ++( ++( list.cbegin() ) ) ) );
      REQUIRE( "values" == *( ++( ++( ++( list.cbegin() ) ) ) ) );
      REQUIRE( "values" == list.back() );
    }

    AND_THEN( "Using bi-directional iterator" )
    {
      list.emplace( list.cbegin(), "values" );
      list.emplace( list.cbegin(), "Some" );
      auto citer = list.cbegin();
      std::advance( citer, 1 );
      REQUIRE( "values" == *citer );
      std::advance( citer, -1 );
      REQUIRE( "Some" == *citer );
    }
  }

  AND_WHEN( "inserting data into list" )
  {
    THEN( "inserting at start of list" )
    {
      list.insert( list.cbegin(), 4, "value" );
      REQUIRE( 4 == list.size() );
    }

    AND_THEN( "inserting at end of list" )
    {
      list.insert( list.cend(), 4, "value" );
      REQUIRE( 4 == list.size() );
    }

    AND_THEN( "inserting at middle of list" )
    {
      list.emplace_front( "two" );
      list.emplace_front( "one" );
      list.insert( ++( list.cbegin() ), 4, "other" );
      REQUIRE( 6 == list.size() );
      REQUIRE( "one" == *list.cbegin() );
      REQUIRE( "one" == list.front() );
      REQUIRE( "other" == *( ++( list.cbegin() ) ) );
      REQUIRE( "two" == list.back() );
    }
  }

  AND_WHEN( "inserting using input iterators" )
  {
    const std::vector<std::string> vector STRING_VALUES;

    THEN( "inserting at start of list" )
    {
      list.insert( list.cbegin(), vector.cbegin(), vector.cend() );
      REQUIRE( 4 == list.size() );
      REQUIRE( "Some" == *( list.cbegin() ) );
      REQUIRE( "random" == *( ++( list.cbegin() ) ) );
      REQUIRE( "text" == *( ++( ++( list.cbegin() ) ) ) );
      REQUIRE( "values" == *( ++( ++( ++( list.cbegin() ) ) ) ) );
    }

    AND_THEN( "inserting at end of list" )
    {
      list.insert( list.cend(), vector.cbegin(), vector.cend() );
      REQUIRE( 4 == list.size() );
      REQUIRE( "Some" == *( list.cbegin() ) );
      REQUIRE( "random" == *( ++( list.cbegin() ) ) );
      REQUIRE( "text" == *( ++( ++( list.cbegin() ) ) ) );
      REQUIRE( "values" == *( ++( ++( ++( list.cbegin() ) ) ) ) );
    }

    AND_THEN( "inserting into list" )
    {
      list.emplace_front( "end" );
      list.emplace_front( "start" );
      list.insert( ++( list.cbegin() ), vector.cbegin(), vector.cend() );
      REQUIRE( 6 == list.size() );
      REQUIRE( "start" == list.front() );
      REQUIRE( "Some" == *( ++( list.cbegin() ) ) );
      REQUIRE( "random" == *( ++( ++( list.cbegin() ) ) ) );
      REQUIRE( "text" == *( ++( ++( ++( list.cbegin() ) ) ) ) );
      REQUIRE( "values" == *( ++( ++( ++( ++( list.cbegin() ) ) ) ) ) );
      REQUIRE( "end" == list.back() );
    }

    AND_THEN( "inserting as initialiser list" )
    {
      list.insert( list.cbegin(), STRING_VALUES );
      REQUIRE( 4 == list.size() );
      REQUIRE( "Some" == *( list.cbegin() ) );
      REQUIRE( "random" == *( ++( list.cbegin() ) ) );
      REQUIRE( "text" == *( ++( ++( list.cbegin() ) ) ) );
      REQUIRE( "values" == *( ++( ++( ++( list.cbegin() ) ) ) ) );
    }
  }

  AND_WHEN( "erasing item from list" )
  {
    THEN( "erasing from front of list" )
    {
      list.insert( list.cbegin(), STRING_VALUES );
      auto iter = list.erase( list.cbegin() );
      REQUIRE( 3 == list.size() );
      REQUIRE( "random" == *( list.cbegin() ) );
      REQUIRE( "random" == *iter );
      REQUIRE( "text" == *( ++( list.cbegin() ) ) );
      REQUIRE( "values" == *( ++( ++( list.cbegin() ) ) ) );
    }

    AND_THEN( "erasing from back of list" )
    {
      list.insert( list.cbegin(), STRING_VALUES );
      auto iter = list.erase( ++( ++( ++( list.cbegin() ) ) ) );
      REQUIRE( 3 == list.size() );
      REQUIRE( "Some" == *( list.cbegin() ) );
      REQUIRE( "random" == *( ++( list.cbegin() ) ) );
      REQUIRE( "text" == *( ++( ++( list.cbegin() ) ) ) );
      REQUIRE( "text" == *iter );
    }

    AND_THEN( "erasing from list" )
    {
      list.assign( STRING_VALUES );
      auto iter = list.erase( ++( list.cbegin() ) );
      REQUIRE( 3 == list.size() );
      REQUIRE( "Some" == *( list.cbegin() ) );
      REQUIRE( "text" == *( ++( list.cbegin() ) ) );
      REQUIRE( "text" == *iter );
      REQUIRE( "values" == *( ++( ++( list.cbegin() ) ) ) );
    }
  }

  AND_WHEN( "erasing range of items from list" )
  {
    THEN( "erasing from front of list" )
    {
      list.assign( STRING_VALUES );
      auto iter = list.erase( list.cbegin(), ++( ++( list.cbegin() ) ) );
      REQUIRE( 2 == list.size() );
      REQUIRE( "text" == *( list.cbegin() ) );
      REQUIRE( "values" == *( ++( list.cbegin() ) ) );
      REQUIRE( "text" == list.front() );
      REQUIRE( "text" == *iter );
      REQUIRE( "values" == list.back() );
    }

    AND_THEN( "erasing from back of list" )
    {
      list.assign( STRING_VALUES );
      auto iter = list.erase( ++( ++( list.cbegin() ) ), list.cend() );
      REQUIRE( 2 == list.size() );
      REQUIRE( "Some" == *( list.cbegin() ) );
      REQUIRE( "random" == *( ++( list.cbegin() ) ) );
      REQUIRE( "Some" == list.front() );
      REQUIRE( "random" == list.back() );
    }

    AND_THEN( "erasing from list" )
    {
      list.assign( STRING_VALUES );
      auto iter = list.erase( ++( list.cbegin() ), ++( ++( ++( list.cbegin() ) ) ) );
      REQUIRE( 2 == list.size() );
      REQUIRE( "Some" == *( list.cbegin() ) );
      REQUIRE( "values" == *( ++( list.cbegin() ) ) );
      REQUIRE( "Some" == list.front() );
      REQUIRE( "values" == list.back() );
      REQUIRE( "values" == *iter );
    }

    AND_THEN( "erasing entire list" )
    {
      list.assign( STRING_VALUES );
      list.erase( list.cbegin(), list.cend() );
      REQUIRE( list.empty() );
    }
  }
}

SCENARIO( "DoublyLinked list can be used with custom objects" )
{
  GIVEN( "A custom class with arbitrarily complex constructor" )
  {
    using csc240::Person;
    using Persons = csc240::DoublyLinkedList<Person>;
    Persons persons;
    persons.emplace_back( 2u, "Person Two", "1970/01/01" );
    persons.emplace_front( 1u, "Person One", "1970/01/01" );

    THEN( "Removing instances within a list" )
    {
      const Person p{ 2u, "Person Two", "1970/01/01" };
      auto front{ persons.front() };

      persons.remove( p );
      REQUIRE( 1 == persons.size() );
      REQUIRE( front == persons.front() );
      REQUIRE( front == persons.back() );
    }

    AND_THEN( "Removing instances using a predicate" )
    {
      persons.emplace_back( 3u, "Person Two", "1970/01/01" );
      REQUIRE( 3 == persons.size() );

      const std::string name{ "Person Two" };
      auto predicate = [&name] ( const Person& person ) { return name == person.getName(); };
      auto front{ persons.front() };

      persons.remove_if( predicate );
      REQUIRE( 1 == persons.size() );
      REQUIRE( front == persons.front() );
      REQUIRE( front == persons.back() );
    }
  }
}

SCENARIO( "DoublyLinked list can be sorted" )
{
  GIVEN( "An unsorted list of integers" )
  {
    auto list = csc240::DoublyLinkedList<uint8_t>{ 3, 9, 5, 2, 1, 4, 6, 8, 7, 0 };

    THEN( "Sorting using default comparator" )
    {
      list.sort();
      REQUIRE( 0 == list.front() );
      REQUIRE( 9 == list.back() );

      uint8_t i = 0;
      for ( auto value : list )
      {
        REQUIRE( value == i++ );
      }
    }

    AND_THEN( "Sorting using custom comparator" )
    {
      list.sort( std::greater_equal<uint8_t>() );
      REQUIRE( 9 == list.front() );
      REQUIRE( 0 == list.back() );

      uint8_t i = 9;
      for ( auto value : list )
      {
        REQUIRE( value == i-- );
      }
    }
  }
}

SCENARIO( "DoublyLinkedList works with standard algorithms" )
{
  GIVEN( "A list of integers" )
  {
    auto list = csc240::DoublyLinkedList<uint8_t>{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    THEN( "find_if can find valid entries" )
    {
      uint8_t match = 3;
      auto it = std::find_if( list.cbegin(), list.cend(),
        [match] ( uint8_t value ) { return value == match; } );
      REQUIRE( *it == match );
    }

    AND_THEN( "for_each can apply specified function" )
    {
      std::vector<uint8_t> vector{};
      vector.reserve( list.size() );
      std::for_each( list.cbegin(), list.cend(),
        [&vector] ( uint8_t value ) { vector.push_back( 2 * value ); } );

      uint8_t i = 0;
      std::for_each( list.cbegin(), list.cend(),
        [&i, &vector] ( uint8_t value ) { REQUIRE( 2 * value == vector[i++] ); } );
    }
  }
}

SCENARIO( "DoublyLinked list can be reversed" )
{
  GIVEN( "A list of integers" )
  {
    auto list = csc240::DoublyLinkedList<uint8_t>{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    WHEN( "Reversed" )
    {
      list.reverse();
      auto result = csc240::DoublyLinkedList<uint8_t>{ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
      REQUIRE( list == result );
    }
  }
}

SCENARIO( "DoublyLinked list can be iterated in reverse" )
{
  GIVEN( "A list of integers" )
  {
    auto list = csc240::DoublyLinkedList<uint8_t>{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    WHEN( "Iterated in reverse" )
    {
      uint8_t i = 9;
      std::for_each( list.crbegin(), list.crend(),
        [&i] ( uint8_t value ) { REQUIRE( value == i-- ); } );
    }
  }
}