3.6 Implementing the Vector

On this page...

Constructor
Element Access
Appending Elements
Helper Method
Inserting Elements
Removing Elements
List Slice

Constructor

class Vector :

  def __init__(self) :

    self._theElements = Array(2)

    self._length = 0

class Vector 

# ...

  def __len__(self) :

    return self._length

Element Access

class Vector :

# ...

  def __getitem__(self, index) :

    assert index >= 0 and index < self._length, "Index out of Range"

    return self._theElements[index]

class Vector :

# ...

  def __setitem__(self, index, element) :

    assert index >= 0 and index <= self._length, "Index out of Range"

    if index == self._length :

      self.append(element)

    else :

      self._theElements[index] = element

Appending Elements

class Vector :

# ...

  def append(self, element) :

    if self._length == len(self._theElements) :

      self._expandArray()

    ndx = self._length;

    self._theElements[ndx] = element

    self._length = self._length + 1

Include the discussion about extending the list here, but leave the method implementation as an exercise.

Helper Method

class Vector :

# ...

  def _expandArray() :

     # Get the current capacity of the underlying array

    size = len(self._theElements)

     # Create a new array that is twice the size of the current array

    newArray = Array(size * 2)

     # Copy the elements from the original array to the new one

    for i in range(size) :

      newArray[i] = self._theElements[i]

     # Assign the new array to the vector

    self._theElements = newArray

Inserting Elements

class Vector :

# ...

  def insert(position, element) :

    assert index >= 0 and index <= self._length, "Index out of Range"

     # If the underlying array is full, it has to be expanded

    if self._length == len(self._theElements) :

      self._expandArray()

     # Shift the elements down to make room for the new element

    i = self._length

    while i > position :

      self._theElements[i] = self._theElements[i - 1]

      i = i + 1

     # Insert the new element 

    self._theElements[position] = element

    self._length = self._length + 1

Removing Elements

List Slice

Leave the implementation as an exercise. Discuss the need to find the first power of two larger than the number of elements in the slice.

3.5 Designing an Expandable Container

Chapter 3. Arrays and Vectors

Chapter Exercises