Program Listing for File MultiStack.h

↰ Return to documentation for file (ADS/stack/MultiStack.h)

/*--------------------------------------------------------------------------*/
/*--------------------------- File MultiStack.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <ranges>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS MultiStack ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class MultiStack {

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

 using Item = T;

 explicit MultiStack( int k );

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

 [[nodiscard]] bool empty( int i ) const;

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

 [[nodiscard]] const T & top( int i ) const;

 void push( int i , const T & v );

 T pop( int i );

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

 struct Cell {
  T value;
  int below;
  };

 public:

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

 // a constant view of each stack, from the top to the bottom, forward

 using value_type = T;
 using const_iterator =
  IndexIterator< Cell , T , &Cell::below , &Cell::value >;

 [[nodiscard]] std::ranges::subrange< const_iterator > stack( int i ) const {
  ADS_PRE( ( i >= 0 ) && ( i < stacks() ) );
  return( std::ranges::subrange( const_iterator( &f_C , f_top[ i ] ) ,
                                 const_iterator( &f_C , -1 ) ) );
  }

 private:

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

 std::vector< Cell > f_C;
 std::vector< int > f_top;
 std::vector< int > f_size;
 int f_free = -1;

 };  // end( class MultiStack )

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

}  // end( namespace ADS )

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

#include "ADS/stack/impl/MultiStack.tpp"

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

#endif  /* MultiStack.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File MultiStack.h --------------------------*/
/*--------------------------------------------------------------------------*/