make a python program that uses 'bag' data structures. make something simple and straight forward and make sure the program works. see starter codes below.

arraybag.py

"""

Project 5.4

File: arraybag.py

Author: Ken Lambert

"""

from arrays import Array

class ArrayBag(object):

"""An array-based bag implementation."""

# Class variable

DEFAULT_CAPACITY = 10

# Constructor

def __init__(self, sourceCollection = None):

"""Sets the initial state of self, which includes the

contents of sourceCollection, if it's present."""

self.items = Array(ArrayBag.DEFAULT_CAPACITY)

self.size = 0

if sourceCollection:

for item in sourceCollection:

self.add(item)

# Accessor methods

def isEmpty(self):

"""Returns True if len(self) == 0, or False otherwise."""

return len(self) == 0

def __len__(self):

"""Returns the number of items in self."""

return self.size

def __str__(self):

"""Returns the string representation of self."""

return "{" + ", ".join(map(str, self)) + "}"

def __iter__(self):

"""Supports iteration over a view of self."""

cursor = 0

while cursor < len(self):

yield self.items[cursor]

cursor += 1

def __add__(self, other):

"""Returns a new bag containing the contents

of self and other."""

result = ArrayBag(self)

for item in other:

result.add(item)

return result

def __eq__(self, other):

"""Returns True if self equals other,

or False otherwise."""

if self is other: return True

if type(self) != type(other) or \

len(self) != len(other):

return False

for item in self:

if self.count(item) != other.count(item):

return False

return True

def count(self, item):

"""Returns the number of instances of item in self."""

total = 0

for nextItem in self:

if nextItem == item:

total += 1

return total

# Mutator methods

def clear(self):

"""Makes self become empty."""

self.size = 0

self.items = Array(ArrayBag.DEFAULT_CAPACITY)

def add(self, item):

"""Adds item to self."""

# Check array memory here and increase it if necessary

if len(self) == len(self.items):

temp = Array(2 * len(self))

for i in range(len(self)):

temp[i] = self.items[i]

self.items = temp

self.items[len(self)] = item

self.size += 1

def remove(self, item):

"""Precondition: item is in self.

Raises: KeyError if item in not in self.

Postcondition: item is removed from self."""

# Check precondition and raise if necessary

if not item in self:

raise KeyError(str(item) + " not in bag")

# Search for the index of the target item

targetIndex = 0

for targetItem in self:

if targetItem == item:

break

targetIndex += 1

# Shift items to the left of target up by one position

for i in range(targetIndex, len(self) - 1):

self.items[i] = self.items[i + 1]

# Decrement logical size

self.size -= 1

# Check array memory here and decrease it if necessary

if len(self) <= len(self.items) // 4 and \

2 * len(self) >= ArrayBag.DEFAULT_CAPACITY:

temp = Array(len(self.items) // 2)

for i in range(len(self)):

temp[i] = self.items[i]

self.items = temp

-----------------------------------------------------------

array.py

"""

File: arrays.py

An Array is a restricted list whose clients can use

only [], len, iter, and str.

To instantiate, use

= array(, )

The fill value is None by default.

"""

class Array(object):

"""Represents an array."""

def __init__(self, capacity, fillValue = None):

"""Capacity is the static size of the array.

fillValue is placed at each position."""

self.items = list()

for count in range(capacity):

self.items.append(fillValue)

def __len__(self):

"""-> The capacity of the array."""

return len(self.items)

def __str__(self):

"""-> The string representation of the array."""

return str(self.items)

def __iter__(self):

"""Supports iteration over a view of an array."""

return iter(self.items)

def __getitem__(self, index):

"""Subscript operator for access at index."""

return self.items[index]

def __setitem__(self, index, newItem):

"""Subscript operator for replacement at index."""

self.items[index] = newItem