aud.Vector< T > Class Template Reference

Implementation of an array-based vector. More...

Inheritance diagram for aud.Vector< T >:

Collaboration diagram for aud.Vector< T >:

Classes
class	Iterator
	Forward iterator. More...

Public Member Functions
	Vector ()
	create empty vector More...
int	size ()
	get number of entries [O(1)] More...
int	capacity ()
	Get Capacity, i.e., the maximum size the vector can grow without allocating new storage. More...
boolean	empty ()
	Is vector empty? [O(1)]. More...
T	front ()
	get first entry [O(1)] More...
T	back ()
	get last entry [O(1)] More...
T	at (int i)
	get i-th entry [O(1)] More...
void	set (T obj, int i)
	set i-th entry [O(1)] More...
void	reserve (int n)
	Ensure capacity for n entries. More...
void	resize (int n)
	Set size of vector. More...
void	push_back (T obj)
	insert new entry obj at the end [O(1) for sufficient capacity] More...
void	insert (int i, T obj)
	Insert new entry obj at position i [O(n)]. More...
void	pop_back ()
	remove last enytry [O(1)] More...
void	erase (int i)
	remove entry at position i [O(n)] More...
void	clear ()
	remove all entries (capacity remains) [O(1)] More...
Iterator	iterator ()
	get forward iterator More...
String	toString ()

Detailed Description

Implementation of an array-based vector.

The implementation is inspired by std::vector of the C++ standard library. (There is a similar data structure java.util.Vector in the Java collections.)

Vectors can grow and shrink in size. Shrinking never frees memory. Growing (see reserve) over-allocates memory.

Implementation notes:

• The utility method check of the implementation ensures that an index is valid or throws a java.lang.ArrayIndexOutOfBoundsException otherwise.
• We use an exponential growth as heuristic, i.e., there are (1.) relatively few reallocations required, and (2.) we may waste a significant amount of memory
• reserve allocates at least MIN_SIZE. This prevents unnecessary reallocations for small vectors.
• Any unused object data_[j] for j in size_,...,capacity_-1 should be null! This way the garbage collection may dispose objects early. The implementation of methods reserve,resize, pop_back, and erase takes care of this. (This convention mimicks the behavior of the C++ std::vector although constructors and destructors work differently.)
• Different to C++, there is no way of manipulating data using the method at due to Java's use of references. Use set instead.

Definition at line 44 of file Vector.java.

Constructor & Destructor Documentation

Vector()

aud.Vector< T >.Vector

(

)

create empty vector

Definition at line 55 of file Vector.java.

{}

Member Function Documentation

at()

T aud.Vector< T >.at

(

int

i

)

get i-th entry [O(1)]

Exceptions

ArrayIndexOutOfBoundsException

Definition at line 92 of file Vector.java.

                     {
    return data_[check(i)];
  }

Referenced by aud.Vector< T >.back(), aud.Vector< T >.front(), aud.test.BinaryTreeTest.testBinaryTree(), aud.test.VectorTest.testInvalid_at(), and aud.test.VectorTest.testVec().

Here is the caller graph for this function:

back()

T aud.Vector< T >.back

(

)

get last entry [O(1)]

Exceptions

ArrayIndexOutOfBoundsException

Definition at line 84 of file Vector.java.

                  {
    return at(size()-1);
  }

References aud.Vector< T >.at(), and aud.Vector< T >.size().

Referenced by aud.test.VectorTest.testInvalid_back(), and aud.test.VectorTest.testVec().

Here is the call graph for this function:

Here is the caller graph for this function:

capacity()

int aud.Vector< T >.capacity

(

)

Get Capacity, i.e., the maximum size the vector can grow without allocating new storage.

Definition at line 67 of file Vector.java.

                        {
    return data_!=null ? data_.length : 0;
  }

Referenced by aud.Vector< T >.resize(), aud.test.VectorTest.testSize(), and aud.test.VectorTest.testVec().

Here is the caller graph for this function:

clear()

void aud.Vector< T >.clear

(

)

remove all entries (capacity remains) [O(1)]

Definition at line 202 of file Vector.java.

                      {
    for (int i=0;i<size_;++i)
      data_[i]=null;             // garbage!
    size_=0;
  }

empty()

boolean aud.Vector< T >.empty

(

)

Is vector empty? [O(1)].

Definition at line 73 of file Vector.java.

{ return size()==0; }

References aud.Vector< T >.size().

Referenced by aud.test.VectorTest.testCtor(), and aud.test.VectorTest.testVec().

Here is the call graph for this function:

Here is the caller graph for this function:

erase()

void aud.Vector< T >.erase

(

int

i

)

remove entry at position i [O(n)]

Exceptions

ArrayIndexOutOfBoundsException

Definition at line 192 of file Vector.java.

                           {
    check(i);
    for (int j=i+1;j<size_;++j)  // shift left
      data_[j-1]=data_[j];
    data_[--size_]=null;         // garbage!
  }

Referenced by aud.test.VectorTest.testInvalid_erase(), and aud.test.VectorTest.testVec().

Here is the caller graph for this function:

front()

T aud.Vector< T >.front

(

)

get first entry [O(1)]

Exceptions

ArrayIndexOutOfBoundsException

Definition at line 78 of file Vector.java.

                   {
    return at(0);
  }

References aud.Vector< T >.at().

Referenced by aud.test.VectorTest.testInvalid_front(), and aud.test.VectorTest.testVec().

Here is the call graph for this function:

Here is the caller graph for this function:

insert()

void aud.Vector< T >.insert	(	int	i,
		T	obj
	)

Insert new entry obj at position i [O(n)].

Requires 0 <= i <= size.

Definition at line 166 of file Vector.java.

                                  {
    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;
  }

Referenced by aud.test.VectorTest.testVec().

Here is the caller graph for this function:

iterator()

Iterator aud.Vector< T >.iterator

(

)

get forward iterator

Definition at line 234 of file Vector.java.

                                       {
    return new Iterator(this,0);
  }

pop_back()

void aud.Vector< T >.pop_back

(

)

remove last enytry [O(1)]

Exceptions

ArrayIndexOutOfBoundsException

Definition at line 182 of file Vector.java.

                         {
    check(0);
    data_[--size_]=null;         // garbage!
  }

Referenced by aud.test.VectorTest.testInvalid_pop_back(), and aud.test.VectorTest.testVec().

Here is the caller graph for this function:

push_back()

void aud.Vector< T >.push_back

(

T

obj

)

insert new entry obj at the end [O(1) for sufficient capacity]

Definition at line 155 of file Vector.java.

                               {
    int n=size_;
    resize(n+1); // usually not much to do!
    data_[n]=obj;
  }

Referenced by aud.test.BinaryTreeTest.testBinaryTree(), aud.test.VectorTest.testInvalid_at(), aud.test.VectorTest.testInvalid_erase(), aud.test.VectorTest.testSize(), aud.test.VectorTest.testVec(), and aud.test.VectorTest.testVecIterator().

Here is the caller graph for this function:

reserve()

void aud.Vector< T >.reserve

(

int

n

)

Ensure capacity for n entries.

This method may allocates new storage and copy data in O(n). New entries equal null.

Definition at line 120 of file Vector.java.

                             {
    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;
    }
  }

Referenced by aud.Vector< T >.resize().

Here is the caller graph for this function:

resize()

void aud.Vector< T >.resize

(

int

n

)

Set size of vector.

Shrinks or grows the vector. On Growing, any "new" entries equal null.

Definition at line 138 of file Vector.java.

                            {
    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;
  }

References aud.Vector< T >.capacity(), and aud.Vector< T >.reserve().

Here is the call graph for this function:

set()

void aud.Vector< T >.set	(	T	obj,
		int	i
	)

set i-th entry [O(1)]

Definition at line 98 of file Vector.java.

                               {
    data_[check(i)]=obj;
  }

size()

int aud.Vector< T >.size

(

)

get number of entries [O(1)]

Definition at line 60 of file Vector.java.

{ return size_; }

Referenced by aud.Vector< T >.back(), aud.Vector< T >.empty(), aud.test.BinaryTreeTest.testBinaryTree(), aud.test.VectorTest.testSize(), aud.test.VectorTest.testVec(), and aud.Vector< T >.toString().

Here is the caller graph for this function:

toString()

String aud.Vector< T >.toString

(

)

Definition at line 239 of file Vector.java.

                             {
    String rv="[";
    for (int i=0;i<size();++i) {
      rv+=data_[i];
      if (i<size()-1)
        rv+=",";
    }
    rv+="]";
    return rv;
  }

References aud.Vector< T >.size().

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• Vector.java