Program Listing for File SearchTree.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File SearchTree.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <concepts>
#include <cstddef>
#include <iterator>
#include <memory>
#include <optional>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS SearchTree ------------------------------*/
/*--------------------------------------------------------------------------*/

enum class Color : unsigned char { RED , BLACK };

template< std::totally_ordered K , class V , bool RB >
class SearchTree {

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

 using Key = K;
 using Value = V;

 struct Link {
  Link * parent;
  Link * left;
  Link * right;
  Color color = Color::BLACK;
  };

 struct Node : Link {
  K key;
  V value;
  };

 SearchTree( void );

 SearchTree( const SearchTree & o );

 SearchTree( SearchTree && o ) noexcept;

 SearchTree & operator=( SearchTree o ) noexcept;

 ~SearchTree();

 void swap( SearchTree & o ) noexcept;

/*--------------------------------------------------------------------------*/
/*------------------------- DICTIONARY OPERATIONS --------------------------*/
/*--------------------------------------------------------------------------*/

 [[nodiscard]] std::optional< V > lookup( const K & k ) const;

 void insert( const K & k , const V & v );

 void remove( const K & k );

 [[nodiscard]] bool contains( const K & k ) const;

 [[nodiscard]] std::size_t size( void ) const;

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

 void clear( void );

/*--------------------------------------------------------------------------*/
/*---------------------------- NAVIGATION ----------------------------------*/
/*--------------------------------------------------------------------------*/
 [[nodiscard]] Link * root( void ) const;

 [[nodiscard]] bool isNil( const Link * u ) const;

 [[nodiscard]] static const K & key( const Link * u );

 [[nodiscard]] static const V & value( const Link * u );

 [[nodiscard]] Link * lookupNode( const K & x ) const;

 [[nodiscard]] Link * min( void ) const;

 [[nodiscard]] Link * max( void ) const;

 [[nodiscard]] Link * successorNode( Link * t ) const;

 template< class F >
 void forEach( F && f ) const;

 [[nodiscard]] Link * predecessorNode( Link * t ) const;

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

 // a constant view of the pairs ( key , value ) by increasing key,
 // bidirectional by the links to the parents, the sentinel leaf being the
 // end

 class const_iterator {
  public:
  using reference = std::pair< const K & , const V & >;
  using value_type = reference;
  using difference_type = std::ptrdiff_t;
  using iterator_concept = std::bidirectional_iterator_tag;
  using iterator_category = std::input_iterator_tag;

  const_iterator( void ) = default;
  const_iterator( const SearchTree * t , Link * x ) : f_t( t ) , f_x( x ) {}

  reference operator*( void ) const {
   return( reference( f_t->key( f_x ) , f_t->value( f_x ) ) );
   }
  const_iterator & operator++( void ) {
   f_x = f_t->successorNode( f_x );
   return( *this );
   }
  const_iterator & operator--( void ) {
   f_x = f_t->isNil( f_x ) ? f_t->max() : f_t->predecessorNode( f_x );
   return( *this );
   }
  const_iterator operator++( int ) { auto t = *this; ++*this; return( t ); }
  const_iterator operator--( int ) { auto t = *this; --*this; return( t ); }
  bool operator==( const const_iterator & o ) const {
   return( f_x == o.f_x );
   }

  [[nodiscard]] Link * node( void ) const { return( f_x ); }

  private:
  const SearchTree * f_t = nullptr;
  Link * f_x = nullptr;
  };

 using value_type = std::pair< const K & , const V & >;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = value_type;
 using const_reference = value_type;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( this , min() ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( this , f_nil.get() ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

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

 [[nodiscard]] Link * nil( void ) const;

 void clear_nil( void );

 static K & key_ref( Link * u );

 static V & value_ref( Link * u );

 Link * new_node( const K & x , const V & v );

 Link * copy( const SearchTree & o , Link * u , Link * p );

/*--------------------------------------------------------------------------*/
/*------------------- THE PROCEDURES OF SECTION 6.1 ------------------------*/
/*--------------------------------------------------------------------------*/

 Link * lookupNode( Link * T , const K & x ) const;

 Link * min( Link * T ) const;

 Link * max( Link * T ) const;

 void link( Link * p , Link * u , const K & x );

 Link * insertNode( Link * T , const K & x , const V & v );

 Link * removeNode( Link * T , const K & x0 );

/*--------------------------------------------------------------------------*/
/*------------------- THE PROCEDURES OF SECTION 6.2 ------------------------*/
/*--------------------------------------------------------------------------*/

 Link * rotateLeft( Link * x );

 Link * rotateRight( Link * x );

 static constexpr Color RED = Color::RED;
 static constexpr Color BLACK = Color::BLACK;

 void balanceInsert( Link * t );

 void balanceDelete( Link * t );

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

 std::unique_ptr< Link > f_nil;
 Link * f_root = f_nil.get();
 std::size_t f_size = 0;

 };  // end( class SearchTree )

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

template< std::totally_ordered K , class V >
using BinarySearchTree = SearchTree< K , V , false >;

template< std::totally_ordered K , class V >
using RedBlackTree = SearchTree< K , V , true >;

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

}  // end( namespace ADS )

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

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

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

#endif  /* SearchTree.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File SearchTree.h --------------------------*/
/*--------------------------------------------------------------------------*/