Program Listing for File SinglyList.h

↰ Return to documentation for file (ADS/sequence/SinglyList.h)

/*--------------------------------------------------------------------------*/
/*--------------------------- File SinglyList.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_SinglyList
 #define __ADS_SinglyList
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/memory/ObjectPool.h"

#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <type_traits>
#include <utility>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS SinglyList ------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class SinglyList {

/*--------------------------------------------------------------------------*/
 public:

 struct Cell {
  T value;
  Cell * next;
  };

 using Item = T;
 using Pos = Cell *;

 SinglyList( void ) = default;

 SinglyList( std::initializer_list< T > items );

 SinglyList( const SinglyList & other );

 SinglyList( SinglyList && other ) noexcept;

 SinglyList & operator=( SinglyList other ) noexcept;

 ~SinglyList();

 void swap( SinglyList & other ) noexcept;

/*--------------------------------------------------------------------------*/
/*-------------------------- THE SEQUENCE ----------------------------------*/
/*--------------------------------------------------------------------------*/

 [[nodiscard]] bool empty( void ) const;

 [[nodiscard]] bool finished( Pos p ) const;

 [[nodiscard]] Pos head( void ) const;

 [[nodiscard]] Pos tail( void ) const;

 [[nodiscard]] Pos next( Pos p ) const;

 [[nodiscard]] Pos prev( Pos p ) const;

 Pos insert( Pos p , const T & v );

 Pos remove( Pos p );

 [[nodiscard]] const T & read( Pos p ) const;

 void write( Pos p , const T & v );

/*--------------------------------------------------------------------------*/
/*---------------------------- BEYOND THE BOOK -----------------------------*/
/*--------------------------------------------------------------------------*/

 [[nodiscard]] bool operator==( const SinglyList & o ) const;

/*------------------------- THE STANDARD INTERFACE -------------------------*/

 // a forward iterator holds the cell of its item, not the cell before it
 // as a position does, so that the end is nil; it stays valid until its
 // cell is removed, and a change made through it bypasses the audits of
 // write()

 template< bool Const >
 class Iterator {
  public:
  using iterator_category = std::forward_iterator_tag;
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using reference = std::conditional_t< Const , const T & , T & >;
  using pointer = std::conditional_t< Const , const T * , T * >;

  Iterator( void ) = default;
  explicit Iterator( Cell * c ) : f_c( c ) {}

  template< bool C > requires ( Const && ! C )
  Iterator( const Iterator< C > & o ) : f_c( o.f_c ) {}

  reference operator*( void ) const { return( f_c->value ); }
  pointer operator->( void ) const { return( &**this ); }
  Iterator & operator++( void ) { f_c = f_c->next; return( *this ); }
  Iterator operator++( int ) { auto t = *this; ++*this; return( t ); }
  bool operator==( const Iterator & o ) const = default;

  private:
  Cell * f_c = nullptr;

  template< bool > friend class Iterator;
  };

 using value_type = T;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = T &;
 using const_reference = const T &;
 using iterator = Iterator< false >;
 using const_iterator = Iterator< true >;

 [[nodiscard]] iterator begin( void ) { return( iterator( f_first ) ); }
 [[nodiscard]] iterator end( void ) { return( iterator() ); }
 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( f_first ) );
  }
 [[nodiscard]] const_iterator end( void ) const { return( const_iterator() ); }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

 template< std::input_iterator I , std::sentinel_for< I > S >
 SinglyList( I first , S last );

 void push_front( const T & v );

/*--------------------------------------------------------------------------*/
 private:

 [[nodiscard]] Cell * cell( Pos p ) const;

 Cell * f_first = nullptr;
 ObjectPool< Cell > f_pool;
 mutable Cell f_before{ T() , nullptr };

 };  // end( class SinglyList )

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/sequence/impl/SinglyList.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* SinglyList.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File SinglyList.h --------------------------*/
/*--------------------------------------------------------------------------*/