Programming Assignment #2: Vector Class

Introduction

The objective of this assignment is to implement a contiguous implementation of the Vector ADT described below. For our purposes, "Vector" is synonymous with "List". The Vector ADT, like other List ADTs, describes a mutable sequence type that dynamically resizes as items are added or removed. The Vector ADT below includes a subset of the functionality of Python's built-in list type. For those methods that Vector does provide, the functionality of the Vector class will be mostly the same as the functionality of Python's list class, with some exceptions described below.

Advice on implementation can be found in Section 2.2 of our textbook. That section describes the implementation of many of Python's list methods. Your implementation doesn't need to follow those descriptions exactly, but efficiency does matter. For example, you will lose points if your implementation requires O(n) time to complete some operation that could be completed in O(1) time.

The Array Class and Memory Management

You must use the provided Array class defined in the module t_array.py as the underlying data structure for your Vector class. This is similar to the Array class described in our textbook with a few key differences. First, this Array class has visualization code that will allow us to inspect the contents of all of the arrays that are in existence at any one time. Second, objects of this array class need to be explicitly released when they are no longer needed.

In Python (and Java) there is a garbage collection process that automatically frees up memory that is no longer being referenced. In some programming languages, like C or C++, it is the responsibility of the programmer to explicitly release any memory that is no longer being used. The Array class defined in t_array.py brings with it that same responsibility: the garbage collector will not free Array objects automatically.

Part of your grade for this project will be based on writing code that has no "memory leaks". A memory leak occurs when some memory is no longer referenced, but has not been explicitly released.

Here is the pydoc documentation for the Array class:

class Array(__builtin__.object)
 |  Array class that supports turtle graphics visualization.  
 |  
 |  There are two public, class-level variables that can be used
 |  to control the visualization: 
 |  
 |  Array.visible  - Set this to False to turn off graphics. 
 |  Array.speed -    Set this value to change the speed of the animation. 
 |                   This value indicates the length of the pauses (in seconds)
 |                   between updates.
 |  
 |  Methods defined here:
 |  
 |  __getitem__(self, index)
 |      Returns the contents of the indicated array entry.
 |  
 |  __init__(self, size)
 |      Creates an array with a given capacity.
 |  
 |  __len__(self)
 |      Returns the size of the array.
 |  
 |  __setitem__(self, index, value)
 |      Stores the value at the indicated index.
 |  
 |  free(self)
 |      Frees this array.  
 |      
 |      The array will no longer appear in the visualization, and may
 |      be garbage collected as long as no external references exist.
 |  
 |  ----------------------------------------------------------------------

Testing

UPDATED 10/3.

I am providing the following set of unit tests to get you started: vector_tests.py. This set of unit tests is not complete. There are no tests for the methods pop, count or reverse. Fifteen percent of your grade on this programming assignment will be based on providing appropriate tests for those methods.

For some of the methods below, you have the option of implementing functionality beyond the minimum requirements of this project. If you choose to implement something extra, you should update the provided unit tests to reflect those changes, and you should document the changes in the header comments of your Vector class.

The Vector ADT

In the following ADT description, italicized entries refer to built-in Python methods and operators that your class will override. For example, you will implement the length() method by defining a function with the signature __len__(self).

Vector()

Create a new vector object. (The initial capacity of the underlying array should be two.)

length()

Return the number of elements contained in the vector.

contains(item)

Return True if item is contained in the vector.

equals(v)

Return True if v is equal to this vector. Two vectors are considered to be equal if they have the same type, the same length, and if all elements at corresponding locations are equal.

notequals(v)

Return False if v is equal to this vector. (This should just return the negation of equals(v).)

getitem(indx)

Return the element stored at position indx in the vector. Raises IndexError if the index is out of range.

NOTE: Your code should correctly handle negative index values. Negative indices may be converted to positive indices by adding the length of the vector. For example v[-1] is equivalent to v[len(v) + (-1)]. Since several methods will need to handle converting negative indices and checking for illegal index values, it makes sense to write a "private" helper method for handling these tasks.

setitem(indx, item)

Sets the element at position indx to be item. Raises IndexError if the index is out of range.

string()

Return a string representation of this vector. The format should be an open bracket, followed by comma separated data elements, followed by a closing bracket.

getSlice(indx1, indx2)

Creates and returns a new vector that contains a sub-sequence of items in the vector from position indx1 to position indx2 - 1. Raises IndexError if either indx1 or indx2 - 1 are outside of range. Returns an empty vector if indx1 > indx2 - 1.

NOTE: getSlice should not override the built-in slicing operator. (If you want to fully implement slicing, you are welcome to do so. The correct way of supporting slicing is through the use of slice objects that are automatically passed to the __getitem__ method.) You do need to handle negative indices. The behavior described above refers to index values after they have been converted from their negative form by adding the length of the list.

iterator()

Creates and returns an iterator that can be used to access the contents of the vector.

append(item)

Add item to the end of the vector.

extend(items)

Extend the vector by appending all the items in items, which can be of any iterable type.

NOTE: You do not need to handle the case where a vector is extended by itself. In that case, you may raise a NotImplementedError.

insert(indx, item)

Insert an item at a given position. The first argument is the index of the element before which to insert, so a.insert(0, x) inserts at the front of the vector, and a.insert(len(a), x) is equivalent to a.append(x). Raises an IndexError if indx is outside of the valid range.

NOTE: keep in mind the logic for what constitutes a valid index is slightly different here than for getitem and setitem.

remove(item)

Remove the first element from the vector whose value is item. Raises ValueError error if there is no such element.

pop([indx])

Remove the item at the given position in the vector, and return it. If no index is specified, a.pop() removes and returns the last item in the vector. Raises IndexError if the vector is empty or the index is out of range. (The square brackets around the indx in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)

index(item)

Return the index in the vector of the first element whose value is item. Raises ValueError if there is no such element.

count(item)

Return the number of times item appears in the vector.

reverse()

Reverse the elements of the vector, in place.

Advice on Memory Management

Your vector class will be responsible for freeing Arrays that are no longer referenced. This means that there must be some way for vector objects to know that they are no longer referenced. When a vector object is released by the garbage collector it will need to explicitly release any Arrays that it is still holding onto. This can be accomplished by overriding the built in Python operator __del__. That method should be called automatically when there are no more references to the vector.

If you've done everything correctly, the following python script should terminate with no arrays remaining on the screen.

from vector import Vector

vec = Vector()
for i in range(8):
    vec.append(i)

# Overwrite the reference to our vector so that it can be garbage
# collected. The __del__ method of vec will be called. 
vec = "Goodbye!"

Note that, under normal circumstances, YOU WOULD NEVER NEED TO OVERRIDE __del__. You are only doing this because this project exists in a Bizarro world where Python garbage collection does not exist for some classes.

Handing In

You should submit two .py files through blackboard before the deadline: a module named vector.py containing your completed Vector class, and an updated version of the unit testing module. As always, your code should conform to the CS240 Python Coding Conventions. You do not need to provide docstrings for the methods in the unit testing class.

Acknowledgments

Several of the method descriptions above are copied from the Python tutorial description of Python's list methods, © 2001-2010 Python Software Foundation; All Rights Reserved. Here is a copy of the PSF License: psf_license.txt. The documentation has been modified for clarity and consistency with this project.

The project as a whole is based on Programming Project 2.1 from Data Structures and Algorithms Using Python. Rance D. Necaise, Wiley, 2011.