Program Listing for File ChildListTree.h

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

/*--------------------------------------------------------------------------*/
/*-------------------------- File ChildListTree.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS ChildListTree ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class ChildListTree {

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

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

 ChildListTree( void ) = default;

 explicit ChildListTree( const T & v );

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

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

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

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

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

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

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

 [[nodiscard]] const List< int > & children( int n ) const;

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

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

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

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

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

 void remove( int n );

 [[nodiscard]] std::vector< int > previsit( void ) const;
 [[nodiscard]] std::vector< int > postvisit( void ) const;
 [[nodiscard]] std::vector< int > invisit( int i ) const;

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

 struct Node {
  T value;
  int parent;
  List< int > children;
  typename List< int >::Pos where;
  bool used;
  };

 const Node & node( int n ) const;
 Node & node( int n );

 int make( const T & v , int p );

 void release( int n );

 void visit( int n , int i , std::vector< int > & P , int kind ) const;

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

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

 };  // end( class ChildListTree )

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

}  // end( namespace ADS )

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

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

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

#endif  /* ChildListTree.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File ChildListTree.h ------------------------*/
/*--------------------------------------------------------------------------*/