Program Listing for File BinaryTreeAlgorithms.h

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

/*--------------------------------------------------------------------------*/
/*---------------------- File BinaryTreeAlgorithms.h -----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/search/RangeMinimum.h"
#include "ADS/tree/BinaryTree.h"

#include <bit>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <memory>
#include <type_traits>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- THE NODES -----------------------------------*/
/*--------------------------------------------------------------------------*/

namespace detail {

template< class N >
auto nodeLeft( N * n )
{
 if constexpr( requires { n->left(); } ) return( n->left() );
 else return( n->left );
 }

template< class N >
auto nodeRight( N * n )
{
 if constexpr( requires { n->right(); } ) return( n->right() );
 else return( n->right );
 }

template< class N >
auto nodeParent( N * n )
{
 if constexpr( requires { n->parent(); } ) return( n->parent() );
 else return( n->parent );
 }

template< class N >
decltype( auto ) nodeKey( N * n )
{
 if constexpr( requires { n->read(); } ) return( n->read() );
 else return( ( n->key ) );
 }

}  // end( namespace detail )

template< class N >
concept BinaryNode = std::is_pointer_v< N > && requires( N n ) {
 detail::nodeLeft( n );
 detail::nodeRight( n );
 };

template< class N >
concept ParentBinaryNode = BinaryNode< N > && requires( N n ) {
 detail::nodeParent( n );
 };

template< class N >
concept KeyedBinaryNode = BinaryNode< N > && requires( N n ) {
 detail::nodeKey( n );
 };

/*--------------------------------------------------------------------------*/
/*---------------------------- THE ANCESTORS -------------------------------*/
/*--------------------------------------------------------------------------*/

template< ParentBinaryNode N >
N lowestCommonAncestor( N u , N v );

/*--------------------------------------------------------------------------*/
/*--------------------------- THE COMPARISONS ------------------------------*/
/*--------------------------------------------------------------------------*/

template< KeyedBinaryNode N , KeyedBinaryNode M ,
          class Equal = std::equal_to<> >
[[nodiscard]] bool equalTrees( N t , M s , Equal eq = {} );

template< KeyedBinaryNode N , class Compare = std::less<> >
[[nodiscard]] bool isSearchTree( N t , Compare less = {} );

template< BinaryNode N , class Red >
[[nodiscard]] bool isRedBlackTree( N t , Red red );

/*--------------------------------------------------------------------------*/
/*------------------------------ THE SEARCHES ------------------------------*/
/*--------------------------------------------------------------------------*/

template< KeyedBinaryNode N , class K , class F ,
          class Compare = std::less<> >
std::size_t searchTreeRange( N t , const K & lo , const K & hi , F && f ,
                             Compare less = {} );

/*--------------------------------------------------------------------------*/
/*------------------------------ THE BUILDERS ------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class Make , class Compare = std::less<> >
auto minimumHeightSearchTree( const std::vector< T > & A , Make make ,
                              Compare less = {} )
 -> std::invoke_result_t< Make & , const T & , std::nullptr_t ,
                          std::nullptr_t >;

template< class T , class Compare = std::less<> >
 requires std::predicate< Compare & , const T & , const T & >
BinaryTree< T > * minimumHeightSearchTree( const std::vector< T > & A ,
                                           Compare less = {} );

template< class T >
BinaryTree< T > * fromPreorderInorder( const std::vector< T > & pre ,
                                       const std::vector< T > & in );

template< class T , class Compare = std::less< T > >
BinaryTree< T > * cartesianBinaryTree( const std::vector< T > & A ,
                                       Compare less = {} );

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

}  // end( namespace ADS )

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

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

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

#endif  /* BinaryTreeAlgorithms.h included */

/*--------------------------------------------------------------------------*/
/*-------------------- End File BinaryTreeAlgorithms.h ---------------------*/
/*--------------------------------------------------------------------------*/