// Copyright (c) 2003 Nick Mathewson.  See LICENSE for licensing information.
// $Id: vec.h 960 2003-12-22 03:58:20Z nickm $
#ifndef _VEC_H
#define _VEC_H

#include <assert.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>

template <class C>
class vec {
 private:
    vec();

    class Item {
     public:
      int index;
      const vec<C> *v;
      Item() {}
      Item(const vec<C> &vec, int i) : index(i), v(&vec) {}
      const C& getValue() const { return (*v)[index]; }
      bool operator<(const vec<C>::Item &o) const {
        return getValue() < o.getValue();
      }
      bool operator>(const vec<C>::Item &o) const {
        return getValue() > o.getValue();
      }
      bool operator==(const vec<C>::Item &o) const {
        return getValue() == o.getValue();
      }
      ~Item() {}
    };

 protected:
    std::vector<C> rep;

 public:
    explicit vec(int len);
    vec(int len, C val) : rep(len, val) {}
    vec(const vec<C> &other) : rep(other.rep) {}
    template <class D> vec(const vec<D> &other) : rep(other.size()) {
	int sz = rep.size();
	for (int i = 0; i < sz; ++i) {
	    rep[i] = static_cast<C>(other[i]);
	}
    }

    void reset(const C& v) {
      int sz = size();
      for(int i = 0; i < sz; ++i) {
        rep[i] = v;
      }
    }

    int size() const {
	return rep.size();
    }

    vec<C> &operator=(const vec<C>& other) {
	rep = other.rep;
	return *this;
    }

    vec<C> operator+(const vec<C>& other) const {
	return (vec<C>(*this) += other);
    }
    vec<C> operator-(const vec<C>& other) const {
	return (vec<C>(*this) -= other);
    }
    vec<C> operator*(const vec<C>& other) const {
	return (vec<C>(*this) *= other);
    }
    vec<C> operator/(const vec<C>& other) const {
	return (vec<C>(*this) /= other);
    }

    vec<C> operator+(const C& other) const {
	return (vec<C>(*this) += other);
    }
    vec<C> operator-(const C& other) const {
	return (vec<C>(*this) -= other);
    }
    vec<C> operator*(const C& other) const {
	return (vec<C>(*this) *= other);
    }
    vec<C> operator/(const C& other) const {
	return (vec<C>(*this) /= other);
    }

    const C &operator[](int i) const { return rep[i]; }
    C &operator[](int i) { return rep[i]; }

    template<class D>
    vec<C> &operator+=(const vec<D>& other) {
	int sz = rep.size();
	assert(other.size() == sz);
	for (int i = 0; i < sz; ++i) {
	    rep[i] += other.rep[i];
	}
	return *this;
    }
    template<class D>
    vec<C> &operator-=(const vec<D>& other) {
	int sz = rep.size();
	assert(other.size() == sz);
	for (int i = 0; i < sz; ++i) {
	    rep[i] -= other.rep[i];
	}
	return *this;
    }
    template<class D>
    vec<C> &operator*=(const vec<D>& other) {
	int sz = rep.size();
	assert(other.size() == sz);
	for (int i = 0; i < sz; ++i) {
	    rep[i] *= other.rep[i];
	}
	return *this;
    }
    template<class D>
    vec<C> &operator/=(const vec<D> other) {
	int sz = rep.size();
	assert(other.size() == sz);
	for (int i = 0; i < sz; ++i) {
	    rep[i] /= other.rep[i];
	}
	return *this;
    }
    vec<C> operator+=(const C& other) {
	int sz = rep.size();
	for (int i = 0; i < sz; ++i) { rep[i]+=other; }
	return *this;
    }
    vec<C> operator-=(const C& other) {
	int sz = rep.size();
	for (int i = 0; i < sz; ++i) { rep[i]-=other; }
	return *this;
    }
    vec<C> operator*=(const C& other) {
	int sz = rep.size();
	for (int i = 0; i < sz; ++i) { rep[i]*=other; }
	return *this;
    }
    vec<C> operator/=(const C& other) {
	int sz = rep.size();
	for (int i = 0; i < sz; ++i) { rep[i]/=other; }
	return *this;
    }

    C total(C start) const {
      int sz = rep.size();
      for (int i = 0; i < sz; ++i) {
        start += rep[i];
      }
      return start;
    }

    int maxidx() const {
	int sz = rep.size();
	C max = rep[0];
	int maxidx = 0;
	for (int i = 1; i < sz; ++i) {
	    if (rep[i] > max) {
		max = rep[i];
		maxidx = i;
	    }
	}
	return maxidx;
    }

    int minidx() const {
	int sz = rep.size();
	C min = rep[0];
	int minidx = 0;
	for (int i = 1; i < sz; ++i) {
	    if (rep[i] < min) {
		min = rep[i];
		minidx = i;
	    }
	}
	return minidx;
    }

    // Returns indices with higest values, in order of indices.
    std::vector<int> topN(int n) const
    {
      int sz = size();
      std::vector<vec<C>::Item> items( sz );
      for (int i = 0; i<sz; ++i) {
        items[i] = vec<C>::Item(*this, i);
      }

      std::partial_sort(items.begin(), items.begin()+n, items.end(),
                        std::greater<vec<C>::Item>() );

      std::vector<int> r(n);
      for (int i = 0; i < n; ++i) {
        r[i] = items[i].index;
      }
      std::sort(r.begin(), r.end());

      return r;
    }

    ~vec() {}
};

template<class C>
inline std::ostream &
operator<<(std::ostream &o, const vec<C> &v) {
  int sz = v.size();
  o << "[";
  for (int i = 0; i < sz; ++i) {
    o << v[i] << " ";
  }
  o << "]";
  return o;
}

inline int
nVecMatch(const std::vector<int> &a, const std::vector<int> &b)
{
  int n = 0;

  for (std::vector<int>::const_iterator it = a.begin(); it != a.end(); ++it) {
    for (std::vector<int>::const_iterator it2 = b.begin(); it2 != b.end(); ++it2) {

      if (*it2 == *it) {
	++n;
	break;
      }
    }
  }
  return n;
}

inline int
nSortedVecMatch(const std::vector<int> &a, const std::vector<int> &b)
{
  int n = 0;
  typedef std::vector<int>::const_iterator iter;
  iter i1 = a.begin();
  iter i2 = b.begin();
  if (i1 == a.end() || i2 == b.end())
    return 0;
  while (1) {
    if (*i1 == *i2) {
      ++n; ++i1; ++i2;
      if (i1 == a.end() || i2 == b.end())
	return n;
    } else if (*i1 < *i2) {
      ++i1;
      if (i1 == a.end()) return n;
    } else {
      ++i2;
      if (i2 == b.end()) return n;
    }
  }
}

template<class C>
std::ostream& pvec(std::ostream &o, const std::vector<C> &v)
{
  o << "[";
  for (typename std::vector<C>::const_iterator i = v.begin(); i != v.end(); ++i) {
    o << *i << ",";
  }
  o << "]";
  return o;
}

#endif /* _VEC_H */