// An implementation of a simplified STL Vector
// This one uses uninitialized alloc and placement new operator
// George F. Riley, Georgia Tech, Fall 2009

template<class T> class GFRVec 
{
public:
  GFRVec() : first(0), last(0), end(0) {}
  GFRVec(size_t n) 
    { // Create a GFRVec with "n" copies of T, with default constructor
      first = (T*)malloc(n * sizeof(T));
      for (size_t i = 0; i < n; ++i)
        {
          new (&first[i]) T();
        }
      last = first + n;
      end = last;
    }
  GFRVec(size_t n, const T& t)
    { // Create a GFRVec with "n" copies of t
      first = (T*)malloc(n * sizeof(T));
      for (size_t i = 0; i < n; ++i)
        { // Use copy constructor to populate
          new (&first[i]) T(t);
        }
      last = first + n;
      end = last;
    }
  GFRVec(const GFRVec& c)
    { // Copy Constructor
      first = (T*)malloc(c.size() * sizeof(T));
      for (size_t i = 0; i < c.size(); ++i)
        {
          new (&first[i]) T(c[i]); // Copy elements
        }
      
      last = first + c.size();
      end = last;
    }
  ~GFRVec()
    { // Destructor, remove all elements
      clear();
      free(first);
    }
  GFRVec& operator=(const GFRVec& rhs)
    { // Assignment operator
      if (this == &rhs) return *this; // Self assignment
      if (!empty())
        {
          // Force destructors on the existing elements, in reverse order
          for (int i = size() - 1; i >= 0; --i)
            {
              first[i].~T();
            }
        }
      free(first);
      first = (T*)malloc(rhs.size() * sizeof(T));
      for (size_t i = 0; i < rhs.size(); ++i)
        {
          new (&first[i]) T(rhs[i]); // Copy the elements
        }
      last = first + rhs.size();
      end = last;
    }
  T& operator[](size_t i) const
    { // Indexing operator
      return first[i];
    }
  T& back() const
    { // Return last element
      return first[size()-1];
    }
  T& front() const
    { // Return last element
      return first[0];
    }
  void pop_back()
    { // Remove last element
      last--;
      first[size()].~T(); // Call destructor on just popped object
    }
  void push_back(const T& t)
    { // Add new element
      if (last != end)
        { // Room for new object without re-allocating
          new (&first[size()]) T(t);
          last++;
        }
      else
        { // Need to re-allocate
          T* tmp = (T*)malloc((size() + 1) * sizeof(T));
          for (size_t i = 0; i < size(); ++i)
            { // Copy old elements
              new (&tmp[i]) T(first[i]);
            }
          new (&tmp[size()]) T(t);
          for (int i = size() - 1; i >= 0; --i)
            { // Destroy old elements
              first[i].~T();
            }
          last = tmp + (last - first) + 1;
          end = last;
          free(first);
          first = tmp;
        }
    }
  size_t size() const
    { // Number of elements in the vector
      return last - first;
    }
  void reserve(size_t n)
    { // Reserve space for "n" elements
      if (n <= (end-first)) return; // Less than already reserved
      T* tmp = (T*)malloc(n * sizeof(T));
      for (size_t i = 0; i < size(); ++i)
        { // Copy elements to new space
          new (&tmp[i]) T(first[i]);
        }
      last = tmp + (last - first);
      free(first);
      first = tmp;
      end = first + n;
    }
  void clear()
  { // Erase all elements
    while(size()) pop_back();
    free(first);
    first = 0;
    last = 0;
    end = 0;
  }
  
private:
  T* first; // Initial element
  T* last;  // Last element
  T* end;   // End of allocated storage
};