util/include/chre/util/dynamic_vector.h

/*
 * Copyright (C) 2016 The Android Open Source Project
 *
 * 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.
 */

#ifndef CHRE_UTIL_DYNAMIC_VECTOR_H_
#define CHRE_UTIL_DYNAMIC_VECTOR_H_

#include <type_traits>

#include "chre/util/dynamic_vector_base.h"

namespace chre {

/**
 * A container for storing a sequential array of elements. This container
 * resizes dynamically using heap allocations.
 */
template <typename ElementType>
class DynamicVector : private DynamicVectorBase {
 public:
  /**
   * Random-access iterator that points to some element in the container.
   */
  typedef ElementType *iterator;
  typedef const ElementType *const_iterator;
  typedef ElementType value_type;
  typedef size_t size_type;

  /**
   * Default-constructs a dynamic vector.
   */
  DynamicVector();

  /**
   * Move-constructs a dynamic vector from another. The other dynamic vector is
   * left in an empty state.
   *
   * @param other The other vector to move from.
   */
  DynamicVector(DynamicVector<ElementType> &&other);

  /**
   * Move-constructs a dynamic vector from another. The other dynamic vector is
   * left in an empty state.
   */
  DynamicVector &operator=(DynamicVector<ElementType> &&other);

  /**
   * Destructs the objects and releases the memory owned by the vector.
   */
  ~DynamicVector();

  /**
   * Removes all elements from the vector, but does not change the capacity.
   * All iterators and references are invalidated.
   */
  void clear();

  /**
   * Returns a pointer to the underlying buffer. Note that this should not be
   * considered to be persistent as the vector will be moved and resized
   * automatically.
   *
   * @return The pointer to the underlying buffer.
   */
  ElementType *data();

  /**
   * Returns a const pointer to the underlying buffer. Note that this should not
   * be considered to be persistent as the vector will be moved and resized
   * automatically.
   *
   * @return The const pointer to the underlying buffer.
   */
  const ElementType *data() const;

  /**
   * Returns the current number of elements in the vector.
   *
   * @return The number of elements in the vector.
   */
  size_type size() const;

  /**
   * Returns the maximum number of elements that can be stored in this vector
   * without a resize operation.
   *
   * @return The capacity of the vector.
   */
  size_type capacity() const;

  /**
   * Determines whether the vector is empty or not.
   *
   * @return true if the vector is empty.
   */
  bool empty() const;

  /**
   * Erases the last element in the vector. Invalid to call on an empty vector.
   *
   * Invalidates any references to back() and end()/cend().
   */
  void pop_back();

  /**
   * Copy- or move-constructs an element onto the back of the vector. If the
   * vector requires a resize and that allocation fails this function will
   * return false. All iterators and references are invalidated if the container
   * has been resized. Otherwise, only the past-the-end iterator is invalidated.
   *
   * @param The element to push onto the vector.
   * @return true if the element was pushed successfully.
   */
  bool push_back(const ElementType &element);
  bool push_back(ElementType &&element);

  /**
   * Constructs an element onto the back of the vector. All iterators and
   * references are invalidated if the container has been resized. Otherwise,
   * only the past-the-end iterator is invalidated.
   *
   * @param The arguments to the constructor
   * @return true if the element is constructed successfully.
   */
  template <typename... Args>
  bool emplace_back(Args &&... args);

  /**
   * Obtains an element of the vector given an index. It is illegal to index
   * this vector out of bounds and the user of the API must check the size()
   * function prior to indexing this vector to ensure that they will not read
   * out of bounds.
   *
   * @param The index of the element.
   * @return The element.
   */
  ElementType &operator[](size_type index);

  /**
   * Obtains a const element of the vector given an index. It is illegal to
   * index this vector out of bounds and the user of the API must check the
   * size() function prior to indexing this vector to ensure that they will not
   * read out of bounds.
   *
   * @param The index of the element.
   * @return The element.
   */
  const ElementType &operator[](size_type index) const;

  /**
   * Compares two vectors for equality. It will compare the vector sizes and
   * return false if those are different; if not, it will compare the contents
   * of the vectors element-by-element. The operator == should be defined and
   * meaningful for the vector's element type.
   *
   * @param Right-hand side vector to compared with.
   * @return true if two vectors are equal, false otherwise.
   */
  bool operator==(const DynamicVector<ElementType> &other) const;

  /**
   * Resizes the vector to a new capacity returning true if allocation was
   * successful. If the new capacity is smaller than the current capacity,
   * the operation is a no-op and true is returned. If a memory allocation
   * fails, the contents of the vector are not modified and false is returned.
   * This is intended to be similar to the reserve function of the std::vector.
   * All iterators and references are invalidated unless the container did not
   * resize.
   *
   * @param newCapacity The new capacity of the vector.
   * @return true if the resize operation was successful.
   */
  bool reserve(size_type newCapacity);

  /**
   * Resizes the vector to a new size. If the new capacity is smaller than the
   * current size, the extraneous objects at the end are destructed. If the new
   * capacity is larger than the current size, the new objects are
   * default-constructed.
   *
   * @param newSize The new size of the vector.
   * @return true if the resize operation was successful.
   */
  bool resize(size_type newSize);

  /**
   * Inserts an element into the vector at a given index. If a resize of the
   * vector is required and the allocation fails, false will be returned. This
   * will shift all vector elements after the given index one position backward
   * in the list. The supplied index must be <= the size of the vector. It is
   * not possible to have a sparse list of items. If the index is > the current
   * size of the vector, false will be returned. All iterators and references
   * to and after the indexed element are invalidated. Iterators and references
   * to before the indexed elements are unaffected if the container did not
   * resize.
   *
   * @param index The index to insert an element at.
   * @param element The element to insert.
   * @return Whether or not the insert operation was successful.
   */
  bool insert(size_type index, const ElementType &element);
  bool insert(size_type index, ElementType &&element);

  /**
   * Removes an element from the vector given an index. All elements after the
   * indexed one are moved forward one position. The destructor is invoked on
   * on the invalid item left at the end of the vector. The index passed in
   * must be less than the size() of the vector. If the index is greater than or
   * equal to the size no operation is performed. All iterators and references
   * to and after the indexed element are invalidated.
   *
   * @param index The index to remove an element at.
   */
  void erase(size_type index);

  /**
   * Searches the vector for an element.
   *
   * @param element The element to comare against.
   * @return The index of the element found. If the return is equal to size()
   *         then the element was not found.
   */
  size_type find(const ElementType &element) const;

  /**
   * Swaps the location of two elements stored in the vector. The indices
   * passed in must be less than the size() of the vector. If the index is
   * greater than or equal to the size, no operation is performed. All
   * iterators and references to these two indexed elements are invalidated.
   *
   * @param index0 The index of the first element
   * @param index1 The index of the second element
   */
  void swap(size_type index0, size_type index1);

  /**
   * Returns a reference to the first element in the vector. It is illegal to
   * call this on an empty vector.
   *
   * @return The first element in the vector.
   */
  ElementType &front();

  /**
   * Returns a const reference to the first element in the vector. It is illegal
   * to call this on an empty vector.
   *
   * @return The first element in the vector.
   */
  const ElementType &front() const;

  /**
   * Returns a reference to the last element in the vector. It is illegal to
   * call this on an empty vector.
   *
   * @return The last element in the vector.
   */
  ElementType &back();

  /**
   * Returns a const reference to the last element in the vector. It is illegal
   * to call this on an empty vector.
   *
   * @return The last element in the vector.
   */
  const ElementType &back() const;

  /**
   * Prepares a vector to push a minimum of one element onto the back. The
   * vector may be resized if required. The capacity of the vector increases
   * with the growth policy of this vector (doubles for each resize for now).
   *
   * @return Whether or not the resize was successful.
   */
  bool prepareForPush();

  /**
   * @return A random-access iterator to the beginning.
   */
  typename DynamicVector<ElementType>::iterator begin();
  typename DynamicVector<ElementType>::const_iterator begin() const;
  typename DynamicVector<ElementType>::const_iterator cbegin() const;

  /**
   * @return A random-access iterator to the end.
   */
  typename DynamicVector<ElementType>::iterator end();
  typename DynamicVector<ElementType>::const_iterator end() const;
  typename DynamicVector<ElementType>::const_iterator cend() const;

 private:
  /**
   * Prepares the vector for insertion - upon successful return, the memory at
   * the given index will be allocated but uninitialized
   *
   * @param index
   * @return true
   */
  bool prepareInsert(size_t index);

  /**
   * Performs the reserve operation for DynamicVector when ElementType is a
   * trivial type. See {@link DynamicVector::reserve} for the rest of the
   * details.
   */
  bool doReserve(size_type newCapacity, std::true_type);

  /**
   * Performs the reserve operation for DynamicVector when ElementType is a
   * non-trivial type. See {@link DynamicVector::reserve} for the rest of the
   * details.
   */
  bool doReserve(size_type newCapacity, std::false_type);

  /**
   * Performs the prepare for push operation for DynamicVector when ElementType
   * is a trivial type. See {@link DynamicVector::prepareForPush} for the rest
   * of the details.
   */
  bool doPrepareForPush(std::true_type);

  /**
   * Performs the prepare for push operation for DynamicVector when ElementType
   * is a non-trivial type. See {@link DynamicVector::prepareForPush} for the
   * rest of the details.
   */
  bool doPrepareForPush(std::false_type);

  /**
   * Performs the erase operation for DynamicVector when ElementType is a
   * trivial type. See {@link DynamicVector::erase} for the rest of the details.
   */
  void doErase(size_type index, std::true_type);

  /**
   * Performs the erase operation for DynamicVector when ElementType is a
   * non-trivial type. See {@link DynamicVector::erase} for the rest of the
   * details.
   */
  void doErase(size_type index, std::false_type);

  /**
   * Performs the push back operation for DynamicVector when ElementType is a
   * trivial type. See {@link DynamicVector::push_back} for the rest of the
   * details.
   */
  bool doPushBack(const ElementType &element, std::true_type);

  /**
   * Performs the push back operation for DynamicVector when ElementType is a
   * non-trivial type. See {@link DynamicVector::push_back} for the rest of the
   * details.
   */
  bool doPushBack(const ElementType &element, std::false_type);
};

}  // namespace chre

#include "chre/util/dynamic_vector_impl.h"

#endif  // CHRE_UTIL_DYNAMIC_VECTOR_H_