Subject Infrastructure Repository

Vector

A vector is a data structure that implements a mapping from an unbounded range of integers to objects of a certain type.

I. Language Agnostic Overview

Vectors are similar to arrays – one the most common and certainly one of the simplest data structures used in computer science. Arrays are hampered, however, by their fixed size. A vector data structure solves this problem, by increasing the array's size automatically when it becomes full and another insert is requested. Vectors are used frequently in both research and production environments. As they are versatile, fast, and space-efficient, they are a smart choice for a wide range of applications. Vectors are simple data structures, so correctness is not especially challenging, but it is extremely important.

The source code for the Vector class was developed by Sun, as part of version 1.4 of the Java framework.

Implementations of vectors are typically required to satisfy the following constraints:

The underlying array can never be null.
The element count can never be negative.
The element count can never be greater than the size of the underlying array.
No element can have a negative index.

II. Java Specific Overview:

The Vector class in Java is implemented on top of an array, so it still provides very fast random access. When an insert is attempted, and the current array doesn't have sufficient capacity, the array size is either increased by a predetermined number, or if that number isn't set, the capacity is simply doubled. It should also be noted that the Java implementation is also generic to any object (and presumably any primitive).

There are two fields which are used in the invariants:

elementData – This is the array of objects on top of which the Vector class is built. It stores the actual data which is accessed and modified by the various methods of the Vector class.
elementCount – This is an integer which stores the count of elements in the array.

So, a given element would be stored at elementData[elementCount-1].

ensureCapacity

a. This method ensures there is enough room in the underlying array for minCapacity elements. If not, the array size is increased (either doubled, incremented by a set amount, or set to minCapacity) to an acceptable size.

b. The preconditions verify that:

The underlying array has been properly initialized (constraint 1)
The number of elements hasn't somehow been set to a negative value (constraint 2)
The number of elements isn't larger than the size of the underlying array (constraint 3).

The postCondition verifies the same properties (1, 2 and 3) and that the underlying array can hold at least minCapacity elements.

indexOf

a. This method searches for the given value and then returns its associated index. It searches forward (index sizes increasing by one) from the given index.

b. The preconditions verify that the underlying array has been properly initialized (constraint 1), the number of elements hasn't somehow been set to a negative value (2), and the number of elements isn't larger than the size of the underlying array (3). It also checks that that a negative search position was not given (4) (note that this only applies to the two-argument form of the indexOf method). The postconditions are that either -1 or a correct index which is not less than the index must be returned.

lastIndexOf

a. This method is similar to indexOf in that it searches for a value and returns the index, however, it searches backward (index sizes decreasing by one) from the given index.

b. The preconditions of this method identical to those of indexOf (constraints 1, 2, 3 and 4). The postconditions are also similar, however there is one notable difference. Since lastIndexOf searches backwards rather than forwards, the returned index cannot be greater than the given index, instead of larger.

removeElementAt

a. This method removes the element from the vector which is stored at the given index.

insertElementAt

a. This method inserts an element into the vector at a given position. Often, it is not called directly, but by the method addElement(E obj), which inserts the given object at the end of the data structure.

b. The preconditions verify that the underlying array has been properly initialized (constraint 1), the number of elements hasn't somehow been set to a negative value (2), and the number of elements isn't larger than the size of the underlying array (3). They also check that the index to insert the element into is not a negative position (4), or a position larger than the size of the array. The postconditions specify that the underlying array has not become null, that the element count is nonnegative, and that the element count is not greater than the size of the underlying array.

add

a. This method simply adds the given element to the end of the vector.

Metrics:

Lines of code for implementation: 254

Methods for implementation: 49

Lines of code for invariants: 60

Methods for invariants: 6

References:

Wikipedia's entry on dynamically resizing arrays: http://en.wikipedia.org/wiki/Dynamic_array

Data Structures, Algorithms and Applications in Java by Sartaj Sahni. Section 5.4: “Vector Representation.” pgs 176 – 180.

Algorithms in Java, 3^rd Edition by Robert Sedgewick. Section 3.2: “Arrays.” pg 87.

Try the following link to upgrade the page display. (Explanation)