Program Listing for File BinaryTree.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File BinaryTree.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <cstddef>
#include <limits>
#include <memory>
#include <ranges>
#include <sstream>
#include <stdexcept>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS BinaryTree ------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class BinaryTree {

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

 using Item = T;

 explicit BinaryTree( const T & v );

 BinaryTree( const BinaryTree & ) = delete;
 BinaryTree & operator=( const BinaryTree & ) = delete;

 ~BinaryTree();

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

 [[nodiscard]] const T & read( void ) const;

 void write( const T & v );

 [[nodiscard]] BinaryTree * parent( void ) const;

 [[nodiscard]] BinaryTree * left( void ) const;

 [[nodiscard]] BinaryTree * right( void ) const;

 void insertLeft( BinaryTree * t );

 void insertRight( BinaryTree * t );

 void deleteLeft( void );

 void deleteRight( void );

 [[nodiscard]] BinaryTree * detachLeft( void );

 [[nodiscard]] BinaryTree * detachRight( void );

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

 void insert( BinaryTree * & child , BinaryTree * t );

 BinaryTree * detach( BinaryTree * & child );

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

 [[nodiscard]] const BinaryTree * top( void ) const;

 T f_value;
 BinaryTree * f_parent = nullptr;
 BinaryTree * f_left = nullptr;
 BinaryTree * f_right = nullptr;

 };  // end( class BinaryTree )

/*--------------------------------------------------------------------------*/
/*------------------------------- VISITS -----------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class Pre , class In , class Post >
void dfs( BinaryTree< T > * t , Pre && pre , In && in , Post && post );

template< class T , class F >
void pre_visit( BinaryTree< T > * t , F && f );

template< class T , class F >
void in_visit( BinaryTree< T > * t , F && f );

template< class T , class F >
void post_visit( BinaryTree< T > * t , F && f );

template< class T >
BinaryTree< T > * copy( const BinaryTree< T > * t );

template< class T >
BinaryTree< T > * join( const T & v , const BinaryTree< T > * l ,
                        const BinaryTree< T > * r );

/*--------------------------------------------------------------------------*/
/*--------------------------- REPRESENTATIONS ------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
std::string to_list( const BinaryTree< T > * t );

template< class T >
BinaryTree< T > * from_list( std::string_view s );

template< class T >
BinaryTree< T > * to_binary( const Tree< T > * t );

inline long dary_child( long i , long d , long j );

inline long dary_parent( long i , long d );

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

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

// the nodes of a binary tree as ranges, forward, by the links to the
// parents, with no stack; *it is a node

namespace detail {

struct BinaryPreorder {
 static constexpr std::nullptr_t none = nullptr;
 template< class N >
 static N * next( const void * , N * n , N * root ) {
  if( n->left() ) return( n->left() );
  if( n->right() ) return( n->right() );
  for( ; n != root ; n = n->parent() )      // up to a right sibling
   if( ( n == n->parent()->left() ) && n->parent()->right() )
    return( n->parent()->right() );
  return( nullptr );
  }
 };

struct BinaryInorder {
 static constexpr std::nullptr_t none = nullptr;
 template< class N >
 static N * leftmost( N * n ) {
  while( n->left() ) n = n->left();
  return( n );
  }
 template< class N >
 static N * next( const void * , N * n , N * root ) {
  if( n->right() ) return( leftmost( n->right() ) );
  for( ; n != root ; n = n->parent() )      // up from a left child
   if( n == n->parent()->left() ) return( n->parent() );
  return( nullptr );
  }
 };

struct BinaryPostorder {
 static constexpr std::nullptr_t none = nullptr;
 template< class N >
 static N * firstLeaf( N * n ) {
  while( n->left() || n->right() )
   n = n->left() ? n->left() : n->right();
  return( n );
  }
 template< class N >
 static N * next( const void * , N * n , N * root ) {
  if( n == root ) return( nullptr );
  N * p = n->parent();
  if( ( n == p->left() ) && p->right() )   // down the right sibling
   return( firstLeaf( p->right() ) );
  return( p );
  }
 };

}  // end( namespace detail )

template< class T >
auto preorder( BinaryTree< T > * t )
{
 using It = WalkIterator< void , BinaryTree< T > * ,
                          detail::BinaryPreorder >;
 return( std::ranges::subrange( It( nullptr , t , t ) , It() ) );
 }

template< class T >
auto inorder( BinaryTree< T > * t )
{
 using It = WalkIterator< void , BinaryTree< T > * , detail::BinaryInorder >;
 return( std::ranges::subrange(
          It( nullptr , detail::BinaryInorder::leftmost( t ) , t ) , It() ) );
 }

template< class T >
auto postorder( BinaryTree< T > * t )
{
 using It = WalkIterator< void , BinaryTree< T > * ,
                          detail::BinaryPostorder >;
 return( std::ranges::subrange(
          It( nullptr , detail::BinaryPostorder::firstLeaf( t ) , t ) ,
          It() ) );
 }

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

}  // end( namespace ADS )

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

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

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

#endif  /* BinaryTree.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File BinaryTree.h --------------------------*/
/*--------------------------------------------------------------------------*/