Program Listing for File List.h

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

/*--------------------------------------------------------------------------*/
/*------------------------------ File List.h -------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_List
 #define __ADS_List
                      /* 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 List ----------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , bool Pooled = true >
class List {

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

 using Item = T;

 struct Cell {
  Cell * pred;
  Cell * succ;
  T value;
  };

 using Pos = Cell *;

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

 List( void );

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

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

 List( const List & other );

 List( List && other ) noexcept;

 List & operator=( List other ) noexcept;

 ~List();

 void swap( List & 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 List & o ) const;

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

 // a bidirectional iterator walks the cells, the sentinel being the end;
 // 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::bidirectional_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.cell() ) {}

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

  [[nodiscard]] Cell * cell( void ) const { return( f_c ); }

  private:
  Cell * f_c = nullptr;
  };

 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 >;
 using reverse_iterator = std::reverse_iterator< iterator >;
 using const_reverse_iterator = std::reverse_iterator< const_iterator >;

 [[nodiscard]] iterator begin( void ) { return( iterator( head() ) ); }
 [[nodiscard]] iterator end( void ) { return( iterator( sentinel() ) ); }
 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( head() ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( sentinel() ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }
 [[nodiscard]] reverse_iterator rbegin( void ) {
  return( reverse_iterator( end() ) );
  }
 [[nodiscard]] reverse_iterator rend( void ) {
  return( reverse_iterator( begin() ) );
  }
 [[nodiscard]] const_reverse_iterator rbegin( void ) const {
  return( const_reverse_iterator( end() ) );
  }
 [[nodiscard]] const_reverse_iterator rend( void ) const {
  return( const_reverse_iterator( begin() ) );
  }

 void push_back( const T & v );
 void push_front( const T & v );

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

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

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

 [[nodiscard]] Cell * sentinel( void ) const;

 void adopt( List & o ) noexcept;

 struct Plain {
  template< class... Args >
  Cell * make( Args &&... args ) {
   return( new Cell{ std::forward< Args >( args )... } );
   }
  void free( Cell * c ) noexcept { delete c; }
  void swap( Plain & ) noexcept {}
  };

 mutable Cell f_sentinel;
 [[no_unique_address]]
 std::conditional_t< Pooled , ObjectPool< Cell > , Plain > f_pool;

 };  // end( class List )

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

}  // end( namespace ADS )

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

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

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

#endif  /* List.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File List.h -----------------------------*/
/*--------------------------------------------------------------------------*/