Program Listing for File Tree.h

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

/*--------------------------------------------------------------------------*/
/*------------------------------ File Tree.h -------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS Tree ---------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class Tree {

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

 using Item = T;

 explicit Tree( const T & v );

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

 ~Tree();

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

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

 void write( const T & v );

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

 [[nodiscard]] Tree * leftmostChild( void ) const;

 [[nodiscard]] Tree * rightSibling( void ) const;

 void insertChild( Tree * t );

 void insertSibling( Tree * t );

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

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

 void deleteChild( void );

 void deleteSibling( void );

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

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

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

 T f_value;
 Tree * f_parent = nullptr;
 Tree * f_child = nullptr;
 Tree * f_sibling = nullptr;

 };  // end( class Tree )

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

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

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

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

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

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

template< class T , class F >
void bfs( Tree< T > * t , F && f );

template< class T >
int maxWeightLevel( Tree< T > * t );

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

template< class T >
Tree< T > * tree_from_list( std::string_view s );

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

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

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

namespace detail {

struct TreeChildren {
 static constexpr std::nullptr_t none = nullptr;
 template< class N >
 static N * next( const void * , N * n , N * ) {
  return( n->rightSibling() );
  }
 };

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

}  // end( namespace detail )

template< class T >
auto children( Tree< T > * t )
{
 using It = WalkIterator< void , Tree< T > * , detail::TreeChildren >;
 return( std::ranges::subrange( It( nullptr , t->leftmostChild() , t ) ,
                                It() ) );
 }

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

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

}  // end( namespace ADS )

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

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

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

#endif  /* Tree.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File Tree.h -----------------------------*/
/*--------------------------------------------------------------------------*/