Program Listing for File SortedArrayDictionary.h

↰ Return to documentation for file (ADS/dictionary/SortedArrayDictionary.h)

/*--------------------------------------------------------------------------*/
/*---------------------- File SortedArrayDictionary.h ----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------- CLASS SortedArrayDictionary -----------------------*/
/*--------------------------------------------------------------------------*/

template< std::totally_ordered K , class V >
class SortedArrayDictionary {

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

 using Key = K;
 using Value = V;

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

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

 void remove( const K & k );

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

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

 [[nodiscard]] const std::vector< std::pair< K , V > > & pairs( void ) const;

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

 // a constant view of the pairs by increasing key, contiguous

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

 [[nodiscard]] const_iterator begin( void ) const { return( f_A.data() ); }
 [[nodiscard]] const_iterator end( void ) const {
  return( f_A.data() + f_A.size() );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 [[nodiscard]] std::size_t place( const K & k ) const;

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

 std::vector< std::pair< K , V > > f_A;

 };  // end( class SortedArrayDictionary )

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

}  // end( namespace ADS )

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

#include "ADS/dictionary/impl/SortedArrayDictionary.tpp"

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

#endif  /* SortedArrayDictionary.h included */

/*--------------------------------------------------------------------------*/
/*-------------------- End File SortedArrayDictionary.h --------------------*/
/*--------------------------------------------------------------------------*/