Program Listing for File SortedListSet.h

↰ Return to documentation for file (ADS/set/SortedListSet.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File SortedListSet.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <functional>
#include <optional>
#include <stdexcept>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS SortedListSet ---------------------------*/
/*--------------------------------------------------------------------------*/

template< std::totally_ordered T >
class SortedListSet {

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

 using Item = T;

 SortedListSet( void ) = default;

 SortedListSet( std::initializer_list< T > items );

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

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

 [[nodiscard]] bool contains( const T & x ) const;

 void insert( const T & x );

 void insertLast( const T & x );

 void remove( const T & x );

 [[nodiscard]] std::optional< T > min( void ) const;

 [[nodiscard]] std::optional< T > max( void ) const;

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

 [[nodiscard]] const List< T > & list( void ) const;

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

 // a constant view of the items in increasing order, bidirectional

 using value_type = T;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = const T &;
 using const_reference = const T &;
 using const_iterator = typename List< T >::const_iterator;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const { return( f_L.begin() ); }
 [[nodiscard]] const_iterator end( void ) const { return( f_L.end() ); }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 typename List< T >::Pos lower( const T & x ) const;

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

 List< T > f_L;
 std::size_t f_size = 0;

 };  // end( class SortedListSet )

template< class T >
SortedListSet< T > merge( const SortedListSet< T > & A ,
                          const SortedListSet< T > & B ,
                          bool a , bool b , bool both );

template< class T >
SortedListSet< T > setUnion( const SortedListSet< T > & A ,
                             const SortedListSet< T > & B );

template< class T >
SortedListSet< T > setIntersection( const SortedListSet< T > & A ,
                                    const SortedListSet< T > & B );

template< class T >
SortedListSet< T > setDifference( const SortedListSet< T > & A ,
                                  const SortedListSet< T > & B );

template< class T >
SortedListSet< T > setSymmetricDifference( const SortedListSet< T > & A ,
                                           const SortedListSet< T > & B );

}  // end( namespace ADS )

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

#include "ADS/set/impl/SortedListSet.tpp"

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

#endif  /* SortedListSet.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File SortedListSet.h ------------------------*/
/*--------------------------------------------------------------------------*/