Program Listing for File Iterators.h

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

/*--------------------------------------------------------------------------*/
/*---------------------------- File Iterators.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include <compare>
#include <cstddef>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS LinkedIterator ---------------------------*/
/*--------------------------------------------------------------------------*/

template< class C , class V , C * C::* Next , V C::* Value ,
          bool Const = true >
class LinkedIterator {
 using Cell = std::conditional_t< Const , const C , C >;

 public:
 using iterator_category = std::forward_iterator_tag;
 using value_type = V;
 using difference_type = std::ptrdiff_t;
 using reference = std::conditional_t< Const , const V & , V & >;
 using pointer = std::conditional_t< Const , const V * , V * >;

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

 template< bool K > requires ( Const && ! K )
 LinkedIterator( const LinkedIterator< C , V , Next , Value , K > & o )
  : f_c( o.cell() ) {}

 reference operator*( void ) const { return( f_c->*Value ); }
 pointer operator->( void ) const { return( &( f_c->*Value ) ); }

 LinkedIterator & operator++( void ) {
  f_c = f_c->*Next;
  return( *this );
  }

 LinkedIterator operator++( int ) {
  auto t = *this;
  ++*this;
  return( t );
  }

 bool operator==( const LinkedIterator & o ) const = default;

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

 private:
 Cell * f_c = nullptr;

 };  // end( class LinkedIterator )

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS IndexIterator ---------------------------*/
/*--------------------------------------------------------------------------*/

template< class C , class V , int C::* Next , V C::* Value ,
          bool Const = true >
class IndexIterator {
 using Cells = std::conditional_t< Const , const std::vector< C > ,
                                   std::vector< C > >;

 public:
 using iterator_category = std::forward_iterator_tag;
 using value_type = V;
 using difference_type = std::ptrdiff_t;
 using reference = std::conditional_t< Const , const V & , V & >;
 using pointer = std::conditional_t< Const , const V * , V * >;

 IndexIterator( void ) = default;
 IndexIterator( Cells * A , int c ) : f_A( A ) , f_c( c ) {}

 template< bool K > requires ( Const && ! K )
 IndexIterator( const IndexIterator< C , V , Next , Value , K > & o )
  : f_A( o.cells() ) , f_c( o.index() ) {}

 reference operator*( void ) const { return( ( *f_A )[ f_c ].*Value ); }
 pointer operator->( void ) const { return( &**this ); }

 IndexIterator & operator++( void ) {
  f_c = ( *f_A )[ f_c ].*Next;
  return( *this );
  }

 IndexIterator operator++( int ) {
  auto t = *this;
  ++*this;
  return( t );
  }

 bool operator==( const IndexIterator & o ) const {
  return( ( f_c == o.f_c ) && ( ( f_c < 0 ) || ( f_A == o.f_A ) ) );
  }

 [[nodiscard]] Cells * cells( void ) const { return( f_A ); }
 [[nodiscard]] int index( void ) const { return( f_c ); }

 private:
 Cells * f_A = nullptr;
 int f_c = -1;

 };  // end( class IndexIterator )

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS CircularIterator --------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , bool Const = true >
class CircularIterator {
 using Item = std::conditional_t< Const , const T , T >;

 public:
 using iterator_category = std::random_access_iterator_tag;
 using value_type = T;
 using difference_type = std::ptrdiff_t;
 using reference = Item &;
 using pointer = Item *;

 CircularIterator( void ) = default;
 CircularIterator( Item * A , std::size_t head , std::size_t capacity ,
                   difference_type i )
  : f_A( A ) , f_head( head ) , f_cap( capacity ) , f_i( i ) {}

 template< bool K > requires ( Const && ! K )
 CircularIterator( const CircularIterator< T , K > & o )
  : f_A( o.base() ) , f_head( o.head() ) , f_cap( o.capacity() ) ,
    f_i( o.index() ) {}

 reference operator*( void ) const { return( ( *this )[ 0 ] ); }
 pointer operator->( void ) const { return( &**this ); }

 reference operator[]( difference_type k ) const {
  return( f_A[ ( f_head + std::size_t( f_i + k ) ) % f_cap ] );
  }

 CircularIterator & operator++( void ) { ++f_i; return( *this ); }
 CircularIterator & operator--( void ) { --f_i; return( *this ); }
 CircularIterator operator++( int ) { auto t = *this; ++f_i; return( t ); }
 CircularIterator operator--( int ) { auto t = *this; --f_i; return( t ); }
 CircularIterator & operator+=( difference_type k ) {
  f_i += k;
  return( *this );
  }
 CircularIterator & operator-=( difference_type k ) {
  f_i -= k;
  return( *this );
  }

 friend CircularIterator operator+( CircularIterator a , difference_type k ) {
  return( a += k );
  }
 friend CircularIterator operator+( difference_type k , CircularIterator a ) {
  return( a += k );
  }
 friend CircularIterator operator-( CircularIterator a , difference_type k ) {
  return( a -= k );
  }
 friend difference_type operator-( const CircularIterator & a ,
                                   const CircularIterator & b ) {
  return( a.f_i - b.f_i );
  }

 bool operator==( const CircularIterator & o ) const {
  return( f_i == o.f_i );
  }
 std::strong_ordering operator<=>( const CircularIterator & o ) const {
  return( f_i <=> o.f_i );
  }

 [[nodiscard]] Item * base( void ) const { return( f_A ); }
 [[nodiscard]] std::size_t head( void ) const { return( f_head ); }
 [[nodiscard]] std::size_t capacity( void ) const { return( f_cap ); }
 [[nodiscard]] difference_type index( void ) const { return( f_i ); }

 private:
 Item * f_A = nullptr;
 std::size_t f_head = 0 , f_cap = 1;
 difference_type f_i = 0;

 };  // end( class CircularIterator )

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS IndirectIterator --------------------------*/
/*--------------------------------------------------------------------------*/

template< std::random_access_iterator I >
class IndirectIterator {
 public:
 using iterator_category = std::random_access_iterator_tag;
 using value_type = std::remove_cvref_t< decltype( **std::declval< I >() ) >;
 using difference_type = std::iter_difference_t< I >;
 using reference = const value_type &;
 using pointer = const value_type *;

 IndirectIterator( void ) = default;
 explicit IndirectIterator( I i ) : f_i( i ) {}

 reference operator*( void ) const { return( **f_i ); }
 pointer operator->( void ) const { return( &**f_i ); }
 reference operator[]( difference_type k ) const { return( *f_i[ k ] ); }

 IndirectIterator & operator++( void ) { ++f_i; return( *this ); }
 IndirectIterator & operator--( void ) { --f_i; return( *this ); }
 IndirectIterator operator++( int ) { auto t = *this; ++f_i; return( t ); }
 IndirectIterator operator--( int ) { auto t = *this; --f_i; return( t ); }
 IndirectIterator & operator+=( difference_type k ) {
  f_i += k;
  return( *this );
  }
 IndirectIterator & operator-=( difference_type k ) {
  f_i -= k;
  return( *this );
  }

 friend IndirectIterator operator+( IndirectIterator a , difference_type k ) {
  return( a += k );
  }
 friend IndirectIterator operator+( difference_type k , IndirectIterator a ) {
  return( a += k );
  }
 friend IndirectIterator operator-( IndirectIterator a , difference_type k ) {
  return( a -= k );
  }
 friend difference_type operator-( const IndirectIterator & a ,
                                   const IndirectIterator & b ) {
  return( a.f_i - b.f_i );
  }

 bool operator==( const IndirectIterator & o ) const = default;
 auto operator<=>( const IndirectIterator & o ) const = default;

 [[nodiscard]] I base( void ) const { return( f_i ); }

 private:
 I f_i{};

 };  // end( class IndirectIterator )

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS SlotIterator ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class O , class P >
class SlotIterator {
 public:
 using reference = decltype( P::read( std::declval< const O & >() , 0 ) );
 using value_type = std::remove_cvref_t< reference >;
 using difference_type = std::ptrdiff_t;
 using iterator_concept = std::bidirectional_iterator_tag;
 using iterator_category = std::conditional_t<
  std::is_reference_v< reference > , std::bidirectional_iterator_tag ,
  std::input_iterator_tag >;

 SlotIterator( void ) = default;

 SlotIterator( const O * o , std::size_t i ) : f_o( o ) , f_i( i ) {
  forward();
  }

 reference operator*( void ) const { return( P::read( *f_o , f_i ) ); }

 SlotIterator & operator++( void ) {
  ++f_i;
  forward();
  return( *this );
  }

 SlotIterator & operator--( void ) {
  do --f_i; while( ! P::occupied( *f_o , f_i ) );
  return( *this );
  }

 SlotIterator operator++( int ) { auto t = *this; ++*this; return( t ); }
 SlotIterator operator--( int ) { auto t = *this; --*this; return( t ); }

 bool operator==( const SlotIterator & o ) const { return( f_i == o.f_i ); }

 [[nodiscard]] std::size_t place( void ) const { return( f_i ); }

 private:
 void forward( void ) {
  const std::size_t m = P::size( *f_o );
  while( ( f_i < m ) && ! P::occupied( *f_o , f_i ) ) ++f_i;
  }

 const O * f_o = nullptr;
 std::size_t f_i = 0;

 };  // end( class SlotIterator )

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS KeyIterator ----------------------------*/
/*--------------------------------------------------------------------------*/

template< std::forward_iterator I >
class KeyIterator {
 public:
 using reference = const std::remove_cvref_t<
  decltype( ( *std::declval< I >() ).first ) > &;
 using value_type = std::remove_cvref_t< reference >;
 using difference_type = std::iter_difference_t< I >;
 using iterator_concept = std::conditional_t<
  std::bidirectional_iterator< I > , std::bidirectional_iterator_tag ,
  std::forward_iterator_tag >;
 using iterator_category = iterator_concept;

 KeyIterator( void ) = default;
 explicit KeyIterator( I i ) : f_i( i ) {}

 reference operator*( void ) const { return( ( *f_i ).first ); }
 const value_type * operator->( void ) const { return( &**this ); }

 KeyIterator & operator++( void ) { ++f_i; return( *this ); }
 KeyIterator operator++( int ) { auto t = *this; ++f_i; return( t ); }
 KeyIterator & operator--( void ) requires std::bidirectional_iterator< I > {
  --f_i;
  return( *this );
  }
 KeyIterator operator--( int ) requires std::bidirectional_iterator< I > {
  auto t = *this;
  --f_i;
  return( t );
  }

 bool operator==( const KeyIterator & o ) const = default;

 private:
 I f_i{};

 };  // end( class KeyIterator )

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS PathIterator ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class O , class P >
class PathIterator {
 using N = std::remove_pointer_t<
  decltype( P::root( std::declval< const O & >() ) ) >;

 public:
 using reference = decltype( P::read( std::declval< N * >() ) );
 using value_type = std::remove_cvref_t< reference >;
 using difference_type = std::ptrdiff_t;
 using iterator_concept = std::bidirectional_iterator_tag;
 using iterator_category = std::conditional_t<
  std::is_reference_v< reference > , std::bidirectional_iterator_tag ,
  std::input_iterator_tag >;

 PathIterator( void ) = default;

 PathIterator( const O * o , bool first ) : f_o( o ) {
  if( first ) descend( P::root( *f_o ) , true );
  }

 reference operator*( void ) const { return( P::read( f_path.back() ) ); }

 PathIterator & operator++( void ) {
  step( true );
  return( *this );
  }

 PathIterator & operator--( void ) {
  if( f_path.empty() ) descend( P::root( *f_o ) , false );
  else step( false );
  return( *this );
  }

 PathIterator operator++( int ) { auto t = *this; ++*this; return( t ); }
 PathIterator operator--( int ) { auto t = *this; --*this; return( t ); }

 bool operator==( const PathIterator & o ) const {
  return( f_path.empty() ? o.f_path.empty()
                         : ( ! o.f_path.empty() &&
                             ( f_path.back() == o.f_path.back() ) ) );
  }

 private:
 static N * child( N * n , bool right ) {
  return( right ? P::right( n ) : P::left( n ) );
  }

 void descend( N * n , bool first ) {
  for( ; n ; n = child( n , ! first ) ) f_path.push_back( n );
  }

 void step( bool forward ) {
  if( N * c = child( f_path.back() , forward ) ) {
   descend( c , forward );
   return;
   }
  N * from;                                 // up while coming from the
  do {                                      // side we move toward
   from = f_path.back();
   f_path.pop_back();
   } while( ! f_path.empty() && ( child( f_path.back() , forward ) == from ) );
  }

 const O * f_o = nullptr;
 std::vector< N * > f_path;

 };  // end( class PathIterator )

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS WalkIterator ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class O , class H , class P >
class WalkIterator {
 public:
 using value_type = H;
 using reference = H;
 using difference_type = std::ptrdiff_t;
 using iterator_concept = std::forward_iterator_tag;
 using iterator_category = std::input_iterator_tag;

 WalkIterator( void ) = default;
 WalkIterator( const O * o , H n , H root )
  : f_o( o ) , f_n( n ) , f_root( root ) {}

 reference operator*( void ) const { return( f_n ); }

 WalkIterator & operator++( void ) {
  f_n = P::next( f_o , f_n , f_root );
  return( *this );
  }

 WalkIterator operator++( int ) { auto t = *this; ++*this; return( t ); }

 bool operator==( const WalkIterator & o ) const { return( f_n == o.f_n ); }

 private:
 const O * f_o = nullptr;
 H f_n = P::none;
 H f_root = P::none;

 };  // end( class WalkIterator )

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

}  // end( namespace ADS )

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

#endif  /* Iterators.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File Iterators.h --------------------------*/
/*--------------------------------------------------------------------------*/