// bslalg_dequeimputil.h                                              -*-C++-*-
#ifndef INCLUDED_BSLALG_DEQUEIMPUTIL
#define INCLUDED_BSLALG_DEQUEIMPUTIL

#include <bsls_ident.h>
BSLS_IDENT("$Id: $")

//@PURPOSE: Provide basic parameters and primitive data structures for deques.
//
//@CLASSES:
//  bslalg::DequeImpUtil: deque parameters and primitive data structures
//
//@SEE_ALSO: bslalg_dequeprimitives, bslalg_arrayprimitives
//
//@DESCRIPTION: This component provides primitive data structures for
// implementing a deque knowing only its value type and the number of objects
// in a block.  Conceptually, a deque is an array of blocks pointers, each
// block capable of containing a fixed number of objects.  An element in the
// deque is identified by an iterator that consists of a pointer to the block
// pointer array, and a pointer to a value.  A deque implementation is
// parameterized by the 'VALUE_TYPE' and a 'BLOCK_LENGTH' (fixed number of
// objects in a block).  'bslalg::DequeImpUtil' provides a namespace for the
// following types and constants:
//..
//  Type                   Short description
//  ----                   -----------------
//  ValueType              An alias for the templatized 'VALUE_TYPE'
//  Block                  An array (of length 'BLOCK_LENGTH') of 'ValueType'
//  BlockPtr               An alias for a pointer to a block
//
//  Constant               Short description
//  --------               -----------------
//  BLOCK_BYTES            Number of bytes in a block
//  BLOCK_ARRAY_PADDING    Number of empty blocks to keep at both ends of the
//                         block array pointer (one on each side).
//..
//
// The picture is as follows:
//..
//  +-----+-----+-----+-----+-----+-----+-----+-----+
//  |  *  |  *  |  *  |  *  |  *  |  *  |  *  |  *  |  (BlockPtr array)
//  +-----+-----+--|--+--|--+--|--+--|--+-----+-----+
//                 |     |     |     |                     Block
//                 |     |     |     |  +---+---+---+---+---+---+---+---+
//                 |     |     |     `--| V | W | X | Y | Z |   |   |   |
//                 |     |     |        +---+---+---+---+---+---+---+---+
//                 |     |     |                      Block
//                 |     |     |  +---+---+---+---+---+---+---+---+
//                 |     |     `--| N | O | P | Q | R | S | T | U |
//                 |     |        +---+---+---+---+---+---+---+---+
//                 |     |                      Block
//                 |     |  +---+---+---+---+---+---+---+---+
//                 |     `--| F | G | H | I | J | K | L | M |
//                 |        +---+---+---+---+---+---+---+---+
//                 |                      Block
//                 |  +---+---+---+---+---+---+---+---+
//                 `--|   |   |   | A | B | C | D | E |
//                    +---+---+---+---+---+---+---+---+
//..
// Depicted above is a deque consisting of an array of eight block pointers,
// only four actually used to point to blocks of eight elements.  In the first
// block, the first three elements are uninitialized, and the twenty six
// elements follow in sequence across the different blocks.  The value of the
// corresponding deque would be '[ A, B, C, ... X, Y, Z ]', its logical length
// 26, and its capacity would be 19 (the minimum number of prepend/append to
// force a reallocation of the block pointer array).
//
///Usage
///-----
// This component is for use by the 'bslalg' package.  Other clients should use
// the STL deque (in header '<deque>').

#include <bslscm_version.h>

namespace BloombergLP {

namespace bslalg {

                           // ==============
                           // class DequeImp
                           // ==============

template <class VALUE_TYPE, int BLOCK_LENGTH>
struct DequeImpUtil {
    // This 'struct', parameterized by the 'VALUE_TYPE' and a 'BLOCK_LENGTH',
    // provides the various parameters of the deque implementation.

    // PUBLIC CONSTANTS
    enum { BLOCK_BYTES         = BLOCK_LENGTH * sizeof(VALUE_TYPE) };
        // Actual number of bytes in a block.

    enum { BLOCK_ARRAY_PADDING = 2 };
        // Minimum number of (allocated) empty blocks to keep at both ends of
        // the block array pointer (one on each side of the deque).

    // PUBLIC TYPES
    typedef VALUE_TYPE  ValueType;
        // 'ValueType' is an alias for the 'VALUE_TYPE' provided as first
        // template parameter to this class.

    struct Block {
        // A block of one or more data objects.  A deque will be organized as a
        // sequence of blocks.

        VALUE_TYPE d_data[BLOCK_LENGTH];
    };

    typedef Block *BlockPtr;
        // Pointer to a block.  A deque will own an array of those.
};

}  // close package namespace

#ifndef BDE_OPENSOURCE_PUBLICATION  // BACKWARD_COMPATIBILITY
// ============================================================================
//                           BACKWARD COMPATIBILITY
// ============================================================================

#ifdef bslalg_DequeImpUtil
#undef bslalg_DequeImpUtil
#endif
#define bslalg_DequeImpUtil bslalg::DequeImpUtil
    // This alias is defined for backward compatibility.
#endif  // BDE_OPENSOURCE_PUBLICATION -- BACKWARD_COMPATIBILITY

}  // close enterprise namespace

#endif

// ----------------------------------------------------------------------------
// Copyright 2013 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------