Program Listing for File CursorBinaryTree.h

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

/*--------------------------------------------------------------------------*/
/*------------------------ File CursorBinaryTree.h -------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_CursorBinaryTree
 #define __ADS_CursorBinaryTree
                      /* 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 CursorBinaryTree -------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class CursorBinaryTree {

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

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

 CursorBinaryTree( void ) = default;

 explicit CursorBinaryTree( const T & v );

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

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

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

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

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

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

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

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

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

 int setRoot( const T & v );

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

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

 int insertLeft( int n , const CursorBinaryTree & t , int s );

 int insertRight( int n , const CursorBinaryTree & t , int s );

 void remove( int n );

 [[nodiscard]] std::vector< int > preorder( void ) 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< CursorBinaryTree , Used >;
  return( std::ranges::subrange( It( this , 0 ) ,
                                 It( this , f_N.size() ) ) );
  }

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

 struct Node {
  T value;
  int parent , left , right;
  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 release( int n );

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

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

 };  // end( class CursorBinaryTree )

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

}  // end( namespace ADS )

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

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

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

#endif  /* CursorBinaryTree.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File CursorBinaryTree.h -----------------------*/
/*--------------------------------------------------------------------------*/