Program Listing for File ArrayBinaryTree.h

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

/*--------------------------------------------------------------------------*/
/*------------------------- File ArrayBinaryTree.h -------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/Iterators.h"
#include "ADS/queue/ArrayQueue.h"
#include "ADS/tree/BinaryTree.h"

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS ArrayBinaryTree --------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class ArrayBinaryTree {

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

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

 ArrayBinaryTree( void ) = default;

 explicit ArrayBinaryTree( const T & v );

 ArrayBinaryTree( const T & v , const ArrayBinaryTree & l ,
                  const ArrayBinaryTree & r );

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

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

 [[nodiscard]] long parent( long i ) const;

 [[nodiscard]] long left( long i ) const;

 [[nodiscard]] long right( long i ) const;

 [[nodiscard]] bool isLeaf( long i ) const;

 [[nodiscard]] const T & read( long i ) const;

 void write( long i , const T & v );

 void setRoot( const T & v );

 void insertLeft( long i , const ArrayBinaryTree & t );

 void insertRight( long i , const ArrayBinaryTree & t );

 void remove( long i );

 [[nodiscard]] std::vector< long > preorder( void ) const;

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

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

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

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

 [[nodiscard]] bool has( long i ) const;

 std::optional< T > & place( long i );

 const std::optional< T > & at( long i ) const;

 std::optional< T > & at( long i );

 void clear( long i );

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

 void copy( long k , const ArrayBinaryTree & t , long j );

 void graft( long i , long c , const ArrayBinaryTree & t );

 std::vector< std::optional< T > > f_A;

 };  // end( class ArrayBinaryTree )

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

}  // end( namespace ADS )

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

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

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

#endif  /* ArrayBinaryTree.h included */

/*--------------------------------------------------------------------------*/
/*----------------------- End File ArrayBinaryTree.h -----------------------*/
/*--------------------------------------------------------------------------*/