You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


// bdlc_queue.h                                                       -*-C++-*-

// ----------------------------------------------------------------------------
//                                   NOTICE
//
// This component is not up to date with current BDE coding standards, and
// should not be used as an example for new development.
// ----------------------------------------------------------------------------

#ifndef INCLUDED_BDLC_QUEUE
#define INCLUDED_BDLC_QUEUE

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

//@PURPOSE: Provide an in-place double-ended queue of 'T' values.
//
//@DEPRECATED: Use 'bsl::deque' instead.
//
//@CLASSES:
//  bdlc::Queue: memory manager for in-place queue of 'T' values
//
//@DESCRIPTION: This component implements an efficient, in-place, indexable,
// double-ended queue of 'T' values, where 'T' is a templatized, user-defined
// type.  The functionality of a 'bdlc::Queue' is relatively rich; it is almost
// a proper superset of a vector, with efficient implementations of 'front',
// 'back', 'pushFront', and 'popBack' methods added.  However, the queue does
// *not* provide a 'data' method (yielding direct access to the underlying
// memory), because its internal organization is not array-like.
//
// Typical usage involves pushing (appending) values to the back of the queue,
// popping (removing) values from the front of the queue, and retrieving
// (operator[]) values from a specified index; unlike the O[n] runtime cost for
// an 'insert(0, v)', however, a 'pushFront' has a constant average-case cost.
//
// Note that appending, inserting, removing or pushing (back and front)
// elements potentially alters the memory address of other element in the
// queue, and there is no guarantee of contiguous storage of consecutive queued
// elements.
//
///Abstract Representation
///-----------------------
// The logical organization of an indexable, in-place, double-ended
// 'bdlc::Queue' object 'q' is shown below, along with an illustration of some
// of its most common methods:
//..
//                                    QUEUE
//                 v = q.front()                          v = q.back()
//                  +------+------+------+------+--//--+------+
//   q.popFront() <-|      |      |      |      |      |      |<- pushBack(v)
// q.pushFront(v) ->|      |      |      |      |      |      |-> popBack()
//                  +------+------+------+------+--//--+------+
//                    q[0]   q[1]                       q[n-1]
//                  <------------ n = q.length() --//--------->
//..
//
///Performance
///-----------
// The following characterizes the performance of representative operations
// using big-oh notation, O[f(N,M)], where the names 'N' and 'M' also refer to
// the number of respective elements in each container (i.e., its 'length').
// Here the average case, A[f(N)], is the amortized cost, which is defined as
// the cost of 'N' successive invocations of the operation divided by 'N'.
//..
//     Operation           Worst Case          Average Case
//     ---------           ----------          ------------
//     DEFAULT CTOR        O[1]
//     COPY CTOR(N)        O[N]
//     N.DTOR()            O[1]
//     N.OP=(M)            O[M]
//     OP==(N,M)           O[min(N,M)]
//
//     N.pushFront(value)  O[N]                A[1]
//     N.pushBack(value)   O[N]                A[1]
//     N.popFront()        O[1]
//     N.popBack()         O[1]
//
//     N.append(value)     O[N]                A[1]
//     N.insert(value)     O[N]
//     N.replace(value)    O[1]
//     N.remove(index)     O[N]
//
//     N.OP[]()            O[1]
//     N.length()          O[1]
//..
//
///Usage
///-----
// The following snippets of code illustrate how to create and use a queue.
// First, create an empty 'bdlc::Queue<double>' 'q' and populate it with two
// elements 'E1' and 'E2'.
//..
//      const double E1 = 100.01;
//      const double E2 = 200.02;
//
//      bdlc::Queue<double> q;          assert( 0 == q.length());
//
//      q.append(E1);                   assert( 1 == q.length());
//                                      assert(E1 == q[0]);
//                                      assert(E1 == q.front());
//                                      assert(E1 == q.back());
//
//      q.append(E2);                   assert( 2 == q.length());
//                                      assert(E1 == q[0]);
//                                      assert(E2 == q[1]);
//                                      assert(E1 == q.front());
//                                      assert(E2 == q.back());
//..
// Now, pop the first element ('E1') from 'q' and push the same value to the
// front of the queue.
//..
//      q.popFront();                   assert( 1 == q.length());
//                                      assert(E2 == q[0]);
//                                      assert(E2 == q.front());
//                                      assert(E2 == q.back());
//
//      q.pushFront(E1);                assert( 2 == q.length());
//                                      assert(E1 == q[0]);
//                                      assert(E2 == q[1]);
//                                      assert(E1 == q.front());
//                                      assert(E2 == q.back());
//..
// Then, pop the last element ('E2') from the back of 'q' and push a new value
// 'E3' at the end of the queue.
//..
//      const double E3 = 300.03;
//
//      q.popBack();                    assert( 1 == q.length());
//                                      assert(E1 == q[0]);
//                                      assert(E1 == q.front());
//                                      assert(E1 == q.back());
//
//      q.pushBack(E3);                 assert( 2 == q.length());
//                                      assert(E1 == q[0]);
//                                      assert(E3 == q[1]);
//                                      assert(E1 == q.front());
//                                      assert(E3 == q.back());
//..
// Now, assign 'E2' to the first element (index position 0) of 'q'.
//..
//      q[0] = E2;                      assert( 2 == q.length());
//                                      assert(E2 == q[0]);
//                                      assert(E3 == q[1]);
//..
// Then, insert a new value in the middle (index position 1) of 'q'.
//..
//      const double E4 = 400.04;
//
//      q.insert(1, E4);                assert( 3 == q.length());
//                                      assert(E2 == q[0]);
//                                      assert(E4 == q[1]);
//                                      assert(E3 == q[2]);
//..
// Next, iterate over the elements in 'q', printing them in increasing order of
// their index positions, '[0 .. q.length() - 1]',
//..
//      bsl::cout << '[';
//      int len = q.length();
//      for (int i = 0; i < len; ++i) {
//          bsl::cout << ' ' << q[i];
//      }
//      bsl::cout << " ]" << bsl::endl;
//
//..
// which produces the following output on 'stdout':
//..
//      [ 200.02 400.04 300.03 ]
//..
// Finally, remove the elements from queue 'q'.
//..
//      q.remove(2);                    assert( 2 == q.length());
//                                      assert(E2 == q[0]);
//                                      assert(E4 == q[1]);
//
//      q.remove(0);                    assert( 1 == q.length());
//                                      assert(E4 == q[0]);
//
//      q.remove(0);                    assert( 0 == q.length());
//
//..
// Note that, in general, specifying index positions greater than or equal to
// length() will result in undefined behavior.

#include <bdlscm_version.h>

#include <bdlb_print.h>
#include <bdlb_printmethods.h>

#include <bslma_default.h>
#include <bslma_usesbslmaallocator.h>

#include <bslmf_nestedtraitdeclaration.h>

#include <bslx_instreamfunctions.h>
#include <bslx_outstreamfunctions.h>

#include <bsl_cstring.h>        // memmove(), memcmp(), memcpy()
#include <bsl_ostream.h>
#include <bsl_new.h>

#ifndef BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
#include <bslalg_typetraits.h>
#endif // BDE_DONT_ALLOW_TRANSITIVE_INCLUDES

namespace BloombergLP {
namespace bdlc {

                                // ===========
                                // class Queue
                                // ===========

template <class T>
class Queue {
    // This class implements an efficient, in-place double-ended queue of
    // values of parameterized type 'T'.  The physical capacity of this queue
    // may grow, but never shrinks.  Capacity may be reserved initially via a
    // constructor, or at any time thereafter by using the 'reserveCapacity'
    // and 'reserveCapacityRaw' methods.  Note that there is no guarantee of
    // contiguous storage of consecutive elements.
    //
    // More generally, this container class supports a complete set of *value*
    // *semantics* operations, including copy construction, assignment,
    // equality comparison, 'ostream' printing, and 'bdex' serialization.  (A
    // precise operational definition of when two objects have the same value
    // can be found in the description of 'operator==' for the class.)  This
    // container is *exception* *neutral* with no guarantee of rollback: if an
    // exception is thrown during the invocation of a method on a pre-existing
    // object, the container is left in a valid state, but its value is
    // undefined.  In no event is memory leaked.  Finally, *aliasing* (e.g.,
    // using all or part of an object as both source and destination) is
    // supported in all cases.

    // PRIVATE TYPES
    enum {
        // The queue is full when 'd_front == d_back'.  Hence, 'k_INITIAL_SIZE'
        // must be at least two.

        k_INITIAL_SIZE   = 2,  // initial physical capacity (in elements)
        k_GROW_FACTOR    = 2,  // multiplicative factor for growing 'd_size'
        k_EXTRA_CAPACITY = 2   // extra capacity needed by implementation
    };

  public:
    // TYPES
    struct InitialCapacity {
        // Enable uniform use of an optional integral constructor argument to
        // specify the initial internal capacity (in elements).  For example,
        //..
        //   Queue<unsigned int> x(Queue::InitialCapacity(8));
        //..
        // instantiates an object 'x' with an initial capacity of 8 elements,
        // but with a logical length of 0 elements.

        unsigned int d_i;

        // CREATORS
        explicit InitialCapacity(unsigned int i) : d_i(i) { }
        ~InitialCapacity() { }
    };

  private:
    // DATA
    T                *d_array_p;      // dynamically allocated array ('d_size'
                                      // elements)

    int               d_size;         // physical capacity of this array (in
                                      // elements)

    int               d_front;        // index of element before first stored
                                      // element

    int               d_back;         // index of element past last stored
                                      // element

    bslma::Allocator *d_allocator_p;  // holds (but not own) memory allocator

  private:
    // PRIVATE MANIPULATORS
    int calculateSufficientSize(int minLength, int size);
        // Grow geometrically the specified current 'size' value while it is
        // less than the specified 'minLength' value plus any additional
        // capacity required by the implementation (i.e., 'k_EXTRA_CAPACITY'
        // elements).  Return the new size value.  The behavior is undefined
        // unless 'k_INITIAL_SIZE <= size' and '0 <= minLength'.  Note that if
        // 'minLength + k_EXTRA_CAPACITY <= size' then 'size' is returned.

    int memcpyCircular(T       *dstArray,
                       int      dstSize,
                       int      dstIndex,
                       const T *srcArray,
                       int      srcSize,
                       int      srcIndex,
                       int      numElements);
        // Copy efficiently the specified 'numElements' data values from the
        // specified 'srcArray' of the specified 'srcSize' starting at the
        // specified 'srcIndex' into the specified 'dstArray' of the specified
        // 'dstSize' starting at the specified 'dstIndex'.  Return the new
        // value for the back of the queue.  The 'srcArray' and the 'dstArray'
        // are assumed to be queues; they are circular which implies copy may
        // have to be broken into multiple parts since the underlying array is
        // linear.  The behavior is undefined unless '0 <= dstSize',
        // '0 <= dstIndex < dstSize', '0 <= srcIndex < srcSize',
        // '0 <= numElements', 'numElements <= dstSize - k_EXTRA_CAPACITY', and
        // 'numElements <= srcSize - k_EXTRA_CAPACITY' (the 'k_EXTRA_CAPACITY'
        // accounts for the locations of 'd_front' and 'd_back').  Note that
        // aliasing is not handled properly.

    void memShiftLeft(T   *array,
                      int  size,
                      int  dstIndex,
                      int  srcIndex,
                      int  numElements);
        // Copy efficiently the specified 'numElements' data values from the
        // specified 'array' of the specified 'size' starting at the specified
        // index 'srcIndex' to the specified 'dstIndex' assuming the elements
        // are to be moved to the left (towards the front of the queue).
        // 'array' is assumed to be a queue; it is circular.  The behavior is
        // undefined unless '0 <= size', '0 <= dstIndex < size',
        // '0 <= srcIndex < size', and
        // '0 <= numElements <= size - k_EXTRA_CAPACITY'.  Note that this
        // function is alias safe.

    void memShiftRight(T   *array,
                       int  size,
                       int  dstIndex,
                       int  srcIndex,
                       int  numElements);
        // Copy efficiently the specified 'numElements' data values from the
        // specified 'array' of the specified 'size' starting at the specified
        // index 'srcIndex' to the specified 'dstIndex' assuming the elements
        // are to be moved to the right (towards the back of the queue).
        // 'array' is assumed to be a queue; it is circular.  The behavior is
        // undefined unless '0 <= size', '0 <= dstIndex < size',
        // '0 <= srcIndex < size', and
        // '0 <= numElements <= size - k_EXTRA_CAPACITY'.  Note that this
        // function is alias safe.

    void copyData(T       *dstArray,
                  int     *dstBack,
                  int      dstSize,
                  int      dstFront,
                  const T *srcArray,
                  int      srcSize,
                  int      srcFront,
                  int      srcBack);
        // Copy efficiently the queue indicated by the specified 'srcArray' of
        // the specified 'srcSize' with the specified 'srcFront' and the
        // specified 'srcBack' into the queue indicated by the specified
        // 'dstArray' of the specified 'dstSize', with the specified
        // 'dstFront'.  The specified 'dstBack' is set to make the length of
        // the destination queue the same as the length of the source queue.
        // The behavior is undefined unless '0 <= dstSize',
        // '0 <= dstFront < dstSize', '0 <= srcSize',
        // '0 <= srcFront < srcSize', and '0 <= srcBack < srcSize'.  Note that
        // aliasing is not handled properly.

    int increaseSizeImp(T                **addrArray,
                        int               *front,
                        int               *back,
                        int                newSize,
                        int                size,
                        bslma::Allocator  *allocator);
        // Increase the physical capacity of the queue represented by the
        // specified 'addrArray' to specified 'newSize' from the specified
        // 'size'.  Return the new size of the queue.  This function copies the
        // data contained within the queue between the specified 'front' and
        // 'back' to the new queue and update the values of both 'front' and
        // 'back'.  Use the specified 'allocator' to supply and retrieve
        // memory.  The behavior is undefined unless
        // 'k_INITIAL_SIZE <= newSize', 'k_INITIAL_SIZE <= size',
        // 'size <= newSize', '0 <= *front < size', and '0 <= *back < size'.

    void increaseSize();
        // Increase the physical capacity of this array by at least one
        // element.

  public:
    // TRAITS
    BSLMF_NESTED_TRAIT_DECLARATION(Queue, bdlb::HasPrintMethod);
    BSLMF_NESTED_TRAIT_DECLARATION(Queue, bslma::UsesBslmaAllocator);

    // CLASS METHODS
    static int maxSupportedBdexVersion(int versionSelector);
        // Return the maximum valid BDEX format version, as indicated by the
        // specified 'versionSelector', to be passed to the 'bdexStreamOut'
        // method.  Note that it is highly recommended that 'versionSelector'
        // be formatted as "YYYYMMDD", a date representation.  Also note that
        // 'versionSelector' should be a *compile*-time-chosen value that
        // selects a format version supported by both externalizer and
        // unexternalizer.  See the 'bslx' package-level documentation for more
        // information on BDEX streaming of value-semantic types and
        // containers.

    // CREATORS
    explicit
    Queue(bslma::Allocator *basicAllocator = 0);
    explicit
    Queue(unsigned int      initialLength,
          bslma::Allocator *basicAllocator = 0);
    Queue(int               initialLength,
          const T&          initialValue,
          bslma::Allocator *basicAllocator = 0);
        // Create an in-place queue.  By default, the queue is empty.
        // Optionally specify the 'initialLength' of the queue.  Queue elements
        // are initialized with the specified 'initialValue', or to 0.0 if
        // 'initialValue' is not specified.  Optionally specify a
        // 'basicAllocator' used to supply memory.  If 'basicAllocator' is 0,
        // the currently installed default allocator is used.  The behavior is
        // undefined unless '0 <= initialLength'.

    explicit
    Queue(const InitialCapacity&  numElements,
          bslma::Allocator       *basicAllocator = 0);
        // Create an in-place queue with sufficient initial capacity to
        // accommodate up to the specified 'numElements' values without
        // subsequent reallocation.  A valid reference returned by the
        // 'operator[]' method is guaranteed to remain valid unless the value
        // returned by the 'length' method exceeds 'numElements' (which would
        // potentially cause a reallocation).  Optionally specify a
        // 'basicAllocator' used to supply memory.  If 'basicAllocator' is 0,
        // the currently installed default allocator is used.  The behavior is
        // undefined unless '0 <= numElements'.

    Queue(const T          *srcArray,
          int               numElements,
          bslma::Allocator *basicAllocator = 0);
        // Create an in-place queue initialized with the specified
        // 'numElements' leading values from the specified 'srcArray'.
        // Optionally specify the 'basicAllocator' used to supply memory.  If
        // 'basicAllocator' is 0, the currently installed default allocator is
        // used.  The behavior is undefined unless '0 <= numElements'.  Note
        // that 'srcArray' must refer to sufficient memory to hold
        // 'numElements' values.

    Queue(const Queue& original, bslma::Allocator* basicAllocator = 0);
        // Create an in-place queue initialized to the value of the specified
        // 'original' queue.  Optionally specify the 'basicAllocator' used to
        // supply memory.  If 'basicAllocator' is 0, the currently installed
        // default allocator is used.

    ~Queue();
        // Destroy this object.

    // MANIPULATORS
    Queue& operator=(const Queue& rhs);
        // Assign to this queue the value of the specified 'rhs' queue and
        // return a reference to this modifiable queue.

    T& operator[](int index);
        // Return a reference to the modifiable element at the specified
        // 'index' position in this queue.  The reference will remain valid as
        // long as this queue is not destroyed or modified (e.g., via 'insert',
        // 'remove', or 'append').  The behavior is undefined unless
        // '0 <= index < length()'.

    void append(const T& item);
        // Append to the end of this queue the value of the specified 'item'.
        // Note that this function is a synonym for 'pushBack' and is logically
        // equivalent to (but generally more efficient than):
        //..
        //   insert(length(), item);
        //..

    void append(const Queue& srcQueue);
        // Append to the end of this queue the sequence of values in the
        // specified 'srcQueue'.  Note that this function is logically
        // equivalent to:
        //..
        //   insert(length(), srcQueue);
        //..

    void append(const Queue& srcQueue, int srcIndex, int numElements);
        // Append to the end of this queue the specified 'numElements' value in
        // the specified 'srcQueue' starting at the specified index position
        // 'srcIndex'.  Note that this function is logically equivalent to:
        //..
        //   insert(length(), srcQueue, srcIndex, numElements);
        //..
        // The behavior is undefined unless '0 <= srcIndex',
        // '0 <= numElements', and
        // 'srcIndex + numElements <= srcQueue.length()'.

    T& back();
        // Return a reference to the modifiable value at the back of this
        // queue.  The reference will remain valid as long as the queue is not
        // destroyed or modified (e.g., via 'insert', 'remove', or 'append').
        // The behavior is undefined if the queue is empty.  Note that this
        // function is logically equivalent to:
        //..
        //  operator[](length() - 1)
        //..

    T& front();
        // Return a reference to the modifiable value at the front of this
        // queue.  The reference will remain valid as long as the queue is not
        // destroyed or modified (e.g., via 'insert', 'remove', or 'append').
        // The behavior is undefined if the queue is empty.  Note that this
        // function is logically equivalent to:
        //..
        //  operator[](0)
        //..

    void insert(int dstIndex, const T& item);
        // Insert the specified 'item' into this queue at the specified
        // 'dstIndex'.  All current values with indices at or above 'dstIndex'
        // are shifted up by one index position.  The behavior is undefined
        // unless '0 <= dstIndex <= length()'.

    void insert(int dstIndex, const Queue& srcQueue);
        // Insert the specified 'srcQueue' into this queue at the specified
        // 'dstIndex'.  All current values with indices at or above 'dstIndex'
        // are shifted up by 'srcQueue.length()' index positions.  The behavior
        // is undefined unless '0 <= dstIndex <= length()'.

    void insert(int          dstIndex,
                const Queue& srcQueue,
                int          srcIndex,
                int          numElements);
        // Insert the specified 'numElements' values starting at the specified
        // 'srcIndex' position from the specified 'srcQueue' into this queue at
        // the specified 'dstIndex'.  All current values with indices at or
        // above 'dstIndex' are shifted up by 'numElements' index positions.
        // The behavior is undefined unless '0 <= dstIndex <= length()',
        // '0 <= srcIndex', '0 <= numElements', and
        // 'srcIndex + numElements <= srcQueue.length()'.

    void popBack();
        // Remove the value from the back of this queue efficiently (in O[1]
        // time).  The behavior is undefined if this queue is empty.  Note that
        // this function is logically equivalent to (but more efficient than):
        //..
        //    remove(length() - 1)
        //..

    void popFront();
        // Remove the value from the front of this queue efficiently (in O[1]
        // time).  The behavior is undefined if this queue is empty.  Note that
        // this function is logically equivalent to (but more efficient than):
        //..
        //    remove(0)
        //..

    void pushBack(const T& item);
        // Append the specified 'item' to the back of this queue efficiently
        // (in O[1] time when memory reallocation is not required).  Note that
        // this function is logically equivalent to (but generally more
        // efficient than):
        //..
        //    insert(length(), item);
        //..

    void pushFront(const T& item);
        // Insert the specified 'item' into the front of this queue efficiently
        // (in O[1] time when memory reallocation is not required).  Note that
        // this function is logically equivalent to (but generally more
        // efficient than):
        //..
        //    insert(0, item);
        //..

    void remove(int index);
        // Remove from this queue the value at the specified 'index'.  All
        // values with initial indices above 'index' are shifted down by one
        // index position.  The behavior is undefined unless
        // '0 <= index < length()'.

    void remove(int index, int numElements);
        // Remove from this queue, beginning at the specified 'index', the
        // specified 'numElements' values.  All values with initial indices at
        // or above 'index + numElements' are shifted down by 'numElements'
        // index positions.  The behavior is undefined unless '0 <= index',
        // '0 <= numElements', and 'index + numElements <= length()'.

    void removeAll(bsl::vector<T> *buffer = 0);
        // Remove all elements from this queue.  If the optionally specified
        // 'buffer' is not 0, append to 'buffer' a copy of each element removed
        // (in front-to-back order of the elements in the queue prior to the
        // invocation of this method).

    void replace(int dstIndex, const T& item);
        // Replace the element at the specified 'dstIndex' in this queue with
        // the specified 'item'.  The behavior is undefined unless
        // '0 <= dstIndex < length()'.  Note that this function is logically
        // equivalent to (but more efficient than):
        //..
        //    insert(dstIndex, item);
        //    remove(dstIndex + 1);
        //..

    void replace(int          dstIndex,
                 const Queue& srcQueue,
                 int          srcIndex,
                 int          numElements);
        // Replace the specified 'numElements' values beginning at the
        // specified 'dstIndex' in this queue with values from the specified
        // 'srcQueue' beginning at the specified 'srcIndex'.  The behavior is
        // undefined unless '0 <= dstIndex, 0 <= numElements',
        // 'dstIndex + numElements <= length()', '0 <= srcIndex', and
        // 'srcIndex + numElements <= srcQueue.length()'.  Note that this
        // function is logically equivalent to (but more efficient than):
        //..
        //    insert(dstIndex, srcQueue, srcIndex, numElements);
        //    remove(dstIndex + numElements, numElements);
        //..

    void reserveCapacity(int numElements);
        // Reserve sufficient internal capacity to accommodate up to the
        // specified 'numElements' values without subsequent reallocation.
        // Note that if 'numElements <= length()', this operation has no
        // effect.

    void reserveCapacityRaw(int numElements);
        // Reserve sufficient and minimal internal capacity to accommodate up
        // to the specified 'numElements' values without subsequent
        // reallocation.  Beware, however, that repeated calls to this function
        // may invalidate bounds on runtime complexity otherwise guaranteed by
        // this container.  Note that if 'numElements <= length()', this
        // operation has no effect.

    void setLength(int newLength);
    void setLength(int newLength, const T& initialValue);
        // Set the length of this queue to the specified 'newLength'.  If
        // 'newLength' is less than the current length, elements at index
        // positions at or above 'newLength' are removed.  Otherwise any new
        // elements (at or above the current length) are initialized to the
        // specified 'initialValue', or to 0.0 if 'initialValue' is not
        // specified.  The behavior is undefined unless '0 <= newLength'.

    void setLengthRaw(int newLength);
        // Set the length of this queue to the specified 'newLength'.  If
        // 'newLength' is less than the current length, elements at index
        // positions at or above 'newLength' are removed.  If 'newLength' is
        // equal to the current length, this function has no effect.  Otherwise
        // new elements at or above the current length are not initialized to
        // any value.

    template <class STREAM>
    STREAM& bdexStreamIn(STREAM& stream, int version);
        // Assign to this object the value read from the specified input
        // 'stream' using the specified 'version' format, and return a
        // reference to 'stream'.  If 'stream' is initially invalid, this
        // operation has no effect.  If 'version' is not supported, this object
        // is unaltered and 'stream' is invalidated, but otherwise unmodified.
        // If 'version' is supported but 'stream' becomes invalid during this
        // operation, this object has an undefined, but valid, state.  Note
        // that no version is read from 'stream'.  See the 'bslx' package-level
        // documentation for more information on BDEX streaming of
        // value-semantic types and containers.

    void swap(int index1, int index2);
        // Swap efficiently the values at the specified indices 'index1' and
        // 'index2'.  The behavior is undefined unless '0 <= index1 < length()'
        // and '0 <= index2 < length()'.

    // ACCESSORS
    const T& operator[](int index) const;
        // Return a reference to the non-modifiable element at the specified
        // 'index' position in this queue.  The reference will remain valid as
        // long as this queue is not destroyed or modified (e.g., via 'insert',
        // 'remove', or 'append').  The behavior is undefined unless
        // '0 <= index < length()'.

    const T& back() const;
        // Return a reference to the non-modifiable element at the back of this
        // queue.  The reference will remain valid as long as this queue is not
        // destroyed or modified (e.g., via 'insert', 'remove', or 'append').
        // The behavior is undefined if this queue is empty.  Note that this
        // function is logically equivalent to:
        //..
        //    operator[](length() - 1)
        //..

    const T& front() const;
        // Return a reference to the non-modifiable element at the front of
        // this queue.  The reference will remain valid as long as this queue
        // is not destroyed or modified (e.g., via 'insert', 'remove', or
        // 'append').  The behavior is undefined if this queue is empty.  Note
        // that this function is logically equivalent to:
        //..
        //    operator[](0)
        //..

    int length() const;
        // Return the number of elements in this queue.

    bsl::ostream& print(bsl::ostream& stream,
                        int           level,
                        int           spacesPerLevel) const;
        // Format this object to the specified output 'stream' at the
        // optionally specified indentation 'level' and return a reference to
        // the modifiable 'stream'.  If 'level' is specified, optionally
        // specify 'spacesPerLevel', the number of spaces per indentation level
        // for this and all of its nested objects.  Each line is indented by
        // the absolute value of 'level * spacesPerLevel'.  If 'level' is
        // negative, suppress indentation of the first line.  If
        // 'spacesPerLevel' is negative, suppress line breaks and format the
        // entire output on one line.  If 'stream' is initially invalid, this
        // operation has no effect.  Note that a trailing newline is provided
        // in multi-line mode only.

    bsl::ostream& streamOut(bsl::ostream& stream) const
        // Write the elements of this queue out to the specified 'stream'.
        // Note that for this method to compile, 'operator<<' has to be defined
        // for arguments 'stream' and type 'T'.
    {
        stream << '[';
        for (int i = 0; i < length(); ++i) {
            stream << ' ' << (*this)[i];
        }
        return stream << " ]";
    }

    template <class STREAM>
    STREAM& bdexStreamOut(STREAM& stream, int version) const;
        // Write the value of this object, using the specified 'version'
        // format, to the specified output 'stream', and return a reference to
        // 'stream'.  If 'stream' is initially invalid, this operation has no
        // effect.  If 'version' is not supported, 'stream' is invalidated, but
        // otherwise unmodified.  Note that 'version' is not written to
        // 'stream'.  See the 'bslx' package-level documentation for more
        // information on BDEX streaming of value-semantic types and
        // containers.

#ifndef BDE_OMIT_INTERNAL_DEPRECATED  // pending deprecation

    static int maxSupportedBdexVersion();
        // !DEPRECATED!: Use 'maxSupportedBdexVersion(int)' instead.
        //
        // Return the most current BDEX streaming version number supported by
        // this class.

    static int maxSupportedVersion();
        // Return the most current 'bdex' streaming version number supported by
        // this class.  (See the package-group-level documentation for more
        // information on 'bdex' streaming of container types.)
        //
        // DEPRECATED: Use 'maxSupportedBdexVersion' instead.

#endif // BDE_OMIT_INTERNAL_DEPRECATED -- pending deprecation
};

// FREE OPERATORS
template <class T>
inline
bool operator==(const Queue<T>& lhs, const Queue<T>& rhs);
    // Return 'true' if the specified 'lhs' and 'rhs' queues have the same
    // value, and 'false' otherwise.  Two queues have the same value if they
    // have the same length and the same element value at each respective index
    // position.

template <class T>
inline
bool operator!=(const Queue<T>& lhs, const Queue<T>& rhs);
    // Return 'true' if the specified 'lhs' and 'rhs' queues do not have the
    // same value, and 'false' otherwise.  Two queues do not have the same
    // value if they have different lengths or differ in at least one index
    // position.

template <class T>
inline
bsl::ostream& operator<<(bsl::ostream& stream, const Queue<T>& queue);
    // Write the specified 'queue' to the specified output 'stream' and return
    // a reference to the modifiable 'stream'.

// ============================================================================
//                            INLINE DEFINITIONS
// ============================================================================

// TBD pass through allocator
// TBD isBitwise, etc.

              // ---------------------------------------------
              // inlined methods used by other inlined methods
              // ---------------------------------------------

template <class T>
inline
int Queue<T>::length() const
{
    return d_back > d_front ? d_back - d_front - 1
                            : d_back + d_size - d_front - 1;
}

// PRIVATE MANIPULATORS
template <class T>
int Queue<T>::calculateSufficientSize(int minLength, int size)
{
    const int len = minLength + k_EXTRA_CAPACITY;
    while (size < len) {
        size *= k_GROW_FACTOR;
    }
    return size;
}

template <class T>
int Queue<T>::memcpyCircular(T       *dstArray,
                             int      dstSize,
                             int      dstIndex,
                             const T *srcArray,
                             int      srcSize,
                             int      srcIndex,
                             int      numElements)
{
    int dst;  // temporary value to store the current destination location

    // Break the source queue into one or two linear arrays to copy.

    int srcA = srcIndex;
    if (srcA + numElements <= srcSize) {  // one linear source array
        int lenSrcA = numElements;

        dst = dstIndex;

        // Compute the maximum number of elements that can be copied to the
        // destination array.

        int dstLen = dstSize - dst;

        if (dstLen >= lenSrcA) {  // can copy everything from srcA
            // TBD efficiency

            for (int i = 0; i < lenSrcA; ++i) {
                new (&dstArray[dst + i]) T(srcArray[srcA + i]);
            }
            dst += lenSrcA;
        }
        else {  // can copy only part of srcA without changing dst
            // TBD efficiency

            for (int i = 0; i < dstLen; ++i) {
                new (&dstArray[dst + i]) T(srcArray[srcA + i]);
            }
            srcA += dstLen;
            lenSrcA -= dstLen;

            // WARNING:  There seems to be an AIX compiler issue for the
            // following four lines.  Removing the 'assert' and moving the
            // 'memcpy' down two lines may cause the program to compile, but
            // not execute properly.

            // TBD efficiency

            for (int i = 0; i < lenSrcA; ++i) {
                new (&dstArray[i]) T(srcArray[srcA + i]);
            }
            dstLen = dst;  // max numElements that can be copied to index 0
            dst = lenSrcA;

            // TBD doc above assert(lenSrcA <= dstLen - k_EXTRA_CAPACITY);
        }
    }
    else {  // two linear source arrays
        int lenSrcA = srcSize - srcA;
        int lenSrcB = numElements - lenSrcA;

        dst = dstIndex;

        // Compute the maximum number of elements that can be copied to the
        // destination array.

        int dstLen = dstSize - dst;

        if (dstLen >= lenSrcA) {  // can copy everything from srcA
            // TBD efficiency

            for (int i = 0; i < lenSrcA; ++i) {
                new (&dstArray[dst + i]) T(srcArray[srcA + i]);
            }
            dst += lenSrcA;
        }
        else {  // can copy only part of srcA without changing dst
            // TBD efficiency

            for (int i = 0; i < dstLen; ++i) {
                new (&dstArray[dst + i]) T(srcArray[srcA + i]);
            }
            srcA += dstLen;
            lenSrcA -= dstLen;

            // WARNING:  There seems to be an AIX compiler issue for the
            // following four lines.  Removing the 'assert' and moving the
            // 'memcpy' down two lines may cause the program to compile, but
            // not execute properly.

            // TBD efficiency

            for (int i = 0; i < lenSrcA; ++i) {
                new (&dstArray[i]) T(srcArray[srcA + i]);
            }
            dstLen = dst;  // max numElements that can be copied to index 0
            dst = lenSrcA;

            // TBD
            // doc above assert(
            // lenSrcA + lenSrcB <= dstLen - k_EXTRA_CAPACITY);
        }
        dstLen -= lenSrcA;

        if (dstLen >= lenSrcB) {  // can copy everything from srcB
            // TBD efficiency

            for (int i = 0; i < lenSrcB; ++i) {
                new (&dstArray[dst + i]) T(srcArray[i]);
            }
            dst += lenSrcB;
        }
        else {  // can copy only part of srcB without changing dst
            // NOTE: could not have had insufficient room for srcA
            // TBD efficiency

            for (int i = 0; i < dstLen; ++i) {
                new (&dstArray[dst + i]) T(srcArray[i]);
            }
            lenSrcB -= dstLen;
            dst = lenSrcB;

            // TBD efficiency

            for (int i = 0; i < lenSrcB; ++i) {
                new (&dstArray[i]) T(srcArray[dstLen + i]);
            }
        }
    }

    return dst % dstSize;
}

template <class T>
void Queue<T>::memShiftLeft(T   *array,
                            int  size,
                            int  dstIndex,
                            int  srcIndex,
                            int  numElements)
{
    // Move the elements that do not wrap around the array end.

    if (srcIndex > dstIndex) {
        int numMove = size - srcIndex;
        if (numMove >= numElements) {
            // TBD efficiency

            for (int i = 0; i < numElements; ++i) {
                new (&array[dstIndex + i]) T(array[srcIndex + i]);
                array[srcIndex + i].~T();
            }
            return;                                                   // RETURN
        }

        // TBD efficiency

        for (int i = 0; i < numMove; ++i) {
            new (&array[dstIndex + i]) T(array[srcIndex + i]);
            array[srcIndex + i].~T();
        }
        numElements -= numMove;
        dstIndex += numMove;
        srcIndex = 0;
    }
    else if (srcIndex == dstIndex) {
        return;                                                       // RETURN
    }

    // Move the elements of the source that will just precede the array end.

    int numMove = size - dstIndex;
    if (numMove >= numElements) {
        // TBD efficiency

        for (int i = numElements - 1; i >= 0; --i) {
            new (&array[dstIndex + i]) T(array[srcIndex + i]);
            array[srcIndex + i].~T();
        }

        return;                                                       // RETURN
    }
    // TBD efficiency

    for (int i = numMove - 1; i >= 0; --i) {
        new (&array[dstIndex + i]) T(array[srcIndex + i]);
        array[srcIndex + i].~T();
    }
    numElements -= numMove;
    srcIndex += numMove;

    // Move the elements of the source that are around the array end.

    // TBD efficiency

    for (int i = 0; i < numElements; ++i) {
        new (&array[i]) T(array[srcIndex + i]);
        array[srcIndex + i].~T();
    }
}

template <class T>
void Queue<T>::memShiftRight(T   *array,
                             int  size,
                             int  dstIndex,
                             int  srcIndex,
                             int  numElements)
{
    if (dstIndex == srcIndex) {
        return;                                                       // RETURN
    }

    {

        // Move the elements of the source that wrap around the array end.

        int numMove = srcIndex + numElements;
        if (numMove > size) {
            numMove -= size;
            // TBD efficiency

            for (int i = numMove - 1; i >= 0; --i) {
                new (&array[(dstIndex + numElements - numMove) % size + i])
                                                                   T(array[i]);
                array[i].~T();
            }
            numElements -= numMove;
        }
    }

    {
        // Move the elements of the source that will wrap around the array end.

        int numMove = dstIndex + numElements;
        if (numMove > size) {
            numMove -= size;
            // TBD efficiency

            for (int i = 0; i < numMove; ++i) {
                new (&array[i])
                       T(array[(srcIndex + numElements - numMove) % size + i]);
                array[srcIndex + numElements - numMove + i].~T();
            }
            numElements -= numMove;
        }
    }

    // Move the elements of the source that do not and will not wrap around
    // the array end.

    if (dstIndex < srcIndex) {
        // TBD efficiency

        for (int i = 0; i < numElements; ++i) {
            new (&array[dstIndex + i]) T(array[srcIndex + i]);
            array[srcIndex + i].~T();
        }
    }
    else {
        // TBD efficiency

        for (int i = numElements - 1; i >= 0; --i) {
            new (&array[dstIndex + i]) T(array[srcIndex + i]);
            array[srcIndex + i].~T();
        }
    }
}

template <class T>
inline
void Queue<T>::copyData(T       *dstArray,
                        int     *dstBack,
                        int      dstSize,
                        int      dstFront,
                        const T *srcArray,
                        int      srcSize,
                        int      srcFront,
                        int      srcBack)
{
    const int dstIndex = (dstFront + 1) % dstSize;
    const int srcIndex = (srcFront + 1) % srcSize;
    const int numElements = (srcBack + srcSize - srcFront - 1) % srcSize;

    *dstBack = memcpyCircular(dstArray,
                              dstSize,
                              dstIndex,
                              srcArray,
                              srcSize,
                              srcIndex,
                              numElements);
}

template <class T>
int Queue<T>::increaseSizeImp(T                **addrArray,
                              int               *front,
                              int               *back,
                              int                newSize,
                              int                size,
                              bslma::Allocator  *allocator)
{
    T *array = (T *)allocator->allocate(newSize * sizeof **addrArray);

    // COMMIT

    const int oldFront = *front;
    const int oldBack = *back;
    *front = newSize - 1;
    copyData(array, back, newSize, *front, *addrArray, size, oldFront, *back);

    // TBD efficiency

    for (int i = (oldFront + 1) % size; i != oldBack; i = (i + 1) % size) {
        (*addrArray)[i].~T();
    }

    allocator->deallocate(*addrArray);
    *addrArray = array;
    return newSize;
}

template <class T>
inline
void Queue<T>::increaseSize()
{
    d_size = increaseSizeImp(&d_array_p,
                             &d_front,
                             &d_back,
                             d_size * k_GROW_FACTOR,
                             d_size,
                             d_allocator_p);
}

// CLASS METHODS
template <class T>
inline
int Queue<T>::maxSupportedBdexVersion(int /* versionSelector */)
{
    return 1;  // Required by BDE policy; versions start at 1.
}

#ifndef BDE_OMIT_INTERNAL_DEPRECATED  // pending deprecation

// DEPRECATED METHODS

template <class T>
inline
int Queue<T>::maxSupportedVersion()
{
    return maxSupportedBdexVersion();
}

template <class T>
inline
int Queue<T>::maxSupportedBdexVersion()
{
    return 1;  // Required by BDE policy; versions start at 1.
}

#endif // BDE_OMIT_INTERNAL_DEPRECATED -- pending deprecation

// CREATORS
template <class T>
Queue<T>::Queue(bslma::Allocator *basicAllocator)
: d_size(k_INITIAL_SIZE)
, d_front(k_INITIAL_SIZE - 1)
, d_back(0)
, d_allocator_p(bslma::Default::allocator(basicAllocator))
{
    d_array_p = (T *)d_allocator_p->allocate(d_size * sizeof *d_array_p);
}

template <class T>
Queue<T>::Queue(unsigned int initialLength, bslma::Allocator *basicAllocator)
: d_back(initialLength)
, d_allocator_p(bslma::Default::allocator(basicAllocator))
{
    d_size = calculateSufficientSize(initialLength, k_INITIAL_SIZE);
    d_array_p = (T *)d_allocator_p->allocate(d_size * sizeof *d_array_p);
    d_front = d_size - 1;

    // initialize the array values
    // TBD efficiency
    // TBD exception neutrality

    for (int i = 0; i < d_back; ++i) {
        new (d_array_p + i) T();
    }
}

template <class T>
Queue<T>::Queue(int               initialLength,
                const T&          initialValue,
                bslma::Allocator *basicAllocator)
: d_back(initialLength)
, d_allocator_p(bslma::Default::allocator(basicAllocator))
{
    d_size = calculateSufficientSize(initialLength, k_INITIAL_SIZE);
    d_array_p = (T *)d_allocator_p->allocate(d_size * sizeof *d_array_p);
    d_front = d_size - 1;

    // TBD efficiency
    // TBD exception neutrality

    for (int i = 0; i < d_back; ++i) {
        new (d_array_p + i) T(initialValue);
    }
}

template <class T>
Queue<T>::Queue(const InitialCapacity&  numElements,
                bslma::Allocator       *basicAllocator)
: d_size(numElements.d_i + k_EXTRA_CAPACITY) // to hold the empty positions
, d_front(numElements.d_i + k_EXTRA_CAPACITY - 1)
, d_back(0)
, d_allocator_p(bslma::Default::allocator(basicAllocator))
{
    d_array_p = (T *)d_allocator_p->allocate(d_size * sizeof *d_array_p);
}

template <class T>
Queue<T>::Queue(const T          *srcArray,
                int               numElements,
                bslma::Allocator *basicAllocator)
: d_back(numElements)
, d_allocator_p(bslma::Default::allocator(basicAllocator))
{
    d_size = calculateSufficientSize(numElements, k_INITIAL_SIZE);
    d_front = d_size - 1;
    d_array_p = (T *)d_allocator_p->allocate(d_size * sizeof *d_array_p);

    // TBD efficiency

    for (int i = 0; i < numElements; ++i) {
        new (&d_array_p[i]) T(srcArray[i]);
    }
}

template <class T>
Queue<T>::Queue(const Queue& original, bslma::Allocator *basicAllocator)
: d_allocator_p(bslma::Default::allocator(basicAllocator))
{
    d_size = calculateSufficientSize(original.length(), k_INITIAL_SIZE);
    d_array_p = (T *)d_allocator_p->allocate(d_size * sizeof *d_array_p);
    d_front = d_size - 1;
    copyData(d_array_p,
             &d_back,
             d_size,
             d_front,
             original.d_array_p,
             original.d_size,
             original.d_front,
             original.d_back);
}

template <class T>
Queue<T>::~Queue()
{
    // TBD efficiency

    for (int i = (d_front + 1) % d_size; i != d_back; i = (i + 1) % d_size) {
        d_array_p[i].~T();
    }

    d_allocator_p->deallocate(d_array_p);
}

// MANIPULATORS
template <class T>
Queue<T>& Queue<T>::operator=(const Queue& rhs)
{
    if (this != &rhs) {
        const int newSize =
                         calculateSufficientSize(rhs.length(), k_INITIAL_SIZE);
        if (newSize > d_size) {
            T *array =
                     (T *)d_allocator_p->allocate(newSize * sizeof *d_array_p);

            // TBD efficiency

            for (int i = (d_front + 1) % d_size; i != d_back;
                                                        i = (i + 1) % d_size) {
                d_array_p[i].~T();
            }

            d_allocator_p->deallocate(d_array_p);
            d_array_p = array;
            d_size = newSize;
        }
        else {
            // TBD efficiency

            for (int i = (d_front + 1) % d_size; i != d_back;
                                                        i = (i + 1) % d_size) {
                d_array_p[i].~T();
            }
        }
        copyData(d_array_p,
                 &d_back,
                 d_size,
                 d_front,
                 rhs.d_array_p,
                 rhs.d_size,
                 rhs.d_front,
                 rhs.d_back);
    }
    return *this;
}

template <class T>
inline
T& Queue<T>::operator[](int index)
{
    return d_array_p[(index + d_front + 1) % d_size];
}

template <class T>
void Queue<T>::append(const Queue& srcQueue)
{
    const int numElements = srcQueue.length();
    const int newLength = length() + numElements;
    const int minSize = calculateSufficientSize(newLength, d_size);
    if (d_size < minSize) {
        d_size = increaseSizeImp(&d_array_p,
                                 &d_front,
                                 &d_back,
                                 minSize,
                                 d_size,
                                 d_allocator_p);
    }
    d_back = memcpyCircular(d_array_p,
                            d_size,
                            d_back,
                            srcQueue.d_array_p,
                            srcQueue.d_size,
                            (srcQueue.d_front + 1) % srcQueue.d_size,
                            numElements);
}

template <class T>
void Queue<T>::append(const Queue& srcQueue,
                      int          srcIndex,
                      int          numElements)
{
    const int newLength = length() + numElements;
    const int minSize = calculateSufficientSize(newLength, d_size);
    if (d_size < minSize) {
        d_size = increaseSizeImp(&d_array_p,
                                 &d_front,
                                 &d_back,
                                 minSize,
                                 d_size,
                                 d_allocator_p);
    }
    d_back = memcpyCircular(d_array_p,
                            d_size,
                            d_back,
                            srcQueue.d_array_p,
                            srcQueue.d_size,
                            (srcQueue.d_front + 1 + srcIndex) %
                                srcQueue.d_size,
                            numElements);
}

template <class T>
inline
T& Queue<T>::back()
{
    return d_array_p[(d_back - 1 + d_size) % d_size];
}

template <class T>
inline
T& Queue<T>::front()
{
    return d_array_p[(d_front + 1) % d_size];
}

template <class T>
void Queue<T>::insert(int dstIndex, const T& item)
{
    T itemCopy(item);  // TBD hack for aliased case

    // The capacity must always be greater than or equal to
    // 'length + k_EXTRA_CAPACITY'.

    const int originalLength = length();
    const int newLength = originalLength + 1;
    const int newSize = calculateSufficientSize(newLength, d_size);

    if (d_size < newSize) {
        // resize, makes move easy

        T *array = (T *)d_allocator_p->allocate(newSize * sizeof *d_array_p);

        // COMMIT

        const int start = d_front + 1;

        // NOTE: newSize >= size + 1 so '% newSize' is not needed in next line.

        memcpyCircular(array,
                       newSize,
                       start,           // no '% newSize'
                       d_array_p,
                       d_size,
                       start % d_size,
                       dstIndex);
        memcpyCircular(array,
                       newSize,
                       (start + dstIndex + 1) % newSize,
                       d_array_p,
                       d_size,
                       (start + dstIndex) % d_size,
                       originalLength - dstIndex);

        // TBD efficiency

        for (int i = (d_front + 1) % d_size; i != d_back;
                                                        i = (i + 1) % d_size) {
            d_array_p[i].~T();
        }

        d_allocator_p->deallocate(d_array_p);
        d_array_p = array;

        d_size = newSize;
        d_back = (start + newLength) % d_size;
        new (&d_array_p[(start + dstIndex) % d_size]) T(itemCopy);
    }
    else {  // sufficient capacity

        // No resize is required.  Copy as few elements as possible.

        // Compute number of elements that are past the insertion point: the
        // back length.

        const int backLen = originalLength - dstIndex;

        if (dstIndex < backLen) {

            // We will choose to shift 'dstIndex' elements to the left.

            const int src = (d_front + 1) % d_size;
            const int dst = d_front;

            memShiftLeft(d_array_p, d_size, dst, src, dstIndex);
            new (&d_array_p[(d_front + dstIndex) % d_size]) T(itemCopy);
            d_front = (d_front - 1 + d_size) % d_size;
        }
        else {

            // We will choose to shift 'backLen' elements to the right.

            const int src = (d_front + 1 + dstIndex) % d_size;
            const int dst = (src + 1) % d_size;

            memShiftRight(d_array_p,
                          d_size,
                          dst,
                          src,
                          backLen);
            new (&d_array_p[(d_front + 1 + dstIndex) % d_size]) T(itemCopy);
            d_back = (d_back + 1) % d_size;
        }
    }
}

template <class T>
void Queue<T>::insert(int          dstIndex,
                      const Queue& srcQueue,
                      int          srcIndex,
                      int          numElements)
{
    // The capacity must always be greater than or equal to
    // 'length + k_EXTRA_CAPACITY'.

    const int originalLength = length();
    const int newLength = originalLength + numElements;
    const int newSize = calculateSufficientSize(newLength, d_size);

    if (d_size < newSize) {
        // resize, makes move easy

        T *array = (T *)d_allocator_p->allocate(newSize * sizeof *d_array_p);

        // COMMIT

        const int start = d_front + 1;
        const int startIndex = start + dstIndex;

        // NOTE: newSize >= size + 1 so '% newSize' is not needed in next line.

        memcpyCircular(array,
                       newSize,
                       start,           // no '% newSize'
                       d_array_p,
                       d_size,
                       start % d_size,
                       dstIndex);
        memcpyCircular(array,
                       newSize,
                       (startIndex + numElements) % newSize,
                       d_array_p,
                       d_size,
                       (startIndex) % d_size,
                       originalLength - dstIndex);
        memcpyCircular(array,
                       newSize,
                       startIndex % newSize,
                       srcQueue.d_array_p,
                       srcQueue.d_size,
                       (srcQueue.d_front + 1 + srcIndex) % srcQueue.d_size,
                       numElements);

        // TBD efficiency

        for (int i = (d_front + 1) % d_size; i != d_back;
                                                        i = (i + 1) % d_size) {
            d_array_p[i].~T();
        }

        d_allocator_p->deallocate(d_array_p);
        d_array_p = array;
        d_size = newSize;
        d_back = (start + newLength) % d_size;
    }
    else { // sufficient capacity

        // No resize is required.  Copy as few elements as possible.

        // Compute number of elements that are past the insertion point: the
        // back length.

        const int backLen = originalLength - dstIndex;
        if (dstIndex < backLen) {

            // We will shift 'dstIndex' elements to the left.

            const int d = (d_front + 1 - numElements + d_size) % d_size;
            memShiftLeft(d_array_p,
                         d_size,
                         d,
                         (d_front + 1) % d_size,
                         dstIndex);

            if (this != &srcQueue || srcIndex >= dstIndex) {  // not aliased
                memcpyCircular(d_array_p,
                               d_size,
                               (d + dstIndex) % d_size,
                               srcQueue.d_array_p,
                               srcQueue.d_size,
                               (srcQueue.d_front + 1 + srcIndex) %
                                                               srcQueue.d_size,
                               numElements);
            }
            else { // aliased
                const int distance = dstIndex - srcIndex;
                if (distance >= numElements) {
                    memcpyCircular(d_array_p,
                                   d_size,
                                   (d + dstIndex) % d_size,
                                   d_array_p,
                                   d_size,
                                   (d + srcIndex) % d_size,
                                   numElements);
                }
                else {
                    memcpyCircular(d_array_p,
                                   d_size,
                                   (d + dstIndex) % d_size,
                                   d_array_p,
                                   d_size,
                                   (d + srcIndex) % d_size,
                                   distance);
                    memcpyCircular(d_array_p,
                                   d_size,
                                   (d + dstIndex + distance) % d_size,
                                   d_array_p,
                                   d_size,
                                   (d_front + 1 + dstIndex) % d_size,
                                   numElements - distance);
                }
            }
            d_front = (d_front - numElements + d_size) % d_size;
        }
        else {

            // We will shift 'backLen' elements to the right.

            // Destination index is as close or closer to the back as to the
            // front.

            const int s = (d_front + 1 + dstIndex) % d_size;
            memShiftRight(d_array_p,
                          d_size,
                          (s + numElements) % d_size,
                          s,
                          backLen);

            if (this != &srcQueue ||
                           srcIndex + numElements <= dstIndex) { // not aliased
                memcpyCircular(d_array_p,
                               d_size,
                               s,
                               srcQueue.d_array_p,
                               srcQueue.d_size,
                               (srcQueue.d_front + 1 + srcIndex) %
                                                               srcQueue.d_size,
                               numElements);
            }
            else { // aliased
                if (dstIndex <= srcIndex) {
                    memcpyCircular(d_array_p,
                                   d_size,
                                   s,
                                   d_array_p,
                                   d_size,
                                   (d_front + 1 + srcIndex + numElements) %
                                                                        d_size,
                                   numElements);
                }
                else {
                    const int distance = dstIndex - srcIndex;
                    memcpyCircular(d_array_p,
                                   d_size,
                                   s,
                                   d_array_p,
                                   d_size,
                                   (d_front + 1 + srcIndex) % d_size,
                                   distance);
                    memcpyCircular(d_array_p,
                                   d_size,
                                   (s + distance) % d_size,
                                   d_array_p,
                                   d_size,
                                   (d_front + 1 + srcIndex + distance +
                                                         numElements) % d_size,
                                   numElements - distance);
                }
            }
            d_back = (d_back + numElements) % d_size;
        }
    }
}

template <class T>
inline
void Queue<T>::insert(int dstIndex, const Queue& srcQueue)
{
    insert(dstIndex, srcQueue, 0, srcQueue.length());
}

template <class T>
inline
void Queue<T>::popBack()
{
    d_back = (d_back - 1 + d_size) % d_size;
    d_array_p[d_back].~T();
}

template <class T>
inline
void Queue<T>::popFront()
{
    d_front = (d_front + 1) % d_size;
    d_array_p[d_front].~T();
}

template <class T>
void Queue<T>::pushBack(const T& item)
{
    T itemCopy(item);  // TBD aliasing hack

    int newBack = (d_back + 1) % d_size;
    if (d_front == newBack) {
        increaseSize();  // NOTE: this can change the value of d_back
        newBack = (d_back + 1) % d_size;
    }
    new (&d_array_p[d_back]) T(itemCopy);
    d_back = newBack;
}

template <class T>
void Queue<T>::pushFront(const T& item)
{
    T itemCopy(item);  // TBD aliasing hack

    int newFront = (d_front - 1 + d_size) % d_size;
    if (newFront == d_back) {
        increaseSize();  // NOTE: this can change the value of d_front
        newFront = (d_front - 1 + d_size) % d_size;
    }
    new (&d_array_p[d_front]) T(itemCopy);
    d_front = newFront;
}

template <class T>
inline
void Queue<T>::append(const T& item)
{
    pushBack(item);
}

template <class T>
void Queue<T>::remove(int index)
{
    d_array_p[(index + d_front + 1) % d_size].~T();

    // Compute number of elements that are past the insertion point: the back
    // length.

    const int backLen =
               (d_back - d_front - k_EXTRA_CAPACITY - index + d_size) % d_size;

    if (index < backLen) {
        d_front = (d_front + 1) % d_size;
        memShiftRight(d_array_p,
                      d_size,
                      (d_front + 1) % d_size,
                      d_front,
                      index);
    }
    else {
        const int d = (d_front + 1 + index) % d_size;
        memShiftLeft(d_array_p,
                     d_size,
                     d,
                     (d + 1) % d_size,
                     (d_back + d_size - d_front - 1) % d_size - 1 - index);
        d_back = (d_back - 1 + d_size) % d_size;
    }
}

template <class T>
void Queue<T>::remove(int index, int numElements)
{
    // TBD efficiency

    for (int i = 0; i < numElements; ++i) {
        d_array_p[(index + d_front + 1 + i) % d_size].~T();
    }

    // Compute number of elements that are past the insertion point: the back
    // length.

    const int backLen = (d_back - d_front - 1
                                      - index - numElements + d_size) % d_size;
    if (index < backLen) {
        const int dst = (d_front + 1 + numElements) % d_size;
        const int src = (d_front + 1) % d_size;

        memShiftRight(d_array_p, d_size, dst, src, index);
        d_front = (d_front + numElements) % d_size;
    }
    else {
        const int dst = (d_front + 1 + index) % d_size;
        const int src = (dst + numElements) % d_size;

        memShiftLeft(d_array_p,
                     d_size,
                     dst,
                     src,
                     (d_back + d_size - d_front - 1) % d_size -
                                                          numElements - index);
        d_back = (d_back - numElements + d_size) % d_size;
    }
}

template <class T>
void Queue<T>::removeAll(bsl::vector<T> *buffer)
{
    d_front = (d_front + 1) % d_size;

    // TBD efficiency

    if (buffer) {
        while (d_back != d_front) {
            buffer->push_back(d_array_p[d_front]);
            d_array_p[d_front].~T();
            d_front = (d_front + 1) % d_size;
        }
    } else {
        while (d_back != d_front) {
            d_array_p[d_front].~T();
            d_front = (d_front + 1) % d_size;
        }
    }
    d_front = (d_back - 1 + d_size) % d_size;
}

template <class T>
void Queue<T>::replace(int dstIndex, const T& item)
{
    T itemCopy(item);  // TBD hack for aliased case

    // TBD efficiency

    d_array_p[(d_front + 1 + dstIndex) % d_size].~T();
    new (&d_array_p[(d_front + 1 + dstIndex) % d_size]) T(itemCopy);
}

template <class T>
void Queue<T>::replace(int          dstIndex,
                       const Queue& srcQueue,
                       int          srcIndex,
                       int          numElements)
{
    // TBD need placement new

    if (this != &srcQueue || srcIndex + numElements <= dstIndex ||
                          dstIndex + numElements <= srcIndex) {  // not aliased
        memcpyCircular(d_array_p,
                       d_size,
                       (d_front + 1 + dstIndex) % d_size,
                       srcQueue.d_array_p,
                       srcQueue.d_size,
                       (srcQueue.d_front + 1 + srcIndex) % srcQueue.d_size,
                       numElements);
    }
    else {  // aliased; do nothing if srcIndex == dstIndex
        if (srcIndex < dstIndex) {
            memShiftRight(d_array_p,
                          d_size,
                          (d_front + 1 + dstIndex) % d_size,
                          (d_front + 1 + srcIndex) % d_size,
                          numElements);
        }
        else if (srcIndex > dstIndex) {
            memShiftLeft(d_array_p,
                         d_size,
                         (d_front + 1 + dstIndex) % d_size,
                         (d_front + 1 + srcIndex) % d_size,
                         numElements);
        }
    }
}

template <class T>
void Queue<T>::reserveCapacity(int numElements)
{
    const int newSize = calculateSufficientSize(numElements, d_size);
    if (d_size < newSize) {
        d_size = increaseSizeImp(&d_array_p,
                                 &d_front,
                                 &d_back,
                                 newSize,
                                 d_size,
                                 d_allocator_p);

        // To improve testability, all empty queues have canonical front and
        // back values.

        if (0 == length()) {
            d_front = d_size - 1;
            d_back = 0;
        }
    }
}

template <class T>
void Queue<T>::reserveCapacityRaw(int numElements)
{
    const int newSize = numElements + k_EXTRA_CAPACITY;
                                            // to hold the front/back positions

    if (d_size < newSize) {
        d_size = increaseSizeImp(&d_array_p,
                                 &d_front,
                                 &d_back,
                                 newSize,
                                 d_size,
                                 d_allocator_p);
    }
}

template <class T>
void Queue<T>::setLength(int newLength)
{
    const int newSize = newLength + k_EXTRA_CAPACITY;
                                            // to hold the front/back positions

    if (d_size < newSize) {
        d_size = increaseSizeImp(&d_array_p,
                                 &d_front,
                                 &d_back,
                                 newSize,
                                 d_size,
                                 d_allocator_p);
    }
    const int oldBack = d_back;
    const int oldLength = length();
    d_back = (d_front + 1 + newLength) % d_size;
    if (newLength > oldLength) {
        if (oldBack < d_back) {
            // TBD efficiency

            for (int i = 0; i < d_back - oldBack; ++i) {
                new (d_array_p + oldBack + i) T();
            }
        }
        else {
            // TBD efficiency

            for (int i = 0; i < d_size - oldBack; ++i) {
                new (d_array_p + oldBack + i) T();
            }

            // TBD efficiency

            for (int i = 0; i < d_back; ++i) {
                new (d_array_p + i) T();
            }
        }
    }
}

template <class T>
void Queue<T>::setLength(int newLength, const T& initialValue)
{
    const int newSize = newLength + k_EXTRA_CAPACITY;
                                                 // to hold the empty positions

    if (d_size < newSize) {
        d_size = increaseSizeImp(&d_array_p,
                                 &d_front,
                                 &d_back,
                                 newSize,
                                 d_size,
                                 d_allocator_p);
    }
    const int oldBack = d_back;
    const int oldLength = length();
    d_back = (d_front + 1 + newLength) % d_size;
    if (newLength > oldLength) {
        if (oldBack < d_back) {
            // TBD efficiency

            for (int i = 0; i < d_back - oldBack; ++i) {
                new (d_array_p + oldBack + i) T(initialValue);
            }
        }
        else {
            // TBD efficiency

            for (int i = 0; i < d_size - oldBack; ++i) {
                new (d_array_p + oldBack + i) T(initialValue);
            }
            // TBD efficiency

            for (int i = 0; i < d_back; ++i) {
                new (d_array_p + i) T(initialValue);
            }
        }
    }
}

template <class T>
void Queue<T>::setLengthRaw(int newLength)
{
    const int newSize = newLength + k_EXTRA_CAPACITY;
                                                 // to hold the empty positions

    if (d_size < newSize) {
        d_size = increaseSizeImp(&d_array_p,
                                 &d_front,
                                 &d_back,
                                 newSize,
                                 d_size,
                                 d_allocator_p);
    }
    d_back = (d_front + 1 + newLength) % d_size;
}

template <class T>
template <class STREAM>
STREAM& Queue<T>::bdexStreamIn(STREAM& stream, int version)
{
    if (stream) {
        switch (version) { // switch on the schema version
          case 1: {
            int newLength;
            stream.getLength(newLength);

            if (stream) {
                int newSize = calculateSufficientSize(newLength, d_size);
                if (d_size < newSize) {
                    d_size = increaseSizeImp(&d_array_p,
                                             &d_front,
                                             &d_back,
                                             newSize,
                                             d_size,
                                             d_allocator_p);
                }
                d_front = d_size - 1;
                d_back = newLength;
                for (int i = 0; i < newLength && stream; ++i) {
                    bslx::InStreamFunctions::bdexStreamIn(
                                                  stream, (*this)[i], version);
                }
            }
          } break;
          default: {
            stream.invalidate();  // unrecognized version number
          }
        }
    }
    return stream;
}

template <class T>
void Queue<T>::swap(int index1, int index2)
{
    if (index1 != index2) {
        const int tmp = d_front + 1;
        const int i1 = (tmp + index1) % d_size;
        const int i2 = (tmp + index2) % d_size;

        T temp(d_array_p[i1]);
        d_array_p[i1].~T();
        new (d_array_p + i1) T(d_array_p[i2]);
        d_array_p[i2].~T();
        new (d_array_p + i2) T(temp);
    }
}

// ACCESSORS
template <class T>
inline
const T& Queue<T>::operator[](int index) const
{
    return d_array_p[(index + d_front + 1) % d_size];
}

template <class T>
inline
const T& Queue<T>::back() const
{
    return d_array_p[(d_back - 1 + d_size) % d_size];
}

template <class T>
inline
const T& Queue<T>::front() const
{
    return d_array_p[(d_front + 1) % d_size];
}

template <class T>
bsl::ostream& Queue<T>::print(bsl::ostream& stream,
                                    int           level,
                                    int           spacesPerLevel) const
{
    if (level < 0) {
        level = -level;
    }
    else {
        bdlb::Print::indent(stream, level, spacesPerLevel);
    }

    int levelPlus1 = level + 1;
    if (0 <= spacesPerLevel) {

        stream << "[\n";

        const int len = length();
        for (int i = 0; i < len; ++i) {
            bdlb::Print::indent(stream, levelPlus1, spacesPerLevel);
            stream << d_array_p[(i + d_front + 1) % d_size] << '\n';
        }

        bdlb::Print::indent(stream, level, spacesPerLevel);
        stream << "]\n";
    }
    else {
        stream << "[ ";

        const int len = length();
        for (int i = 0; i < len; ++i) {
            stream << ' ';
            stream << d_array_p[(i + d_front + 1) % d_size];
        }

        stream << " ] ";
    }
    return stream << bsl::flush;
}

template <class T>
template <class STREAM>
STREAM& Queue<T>::bdexStreamOut(STREAM& stream, int version) const
{
    if (stream) {
        switch (version) { // switch on the schema version
          case 1: {
            const int len = length();
            stream.putLength(len);
            for (int i = 0; i < len && stream; ++i) {
                bslx::OutStreamFunctions::bdexStreamOut(
                                                  stream, (*this)[i], version);
            }
          } break;
          default: {
            stream.invalidate();  // unrecognized version number
          }
        }
    }
    return stream;
}

}  // close package namespace

// FREE OPERATORS
template <class T>
bool bdlc::operator==(const Queue<T>& lhs, const Queue<T>& rhs)
{
    const int len = lhs.length();
    if (rhs.length() != len) {
        return 0;                                                     // RETURN
    }

    // Lengths are equal.

    for (int i = 0; i < len; ++i) {
        if (!(lhs[i] == rhs[i])) {
            return 0;                                                 // RETURN
        }
    }
    return 1;
}

template <class T>
inline
bool bdlc::operator!=(const Queue<T>& lhs, const Queue<T>& rhs)
{
    return !(lhs == rhs);
}

template <class T>
inline
bsl::ostream& bdlc::operator<<(bsl::ostream& stream, const Queue<T>& queue)
{
    return queue.streamOut(stream);
}

}  // close enterprise namespace

#endif

// ----------------------------------------------------------------------------
// Copyright 2018 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 ----------------------------------