bdlc_compactedarray.h

Go to the documentation of this file.

/// @file bdlc_compactedarray.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bdlc_compactedarray.h                                              -*-C++-*-
#ifndef INCLUDED_BDLC_COMPACTEDARRAY
#define INCLUDED_BDLC_COMPACTEDARRAY
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bdlc_compactedarray bdlc_compactedarray
/// @brief  Provide a compacted array of `const` user-defined objects.
/// @addtogroup bdl
/// @{
/// @addtogroup bdlc
/// @{
/// @addtogroup bdlc_compactedarray
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bdlc_compactedarray-purpose"> Purpose</a>
/// * <a href="#bdlc_compactedarray-classes"> Classes </a>
/// * <a href="#bdlc_compactedarray-description"> Description </a>
///   * <a href="#bdlc_compactedarray-usage"> Usage </a>
///     * <a href="#bdlc_compactedarray-example-1-storing-daily-schedules"> Example 1: Storing Daily Schedules </a>
///
/// # Purpose {#bdlc_compactedarray-purpose}
/// Provide a compacted array of `const` user-defined objects.
///
/// # Classes {#bdlc_compactedarray-classes}
///
/// -  bdlc::CompactedArray: compacted array of user-defined objects
///
/// # Description {#bdlc_compactedarray-description}
/// This component provides a space-efficient value-semantic array,
/// `bdlc::CompactedArray`, and an associated iterator,
/// `bdlc::CompactedArray::const_iterator`, that provides non-modifiable access
/// to its elements.  The interface of this class provides the user with
/// functionality similar to a `bsl::vector<T>`.  The implementation is designed
/// to reduce dynamic memory usage by (1) removing data duplication at the
/// expense of an additional indirection to obtain the stored objects (using the
/// flyweight design pattern) and (2) requiring `operator<` to be defined for
/// the type of the stored objects.  The array supports primitive operations
/// (e.g., insertion, look-up, removal), as well as a complete set of
/// value-semantic operations; however, modifiable reference to individual
/// elements is not available.  Users can access the (non-modifiable) value of
/// individual elements by calling the indexing operator or via iterators.
///
/// ## Usage {#bdlc_compactedarray-usage}
///
///
/// This section illustrates intended use of this component.
///
/// ### Example 1: Storing Daily Schedules {#bdlc_compactedarray-example-1-storing-daily-schedules}
///
///
/// Suppose we are creating a sequence of daily schedules for an employee.  Most
/// Mondays (and Tuesdays, Wednesdays, etc.) will have the same schedule,
/// although some may differ.  Instead of storing this data in a
/// `bsl::vector<my_DailySchedule>`, we can use
/// `bdlc::CompactedArray<my_DailySchedule>` to efficiently store this data.
///
/// First, we declare and define a `my_DailySchedule` class.  This class is not
/// overly relevant to the example and is elided for the sake of brevity:
/// @code
///                         // ================
///                         // my_DailySchedule
///                         // ================
///
/// class my_DailySchedule {
///     // A value-semantic class that provides a daily schedule and consumes a
///     // significant amount of memory.
///
///     int d_initialLocationId;
///
///     // ...
///
///     // FRIENDS
///     friend bool operator<(const my_DailySchedule&,
///                           const my_DailySchedule&);
///
///   public:
///     // CREATORS
///     my_DailySchedule(int               initialLocationId,
///                      bslma::Allocator *basicAllocator = 0);
///         // Create a 'my_DailySchedule' object having the specified
///         // 'initialLocationId'.  Optionally specify a 'basicAllocator' used
///         // to supply memory.  If 'basicAllocator' is 0, the currently
///         // installed default allocator is used.
///
///     // ...
///
/// };
///
/// bool operator<(const my_DailySchedule& lhs, const my_DailySchedule& rhs);
///     // Return 'true' if the specified 'lhs' is lexicographically less than
///     // the specified 'rhs' object, and 'false' otherwise.
///
///                          // ----------------
///                          // my_DailySchedule
///                          // ----------------
///
/// // CREATORS
/// inline
/// my_DailySchedule::my_DailySchedule(int               initialLocationId,
///                                    bslma::Allocator *basicAllocator)
/// : d_initialLocationId(initialLocationId)
/// {
///     (void)basicAllocator;  // suppress unused variable compiler warning
///
///     // ...
/// }
///
/// bool operator<(const my_DailySchedule& lhs, const my_DailySchedule& rhs)
/// {
///     if (lhs.d_initialLocationId < rhs.d_initialLocationId) {
///         return true;                                              // RETURN
///     }
///
///     // ...
///
///     return false;
/// }
/// @endcode
/// Then, we create our schedule, which is an array of `my_DailySchedule` where
/// the index of each element is the date offset (from an arbitrary epoch
/// measured in days).
/// @code
/// bdlc::CompactedArray<my_DailySchedule> schedule;
/// @endcode
/// Now, we create some daily schedules and append them to the `schedule`:
/// @code
/// my_DailySchedule evenDays(0);
/// my_DailySchedule oddDays(1);
///
/// // Population of the 'my_DailySchedule' objects is elided.
///
/// schedule.push_back(evenDays);
/// schedule.push_back(oddDays);
/// schedule.push_back(evenDays);
/// schedule.push_back(oddDays);
/// schedule.push_back(evenDays);
/// @endcode
/// Finally, we verify that the storage is compacted:
/// @code
/// assert(5 == schedule.length());
/// assert(2 == schedule.uniqueLength());
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bdl
 * @{
 */
/** @addtogroup bdlc
 * @{
 */
/** @addtogroup bdlc_compactedarray
 * @{
 */
 
#include <bdlscm_version.h>
 
#include <bdlc_packedintarray.h>
 
#include <bdlb_algorithmworkaroundutil.h>
#include <bslalg_swaputil.h>
 
#include <bslh_hash.h>
 
#include <bslim_printer.h>
 
#include <bslma_allocator.h>
#include <bslma_constructionutil.h>
#include <bslma_usesbslmaallocator.h>
 
#include <bsls_assert.h>
#include <bsls_objectbuffer.h>
#include <bsls_review.h>
 
#include <bsl_algorithm.h>
#include <bsl_cstddef.h>
#include <bsl_iosfwd.h>
#include <bsl_iterator.h>
#include <bsl_limits.h>
#include <bsl_vector.h>
 
 
namespace bdlc {
 
// FORWARD DECLARATIONS
template <class TYPE> class CompactedArray;
 
template <class TYPE> class CompactedArray_ConstIterator;
 
template <class TYPE> CompactedArray_ConstIterator<TYPE>
                          operator++(CompactedArray_ConstIterator<TYPE>&, int);
 
template <class TYPE> CompactedArray_ConstIterator<TYPE>
                          operator--(CompactedArray_ConstIterator<TYPE>&, int);
 
template <class TYPE>
CompactedArray_ConstIterator<TYPE> operator+(
                                     const CompactedArray_ConstIterator<TYPE>&,
                                     bsl::ptrdiff_t);
 
template <class TYPE>
CompactedArray_ConstIterator<TYPE> operator-(
                                     const CompactedArray_ConstIterator<TYPE>&,
                                     bsl::ptrdiff_t);
 
template <class TYPE>
bsl::ptrdiff_t operator-(const CompactedArray_ConstIterator<TYPE>&,
                         const CompactedArray_ConstIterator<TYPE>&);
 
template <class TYPE>
bool operator==(const CompactedArray_ConstIterator<TYPE>&,
                const CompactedArray_ConstIterator<TYPE>&);
 
template <class TYPE>
bool operator!=(const CompactedArray_ConstIterator<TYPE>&,
                const CompactedArray_ConstIterator<TYPE>&);
 
template <class TYPE>
bool operator<(const CompactedArray_ConstIterator<TYPE>&,
               const CompactedArray_ConstIterator<TYPE>&);
 
template <class TYPE>
bool operator<=(const CompactedArray_ConstIterator<TYPE>&,
                const CompactedArray_ConstIterator<TYPE>&);
 
template <class TYPE>
bool operator>(const CompactedArray_ConstIterator<TYPE>&,
               const CompactedArray_ConstIterator<TYPE>&);
 
template <class TYPE>
bool operator>=(const CompactedArray_ConstIterator<TYPE>&,
                const CompactedArray_ConstIterator<TYPE>&);
 
                  // =====================================
                  // class CompactedArray_RemoveAllProctor
                  // =====================================
 
/// This class implements a proctor that, unless its `release` method has
/// previously been invoked, automatically invokes `removeAll` on a
/// `CompactedArray` upon destruction.
///
/// See @ref bdlc_compactedarray 
template <class TYPE>
class CompactedArray_RemoveAllProctor {
 
    // DATA
    CompactedArray<TYPE> *d_array_p;  // managed array
 
    // NOT IMPLEMENTED
    CompactedArray_RemoveAllProctor();
    CompactedArray_RemoveAllProctor(const CompactedArray_RemoveAllProctor&);
    CompactedArray_RemoveAllProctor& operator=(
                                       const CompactedArray_RemoveAllProctor&);
 
  public:
    // CREATORS
 
    /// Create a `removeAll` proctor that conditionally manages the
    /// specified `array` (if non-zero).
    CompactedArray_RemoveAllProctor(CompactedArray<TYPE> *array);
 
    /// Destroy this object and, if `release` has not been invoked, invoke
    /// the managed array's `removeAll` method.
    ~CompactedArray_RemoveAllProctor();
 
    // MANIPULATORS
 
    /// Release from management the array currently managed by this proctor.
    /// If no array, this method has no effect.
    void release();
};
 
                    // ==================================
                    // struct CompactedArray_CountedValue
                    // ==================================
 
/// This `struct` represents a reference-counted value.  Note that
/// comparison of `d_count` is intentionally omitted from the free
/// equality-comparison operators of this class.
template <class TYPE>
struct CompactedArray_CountedValue {
 
    // PUBLIC DATA
    bsls::ObjectBuffer<TYPE> d_value;  // footprint of stored object
    bsl::size_t              d_count;  // reference count of the stored object
 
    // CREATORS
 
    /// Create a `CompactedArray_CountedValue` having the specified `value`
    /// and reference `count`.  The specified `basicAllocator` is used to
    /// supply memory.  The behavior is undefined unless
    /// `0 != basicAllocator`.
    CompactedArray_CountedValue(const TYPE&       value,
                                bsl::size_t       count,
                                bslma::Allocator *basicAllocator);
 
    /// Create a `CompactedArray_CountedValue` having the same underlying
    /// object value and reference count as the specified `original` object.
    /// The specified `basicAllocator` is used to supply memory.  The
    /// behavior is undefined unless `0 != basicAllocator`.
    CompactedArray_CountedValue(
                     const CompactedArray_CountedValue<TYPE>&  original,
                     bslma::Allocator                         *basicAllocator);
 
    /// Destroy this object.
    ~CompactedArray_CountedValue();
 
    // MANIPULATORS
 
    /// Assign to this object the underlying object value and reference
    /// count of the specified `rhs` object, and return a reference
    /// providing modifiable access to this object.
    CompactedArray_CountedValue& operator=(
                                 const CompactedArray_CountedValue<TYPE>& rhs);
};
 
// FREE OPERATORS
 
/// Return `true` if the underlying object value of the specified `lhs` is
/// the same as the underlying object value of the specified `rhs`, and
/// `false` otherwise.  Note that the reference counts are intentionally
/// ignored.
template <class TYPE>
bool operator==(const CompactedArray_CountedValue<TYPE>& lhs,
                const CompactedArray_CountedValue<TYPE>& rhs);
 
/// Return `true` if the underlying object value of the specified `lhs` is
/// not the same as the underlying object value of the specified `rhs`, and
/// `false` otherwise.  Note that the reference counts are intentionally
/// ignored.
template <class TYPE>
bool operator!=(const CompactedArray_CountedValue<TYPE>& lhs,
                const CompactedArray_CountedValue<TYPE>& rhs);
 
/// Return `true` if the underlying object value of the specified `lhs` is
/// less than the value of the specified `rhs`, and `false` otherwise.  Note
/// that the reference count is intentionally ignored.
template <class TYPE>
bool operator<(const CompactedArray_CountedValue<TYPE>& lhs, const TYPE& rhs);
 
/// Return `true` if the value of the specified `lhs` is less than the
/// underlying object value of the specified `rhs`, and `false` otherwise.
/// Note that the reference count is intentionally ignored.
template <class TYPE>
bool operator<(const TYPE& lhs, const CompactedArray_CountedValue<TYPE>& rhs);
 
                    // ==================================
                    // class CompactedArray_ConstIterator
                    // ==================================
 
/// This value-semantic class represents a random access iterator providing
/// non-modifiable access to the elements of a `CompactedArray`.  This class
/// provides all functionality of a random access iterator, as defined by
/// the standard, but is *not* compatible with most standard methods
/// requiring a bidirectional `const_iterator`.
///
/// This class does not perform any bounds checking.  Any iterator, `it`,
/// referencing a `CompactedArray` `array`, remains valid while
/// `0 <= it - array.begin() < array.length()`.
///
/// See @ref bdlc_compactedarray 
template <class TYPE>
class CompactedArray_ConstIterator {
 
    // DATA
    const CompactedArray<TYPE> *d_array_p;  // 'CompactedArray' referenced by
                                            // this iterator, or 0 if default
                                            // value
 
    bsl::size_t                 d_index;    // index of the referenced element,
                                            // or one past the end of
                                            // 'd_array_p'
 
    // FRIENDS
    friend class CompactedArray<TYPE>;
 
    friend CompactedArray_ConstIterator
                              operator++<>(CompactedArray_ConstIterator&, int);
 
    friend CompactedArray_ConstIterator
                              operator--<>(CompactedArray_ConstIterator&, int);
 
    friend bool operator==<>(const CompactedArray_ConstIterator&,
                             const CompactedArray_ConstIterator&);
 
    friend bool operator!=<>(const CompactedArray_ConstIterator&,
                             const CompactedArray_ConstIterator&);
 
    friend CompactedArray_ConstIterator<TYPE> operator+<>(
                                     const CompactedArray_ConstIterator<TYPE>&,
                                     bsl::ptrdiff_t);
 
    friend CompactedArray_ConstIterator<TYPE> operator-<>(
                                     const CompactedArray_ConstIterator<TYPE>&,
                                     bsl::ptrdiff_t);
 
    friend bsl::ptrdiff_t operator-<>(const CompactedArray_ConstIterator&,
                                      const CompactedArray_ConstIterator&);
 
    friend bool operator< <>(const CompactedArray_ConstIterator&,
                             const CompactedArray_ConstIterator&);
 
    friend bool operator<=<>(const CompactedArray_ConstIterator&,
                             const CompactedArray_ConstIterator&);
 
    friend bool operator><>(const CompactedArray_ConstIterator&,
                            const CompactedArray_ConstIterator&);
 
    friend bool operator>=<>(const CompactedArray_ConstIterator&,
                             const CompactedArray_ConstIterator&);
 
  public:
    // PUBLIC TYPES
 
    // The following 'typedef's define the traits for this iterator to make it
    // compatible with standard functions.
 
    typedef bsl::ptrdiff_t  difference_type;  // The type used for the distance
                                              // between two iterators.
 
    typedef bsl::size_t     size_type;        // The type used for any function
                                              // requiring a length (i.e,
                                              // index).
 
    typedef TYPE            value_type;       // The type for elements.
 
    typedef TYPE           *pointer;          // The type of an arbitrary
                                              // pointer into the array.
 
    typedef TYPE&           reference;        // The type for element
                                              // references.
 
    typedef std::random_access_iterator_tag iterator_category;
                                              // This is a random access
                                              // iterator.
 
  private:
    // PRIVATE CREATORS
 
    /// Create a `CompactedArray_ConstIterator` object that refers to the
    /// element at the specified `index` in the specified `array`, or the
    /// past-the-end iterator for `array` if `index == array->length()`.
    /// The behavior is undefined unless `index <= array->length()`.
    CompactedArray_ConstIterator(const CompactedArray<TYPE> *array,
                                 bsl::size_t                 index);
 
  public:
    // CREATORS
 
    /// Create a default `CompactedArray_ConstIterator`.  Note that the
    /// behavior of most methods is undefined when used on a
    /// default-constructed iterator.
    CompactedArray_ConstIterator();
 
    /// Create a `CompactedArray_ConstIterator` having the same value as the
    /// specified `original` object.
    CompactedArray_ConstIterator(const CompactedArray_ConstIterator& original);
 
     ~CompactedArray_ConstIterator() = default;
        // Destroy this object.
 
    // MANIPULATORS
 
    /// Assign to this iterator the value of the specified `rhs` iterator,
    /// and return a reference providing modifiable access to this iterator.
    CompactedArray_ConstIterator&
                             operator=(
                                      const CompactedArray_ConstIterator& rhs);
 
    /// Advance this iterator by the specified `offset` from the location
    /// referenced by this iterator, and return a reference providing
    /// modifiable access to this iterator.  The returned iterator, `it`,
    /// referencing a `CompactedArray` `array`, remains valid as long as
    /// `0 <= it - array.begin() <= array.length()`.  The behavior is
    /// undefined unless `CompactedArray_ConstIterator() != *this` and
    /// `0 <= *this - array.begin() + offset <= array.length()`.
    CompactedArray_ConstIterator& operator+=(bsl::ptrdiff_t offset);
 
    /// Decrement this iterator by the specified `offset` from the location
    /// referenced by this iterator, and return a reference providing
    /// modifiable access to this iterator.  The returned iterator, `it`,
    /// referencing a `CompactedArray` `array`, remains valid as long as
    /// `0 <= it - array.begin() <= array.length()`.  The behavior is
    /// undefined unless `CompactedArray_ConstIterator() != *this` and
    /// `0 <= *this - array.begin() - offset <= array.length()`.
    CompactedArray_ConstIterator& operator-=(bsl::ptrdiff_t offset);
 
    /// Advance this iterator to refer to the next location in the
    /// referenced array, and return a reference to this iterator *after*
    /// the advancement.  The returned iterator, `it`, referencing a
    /// `CompactedArray` `array`, remains valid as long as
    /// `0 <= it - array.begin() <= array.length()`.  The behavior is
    /// undefined unless, on entry,
    /// `CompactedArray_ConstIterator() != *this` and
    /// `*this - array.begin() < array.length()`.
    CompactedArray_ConstIterator& operator++();
 
    /// Decrement this iterator to refer to the previous location in the
    /// referenced array, and return a reference to this iterator *after*
    /// the decrementation.  The returned iterator, `it`, referencing a
    /// `CompactedArray` `array`, remains valid as long as
    /// `0 <= it - array.begin() <= array.length()`.  The behavior is
    /// undefined unless, on entry,
    /// `CompactedArray_ConstIterator() != *this` and
    /// `0 < *this - array.begin()`.
    CompactedArray_ConstIterator& operator--();
 
    // ACCESSORS
 
    /// Return a `const` reference to the element referenced by this
    /// iterator.  The behavior is undefined unless for this iterator,
    /// referencing a `CompactedArray` `array`,
    /// `CompactedArray_ConstIterator() != *this` and
    /// `*this - array.begin() < array.length()`.
    const TYPE& operator*() const;
 
    /// Return a `const` reference to the element referenced by this
    /// iterator.  The behavior is undefined unless for this iterator,
    /// referencing a `CompactedArray` `array`,
    /// `CompactedArray_ConstIterator() != *this` and
    /// `*this - array.begin() < array.length()`.
    const TYPE& operator->() const;
 
    /// Return a `const` reference to the element at the specified `offset`
    /// from the location referenced by this iterator.  The behavior is
    /// undefined unless for this iterator, referencing a `CompactedArray`
    /// `array`, `CompactedArray_ConstIterator() != *this` and
    /// `0 <= *this - array.begin() + offset < array.length()`.
    const TYPE& operator[](bsl::ptrdiff_t offset) const;
};
 
// FREE OPERATORS
 
/// Advance the specified `iterator` to refer to the next location in the
/// referenced array, and return an iterator referring to the original
/// location (*before* the advancement).  The returned iterator, `it`,
/// referencing a `CompactedArray` `array`, remains valid as long as
/// `0 <= it - array.begin() <= array.length()`.  The behavior is undefined
/// unless, on entry, `CompactedArray_ConstIterator() != iterator` and
/// `iterator - array.begin() < array.length()`.
template <class TYPE>
CompactedArray_ConstIterator<TYPE>
                       operator++(CompactedArray_ConstIterator<TYPE>& iterator,
                                  int);
 
/// Decrement the specified `iterator` to refer to the previous location in
/// the referenced array, and return an iterator referring to the original
/// location (*before* the decrementation).  The returned iterator, `it`,
/// referencing a `CompactedArray` `array`, remains valid as long as
/// `0 <= it - array.begin() <= array.length()`.  The behavior is undefined
/// unless, on entry, `CompactedArray_ConstIterator() != iterator` and
/// `0 < iterator - array.begin()`.
template <class TYPE>
CompactedArray_ConstIterator<TYPE>
                       operator--(CompactedArray_ConstIterator<TYPE>& iterator,
                                  int);
 
/// Return an iterator referencing the location at the specified `offset`
/// from the location referenced by the specified `iterator`.  The returned
/// iterator, `it`, referencing a `CompactedArray` `array`, remains valid as
/// long as `0 <= it - array.begin() <= array.length()`.  The behavior is
/// undefined unless `CompactedArray_ConstIterator() != iterator` and
/// `0 <= iterator - array.begin() + offset <= array.length()`.
template <class TYPE>
CompactedArray_ConstIterator<TYPE> operator+(
                           const CompactedArray_ConstIterator<TYPE>& iterator,
                           bsl::ptrdiff_t                            offset);
template <class TYPE>
CompactedArray_ConstIterator<TYPE> operator+(
                           bsl::ptrdiff_t                            offset,
                           const CompactedArray_ConstIterator<TYPE>& iterator);
 
/// Return an iterator referencing the location at the specified `offset`
/// from the location referenced by the specified `iterator`.  The returned
/// iterator, `it`, referencing a `CompactedArray` `array`, remains valid as
/// long as `0 <= it - array.begin() <= array.length()`.  The behavior is
/// undefined unless `CompactedArray_ConstIterator() != iterator` and
/// `0 <= iterator - array.begin() - offset <= array.length()`.
template <class TYPE>
CompactedArray_ConstIterator<TYPE> operator-(
                            const CompactedArray_ConstIterator<TYPE>& iterator,
                            bsl::ptrdiff_t                            offset);
 
/// Return the number of elements between the specified `lhs` and `rhs` as a
/// signed value.  The behavior is undefined unless `lhs` and `rhs`
/// reference the same array.  Note that the return value is positive when a
/// positive number of `rhs++` invocations would result in `lhs == rhs`, and
/// negative when a positive number of `rhs--` invocations would result in
/// `lhs == rhs`.
template <class TYPE>
bsl::ptrdiff_t operator-(const CompactedArray_ConstIterator<TYPE>& lhs,
                         const CompactedArray_ConstIterator<TYPE>& rhs);
 
/// Return `true` if the specified `lhs` and `rhs` iterators have the same
/// value, and `false` otherwise.  Two `CompactedArray_ConstIterator`
/// iterators have the same value if they both have the default value, or
/// neither has the default value and they reference the same location in
/// the same array.
template <class TYPE>
bool operator==(const CompactedArray_ConstIterator<TYPE>& lhs,
                const CompactedArray_ConstIterator<TYPE>& rhs);
 
/// Return `true` if the specified `lhs` and `rhs` iterators do not have the
/// same value, and `false` otherwise.  Two `CompactedArray_ConstIterator`
/// iterators do not have the same value if one has the default value and
/// the other does not, or neither has the default value and they do not
/// reference the same location in the same array.
template <class TYPE>
bool operator!=(const CompactedArray_ConstIterator<TYPE>& lhs,
                const CompactedArray_ConstIterator<TYPE>& rhs);
 
/// Return `true` if the specified `lhs` has a value less than the specified
/// `rhs`, and `false` otherwise.  Iterator `lhs` has a value less than
/// iterator `rhs` if `0 < rhs - lhs` (see `operator-`).  The behavior is
/// undefined unless `lhs` and `rhs` refer to the same array.
template <class TYPE>
bool operator<(const CompactedArray_ConstIterator<TYPE>& lhs,
               const CompactedArray_ConstIterator<TYPE>& rhs);
 
/// Return `true` if the specified `lhs` has a value less than or equal to
/// the specified `rhs, and `false' otherwise.  Iterator `lhs` has a value
/// less than or equal to iterator `rhs` if `0 <= rhs - lhs` (see
/// `operator-`).  The behavior is undefined unless `lhs` and `rhs` refer to
/// the same array.
template <class TYPE>
bool operator<=(const CompactedArray_ConstIterator<TYPE>& lhs,
                const CompactedArray_ConstIterator<TYPE>& rhs);
 
/// Return `true` if the specified `lhs` has a value greater than the
/// specified `rhs`, and `false` otherwise.  Iterator `lhs` has a value
/// greater than iterator `rhs` if `0 > rhs - lhs` (see `operator-`).  The
/// behavior is undefined unless `lhs` and `rhs` refer to the same array.
template <class TYPE>
bool operator>(const CompactedArray_ConstIterator<TYPE>& lhs,
               const CompactedArray_ConstIterator<TYPE>& rhs);
 
/// Return `true` if the specified `lhs` has a value greater or equal than
/// the specified `rhs`, and `false` otherwise.  Iterator `lhs` has a value
/// greater than or equal to iterator `rhs` if `0 >= rhs - lhs` (see
/// `operator-`).  The behavior is undefined unless `lhs` and `rhs` refer to
/// the same array.
template <class TYPE>
bool operator>=(const CompactedArray_ConstIterator<TYPE>& lhs,
                const CompactedArray_ConstIterator<TYPE>& rhs);
 
                           // ====================
                           // class CompactedArray
                           // ====================
 
/// This space-efficient, value-semantic array class represents a sequence
/// of `TYPE` elements.  The interface provides functionality similar to a
/// `vector<TYPE>`, however, modifiable references to individual elements
/// are not provided.  This class provides accessors that return iterators
/// that provide non-modifiable access to its elements.  The returned
/// iterators, unlike those returned by a `vector<TYPE>`, are *not*
/// invalidated upon reallocation.
///
/// See @ref bdlc_compactedarray 
template <class TYPE>
class CompactedArray {
 
    // PRIVATE TYPES
    typedef bsl::vector<CompactedArray_CountedValue<TYPE> > Data;
 
    // DATA
    Data                        d_data;   // sorted vector of reference-counted
                                          // unique objects
 
    PackedIntArray<bsl::size_t> d_index;  // array of indices into 'd_data'
 
  private:
    // PRIVATE MANIPULATORS
 
    /// Remove the element in `d_data` at the specified `index`.  Update the
    /// `d_index` values to account for this removal.  The behavior is
    /// undefined unless `index < uniqueLength()`.
    void erase(bsl::size_t index);
 
    /// Find the element in `d_data` equal to the specified `value`,
    /// increment the element's reference count by the specified `count`,
    /// and return the element's index.  If the `value` is not in `d_data`,
    /// insert the element so as to retain sorted order in `d_data`, assign
    /// `count` as the new element's reference count, and return the
    /// inserted element's index.  The behavior is undefined unless
    /// `0 < count`.
    bsl::size_t increment(const TYPE& value, bsl::size_t count = 1);
 
  public:
    // PUBLIC TYPES
    typedef TYPE value_type;  // The type for elements.
 
    typedef CompactedArray_ConstIterator<TYPE> const_iterator;
 
    // CREATORS
 
    /// Create an empty `CompactedArray`.  Optionally specify a
    /// `basicAllocator` used to supply memory.  If `basicAllocator` is 0,
    /// the currently installed default allocator is used.
    explicit CompactedArray(bslma::Allocator *basicAllocator = 0);
 
    /// Create a `CompactedArray` having the specified `numElements`.
    /// Optionally specify a `value` to which each element will be set.  If
    /// `value` is not specified, `TYPE()` is used.  Optionally specify a
    /// `basicAllocator` used to supply memory.  If `basicAllocator` is 0,
    /// the currently installed default allocator is used.
    explicit CompactedArray(bsl::size_t       numElements,
                            const TYPE&       value = TYPE(),
                            bslma::Allocator *basicAllocator = 0);
 
    /// Create a `CompactedArray` having the same value as the specified
    /// `original` object.  Optionally specify a `basicAllocator` used to
    /// supply memory.  If `basicAllocator` is 0, the currently installed
    /// default allocator is used.
    CompactedArray(const CompactedArray&  original,
                   bslma::Allocator      *basicAllocator = 0);
 
    /// Destroy this object
    ~CompactedArray();
 
    // MANIPULATORS
 
    /// Assign to this array the value of the specified `rhs` array, and
    /// return a reference providing modifiable access to this array.
    CompactedArray& operator=(const CompactedArray& rhs);
 
    /// Append to this array an element having the specified `value`.  Note
    /// that this method is logically equivalent to:
    /// @code
    /// push_back(value);
    /// @endcode
    void append(const TYPE& value);
 
    /// Append to this array the elements from the specified `srcArray`.
    /// Note that if this array and `srcArray` are the same, the behavior is
    /// as if a copy of `srcArray` were passed.
    void append(const CompactedArray& srcArray);
 
    /// Append to this array the specified `numElements` starting at the
    /// specified `srcIndex` in the specified `srcArray`.  The behavior is
    /// undefined unless `srcIndex + numElements <= srcArray.length()`.
    /// Note that if this array and `srcArray` are the same, the behavior is
    /// as if a copy of `srcArray` were passed.
    void append(const CompactedArray& srcArray,
                bsl::size_t           srcIndex,
                bsl::size_t           numElements);
 
    /// Insert into this array, at the specified `dstIndex`, an element
    /// having the specified `value`, shifting any elements originally at or
    /// above `dstIndex` up by one index position.  The behavior is
    /// undefined unless `dstIndex <= length()`.
    void insert(bsl::size_t dstIndex, const TYPE& value);
 
    /// Insert into this array, at the specified `dst`, an element having
    /// the specified `value`, shifting any elements originally at or above
    /// `dst` up by one index position.  Return an iterator to the newly
    /// inserted element.  The behavior is undefined unless `dst` is an
    /// iterator over this array.
    const_iterator insert(const_iterator dst, const TYPE& value);
 
    /// Insert into this array, at the specified `dstIndex`, the elements
    /// from the specified `srcArray`, shifting any elements originally at
    /// or above `dstIndex` up by `srcArray.length()` index positions.  The
    /// behavior is undefined unless `dstIndex <= length()`.  Note that if
    /// this array and `srcArray` are the same, the behavior is as if a copy
    /// of `srcArray` were passed.
    void insert(bsl::size_t dstIndex, const CompactedArray& srcArray);
 
    /// Insert into this array, at the specified `dstIndex`, the specified
    /// `numElements` starting at the specified `srcIndex` in the specified
    /// `srcArray`.  Elements having an index greater than or equal to
    /// `dstIndex` before the insertion are shifted up by `numElements`
    /// index positions.  The behavior is undefined unless
    /// `dstIndex <= length()` and
    /// `srcIndex + numElements <= srcArray.length()`.  Note that if this
    /// array and `srcArray` are the same, the behavior is as if a copy of
    /// `srcArray` were passed.
    void insert(bsl::size_t           dstIndex,
                const CompactedArray& srcArray,
                bsl::size_t           srcIndex,
                bsl::size_t           numElements);
 
    /// Remove the last element from this array.  The behavior is undefined
    /// unless `0 < length()`.
    void pop_back();
 
    /// Append to this array an element having the specified `value`.
    void push_back(const TYPE& value);
 
    /// Remove from this array the element at the specified `dstIndex`.
    /// Each element having an index greater than `dstIndex` before the
    /// removal is shifted down by one index position.  The behavior is
    /// undefined unless `dstIndex < length()`.
    void remove(bsl::size_t dstIndex);
 
    /// Remove from this array the specified `numElements` starting at the
    /// specified `dstIndex`.  Each element having an index greater than or
    /// equal to `dstIndex + numElements` before the removal is shifted down
    /// by `numElements` index positions.  The behavior is undefined unless
    /// `dstIndex + numElements <= length()`.
    void remove(bsl::size_t dstIndex, bsl::size_t numElements);
 
    /// Remove from this array the elements starting at the specified
    /// `dstFirst` iterator up to, but not including, the specified
    /// `dstLast` iterator.  Each element at or above `dstLast` before the
    /// removal is shifted down by `dstLast - dstFirst` index positions.
    /// Return an iterator to the new position of the element that was
    /// referred to by `dstLast`, or `end()` if `dstLast == end()`.  The
    /// behavior is undefined unless `dstFirst` and `dstLast` are iterators
    /// over this array, and `dstFirst <= dstLast`.
    const_iterator remove(const_iterator dstFirst, const_iterator dstLast);
 
    /// Remove all the elements from this array.
    void removeAll();
 
    /// Change the value of the element at the specified `dstIndex` in this
    /// array to the specified `value`.  The behavior is undefined unless
    /// `dstIndex < length()`.
    void replace(bsl::size_t dstIndex, const TYPE& value);
 
    /// Change the values of the specified `numElements` starting at the
    /// specified `dstIndex` in this array to those of the `numElements`
    /// starting at the specified `srcIndex` in the specified `srcArray`.
    /// The behavior is undefined unless
    /// `srcIndex + numElements <= srcArray.length()` and
    /// `dstIndex + numElements <= length()`.  Note that if this array and
    /// `srcArray` are the same, the behavior is as if a copy of `srcArray`
    /// were passed.
    void replace(bsl::size_t           dstIndex,
                 const CompactedArray& srcArray,
                 bsl::size_t           srcIndex,
                 bsl::size_t           numElements);
 
    /// Make the capacity of this array at least the specified
    /// `numElements`, assuming the number of unique elements within this
    /// array does not increase.  This method has no effect if the current
    /// capacity meets or exceeds the required capacity.  The behavior is
    /// undefined unless `false == isEmpty() || 0 == numElements`.  Note
    /// that the assumption of not increasing the number of unique elements
    /// implies the need for the narrow contract.
    void reserveCapacity(bsl::size_t numElements);
 
    /// Make the capacity of this array at least the specified
    /// `numElements`, assuming the number of unique elements in this array
    /// does not exceed the greater of the specified `numUniqueElements` and
    /// `uniqueLength()`.  This method has no effect if the current capacity
    /// meets or exceeds the required capacity.  The behavior is undefined
    /// unless `numUniqueElements <= numElements` and
    /// `0 < numUniqueElements || 0 == numElements`.
    void reserveCapacity(bsl::size_t numElements,
                         bsl::size_t numUniqueElements);
 
    /// Set the length of this array to the specified `numElements`.  If
    /// `numElements > length()`, the added elements are initialized to
    /// `TYPE()`.
    void resize(bsl::size_t numElements);
 
    /// Efficiently exchange the value of this array with the value of the
    /// specified `other` array.  This method provides the no-throw
    /// exception-safety guarantee.  The behavior is undefined unless this
    /// array was created with the same allocator as `other`.
    void swap(CompactedArray& other);
 
    // ACCESSORS
 
    /// Return a `const` reference to the element at the specified `index`
    /// in this array.  The behavior is undefined unless `index < length()`.
    const TYPE& operator[](bsl::size_t index) const;
 
    /// Return the allocator used by this array to supply memory.
    bslma::Allocator *allocator() const;
 
    /// Return a `const` reference to the element at the back of this array.
    /// The behavior is undefined unless `0 < length()`.  Note that this
    /// method is logically equivalent to:
    /// @code
    ///   operator[](length() - 1)
    /// @endcode
    const TYPE& back() const;
 
    /// Return an iterator referring to the first element in this array, or
    /// the past-the-end iterator if this array is empty.  The iterator
    /// remains valid as long as this array exists.
    const_iterator begin() const;
 
    /// Return the number of elements this array can hold, without
    /// reallocation, assuming the number of unique elements within this
    /// array does not increase.
    bsl::size_t capacity() const;
 
    /// Return the past-the-end iterator for this array.  The iterator
    /// remains valid as long as this array exists, and its length does not
    /// decrease.
    const_iterator end() const;
 
    /// Return a `const` reference to the element at the front of this
    /// array.  The behavior is undefined unless `0 < length()`.  Note that
    /// this method is logically equivalent to:
    /// @code
    ///   operator[](0)
    /// @endcode
    const TYPE& front() const;
 
    /// Return `true` if there are no elements in this array, and `false`
    /// otherwise.
    bool isEmpty() const;
 
    /// Return `true` if this and the specified `other` array have the same
    /// value, and `false` otherwise.  Two `CompactedArray` arrays have the
    /// same value if they have the same length, and all corresponding
    /// elements (those at the same indices) have the same value.
    bool isEqual(const CompactedArray& other) const;
 
    /// Return the number of elements in this array.
    bsl::size_t length() const;
 
    /// Write the value of this array to the specified output `stream` in a
    /// human-readable format, and return a reference to `stream`.
    /// Optionally specify an initial indentation `level`, whose absolute
    /// value is incremented recursively for nested arrays.  If `level` is
    /// specified, optionally specify `spacesPerLevel`, whose absolute value
    /// indicates the number of spaces per indentation level for this and
    /// all of its nested arrays.  If `level` is negative, format the entire
    /// output on one line, suppressing all but the initial indentation (as
    /// governed by `level`).  If `stream` is not valid on entry, this
    /// operation has no effect.  Note that the format is not fully
    /// specified, and can change without notice.
    bsl::ostream& print(bsl::ostream& stream,
                        int           level = 0,
                        int           spacesPerLevel = 4) const;
 
    /// Return a `const` reference to the element at the specified `index`
    /// within the sorted sequence of unique element values in this object.
    /// The behavior is undefined unless `index < uniqueLength()`.  Note
    /// that `uniqueElement(index)` and `operator@ref index ` can return
    /// different objects.
    const TYPE& uniqueElement(bsl::size_t index) const;
 
    /// Return the number of unique elements in this array.
    bsl::size_t uniqueLength() const;
};
 
// FREE OPERATORS
 
/// Write the value of the specified `array` to the specified output
/// `stream` in a single-line format, and return a reference providing
/// modifiable access to `stream`.  If `stream` is not valid on entry, this
/// operation has no effect.  Note that this human-readable format is not
/// fully specified and can change without notice.
template <class TYPE>
bsl::ostream& operator<<(bsl::ostream&               stream,
                         const CompactedArray<TYPE>& array);
 
/// Return `true` if the specified `lhs` and `rhs` arrays have the same
/// value, and `false` otherwise.  Two `CompactedArray` arrays have the same
/// value if they have the same length, and all corresponding elements
/// (those at the same indices) have the same value.
template <class TYPE>
bool operator==(const CompactedArray<TYPE>& lhs,
                const CompactedArray<TYPE>& rhs);
 
/// Return `true` if the specified `lhs` and `rhs` arrays do not have the
/// same value, and `false` otherwise.  Two `CompactedArray` arrays do not
/// have the same value if they do not have the same length, or if any
/// corresponding elements (those at the same indices) do not have the same
/// value.
template <class TYPE>
bool operator!=(const CompactedArray<TYPE>& lhs,
                const CompactedArray<TYPE>& rhs);
 
// FREE FUNCTIONS
 
/// Exchange the values of the specified `a` and `b` objects.  This function
/// provides the no-throw exception-safety guarantee if the two objects were
/// created with the same allocator and the basic guarantee otherwise.
template <class TYPE>
void swap(CompactedArray<TYPE>& a, CompactedArray<TYPE>& b);
 
// HASH SPECIALIZATIONS
 
/// Pass the specified `input` to the specified `hashAlg`.
template <class HASHALG, class TYPE>
void hashAppend(HASHALG& hashAlg, const CompactedArray<TYPE>& input);
 
// ============================================================================
//                             INLINE DEFINITIONS
// ============================================================================
 
                  // -------------------------------------
                  // class CompactedArray_RemoveAllProctor
                  // -------------------------------------
 
// CREATORS
template <class TYPE>
inline
CompactedArray_RemoveAllProctor<TYPE>::CompactedArray_RemoveAllProctor(
                                                   CompactedArray<TYPE> *array)
: d_array_p(array)
{
}
 
template <class TYPE>
inline
CompactedArray_RemoveAllProctor<TYPE>::~CompactedArray_RemoveAllProctor()
{
    if (d_array_p) {
        d_array_p->removeAll();
    }
}
 
// MANIPULATORS
template <class TYPE>
inline
void CompactedArray_RemoveAllProctor<TYPE>::release()
{
    d_array_p = 0;
}
 
                    // ----------------------------------
                    // struct CompactedArray_CountedValue
                    // ----------------------------------
 
// CREATORS
template <class TYPE>
inline
CompactedArray_CountedValue<TYPE>::CompactedArray_CountedValue(
                                              const TYPE&       value,
                                              bsl::size_t       count,
                                              bslma::Allocator *basicAllocator)
: d_count(count)
{
    BSLS_ASSERT(basicAllocator);
 
    bslma::ConstructionUtil::construct(d_value.address(),
                                       basicAllocator,
                                       value);
}
 
template <class TYPE>
inline
CompactedArray_CountedValue<TYPE>::CompactedArray_CountedValue(
                      const CompactedArray_CountedValue<TYPE>&  original,
                      bslma::Allocator                         *basicAllocator)
: d_count(original.d_count)
{
    BSLS_ASSERT(basicAllocator);
 
    bslma::ConstructionUtil::construct(d_value.address(),
                                       basicAllocator,
                                       original.d_value.object());
}
 
template <class TYPE>
inline
CompactedArray_CountedValue<TYPE>::~CompactedArray_CountedValue()
{
    d_value.object().~TYPE();
}
 
// MANIPULATORS
template <class TYPE>
inline
CompactedArray_CountedValue<TYPE>&
        CompactedArray_CountedValue<TYPE>::operator=(
                                  const CompactedArray_CountedValue<TYPE>& rhs)
{
    d_value.object() = rhs.d_value.object();
    d_count          = rhs.d_count;
 
    return *this;
}
 
}  // close package namespace
 
// FREE OPERATORS
template <class TYPE>
inline
bool bdlc::operator==(const CompactedArray_CountedValue<TYPE>& lhs,
                      const CompactedArray_CountedValue<TYPE>& rhs)
{
    return lhs.d_value.object() == rhs.d_value.object();
}
 
template <class TYPE>
inline
bool bdlc::operator!=(const CompactedArray_CountedValue<TYPE>& lhs,
                      const CompactedArray_CountedValue<TYPE>& rhs)
{
    return lhs.d_value.object() != rhs.d_value.object();
}
 
template <class TYPE>
inline
bool bdlc::operator<(const CompactedArray_CountedValue<TYPE>& lhs,
                     const TYPE&                              rhs)
{
    return lhs.d_value.object() < rhs;
}
 
template <class TYPE>
inline
bool bdlc::operator<(const TYPE&                              lhs,
                     const CompactedArray_CountedValue<TYPE>& rhs)
{
    return lhs < rhs.d_value.object();
}
 
namespace bdlc {
 
                    // ----------------------------------
                    // class CompactedArray_ConstIterator
                    // ----------------------------------
 
// PRIVATE CREATORS
template <class TYPE>
inline
CompactedArray_ConstIterator<TYPE>::CompactedArray_ConstIterator(
                                             const CompactedArray<TYPE> *array,
                                             bsl::size_t                 index)
: d_array_p(array)
, d_index(index)
{
    BSLS_ASSERT(d_array_p);
    BSLS_ASSERT(d_index <= d_array_p->length());
}
 
// CREATORS
template <class TYPE>
inline
CompactedArray_ConstIterator<TYPE>::CompactedArray_ConstIterator()
: d_array_p(0)
, d_index(0)
{
}
 
template <class TYPE>
inline
CompactedArray_ConstIterator<TYPE>::CompactedArray_ConstIterator(
                                  const CompactedArray_ConstIterator& original)
: d_array_p(original.d_array_p)
, d_index(original.d_index)
{
}
 
// MANIPULATORS
template <class TYPE>
inline
CompactedArray_ConstIterator<TYPE>& CompactedArray_ConstIterator<TYPE>::
                             operator=(const CompactedArray_ConstIterator& rhs)
{
    d_array_p = rhs.d_array_p;
    d_index   = rhs.d_index;
    return *this;
}
 
template <class TYPE>
inline
CompactedArray_ConstIterator<TYPE>&
          CompactedArray_ConstIterator<TYPE>::operator+=(bsl::ptrdiff_t offset)
{
    BSLS_ASSERT(d_array_p);
 
    // Assert '0 <= d_index + offset <= d_array_p->length()' without risk of
    // overflow.
    BSLS_ASSERT(   0 <= offset || d_index >= bsl::size_t(-offset));
    BSLS_ASSERT(   0 >= offset
                     || d_array_p->length() - d_index >= bsl::size_t(offset));
 
    d_index += offset;
    return *this;
}
 
template <class TYPE>
inline
CompactedArray_ConstIterator<TYPE>&
          CompactedArray_ConstIterator<TYPE>::operator-=(bsl::ptrdiff_t offset)
{
    BSLS_ASSERT(d_array_p);
 
    // Assert '0 <= d_index - offset <= d_array_p->length()' without risk of
    // overflow.
    BSLS_ASSERT(   0 >= offset || d_index >= bsl::size_t(offset));
    BSLS_ASSERT(   0 <= offset
                     || d_array_p->length() - d_index >= bsl::size_t(-offset));
 
    d_index -= offset;
    return *this;
}
 
template <class TYPE>
inline
CompactedArray_ConstIterator<TYPE>&
                               CompactedArray_ConstIterator<TYPE>::operator++()
{
    BSLS_ASSERT(d_array_p);
    BSLS_ASSERT(d_index < d_array_p->length());
 
    ++d_index;
    return *this;
}
 
template <class TYPE>
inline
CompactedArray_ConstIterator<TYPE>&
                               CompactedArray_ConstIterator<TYPE>::operator--()
{
    BSLS_ASSERT(d_array_p);
    BSLS_ASSERT(0 < d_index);
 
    --d_index;
    return *this;
}
 
// ACCESSORS
template <class TYPE>
inline
const TYPE& CompactedArray_ConstIterator<TYPE>::operator*() const
{
    BSLS_ASSERT(d_array_p);
    BSLS_ASSERT(d_index < d_array_p->length());
 
    return (*d_array_p)[d_index];
}
 
template <class TYPE>
inline
const TYPE& CompactedArray_ConstIterator<TYPE>::operator->() const
{
    BSLS_ASSERT(d_array_p);
    BSLS_ASSERT(d_index < d_array_p->length());
 
    return (*d_array_p)[d_index];
}
 
template <class TYPE>
inline
const TYPE& CompactedArray_ConstIterator<TYPE>::
                                        operator[](bsl::ptrdiff_t offset) const
{
    BSLS_ASSERT(d_array_p);
 
    // Assert '0 <= d_index + offset < d_array_p->length()' without risk of
    // overflow.
    BSLS_ASSERT(   0 <= offset || d_index >= bsl::size_t(-offset));
    BSLS_ASSERT(   0 >= offset
                     || d_array_p->length() - d_index > bsl::size_t(offset));
 
    return (*d_array_p)[d_index + offset];
}
 
}  // close package namespace
 
// FREE OPERATORS
template <class TYPE>
inline
bdlc::CompactedArray_ConstIterator<TYPE> bdlc::operator++(
                                  CompactedArray_ConstIterator<TYPE>& iterator,
                                  int)
{
    BSLS_ASSERT(iterator.d_array_p);
    BSLS_ASSERT(iterator.d_index < iterator.d_array_p->length());
 
    const CompactedArray_ConstIterator<TYPE> curr = iterator;
    ++iterator;
    return curr;
}
 
template <class TYPE>
inline
bdlc::CompactedArray_ConstIterator<TYPE> bdlc::operator--(
                                  CompactedArray_ConstIterator<TYPE>& iterator,
                                  int)
{
    BSLS_ASSERT(iterator.d_array_p);
    BSLS_ASSERT(iterator.d_index > 0);
 
    const CompactedArray_ConstIterator<TYPE> curr = iterator;
    --iterator;
    return curr;
}
 
template <class TYPE>
inline
bdlc::CompactedArray_ConstIterator<TYPE> bdlc::operator+(
                            const CompactedArray_ConstIterator<TYPE>& iterator,
                            bsl::ptrdiff_t                            offset)
{
    BSLS_ASSERT(iterator.d_array_p);
 
    // Assert '0 <= iterator.d_index + offset <= iterator.d_array_p->length()'
    // without risk of overflow.
    BSLS_ASSERT(   0 <= offset
                     || iterator.d_index              >= bsl::size_t(-offset));
    BSLS_ASSERT(   0 >= offset
                     || iterator.d_array_p->length() - iterator.d_index
                                                      >= bsl::size_t( offset));
 
    return CompactedArray_ConstIterator<TYPE>(iterator.d_array_p,
                                              iterator.d_index + offset);
}
 
template <class TYPE>
inline
bdlc::CompactedArray_ConstIterator<TYPE> bdlc::operator+(
                            bsl::ptrdiff_t                            offset,
                            const CompactedArray_ConstIterator<TYPE>& iterator)
{
    return iterator + offset;
}
 
template <class TYPE>
inline
bdlc::CompactedArray_ConstIterator<TYPE> bdlc::operator-(
                            const CompactedArray_ConstIterator<TYPE>& iterator,
                            bsl::ptrdiff_t                            offset)
{
    BSLS_ASSERT(iterator.d_array_p);
 
    // Assert '0 <= iterator.d_index - offset <= iterator.d_array_p->length()'
    // without risk of overflow.
    BSLS_ASSERT(   0 >= offset
                     || iterator.d_index              >= bsl::size_t( offset));
    BSLS_ASSERT(   0 <= offset
                     || iterator.d_array_p->length() - iterator.d_index
                                                      >= bsl::size_t(-offset));
 
    return CompactedArray_ConstIterator<TYPE>(iterator.d_array_p,
                                              iterator.d_index - offset);
}
 
template <class TYPE>
inline
bsl::ptrdiff_t bdlc::operator-(const CompactedArray_ConstIterator<TYPE>& lhs,
                               const CompactedArray_ConstIterator<TYPE>& rhs)
{
    BSLS_ASSERT(lhs.d_array_p);
    BSLS_ASSERT(rhs.d_array_p);
    BSLS_ASSERT(lhs.d_array_p == rhs.d_array_p);
 
    BSLS_ASSERT(
          lhs.d_index >= rhs.d_index
        ? lhs.d_index - rhs.d_index <=
                        bsl::size_t(bsl::numeric_limits<bsl::ptrdiff_t>::max())
        : rhs.d_index - lhs.d_index <=
                      bsl::size_t(bsl::numeric_limits<bsl::ptrdiff_t>::min()));
 
    return static_cast<bsl::ptrdiff_t>(lhs.d_index - rhs.d_index);
}
 
template <class TYPE>
inline
bool bdlc::operator==(const CompactedArray_ConstIterator<TYPE>& lhs,
                      const CompactedArray_ConstIterator<TYPE>& rhs)
{
    return lhs.d_array_p == rhs.d_array_p && lhs.d_index == rhs.d_index;
}
 
template <class TYPE>
inline
bool bdlc::operator!=(const CompactedArray_ConstIterator<TYPE>& lhs,
                      const CompactedArray_ConstIterator<TYPE>& rhs)
{
    return lhs.d_array_p != rhs.d_array_p || lhs.d_index != rhs.d_index;
}
 
template <class TYPE>
inline
bool bdlc::operator<(const CompactedArray_ConstIterator<TYPE>& lhs,
                     const CompactedArray_ConstIterator<TYPE>& rhs)
{
    BSLS_ASSERT(lhs.d_array_p);
    BSLS_ASSERT(rhs.d_array_p);
    BSLS_ASSERT(lhs.d_array_p == rhs.d_array_p);
 
    return lhs.d_index < rhs.d_index;
}
 
template <class TYPE>
inline
bool bdlc::operator<=(const CompactedArray_ConstIterator<TYPE>& lhs,
                      const CompactedArray_ConstIterator<TYPE>& rhs)
{
    BSLS_ASSERT(lhs.d_array_p);
    BSLS_ASSERT(rhs.d_array_p);
    BSLS_ASSERT(lhs.d_array_p == rhs.d_array_p);
 
    return lhs.d_index <= rhs.d_index;
}
 
template <class TYPE>
inline
bool bdlc::operator>(const CompactedArray_ConstIterator<TYPE>& lhs,
                     const CompactedArray_ConstIterator<TYPE>& rhs)
{
    BSLS_ASSERT(lhs.d_array_p);
    BSLS_ASSERT(rhs.d_array_p);
    BSLS_ASSERT(lhs.d_array_p == rhs.d_array_p);
 
    return lhs.d_index > rhs.d_index;
}
 
template <class TYPE>
inline
bool bdlc::operator>=(const CompactedArray_ConstIterator<TYPE>& lhs,
                      const CompactedArray_ConstIterator<TYPE>& rhs)
{
    BSLS_ASSERT(lhs.d_array_p);
    BSLS_ASSERT(rhs.d_array_p);
    BSLS_ASSERT(lhs.d_array_p == rhs.d_array_p);
 
    return lhs.d_index >= rhs.d_index;
}
 
namespace bdlc {
 
                           // --------------------
                           // class CompactedArray
                           // --------------------
 
// PRIVATE MANIPULATORS
template <class TYPE>
void CompactedArray<TYPE>::erase(bsl::size_t index)
{
    BSLS_ASSERT(index < uniqueLength());
 
    for (bsl::size_t i = 0; i < d_index.length(); ++i) {
        if (d_index[i] > index) {
            d_index.replace(i, d_index[i] - 1);
        }
    }
 
    d_data.erase(d_data.begin() + index);
}
 
template <class TYPE>
bsl::size_t CompactedArray<TYPE>::increment(const TYPE& value,
                                            bsl::size_t count)
{
    BSLS_ASSERT(0 < count);
 
    bsl::size_t index;
 
    typename Data::iterator iter =
                      bdlb::AlgorithmWorkaroundUtil::lowerBound(d_data.begin(),
                                                                d_data.end(),
                                                                value);
 
    if (iter == d_data.end()) {
        index = d_data.size();
        d_data.emplace_back(value, count);
    }
    else if (value < iter->d_value.object()) {
        index = iter - d_data.begin();
 
        d_data.insert(iter,
                      CompactedArray_CountedValue<TYPE>(
                                          value,
                                          count,
                                          d_data.get_allocator().mechanism()));
 
        for (bsl::size_t i = 0; i < d_index.length(); ++i) {
            if (d_index[i] >= index) {
                d_index.replace(i, d_index[i] + 1);
            }
        }
    }
    else {
        index = iter - d_data.begin();
 
        iter->d_count += count;
    }
 
    return index;
}
 
// CREATORS
template <class TYPE>
CompactedArray<TYPE>::CompactedArray(bslma::Allocator *basicAllocator)
: d_data(basicAllocator)
, d_index(basicAllocator)
{
}
 
template <class TYPE>
CompactedArray<TYPE>::CompactedArray(bsl::size_t       numElements,
                                     const TYPE&       value,
                                     bslma::Allocator *basicAllocator)
: d_data(basicAllocator)
, d_index(basicAllocator)
{
    if (numElements) {
        d_index.reserveCapacity(numElements, 1);
 
        d_data.emplace_back(value, numElements);
        d_index.resize(numElements);
    }
}
 
template <class TYPE>
CompactedArray<TYPE>::CompactedArray(
                                   const CompactedArray<TYPE>&  original,
                                   bslma::Allocator            *basicAllocator)
: d_data(original.d_data, basicAllocator)
, d_index(original.d_index, basicAllocator)
{
}
 
template <class TYPE>
CompactedArray<TYPE>::~CompactedArray()
{
}
 
// MANIPULATORS
template <class TYPE>
CompactedArray<TYPE>& CompactedArray<TYPE>::operator=(
                                               const CompactedArray<TYPE>& rhs)
{
    if (this != &rhs) {
        CompactedArray_RemoveAllProctor<TYPE> proctor(this);
 
        d_index.reserveCapacity(rhs.length(), rhs.uniqueLength());
        d_data  = rhs.d_data;
        d_index = rhs.d_index;
 
        proctor.release();
    }
 
    return *this;
}
 
template <class TYPE>
void CompactedArray<TYPE>::append(const TYPE& value)
{
    CompactedArray_RemoveAllProctor<TYPE> proctor(this);
 
    d_index.reserveCapacity(d_index.length() + 1, d_data.size() + 1);
 
    d_index.push_back(increment(value));
 
    proctor.release();
}
 
template <class TYPE>
void CompactedArray<TYPE>::append(const CompactedArray& srcArray)
{
    if (&srcArray != this) {
        CompactedArray_RemoveAllProctor<TYPE> proctor(this);
 
        d_index.reserveCapacity(d_index.length() + srcArray.d_index.length(),
                                d_data.size()    + srcArray.d_data.size());
 
        for (bsl::size_t i = 0; i < srcArray.length(); ++i) {
            d_index.push_back(increment(srcArray[i]));
        }
 
        proctor.release();
    }
    else {
        d_index.reserveCapacity(d_index.length() * 2);
 
        for (bsl::size_t i = 0; i < d_data.size(); ++i) {
            d_data[i].d_count *= 2;
        }
 
        d_index.append(d_index);
    }
}
 
template <class TYPE>
void CompactedArray<TYPE>::append(const CompactedArray& srcArray,
                                  bsl::size_t           srcIndex,
                                  bsl::size_t           numElements)
{
    // Assert 'srcIndex + numElements <= srcArray.length()' without risk of
    // overflow.
    BSLS_ASSERT(numElements <= srcArray.length());
    BSLS_ASSERT(srcIndex    <= srcArray.length() - numElements);
 
    if (&srcArray != this) {
        CompactedArray_RemoveAllProctor<TYPE> proctor(this);
 
        d_index.reserveCapacity(d_index.length() + numElements,
                                d_data.size()    + numElements);
 
        for (bsl::size_t i = 0; i < numElements; ++i) {
            d_index.push_back(increment(srcArray[srcIndex + i]));
        }
 
        proctor.release();
    }
    else {
        d_index.reserveCapacity(d_index.length() + numElements);
 
        for (bsl::size_t i = 0; i < numElements; ++i) {
            d_data[d_index[srcIndex + i]].d_count += 1;
        }
 
        d_index.append(d_index, srcIndex, numElements);
    }
}
 
template <class TYPE>
void CompactedArray<TYPE>::insert(bsl::size_t dstIndex, const TYPE& value)
{
    BSLS_ASSERT(dstIndex <= d_index.length());
 
    CompactedArray_RemoveAllProctor<TYPE> proctor(this);
 
    d_index.reserveCapacity(d_index.length() + 1, d_data.size() + 1);
 
    d_index.insert(dstIndex, increment(value));
 
    proctor.release();
}
 
template <class TYPE>
inline
typename CompactedArray<TYPE>::const_iterator
            CompactedArray<TYPE>::insert(const_iterator dst, const TYPE& value)
{
    BSLS_ASSERT(this == dst.d_array_p);
 
    insert(dst.d_index, value);
    return dst;
}
 
template <class TYPE>
void CompactedArray<TYPE>::insert(bsl::size_t           dstIndex,
                                  const CompactedArray& srcArray)
{
    BSLS_ASSERT(dstIndex <= d_index.length());
 
    if (&srcArray != this) {
        CompactedArray_RemoveAllProctor<TYPE> proctor(this);
 
        d_index.reserveCapacity(d_index.length() + srcArray.d_index.length(),
                                d_data.size()    + srcArray.d_data.size());
 
        for (bsl::size_t i = 0; i < srcArray.length(); ++i) {
            d_index.insert(dstIndex + i, increment(srcArray[i]));
        }
 
        proctor.release();
    }
    else {
        d_index.reserveCapacity(d_index.length() * 2);
 
        for (bsl::size_t i = 0; i < d_data.size(); ++i) {
            d_data[i].d_count *= 2;
        }
 
        d_index.insert(dstIndex, d_index);
    }
}
 
template <class TYPE>
void CompactedArray<TYPE>::insert(bsl::size_t           dstIndex,
                                  const CompactedArray& srcArray,
                                  bsl::size_t           srcIndex,
                                  bsl::size_t           numElements)
{
    BSLS_ASSERT(dstIndex <= d_index.length());
 
    // Assert 'srcIndex + numElements <= srcArray.length()' without risk of
    // overflow.
    BSLS_ASSERT(numElements <= srcArray.length());
    BSLS_ASSERT(srcIndex    <= srcArray.length() - numElements);
 
    if (&srcArray != this) {
        CompactedArray_RemoveAllProctor<TYPE> proctor(this);
 
        d_index.reserveCapacity(d_index.length() + numElements,
                                d_data.size()    + numElements);
 
        for (bsl::size_t i = 0; i < numElements; ++i) {
            d_index.insert(dstIndex + i, increment(srcArray[srcIndex + i]));
        }
 
        proctor.release();
    }
    else {
        d_index.reserveCapacity(d_index.length() + numElements);
 
        for (bsl::size_t i = 0; i < numElements; ++i) {
            d_data[d_index[srcIndex + i]].d_count += 1;
        }
 
        d_index.insert(dstIndex, d_index, srcIndex, numElements);
    }
}
 
template <class TYPE>
void CompactedArray<TYPE>::pop_back()
{
    BSLS_ASSERT(!isEmpty());
 
    bsl::size_t                        dataIndex = d_index.back();
    CompactedArray_CountedValue<TYPE>& dataValue = d_data[dataIndex];
 
    d_index.pop_back();
 
    if (0 == --dataValue.d_count) {
        CompactedArray_RemoveAllProctor<TYPE> proctor(this);
 
        erase(dataIndex);
 
        proctor.release();
    }
}
 
template <class TYPE>
inline
void CompactedArray<TYPE>::push_back(const TYPE& value)
{
    append(value);
}
 
template <class TYPE>
inline
void CompactedArray<TYPE>::remove(bsl::size_t dstIndex)
{
    BSLS_ASSERT(dstIndex < d_index.length());
 
    remove(dstIndex, 1);
}
 
template <class TYPE>
void CompactedArray<TYPE>::remove(bsl::size_t dstIndex,
                                  bsl::size_t numElements)
{
    // Assert 'dstIndex + numElements <= d_index.length()' without risk of
    // overflow.
    BSLS_ASSERT(numElements <= d_index.length());
    BSLS_ASSERT(dstIndex    <= d_index.length() - numElements);
 
    CompactedArray_RemoveAllProctor<TYPE> proctor(this);
 
    bsl::size_t endIndex = dstIndex + numElements;
    for (bsl::size_t i = dstIndex; i < endIndex; ++i) {
        bsl::size_t                        dataIndex = d_index[i];
        CompactedArray_CountedValue<TYPE>& dataValue = d_data[dataIndex];
 
        if (0 == --dataValue.d_count) {
            erase(dataIndex);
        }
    }
 
    d_index.remove(dstIndex, numElements);
 
    proctor.release();
}
 
template <class TYPE>
inline
typename CompactedArray<TYPE>::const_iterator
                          CompactedArray<TYPE>::remove(const_iterator dstFirst,
                                                       const_iterator dstLast)
{
    BSLS_ASSERT(this     == dstFirst.d_array_p);
    BSLS_ASSERT(this     == dstLast.d_array_p);
    BSLS_ASSERT(dstFirst <= dstLast);
 
    remove(dstFirst.d_index, dstLast.d_index - dstFirst.d_index);
    return dstFirst;
}
 
template <class TYPE>
void CompactedArray<TYPE>::removeAll()
{
    d_data.clear();
    d_index.removeAll();
}
 
template <class TYPE>
void CompactedArray<TYPE>::replace(bsl::size_t dstIndex, const TYPE& value)
{
    BSLS_ASSERT(dstIndex < length());
 
    CompactedArray_RemoveAllProctor<TYPE> proctor(this);
 
    d_index.reserveCapacity(d_index.length(), d_data.size() + 1);
 
    bsl::size_t                        newDataIndex = increment(value);
    bsl::size_t                        dataIndex    = d_index[dstIndex];
    CompactedArray_CountedValue<TYPE>& dataValue    = d_data[dataIndex];
 
    if (0 == --dataValue.d_count) {
        erase(dataIndex);
        if (dataIndex <= newDataIndex) {
            --newDataIndex;
        }
    }
 
    d_index.replace(dstIndex, newDataIndex);
 
    proctor.release();
}
 
template <class TYPE>
void CompactedArray<TYPE>::replace(bsl::size_t           dstIndex,
                                   const CompactedArray& srcArray,
                                   bsl::size_t           srcIndex,
                                   bsl::size_t           numElements)
{
    // Assert 'dstIndex + numElements <= length()' without risk of overflow.
    BSLS_ASSERT(numElements <= length());
    BSLS_ASSERT(dstIndex    <= length() - numElements);
 
    // Assert 'srcIndex + numElements <= srcArray.length()' without risk of
    // overflow.
    BSLS_ASSERT(numElements <= srcArray.length());
    BSLS_ASSERT(srcIndex    <= srcArray.length() - numElements);
 
    CompactedArray_RemoveAllProctor<TYPE> proctor(this);
 
    if (&srcArray != this) {
        d_index.reserveCapacity(d_index.length(), d_data.size() + numElements);
 
        for (bsl::size_t i = 0; i < numElements; ++i) {
            bsl::size_t newDataIndex = increment(srcArray[srcIndex + i]);
            bsl::size_t dataIndex    = d_index[dstIndex + i];
 
            CompactedArray_CountedValue<TYPE>& dataValue = d_data[dataIndex];
 
            if (0 == --dataValue.d_count) {
                erase(dataIndex);
                if (dataIndex <= newDataIndex) {
                    --newDataIndex;
                }
            }
 
            d_index.replace(dstIndex + i, newDataIndex);
        }
    }
    else {
        bsl::size_t endIndex;
 
        endIndex = srcIndex + numElements;
        for (bsl::size_t i = srcIndex; i < endIndex; ++i) {
            ++d_data[d_index[i]].d_count;
        }
 
        endIndex = dstIndex + numElements;
        for (bsl::size_t i = dstIndex; i < endIndex; ++i) {
            bsl::size_t                        dataIndex = d_index[i];
            CompactedArray_CountedValue<TYPE>& dataValue = d_data[dataIndex];
 
            if (0 == --dataValue.d_count) {
                erase(dataIndex);
            }
        }
 
        d_index.replace(dstIndex, d_index, srcIndex, numElements);
    }
 
    proctor.release();
}
 
template <class TYPE>
void CompactedArray<TYPE>::reserveCapacity(bsl::size_t numElements)
{
    BSLS_ASSERT(false == isEmpty() || 0 == numElements);
 
    if (0 < numElements) {
        d_index.reserveCapacity(numElements, d_data.size() - 1);
    }
}
 
template <class TYPE>
void CompactedArray<TYPE>::reserveCapacity(bsl::size_t numElements,
                                           bsl::size_t numUniqueElements)
{
    BSLS_ASSERT(numUniqueElements <= numElements);
    BSLS_ASSERT(0 < numUniqueElements || 0 == numElements);
 
    if (0 < numElements) {
        d_data.reserve(numUniqueElements);
        if (d_data.size() > numUniqueElements) {
            numUniqueElements = d_data.size();
        }
        d_index.reserveCapacity(numElements, numUniqueElements - 1);
    }
}
 
template <class TYPE>
void CompactedArray<TYPE>::resize(bsl::size_t numElements)
{
    if (d_index.length() < numElements) {
        CompactedArray_RemoveAllProctor<TYPE> proctor(this);
 
        d_index.reserveCapacity(numElements, d_data.size() + 1);
 
        bsl::size_t count = numElements - d_index.length();
        bsl::size_t index = increment(TYPE(), count);
 
        for (bsl::size_t i = 0; i < count; ++i) {
            d_index.push_back(index);
        }
 
        proctor.release();
    }
    else {
        bsl::size_t count = d_index.length() - numElements;
 
        for (bsl::size_t i = 0; i < count; ++i) {
            pop_back();
        }
    }
}
 
template <class TYPE>
void CompactedArray<TYPE>::swap(CompactedArray<TYPE>& other)
{
    BSLS_ASSERT(allocator() == other.allocator());
 
    bslalg::SwapUtil::swap(&d_data,  &other.d_data);
    bslalg::SwapUtil::swap(&d_index, &other.d_index);
}
 
// ACCESSORS
template <class TYPE>
inline
const TYPE& CompactedArray<TYPE>::operator[](bsl::size_t index) const
{
    BSLS_ASSERT(index < length());
 
    return d_data[d_index[index]].d_value.object();
}
 
template <class TYPE>
inline
bslma::Allocator *CompactedArray<TYPE>::allocator() const
{
    return d_index.allocator();
}
 
template <class TYPE>
inline
const TYPE& CompactedArray<TYPE>::back() const
{
    BSLS_ASSERT(0 < length());
 
    return operator[](length() - 1);
}
 
template <class TYPE>
inline
typename CompactedArray<TYPE>::const_iterator
                                            CompactedArray<TYPE>::begin() const
{
    return const_iterator(this, 0);
}
 
template <class TYPE>
inline
bsl::size_t CompactedArray<TYPE>::capacity() const
{
    return d_index.isEmpty() ? 0 : d_index.capacity();
}
 
template <class TYPE>
inline
typename CompactedArray<TYPE>::const_iterator CompactedArray<TYPE>::end() const
{
    return const_iterator(this, d_index.length());
}
 
template <class TYPE>
inline
const TYPE& CompactedArray<TYPE>::front() const
{
    BSLS_ASSERT(0 < length());
 
    return operator[](0);
}
 
template <class TYPE>
inline
bool CompactedArray<TYPE>::isEmpty() const
{
    return 0 == length();
}
 
template <class TYPE>
inline
bool CompactedArray<TYPE>::isEqual(const CompactedArray& other) const
{
    return d_index == other.d_index && d_data == other.d_data;
}
 
template <class TYPE>
inline
bsl::size_t CompactedArray<TYPE>::length() const
{
    return d_index.length();
}
 
template <class TYPE>
bsl::ostream& CompactedArray<TYPE>::print(bsl::ostream& stream,
                                          int           level,
                                          int           spacesPerLevel) const
{
    if (stream.bad()) {
        return stream;                                                // RETURN
    }
 
    bslim::Printer printer(&stream, level, spacesPerLevel);
    printer.start();
    for (bsl::size_t i = 0; i < d_index.length(); ++i) {
        printer.printValue(d_data[d_index[i]].d_value.object());
    }
    printer.end();
 
    return stream;
}
 
template <class TYPE>
inline
const TYPE& CompactedArray<TYPE>::uniqueElement(bsl::size_t index) const
{
    BSLS_ASSERT(index < uniqueLength());
 
    return d_data[index].d_value.object();
}
 
template <class TYPE>
inline
bsl::size_t CompactedArray<TYPE>::uniqueLength() const
{
    return d_data.size();
}
 
}  // close package namespace
 
// FREE OPERATORS
template <class TYPE>
inline
bsl::ostream& bdlc::operator<<(bsl::ostream&               stream,
                               const CompactedArray<TYPE>& array)
{
    return array.print(stream, 0, -1);
}
 
template <class TYPE>
inline
bool bdlc::operator==(const CompactedArray<TYPE>& lhs,
                      const CompactedArray<TYPE>& rhs)
{
    return lhs.isEqual(rhs);
}
 
template <class TYPE>
inline
bool bdlc::operator!=(const CompactedArray<TYPE>& lhs,
                      const CompactedArray<TYPE>& rhs)
{
    return !lhs.isEqual(rhs);
}
 
// FREE FUNCTIONS
template <class TYPE>
void bdlc::swap(CompactedArray<TYPE>& a, CompactedArray<TYPE>& b)
{
    if (a.allocator() == b.allocator()) {
        a.swap(b);
 
        return;                                                       // RETURN
    }
 
    CompactedArray<TYPE> futureA(b, a.allocator());
    CompactedArray<TYPE> futureB(a, b.allocator());
 
    futureA.swap(a);
    futureB.swap(b);
}
 
// HASH SPECIALIZATIONS
template <class HASHALG, class TYPE>
void bdlc::hashAppend(HASHALG& hashAlg, const CompactedArray<TYPE>& input)
{
    using ::BloombergLP::bslh::hashAppend;
    typedef typename CompactedArray<TYPE>::const_iterator citer;
    hashAppend(hashAlg, input.length());
    for (citer b = input.begin(), e = input.end(); b != e; ++b) {
        hashAppend(hashAlg, *b);
    }
}
 
 
 
// TRAITS
 
 
namespace bslma {
 
template <class TYPE>
struct UsesBslmaAllocator<bdlc::CompactedArray_CountedValue<TYPE> >
                                                           : bsl::true_type {};
 
template <class TYPE>
struct UsesBslmaAllocator<bdlc::CompactedArray<TYPE> > : bsl::true_type {};
 
}  // close namespace bslma
 
 
#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 ----------------------------------
 
/** @} */
/** @} */
/** @} */