// Copyright 2017-2019 VMware, Inc.
// SPDX-License-Identifier: BSD-2-Clause
//
// The BSD-2 license (the License) set forth below applies to all parts of the
// Cascade project.  You may not use this file except in compliance with the
// License.
//
// BSD-2 License
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS AS IS AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef CASCADE_SRC_COMMON_VECTOR_H
#define CASCADE_SRC_COMMON_VECTOR_H

#include <algorithm>
#include <cassert>
#include <stddef.h>
#include <stdint.h>

namespace cascade {

// This class a space-optimized implementation of std::vector. It assumes no
// more than 2^16 elements, and won't over-provision when a call to resize
// exceeds capacity.

template <typename T>
class Vector {
  public:
    typedef size_t size_type;
    typedef ptrdiff_t	difference_type;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T* iterator;
    typedef const T* const_iterator; 
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T	value_type;

    Vector();
    Vector(size_type n, const value_type& v = value_type());
    Vector(const Vector& rhs);
    Vector(Vector&& rhs);
    Vector& operator=(Vector rhs);
    ~Vector();

    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;

    size_type size() const;
    void resize(size_type n, const value_type& v = value_type());
    size_type capacity() const;
    bool empty() const;
    void reserve(size_type n);

    reference operator[](size_t idx);
    const_reference operator[](size_t idx) const;

    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;
    pointer data();
    const_pointer data() const;

    void push_back(const value_type& v);
    void pop_back();

    iterator insert(iterator itr, const value_type& v);
    iterator insert(iterator itr, size_type n, const value_type& v);
    template <typename Itr>
    iterator insert(iterator itr, Itr rb, Itr re);

    iterator erase(iterator itr);

    void swap(Vector& rhs);
    void clear();

  private:
    T* ts_;
    uint16_t size_;
    uint16_t capacity_;    
};

template <typename T>
inline Vector<T>::Vector() {
  ts_ = nullptr; 
  size_ = 0;
  capacity_ = 0;
}

template <typename T>
inline Vector<T>::Vector(size_t n, const value_type& val) : Vector() {
  insert(end(), n, val);
}

template <typename T>
inline Vector<T>::Vector(const Vector& rhs) : Vector() {
  insert(end(), rhs.begin(), rhs.end());
}

template <typename T>
inline Vector<T>::Vector(Vector&& rhs) : Vector() {
  swap(rhs);
}

template <typename T>
inline Vector<T>& Vector<T>::operator=(Vector rhs) {
  swap(rhs);
  return *this;
}

template <typename T>
inline Vector<T>::~Vector() {
  if (ts_ != nullptr) {
    delete[] ts_;
  }
}

template <typename T>
inline typename Vector<T>::iterator Vector<T>::begin() {
  return ts_;
}

template <typename T>
inline typename Vector<T>::const_iterator Vector<T>::begin() const {
  return ts_;
}

template <typename T>
inline typename Vector<T>::iterator Vector<T>::end() {
  return ts_ + size_;
}

template <typename T>
inline typename Vector<T>::const_iterator Vector<T>::end() const {
  return ts_ + size_;
}

template <typename T>
inline typename Vector<T>::size_type Vector<T>::size() const {
  return size_;
}

template <typename T>
inline void Vector<T>::resize(size_type n, const value_type& v) {
  assert(n <= static_cast<size_t>(0xffffu));
  if (n <= size_) {
    size_ = n;
  } else {
    insert(end(), n - size_, v);
  }
}

template <typename T>
inline typename Vector<T>::size_type Vector<T>::capacity() const {
  return capacity_;
}

template <typename T>
inline bool Vector<T>::empty() const {
  return size_ == 0;
}

template <typename T>
inline void Vector<T>::reserve(size_type n) {
  assert(n <= static_cast<size_t>(0xffffu));
  if (capacity_ >= n) {
    return;
  }
  auto new_ts = new T[n];
  if (ts_ != nullptr) {
    std::copy(ts_, ts_ + size_, new_ts);
    delete[] ts_;
  }
  ts_ = new_ts; 
  capacity_ = n;
}

template <typename T>
inline typename Vector<T>::reference Vector<T>::operator[](size_t idx) {
  assert(idx < size_);
  return ts_[idx];
}

template <typename T>
inline typename Vector<T>::const_reference Vector<T>::operator[](size_t idx) const {
  assert(idx < size_);
  return ts_[idx];
}

template <typename T>
inline typename Vector<T>::reference Vector<T>::front() {
  assert(size_ > 0);
  return ts_[0];
}

template <typename T>
inline typename Vector<T>::const_reference Vector<T>::front() const {
  assert(size_ > 0);
  return ts_[0];
}

template <typename T>
inline typename Vector<T>::reference Vector<T>::back() {
  assert(size_ > 0);
  return ts_[size_ - 1];
}

template <typename T>
inline typename Vector<T>::const_reference Vector<T>::back() const {
  assert(size_ > 0);
  return ts_[size_ - 1];
}

template <typename T>
inline typename Vector<T>::pointer Vector<T>::data() {
  return ts_;
}

template <typename T>
inline typename Vector<T>::const_pointer Vector<T>::data() const {
  return ts_;
}

template <typename T>
inline void Vector<T>::push_back(const value_type& v) {
  if (size_ < capacity_) {
    ts_[size_++] = v;
  } else {
    insert(end(), v);
  }
}

template <typename T>
inline void Vector<T>::pop_back() {
  assert(size_ > 0);
  --size_;
}

template <typename T>
inline typename Vector<T>::iterator Vector<T>::insert(iterator itr, const value_type& v) {
  assert(itr >= begin());
  assert(itr <= end());

  if (itr == nullptr) {
    reserve(1);
    ts_[0] = v;
    size_ = 1;
    return end();
  }

  const auto delta = itr - ts_;
  reserve(size_ + 1);
  itr = begin() + delta;   

  std::copy(itr, end(), itr + 1);
  *itr++ = v;
  ++size_;

  return itr;
}

template <typename T>
inline typename Vector<T>::iterator Vector<T>::insert(iterator itr, size_type n, const value_type& v) {
  assert(itr >= begin());
  assert(itr <= end());

  if (itr == nullptr) {
    reserve(n);
    std::fill_n(begin(), n, v);
    size_ = n;
    return end();
  }

  const auto delta = itr - ts_;
  reserve(size_ + n);
  itr = begin() + delta;

  std::copy(itr, end(), itr+n);
  std::fill_n(itr, n, v);
  size_ += n;

  return itr + n;
}

template <typename T>
template <typename Itr>
inline typename Vector<T>::iterator Vector<T>::insert(iterator itr, Itr rb, Itr re) {
  assert(itr >= begin());
  assert(itr <= end());
  assert(re >= rb);

  const size_type n = re-rb;
  if (n == 0) {
    return itr;
  }

  if (itr == nullptr) {
    reserve(n);
    std::copy(rb, re, begin());
    size_ = n;
    return end();
  }

  const auto delta = itr - ts_;
  reserve(size_ + n);
  itr = begin() + delta;

  std::copy(itr, end(), itr+n);
  std::copy(rb, re, itr);
  size_ += n;

  return itr + n;
}

template <typename T>
inline typename Vector<T>::iterator Vector<T>::erase(iterator itr) {
  assert(itr >= begin());
  assert(itr < end());

  std::copy(itr + 1, end(), itr);
  --size_; 
  return itr;
}

template <typename T>
inline void Vector<T>::swap(Vector& rhs) {
  std::swap(ts_, rhs.ts_);
  std::swap(size_, rhs.size_);
  std::swap(capacity_, rhs.capacity_);
}

template <typename T>
inline void Vector<T>::clear() {
  size_ = 0;
}

} // namespace cascade

#endif

