/*************************************************************************
 *
 * HTCd - Copyright (C) 1998-2006 Henrik Rydberg
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

#ifndef MVECH
#define MVECH

#include <malloc.h>
#include <string.h>
#include <new>

const int mv_mincaps=16;

template <class T> class mrvec {
public:
  typedef T* iterator;
  typedef const T* const_iterator;
  
  mrvec():
    map((T*)malloc(mv_mincaps*sizeof(T))),dim(0),caps(mv_mincaps) {}
  mrvec(int n):
    map((T*)malloc(mv_mincaps*sizeof(T))),dim(0),caps(mv_mincaps) { resize(n); }
  ~mrvec() { free(map); }

  int size() const { return dim; }
  int capacity() const { return caps; }
  
  bool empty() const { return dim==0; }
  bool nempty() const { return dim!=0; }
  
  T& at(int pos) { return map[pos]; }
  const T& at(int pos) const { return map[pos]; }

  T& operator[](int pos) { return map[pos]; }
  const T& operator[](int pos) const { return map[pos]; }
  
  iterator begin() { return map; }
  const_iterator begin() const { return map; }
  
  iterator end() { return map+dim; }
  const_iterator end() const { return map+dim; }
  
  T& front() { return map[0]; }
  const T& front() const { return map[0]; }

  T& back() { return map[dim?dim-1:0]; }
  const T& back() const { return map[dim?dim-1:0]; }
  
  ////////////////////////////////////////////////////////////////
  
  void clear() { dim=0; }
  
  iterator insert(iterator it,const T& s) {
    int pos=it-map; ins(pos,1); return &(map[pos]=s);
  }
  void insert(iterator it,int n,const T& s) {
    int pos=it-map; ins(pos,n); while(n--) map[pos++]=s;
  }
  void insert(iterator it,const_iterator p,const_iterator e) {
    int pos=it-map; ins(pos,e-p); while(p<e) map[pos++]=*p++;
  }
  iterator erase(iterator it) {
    int pos=it-map; ins(pos+1,-1); return map+pos;
  }

  ////////////////////////////////////////////////////////////////
  
  void reserve(int n) {
    if(caps<n) { while(caps<n) caps<<=1; map=(T*)realloc(map,caps*sizeof(T)); }
  }
  void resize(int n) { reserve(n); dim=n; }

  void push_back(const T& s) { reserve(dim+1); map[dim++]=s; }
  void pop_back(const T& s) { if(dim) --dim; }

  ////////////////////////////////////////////////////////////////

protected:
  mrvec(const mrvec&) {}
  void operator=(const mrvec&) {}

  void ins(int pos,int n) {
    if(n) { reserve(dim+n); memmove(map+pos+n,map+pos,(dim-pos)*sizeof(T)); dim+=n; }
  }

  T* map;
  int dim,caps;
};

template <class T> class msvec : public mrvec<T> {
public:
  using mrvec<T>::map;
  using mrvec<T>::dim;
  typedef typename mrvec<T>::iterator iterator;
  typedef typename mrvec<T>::const_iterator const_iterator;
  
  msvec() : mrvec<T>() {}
  msvec(int n) : mrvec<T>(n) { for(int i=0;i<dim;i++) new (map+i) T(); }
  ~msvec() { while(dim) map[--dim].~T(); }

  ////////////////////////////////////////////////////////////////
  
  void clear() { while(dim) map[--dim].~T(); }
  
  iterator insert(iterator it,const T& s) {
    int pos=it-map; mrvec<T>::ins(pos,1); return new(map+pos) T(s);
  }
  void insert(iterator it,int n,const T& s) {
    int pos=it-map; mrvec<T>::ins(pos,n); while(n--) new(map+pos++) T(s);
  }
  void insert(iterator it,const_iterator p,const_iterator e) {
    int pos=it-map; mrvec<T>::ins(pos,e-p); while(p<e) new(map+pos++) T(*p++);
  }
  iterator erase(iterator it) {
    it->~T(); int pos=it-map; mrvec<T>::ins(pos+1,-1); return map+pos;
  }

  void push_back(const T& s) { mrvec<T>::reserve(dim+1); new(map+dim++) T(s); }
  void pop_back(const T& s) { if(dim) map[--dim].~T(); }

  ////////////////////////////////////////////////////////////////

  void resize(int n) {
    while(dim>n) map[--dim].~T();
    mrvec<T>::reserve(n);
    while(dim<n) new (map+dim++) T();
  }
  
protected:
  msvec(const msvec&) {}
  void operator=(const msvec&) {}
};

#endif