Program Listing for File PreorderArrayTree.h

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

/*--------------------------------------------------------------------------*/
/*------------------------ File PreorderArrayTree.h ------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <ranges>
#include <stdexcept>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS PreorderArrayTree -------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class PreorderArrayTree {

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

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

 PreorderArrayTree( void ) = default;

 explicit PreorderArrayTree( const T & v );

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

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

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

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

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

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

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

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

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

 [[nodiscard]] int subtreeEnd( int i ) const;

 void insertChild( int i , const PreorderArrayTree & t );

 void insertSibling( int i , const PreorderArrayTree & t );

 void remove( int i );

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

 [[nodiscard]] auto values( void ) const;

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

 struct Cell {
  int parent;
  T value;
  };

 const Cell & cell( int i ) const;

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

 void splice( int at , int p , const PreorderArrayTree & t );

 std::vector< Cell > f_A;

 };  // end( class PreorderArrayTree )

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

}  // end( namespace ADS )

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

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

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

#endif  /* PreorderArrayTree.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File PreorderArrayTree.h ----------------------*/
/*--------------------------------------------------------------------------*/