[Tutor] Fixed Vector Array

[Alan Gauld]

On 04/03/15 15:40, niyanaxx95 at gmail.com wrote:
> Need help trying to implement insert, remove, indexof, and reverse functions.
>
> I tried to do them but am not sure if it is correct. I am struggling with arrays.

I;m not sure why so many courses seem to insist on teaching old school 
arrays using Python. It involves rewriting functions that already exist, 
in superior form in the standard library. Reinventing the wheel is a bad 
practice and it seems a shame that some teachers appear to want to teach 
bad habits!

> This is python and using ezarrays.

And using third party libraries to do so just compounds the wrong,
why not at least base it on a standard list? Caveat I have no idea
what this module does so some of my answers may be off track.

Anyway, rant over, it's not your fault and I doubt you
can influence your course design.

> Assignment:
>
> A fixed vector is very similar to the vector in that
> it is a sequence containerthat can grow and shrink
 > as needed and include many useful operations.

Just like a Python list in fact...

> But the fixed vector has a maximum capacity beyond which it can not expand.

Which is rather limiting and very rarely what you want...

> • FixedVector(maxSize): Creates an empty fixed vector with the given maximum capacity.
> • length(): Returns the number of elements contained in the vector.
> • isFull(): Returns a Boolean indicating if the vector is full.
> • getitem(index): Returns the element stored in the vector at position index. The value of index must be within the valid range.
> • setitem(index, item): Sets the element at position index to contain the given item. The value of index must be within the valid range, which includes one position beyond the end of the vector. In the latter case, the item is simply appended onto the end. • contains(item): Determines if the given item is contained in the vector.
> • toString(): Returns a string representation of the vector.
> • append(item): Adds the given item to the end of the vector. An item can not be appended to a full vector.
> • clear(): Removes all elements from the vector.
> • insert(index, item): Inserts the given item into the vector at position index. The elements at and following the given position are shifted down to make room for the new item. The index must be within the valid range and the vector can not be full. If index is one position beyond the end of the vector, the item is appended onto the vector.
> • remove(index): Removes the element at position index from the vector. The removed element is returned. The index must be within the valid range.
> • indexOf(item): Returns the index of the element containing the given item. The item must be in the list.
> • reverse(): Performs a list reversal by reversing the order of the elements within the vector.

> from ezarrays import Array
>
> class FixedVector :
>     # Creates a new empty fixed vector with the given maximum capacity.
>    def __init__(self, maxSize) :
>      self._theItems = Array(maxSize)
>      self._numItems = 0

Presumably the Array created has maxSize items already created? If so of 
what type? Or is it type agnostic?

>     # Returns the number of elements contained in the vector.
>    def __len__(self) :
>      return self._numItems

I'd probably prefer to return the actual number of elements rather than 
rely on your counter being accurate. is I assume len(self._theItems) 
will return an accurate result?

Of if the Array really is fixed size maybe the correct answer
is return maxSize?

Or should it only return the number of non-empty items?

>     # Returns a Boolean indicating if the vector is full.
>    def isFull(self) :
>      return self._numItems == len(self._theItems)

This suggests that your len() returns the number of non empty cells and 
len(Array) returns the maxsize value?

>     # Returns the element stored in the vector at position index.
>     # The value of index must be within the valid range.
>    def __getitem__(self, index) :
>      assert index >= 0 and index < self._numItems, "Index out of Range."
>      return self._theItems[index]

I don;t think an assert is the correct solution here, it wouyld be 
better to raise an IndexError exception. This would be consistent with 
what Python does with the built in list type.


>     # Sets the element at position index to contain the given item. The
>     # value of index must be within the valid range, which includes one
>     # position beyond the end of the vector. In the latter case, the item
>     # is simply appended onto the end.
>    def __setitem__(self, index, item) :
>      assert index >= 0 and index <= self._numItems, "Index out of range."

Same issue here.

>      if index == self._numItems :
>        self.append(item)
>      else :
>        self._theItems[index] = item

If Array returns a fixed size array can't you just always assign to the 
index position. In other words does the array need to be filled
in a sequential manner or could you have a 'hole' in the middle (one of 
the few things an array allows that a list doesn't - although you can 
just use a dictionary if that's really important!

>     # Determines if the given item is contained in the vector.
>    def __contains__(self, item) :
>      i = 0
>      while i < self._numItems :
>        if self._theItems[i] == item :
>          return True
>        i = i + 1
 >
 >      return False

Couldn't this be more clearly written as

for thing in self.theItems:
     if thing == item: return True
return False

>     # Returns a string representation of the vector.
>    def __repr__(self) :
>      if self._numItems == 0 :
>        return "[]"
>
>      vectStr = "[" + str(self._theItems[0])
>      for i in range(1, self._numItems) :
>        vectStr = vectStr + ", " + str(self._theItems[i])
>
>      vectStr = vectStr + "]"
>      return vectStr

As a matter of interest what does str(self._theItems) return?

>     # Adds the given item to the end of the vector. An item can not be
>     # appended to a full vector.
>    def append(self, item) :
>      assert self._numItems < len(self._theItems), \
>             "Can not add to a full vector."
>      self._theItems[self._numItems] = item
>      self._numItems = self._numItems + 1

I'm not sure this makes sense for a *fixed* array, but its
in the assignment so...

I'm not sure what the vectStr thing does. A feature of ezarray presumably?

>     # Removes all elements from the vector.
>    def clear(self) :
>      self._theItems.clear(None)

Shouldn't you also reset self_numItems?

>     # Inserts the given item into the vector at position index. The elements
>     # at and following the given position are shifted down to make room
>     # for the new item. The index must be within the valid range and the
>     # vector can not be full. If index is one position beyond the end of
>     # the vector, the item is appended.
>    def insert(self, index, item) :
>      i = numItems

I guess that should be

        i = self._numItems

>      while i > index :
>          self._theItem[i] = self._theItem[i-1]

And that should be self._the items  - ie plural

>          i = i-1
>      self._theItems[i] = item
>      self._numItems = self._numItems + 1

What happens if index >= numItems?

Won't you wind up with an index error from your setitems code earlier??

>     # Removes the element at position index from the vector. The removed
>     # element is returned. The index must be within the valid range.
>    def remove(self, index) :
>      removed = self._theItems[index]
>      self._theItems[index] = None
>      return removed

This is relying on the earlier getitem/setitem error checking
of index I assume?

>     # Returns the index of the element containing the given item. The item
>     # must be in the list.
>    def indexOf(self, item) :
>      for i in range(0, self._numItems ):
>        if self._theItems[i] == item :
>          return i
>
>
>     # Reverses the order of the elements within the vector.
>    def reverse(self) :
>      end = self._numItems -1
>      for x in range(0, self._numItems // 2) :
>        tmp = self._theItems[x]
>        self._theItems[x] = self._theItems[end]
>        self._theItems = tmp
>        end = end -1

Shouldn't that last line be

self._theItems[end] = tmp?

But in Python we can swap without using a tmp:

items = self._theItems
for x in range(len(items)//2):
     items[x],items[end] = items[end],items[x]
     end -= 1

HTH

-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos