Program Listing for File CursorTree.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File CursorTree.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/Iterators.h"

#include <cstddef>
#include <ranges>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS CursorTree ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class CursorTree {

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

 using Item = T;
 static constexpr int NIL = -1;

 CursorTree( void ) = default;

 explicit CursorTree( const T & v );

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

 [[nodiscard]] int root( void ) const;

 [[nodiscard]] int parent( int n ) const;

 [[nodiscard]] int leftmostChild( int n ) const;

 [[nodiscard]] int rightSibling( int n ) const;

 [[nodiscard]] bool isLeaf( int n ) const;

 [[nodiscard]] bool isLastSibling( int n ) const;

 [[nodiscard]] const T & read( int n ) const;

 void write( int n , const T & v );

 [[nodiscard]] int size( void ) const;

 int insertChild( int n , const T & v );

 int insertSibling( int n , const T & v );

 int insertChildTree( int n , const CursorTree & t , int s );

 int insertSiblingTree( int n , const CursorTree & t , int s );

 void remove( int n );

 [[nodiscard]] std::vector< int > previsit( void ) const;

 [[nodiscard]] std::vector< int > postvisit( void ) const;

 [[nodiscard]] std::vector< int > invisit( int i ) const;

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

 struct Used {
  static std::size_t size( const auto & o ) { return( o.f_N.size() ); }
  static bool occupied( const auto & o , std::size_t i ) {
   return( o.f_N[ i ].used );
   }
  static int read( const auto & , std::size_t i ) { return( int( i ) ); }
  };

 [[nodiscard]] auto nodes( void ) const {
  using It = SlotIterator< CursorTree , Used >;
  return( std::ranges::subrange( It( this , 0 ) ,
                                 It( this , f_N.size() ) ) );
  }

 struct Siblings {
  static constexpr int none = NIL;
  static int next( const CursorTree * o , int n , int ) {
   return( o->rightSibling( n ) );
   }
  };

 [[nodiscard]] auto children( int n ) const {
  using It = WalkIterator< CursorTree , int , Siblings >;
  return( std::ranges::subrange( It( this , leftmostChild( n ) , n ) ,
                                 It() ) );
  }

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

 struct Node {
  T value;
  int parent , child , sibling;
  bool used;
  };

 const Node & node( int n ) const;

 Node & node( int n );

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

 int make( const T & v , int p );

 void free_node( int n );

 void release_children( int n );

 int copy( const CursorTree & t , int s , int p );

 void visit( int n , int i , std::vector< int > & P , int kind ) const;

 std::vector< Node > f_N;
 int f_root = NIL;
 int f_free = NIL;
 int f_size = 0;

 };  // end( class CursorTree )

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

}  // end( namespace ADS )

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

#include "ADS/tree/impl/CursorTree.tpp"

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

#endif  /* CursorTree.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File CursorTree.h --------------------------*/
/*--------------------------------------------------------------------------*/