Program Listing for File CursorList.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File CursorList.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS CursorSpace -----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class CursorSpace {

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

 struct Cell {
  T value;
  long next;
  };

 explicit CursorSpace( long dim = 8 );

 [[nodiscard]] Cell & operator[]( long c );

 [[nodiscard]] const Cell & operator[]( long c ) const;

 long take( void );

 void give( long c );

 [[nodiscard]] long capacity( void ) const;

 [[nodiscard]] long used( void ) const;

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

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

 std::vector< Cell > f_A;
 long f_free;
 long f_used = 0;

 };  // end( class CursorSpace )

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS CursorList ------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class CursorList {

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

 using Item = T;
 using Pos = long;

 CursorList( void );

 explicit CursorList( std::shared_ptr< CursorSpace< T > > S );

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

 CursorList( const CursorList & other );

 CursorList( CursorList && other ) noexcept;

 CursorList & operator=( CursorList other ) noexcept;

 ~CursorList();

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

 [[nodiscard]] const CursorSpace< T > & space( void ) const;

 [[nodiscard]] long first( void ) const;

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

 // a forward iterator holds the space and the index of the cell of its
 // item, never a reference to the cell, since take() in any list of the
 // space may move the cells; the end is the index 0

 template< bool Const >
 class Iterator {
  using Space = std::conditional_t< Const , const CursorSpace< T > ,
                                    CursorSpace< T > >;

  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;
  Iterator( Space * S , long c ) : f_S( S ) , f_c( c ) {}

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

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

  private:
  Space * f_S = nullptr;
  long f_c = 0;

  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_S.get() , f_first ) );
  }
 [[nodiscard]] iterator end( void ) { return( iterator( f_S.get() , 0 ) ); }
 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( f_S.get() , f_first ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( f_S.get() , 0 ) );
  }
 [[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 >
 CursorList( I first , S last );

 void push_front( const T & v );

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

 [[nodiscard]] long & link( Pos p );

 [[nodiscard]] long cell( Pos p ) const;

 std::shared_ptr< CursorSpace< T > > f_S;
 long f_first = 0;

 };  // end( class CursorList )

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

}  // end( namespace ADS )

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

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

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

#endif  /* CursorList.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File CursorList.h --------------------------*/
/*--------------------------------------------------------------------------*/