utility/PtrVector.hpp

/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you 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 QUICKSTEP_UTILITY_PTR_VECTOR_HPP_
#define QUICKSTEP_UTILITY_PTR_VECTOR_HPP_

#include <iterator>
#include <vector>

#include "utility/Macros.hpp"

#include "glog/logging.h"

namespace quickstep {

/** \addtogroup Utility
 *  @{
 */

/**
 * @brief A vector of pointers to objects, which are automatically deleted when
 *        the PtrVector goes out of scope.
 **/
template <typename T, bool null_allowed = false>
class PtrVector {
 public:
  // TODO(chasseur): Attempt some template magic to get rid of the duplicated
  // code between iterator classes.

  /**
   * @brief Iterator over the contents of a PtrVector.
   * @warning If null_allowed is true, then always check that isNull() is false
   *          before attempting to dereference.
   **/
  class PtrVectorIterator : public std::iterator<std::random_access_iterator_tag, T> {
   public:
    typedef typename std::iterator<std::random_access_iterator_tag, T>::difference_type difference_type;

    PtrVectorIterator() {
    }

    PtrVectorIterator(const PtrVectorIterator& other)
        : internal_iterator_(other.internal_iterator_) {
    }

    PtrVectorIterator& operator=(const PtrVectorIterator& other) {
      if (this != &other) {
        internal_iterator_ = other.internal_iterator_;
      }
      return *this;
    }

    // Comparisons.
    inline bool operator==(const PtrVectorIterator& other) const {
      return internal_iterator_ == other.internal_iterator_;
    }

    inline bool operator!=(const PtrVectorIterator& other) const {
      return internal_iterator_ != other.internal_iterator_;
    }

    inline bool operator<(const PtrVectorIterator& other) const {
      return internal_iterator_ < other.internal_iterator_;
    }

    inline bool operator<=(const PtrVectorIterator& other) const {
      return internal_iterator_ <= other.internal_iterator_;
    }

    inline bool operator>(const PtrVectorIterator& other) const {
      return internal_iterator_ > other.internal_iterator_;
    }

    inline bool operator>=(const PtrVectorIterator& other) const {
      return internal_iterator_ >= other.internal_iterator_;
    }

    // Increment/decrement.
    inline PtrVectorIterator& operator++() {
      ++internal_iterator_;
      return *this;
    }

    PtrVectorIterator operator++(int) {
      PtrVectorIterator result(*this);
      ++(*this);
      return result;
    }

    inline PtrVectorIterator& operator--() {
      --internal_iterator_;
      return *this;
    }

    PtrVectorIterator operator--(int) {
      PtrVectorIterator result(*this);
      --(*this);
      return result;
    }

    // Compound assignment.
    inline PtrVectorIterator& operator+=(difference_type n) {
      internal_iterator_ += n;
      return *this;
    }

    inline PtrVectorIterator& operator-=(difference_type n) {
      internal_iterator_ -= n;
      return *this;
    }

    // Note: + operator with difference_type on the left is defined out-of-line.
    PtrVectorIterator operator+(difference_type n) const {
      return PtrVectorIterator(internal_iterator_ + n);
    }

    PtrVectorIterator operator-(difference_type n) const {
      return PtrVectorIterator(internal_iterator_ - n);
    }

    difference_type operator-(const PtrVectorIterator &other) const {
      return PtrVectorIterator(internal_iterator_ - other.internal_iterator_);
    }

    // Dereference.
    /**
     * @brief Check whether the element at the current iterator position is
     *        NULL.
     * @return Whether the element at the current iterator position is NULL.
     **/
    inline bool isNull() const {
      return (null_allowed && (*internal_iterator_ == nullptr));
    }

    /**
     * @brief Delete the element at the current iterator position and replace
     *        it with a new value.
     *
     * @param value_ptr The new value to place at the current position. The
     *        PtrVector takes ownership of the pointed-to value.
     **/
    void replaceValue(T *value_ptr) {
      if (!null_allowed) {
        DCHECK(value_ptr != nullptr);
      }
      if (!null_allowed || (*internal_iterator_ != nullptr)) {
        delete *internal_iterator_;
      }
      *internal_iterator_ = value_ptr;
    }

    /**
     * @brief Replace the element at the current iterator position, and
     *        release ownership and return the original value.
     *
     * @param value_ptr The new value to place at the current position. The
     *        PtrVector takes ownership of the pointed-to value.
     * @return A pointer to the original value at the current position. The
     *         PtrVector no longer owns the pointed-to object, which should now
     *         be managed by the caller.
     **/
    T* releaseAndReplaceElement(T *value_ptr) {
      if (!null_allowed) {
        DCHECK(value_ptr != nullptr);
      }
      T *original_value = *internal_iterator_;
      *internal_iterator_ = value_ptr;
      return original_value;
    }

    inline T& operator*() const {
      if (null_allowed) {
        DCHECK(!isNull());
      }
      return **internal_iterator_;
    }

    inline T* operator->() const {
      if (null_allowed) {
        DCHECK(!isNull());
      }
      return *internal_iterator_;
    }

    // Offset dereference. Potentially unsafe if null_allowed.
    T& operator[](difference_type n) const {
      if (null_allowed) {
        DCHECK(internal_iterator_[n] != nullptr);
      }
      return *(internal_iterator_[n]);
    }

   private:
    explicit PtrVectorIterator(const typename std::vector<T*>::iterator &internal_iterator)
        : internal_iterator_(internal_iterator) {
    }

    typename std::vector<T*>::iterator internal_iterator_;

    friend class PtrVector;
    friend class PtrVectorConstIterator;
  };

  /**
   * @brief Const iterator over the contents of a PtrVector.
   * @warning If null_allowed is true, then always check that isNull() is false
   *          before attempting to dereference.
   **/
  class PtrVectorConstIterator : public std::iterator<std::input_iterator_tag, const T> {
   public:
    typedef typename std::iterator<std::input_iterator_tag, T>::difference_type difference_type;

    PtrVectorConstIterator() {
    }

    PtrVectorConstIterator(const PtrVectorConstIterator& other)
        : internal_iterator_(other.internal_iterator_) {
    }

    PtrVectorConstIterator(const PtrVectorIterator& other)  // NOLINT(runtime/explicit) - allow implicit conversion
        : internal_iterator_(other.internal_iterator_) {
    }

    PtrVectorConstIterator& operator=(const PtrVectorConstIterator& other) {
      if (this != &other) {
        internal_iterator_ = other.internal_iterator_;
      }
      return *this;
    }

    PtrVectorConstIterator& operator=(const PtrVectorIterator& other) {
      internal_iterator_ = other.internal_iterator_;
      return *this;
    }

    // Comparisons.
    inline bool operator==(const PtrVectorConstIterator& other) const {
      return internal_iterator_ == other.internal_iterator_;
    }

    inline bool operator!=(const PtrVectorConstIterator& other) const {
      return internal_iterator_ != other.internal_iterator_;
    }

    inline bool operator<(const PtrVectorConstIterator& other) const {
      return internal_iterator_ < other.internal_iterator_;
    }

    inline bool operator<=(const PtrVectorConstIterator& other) const {
      return internal_iterator_ <= other.internal_iterator_;
    }

    inline bool operator>(const PtrVectorConstIterator& other) const {
      return internal_iterator_ > other.internal_iterator_;
    }

    inline bool operator>=(const PtrVectorConstIterator& other) const {
      return internal_iterator_ >= other.internal_iterator_;
    }

    // Increment/decrement.
    inline PtrVectorConstIterator& operator++() {
      ++internal_iterator_;
      return *this;
    }

    PtrVectorConstIterator operator++(int) {
      PtrVectorConstIterator result(*this);
      ++(*this);
      return result;
    }

    inline PtrVectorConstIterator& operator--() {
      --internal_iterator_;
      return *this;
    }

    PtrVectorConstIterator operator--(int) {
      PtrVectorConstIterator result(*this);
      --(*this);
      return result;
    }

    // Compound assignment.
    inline PtrVectorConstIterator& operator+=(difference_type n) {
      internal_iterator_ += n;
      return *this;
    }

    inline PtrVectorConstIterator& operator-=(difference_type n) {
      internal_iterator_ -= n;
      return *this;
    }

    // Note: + operator with difference_type on the left is defined out-of-line.
    PtrVectorConstIterator operator+(difference_type n) const {
      return PtrVectorConstIterator(internal_iterator_ + n);
    }

    PtrVectorConstIterator operator-(difference_type n) const {
      return PtrVectorConstIterator(internal_iterator_ - n);
    }

    difference_type operator-(const PtrVectorConstIterator &other) const {
      return PtrVectorConstIterator(internal_iterator_ - other.internal_iterator_);
    }

    // Dereference.
    /**
     * @brief Check whether the element at the current iterator position is
     *        NULL.
     * @return Whether the element at the current iterator position is NULL.
     **/
    inline bool isNull() const {
      return (null_allowed && (*internal_iterator_ == nullptr));
    }

    inline const T& operator*() const {
      if (null_allowed) {
        DCHECK(!isNull());
      }
      return **internal_iterator_;
    }

    inline const T* operator->() const {
      if (null_allowed) {
        DCHECK(!isNull());
      }
      return *internal_iterator_;
    }

    // Offset dereference. Potentially unsafe if null_allowed.
    const T& operator[](difference_type n) const {
      if (null_allowed) {
        DCHECK(internal_iterator_[n] != nullptr);
      }
      return *(internal_iterator_[n]);
    }

   private:
    explicit PtrVectorConstIterator(const typename std::vector<T*>::const_iterator &internal_iterator)
        : internal_iterator_(internal_iterator) {
    }

    typename std::vector<T*>::const_iterator internal_iterator_;

    friend class PtrVector;
  };

  /**
   * @brief Input iterator over the contents of a PtrVector which automatically
   *        skips over NULL entries.
   **/
  class PtrVectorConstSkipIterator : public std::iterator<std::input_iterator_tag, const T> {
   public:
    typedef typename std::iterator<std::input_iterator_tag, T>::difference_type difference_type;

    PtrVectorConstSkipIterator()
        : parent_vector_(nullptr) {
    }

    PtrVectorConstSkipIterator(const PtrVectorConstSkipIterator& other)
        : internal_iterator_(other.internal_iterator_),
          parent_vector_(other.parent_vector_) {
    }

    PtrVectorConstSkipIterator& operator=(const PtrVectorConstSkipIterator& other) {
      if (this != &other) {
        internal_iterator_ = other.internal_iterator_;
        parent_vector_ = other.parent_vector_;
      }
      return *this;
    }

    // Comparisons.
    inline bool operator==(const PtrVectorConstSkipIterator& other) const {
      return internal_iterator_ == other.internal_iterator_;
    }

    inline bool operator!=(const PtrVectorConstSkipIterator& other) const {
      return internal_iterator_ != other.internal_iterator_;
    }

    inline bool operator<(const PtrVectorConstSkipIterator& other) const {
      return internal_iterator_ < other.internal_iterator_;
    }

    inline bool operator<=(const PtrVectorConstSkipIterator& other) const {
      return internal_iterator_ <= other.internal_iterator_;
    }

    inline bool operator>(const PtrVectorConstSkipIterator& other) const {
      return internal_iterator_ > other.internal_iterator_;
    }

    inline bool operator>=(const PtrVectorConstSkipIterator& other) const {
      return internal_iterator_ >= other.internal_iterator_;
    }

    // Increment/decrement.
    inline PtrVectorConstSkipIterator& operator++() {
      ++internal_iterator_;
      DCHECK(parent_vector_ != nullptr);
      while (internal_iterator_ != parent_vector_->end()) {
        if (*internal_iterator_ != nullptr) {
          break;
        }
        ++internal_iterator_;
      }
      return *this;
    }

    PtrVectorConstSkipIterator operator++(int) {
      PtrVectorConstSkipIterator result(*this);
      ++(*this);
      return result;
    }

    inline const T& operator*() const {
      return **internal_iterator_;
    }

    inline const T* operator->() const {
      return *internal_iterator_;
    }

   private:
    explicit PtrVectorConstSkipIterator(const typename std::vector<T*>::const_iterator &internal_iterator,
                                        const std::vector<T*> *parent_vector)
        : internal_iterator_(internal_iterator), parent_vector_(parent_vector) {
      DCHECK(parent_vector_ != nullptr);
      while ((internal_iterator_ != parent_vector_->end()) && (*internal_iterator_ == nullptr)) {
        ++internal_iterator_;
      }
    }

    typename std::vector<T*>::const_iterator internal_iterator_;
    const std::vector<T*> *parent_vector_;

    friend class PtrVector;
  };

  typedef typename std::vector<T*>::size_type size_type;
  typedef T value_type;
  typedef PtrVectorIterator iterator;
  typedef PtrVectorConstIterator const_iterator;
  typedef PtrVectorConstSkipIterator const_skip_iterator;

  PtrVector() {
  }

  ~PtrVector() {
    for (typename std::vector<T*>::iterator it = internal_vector_.begin();
         it != internal_vector_.end();
         ++it) {
      if (!null_allowed || (*it != nullptr)) {
        delete *it;
      }
    }
  }

  inline size_type size() const {
    return internal_vector_.size();
  }

  inline size_type max_size() const {
    return internal_vector_.max_size();
  }

  inline size_type capacity() const {
    return internal_vector_.capacity();
  }

  inline bool empty() const {
    return internal_vector_.empty();
  }

  /**
   * @brief Check whether this vector contains any actual objects. Unlike
   *        empty(), this returns true if the vector has some elements, but
   *        they are all NULL.
   *
   * @return Whether this PtrVector is empty of actual objects.
   **/
  bool emptyNullCheck() const {
    if (null_allowed) {
      for (typename std::vector<T*>::const_iterator it = internal_vector_.begin();
           it != internal_vector_.end();
           ++it) {
        if (*it != nullptr) {
          return false;
        }
      }
      return true;
    } else {
      return empty();
    }
  }

  inline void reserve(size_type n) {
    internal_vector_.reserve(n);
  }

  // Iterators
  iterator begin() {
    return iterator(internal_vector_.begin());
  }

  iterator end() {
    return iterator(internal_vector_.end());
  }

  const_iterator begin() const {
    return const_iterator(internal_vector_.begin());
  }

  const_iterator end() const {
    return const_iterator(internal_vector_.end());
  }

  /**
   * @brief Get an iterator at the beginning of this PtrVector which
   *        automatically skips over NULL entries.
   *
   * @return An iterator at the beginning of this PtrVector which automatically
   *         skips over NULL entries.
   **/
  const_skip_iterator begin_skip() const {
    return const_skip_iterator(internal_vector_.begin(), &internal_vector_);
  }

  /**
   * @brief Get an iterator at one past the end of this PtrVector which
   *        automatically skips over NULL entries.
   *
   * @return An iterator at one past the end of this PtrVector which
   *         automatically skips over NULL entries.
   **/
  const_skip_iterator end_skip() const {
    return const_skip_iterator(internal_vector_.end(), &internal_vector_);
  }

  /**
   * @brief Check whether the element at the specified position is NULL.
   *
   * @param n The position in this PtrVector to check.
   * @return Whether the element at position n is NULL.
   **/
  inline bool elementIsNull(const size_type n) const {
    if (null_allowed && (internal_vector_[n] == nullptr)) {
      return true;
    } else {
      return false;
    }
  }

  /**
   * @brief Check whether the element at the specified position is NULL.
   * @note This is similar to elementIsNull(), but uses std::vector::at(),
   *       which throws std::out_of_range exceptions.
   *
   * @param n The position in this PtrVector to check.
   * @return Whether the element at position n is NULL.
   **/
  inline bool elementIsNullAt(const size_type n) const {
    if (null_allowed && (internal_vector_.at(n) == nullptr)) {
      return true;
    } else {
      return false;
    }
  }

  inline T& front() {
    if (null_allowed) {
      typename std::vector<T*>::iterator it = internal_vector_.begin();
      while ((it != internal_vector_.end()) && (*it == nullptr)) {
        ++it;
      }
      return **it;
    } else {
      return *(internal_vector_.front());
    }
  }

  inline const T& front() const {
    if (null_allowed) {
      typename std::vector<T*>::const_iterator it = internal_vector_.begin();
      while ((it != internal_vector_.end()) && (*it == nullptr)) {
        ++it;
      }
      return **it;
    } else {
      return *(internal_vector_.front());
    }
  }

  inline T& back() {
    if (null_allowed) {
      typename std::vector<T*>::reverse_iterator it = internal_vector_.rbegin();
      while ((it != internal_vector_.rend()) && (*it == nullptr)) {
        ++it;
      }
      return **it;
    } else {
      return *(internal_vector_.back());
    }
  }

  inline const T& back() const {
    if (null_allowed) {
      typename std::vector<T*>::const_reverse_iterator it = internal_vector_.rbegin();
      while ((it != internal_vector_.rend()) && (*it == nullptr)) {
        ++it;
      }
      return **it;
    } else {
      return *(internal_vector_.back());
    }
  }

  inline T& operator[](const size_type n) {
    if (null_allowed) {
      DCHECK(!elementIsNull(n));
    }
    return *(internal_vector_[n]);
  }

  inline const T& operator[](const size_type n) const {
    if (null_allowed) {
      DCHECK(!elementIsNull(n));
    }
    return *(internal_vector_[n]);
  }

  inline T& at(const size_type n) {
    if (null_allowed) {
      DCHECK(!elementIsNullAt(n));
    }
    return *(internal_vector_.at(n));
  }

  inline const T& at(const size_type n) const {
    if (null_allowed) {
      DCHECK(!elementIsNullAt(n));
    }
    return *(internal_vector_.at(n));
  }

  inline void push_back(T *value_ptr) {
    if (!null_allowed) {
      DCHECK(value_ptr != nullptr);
    }
    internal_vector_.push_back(value_ptr);
  }

  /**
   * @brief Delete an element at the specified index and replace it with a new
   *        value.
   *
   * @param n The position of the element to replace.
   * @param value_ptr The new value to place at position n. This PtrVector
   *        takes ownership of the pointed-to value.
   **/
  void replaceElement(const size_type n, T *value_ptr) {
    if (!null_allowed) {
      DCHECK(value_ptr != nullptr);
    }
    if (!null_allowed || (internal_vector_[n] != nullptr)) {
      delete internal_vector_[n];
    }
    internal_vector_[n] = value_ptr;
  }

  /**
   * @brief Replace an element at the specified index with a new value, and
   *        release ownership and return the original value.
   *
   * @param n The position of the element to replace.
   * @param value_ptr The new value to place at position n. This PtrVector
   *        takes ownership of the pointed-to value.
   * @return A pointer to the original value at position n. This PtrVector no
   *         longer owns the pointed-to object, which should now be managed
   *         by the caller.
   **/
  T* releaseAndReplaceElement(const size_type n, T *value_ptr) {
    if (!null_allowed) {
      DCHECK(value_ptr != nullptr);
    }
    T *original_value = internal_vector_[n];
    internal_vector_[n] = value_ptr;
    return original_value;
  }

  /**
   * @brief Delete an element and set it to null. Only usable if null_allowed
   *        is true.
   *
   * @param n The position of the element to delete.
   **/
  void deleteElement(const size_type n) {
    DCHECK(null_allowed);
    if (internal_vector_[n] != nullptr) {
      delete internal_vector_[n];
      internal_vector_[n] = nullptr;
    }
  }

  /**
   * @brief Delete the last element and truncate the vector. Only usable if
   *        null_allowed is false.
   **/
  void removeBack() {
    DCHECK(!null_allowed);
    DCHECK(!internal_vector_.empty());
    delete internal_vector_.back();
    internal_vector_.resize(internal_vector_.size() - 1);
  }

  /**
   * @brief Get a const reference to the internal vector of pointers.
   *
   * @return A const reference to the internal vector of pointers.
   **/
  const std::vector<T*>& getInternalVector() const {
    return internal_vector_;
  }

  /**
   * @brief Get a mutable pointer to the internal vector of pointers.
   * @warning Only call this if you really know what you are doing.
   *
   * @return A mutable pointer to the internal vector of pointers.
   **/
  std::vector<T*>* getInternalVectorMutable() {
    return &internal_vector_;
  }

 private:
  std::vector<T*> internal_vector_;

  DISALLOW_COPY_AND_ASSIGN(PtrVector);
};

template <typename T>
typename PtrVector<T>::PtrVectorIterator operator+(
    const typename PtrVector<T>::PtrVectorIterator::difference_type n,
    const typename PtrVector<T>::PtrVectorIterator &it) {
  return it + n;
}

/** @} */

}  // namespace quickstep

#endif  // QUICKSTEP_UTILITY_PTR_VECTOR_HPP_