Vector.java

Go to the documentation of this file.

package aud;
 
//@<vector:class
public class Vector<T> implements Iterable<T> {
 
  static final int MIN_SIZE = 16;
 
  T[] data_ = null;
  int size_ = 0;
  //@>vector:class
 
  // @<vector:ctor
  public Vector() {}
  // @>vector:ctor
 
  // @<vector:size
  public int size() { return size_; }
  // @>vector:size
 
  // @<vector:capacity
  public int capacity() {
    return data_!=null ? data_.length : 0;
  }
  // @>vector:capacity
 
  public boolean empty() { return size()==0; }
 
  public T front() {
    return at(0);
  }
  public T back() {
    return at(size()-1);
  }
 
  //@<vector:at
  public T at(int i) {
    return data_[check(i)];
  }
  //@>vector:at
 
  public void set(T obj,int i) {
    data_[check(i)]=obj;
  }
 
  //@<vector:check
  int check(int i) {
    if (!(0<=i && i<size_))
      throw new ArrayIndexOutOfBoundsException(i);
    return i;
  }
  //@>vector:check
 
  @SuppressWarnings("unchecked")
  //@<vector:reserve
  public void reserve(int n) {
    n=(n>=MIN_SIZE) ? n : MIN_SIZE;
    if (capacity()<n) {
      T[] a=(T[]) new Object[n]; // unchecked
      for (int i=0;i<size_;++i)
        a[i]=data_[i];
      for (int i=size_;i<a.length;++i)
        a[i]=null;
      data_=a;
    }
  }
  //@>vector:reserve
 
  //@<vector:resize
  public void resize(int n) {
    if (n>capacity()) {
      int c=(3*capacity()+1)/2; // grow $\times\,\frac{3}{2}$
      reserve(c>n ? c : n);
    }
    else if (n<size_) {
      n=(n>0 ? n : 0);          // ensure n>=0
      for (int i=size_-1;i>=n;--i)
        data_[i]=null;          // garbage!
    }
    size_=n;
  }
  //@>vector:resize
 
  //@<vector:push_back
  public void push_back(T obj) {
    int n=size_;
    resize(n+1); // usually not much to do!
    data_[n]=obj;
  }
  //@>vector:push_back
 
  //@<vector:insert
  public void insert(int i,T obj) {
    int n=size_;
    resize(n+1);
 
    check(i); // checks 0 <= i < new size
 
    for (int j=n;j>i;--j)  // shift right
      data_[j]=data_[j-1];
    data_[i]=obj;
  }
  //@>vector:insert
 
  //@<vector:pop_back
  public void pop_back() {
    check(0);
    data_[--size_]=null;         // garbage!
  }
  //@>vector:pop_back
 
  //@<vector:erase
  public void erase(int i) {
    check(i);
    for (int j=i+1;j<size_;++j)  // shift left
      data_[j-1]=data_[j];
    data_[--size_]=null;         // garbage!
  }
  //@>vector:erase
 
  public void clear() {
    for (int i=0;i<size_;++i)
      data_[i]=null;             // garbage!
    size_=0;
  }
 
  //
  // iterators
  //
 
  public class Iterator implements java.util.Iterator<T> {
 
    Vector<T> v_;
    int       idx_;
    Iterator(Vector<T> v,int idx) { v_=v; idx_=idx; }
 
    @Override public boolean hasNext() { return idx_<v_.size();  }
 
    @Override public T next() { return v_.at(idx_++); }
 
    @Override public void remove() {
      throw new UnsupportedOperationException();
    }
  }
 
  @Override public Iterator iterator() {
    return new Iterator(this,0);
  }
 
  @Override
    public String toString() {
    String rv="[";
    for (int i=0;i<size();++i) {
      rv+=data_[i];
      if (i<size()-1)
        rv+=",";
    }
    rv+="]";
    return rv;
  }
}