Lab 10 - Singly Linked List

In this exercise we will implement a singly linked list using std::unique_ptr to manage dynamically allocated node instances stored in the list.

Node

We will use a Node structure that will store the data for the linked list element, as well as a std::unique_ptr to the next 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.

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.

LinkedList.h

The main header file that defines the singly 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 ListImpl.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 LinkedList
  {
    struct Node;

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

  public:
    template <typename T>
    struct BaseIterator : std::iterator<std::forward_iterator_tag, T>
    {
      BaseIterator() = delete;

      BaseIterator& operator++()
      {
        node = node->next.get();
        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 LinkedList<Data>;
      explicit BaseIterator( Node* node ) : node{ node } {}
      Node* node;
    };

    LinkedList() = default;

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

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

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

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

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

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

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

    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 = {} )
    {
      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 }; }

    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( LinkedList& rhs ) noexcept;

  private:
    Node* getParent( const Node* const node );

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

    template <typename Comparator>
    void sort( typename Node::Ptr& node, Comparator& comparator );

    template <typename Comparator>
    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 ) : data{ std::move( data ) }, next{ std::move( next ) } {}

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

      Data data;
      Ptr next;
    };

    typename Node::Ptr head = nullptr;
    Node* tail = nullptr;
    std::size_t count = 0;
  };

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

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

#include "private/ListImpl.h"
}

ListImpl.h

Implementation of the more complex linked list member functions.

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

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

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

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

template <typename Data>
template <typename... Args>
void LinkedList<Data>::emplace_front( Args&&... args )
{
  Data data{ std::forward<Args>( args )... };
  head = std::make_unique<Node>( std::move( data ), std::move( head ) );
  if ( ! head->next ) tail = head.get();

  ++count;
}

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

  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 LinkedList<Data>::iterator LinkedList<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 = getParent( position.node );

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

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

template <typename Data>
typename LinkedList<Data>::iterator LinkedList<Data>::insert(
  const_iterator position, std::size_t number, const Data& value )
{
  Node* previous = getParent( 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 ) );
      if ( ! head->next ) tail = head.get();
      previous = head.get();
      iter.node = head.get();
      ++count;
      continue;
    }

    previous->next = std::make_unique<Node>(
      Data{ value }, std::move( previous->next ) );
    if ( i == 0 ) iter.node = previous->next.get();
    previous = previous->next.get();
    ++count;
  }

  return iter;
}

template <typename Data>
template <typename InputIterator>
typename LinkedList<Data>::iterator LinkedList<Data>::insert(
  const_iterator position, InputIterator first, InputIterator last )
{
  Node* previous = getParent( 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 ) );
      if ( ! head->next ) tail = head.get();
      previous = head.get();
      iter.node = head.get();
      ++count;
      continue;
    }

    previous->next = std::make_unique<Node>(
      Data{ *first }, std::move( previous->next ) );
    if ( start == first ) iter.node = previous->next.get();
    previous = previous->next.get();
    if ( updateTail ) tail = previous;
    ++count;
  }

  return iter;
}

template <typename Data>
typename LinkedList<Data>::iterator LinkedList<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 = getParent( position.node );
  if ( ! previous ) throw std::out_of_range( "No such element!" );

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

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

  Node* previous = getParent( first.node );
  if ( !previous ) throw std::out_of_range( "Invalid iterator range" );
  Node* current = ( previous == first.node ) ? previous : previous->next.get();

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

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

    --count;
  }

  if ( count == 0 ) tail = nullptr;

  return iterator{ last.node };
}

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

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

  --count;
}

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

  auto previous = getParent( tail );

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

  --count;
}

template <typename Data>
template <typename Predicate>
void LinkedList<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 );
      previous = head.get();
      --count;
      if ( count == 1 ) tail = head.get();
    }
    else
    {
      previous->next = std::move( current->next );
      --count;
    }

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

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

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

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

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

template<typename Data>
typename LinkedList<Data>::Node* LinkedList<Data>::getParent( const Node* const node )
{
  if ( count == 0 ) return nullptr;
  Node* n = head.get();
  if ( n == node ) return n;

  while ( n->next && n->next.get() != node ) n = n->next.get();
  return n;
}

template <typename Data>
typename LinkedList<Data>::Pair LinkedList<Data>::split( typename Node::Ptr& source )
{
  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();
    }
  }

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


template <typename Data>
template <typename Comparator>
void LinkedList<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 LinkedList<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 );
    }

    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::LinkedList<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 ( target.next )
    {
      auto t = std::move( target.next );
      target.next = std::move( temp );
      target.next->next = std::move( t );
    }
    else target.next = std::move( temp );
  }

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

template<typename Data>
bool operator==( const LinkedList<Data>& lhs, const LinkedList<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 } {}

    Person( const Person& ) = default;
    Person( Person&& ) = default;

    Person& operator=( const Person& ) = default;
    Person& operator=( Person&& ) = default;

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

LinkedList.cpp

Unit test suite for the linked list implementation

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

#include <vector>

SCENARIO( "LinkedList can work with integer data" )
{
  csc240::LinkedList<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() );
    }
  }
}

SCENARIO( "Linked list can be used with strings" )
{
  using List = csc240::LinkedList<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" )
  {
    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_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( "Linked list can be used with custom objects" )
{
  GIVEN( "A custom class with arbitrarily complex constructor" )
  {
    using csc240::Person;
    using Persons = csc240::LinkedList<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( "Linked list can be sorted" )
{
  GIVEN( "An unsorted list of integers" )
  {
    auto list = csc240::LinkedList<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( "Linked list can be reversed" )
{
  GIVEN( "A list of integers" )
  {
    auto list = csc240::LinkedList<uint8_t>{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

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

SCENARIO( "LinkedList works with standard algorithms" )
{
  GIVEN( "A list of integers" )
  {
    auto list = csc240::LinkedList<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++] ); } )
    }
  }
}

Sans Pareil Technologies, Inc.

Key To Your Business

Lab 10 - Singly Linked List

Node

Iterators

LinkedList