Question

Implement a Bag ADT using Dynamic Array structure as underlying data storage for Bag ADT. 

RESTRICTIONS: Not allowed to use ANY built-in Python data structures and their methods. You must solve by importing the DynamicArray class and using class methods to write solution. Also not allowed to directly access any variables of the DynamicArray class (like self.size, self.capacity and self.data in part 1). All work must be done by only using class methods.

Below is the Bag ADT starter code and the Dynamic Array program. Basic testing below shows how the code might be used.

Bag Methods to implement:

add (self, value: object) -> None: This method adds a new element to the bag.remove()

remove (self, value: object) -> bool: This method removes any one element from the bag that matches the provided “value” object. Method returns True if some object was actually removed from the bag. Otherwise it returns False.

count (self, value: object) -> int: This method counts the number of elements in the bag that match the provided “value” object.

clear (self) -> None: This method clears the content of the bag.

size (self) -> int: This method returns the number of elements currently in the bag.

equal (self, second_bag: object) -> bool: This method compares the content of the bag with the content of the second bag provided by the user. Method returns True if the bags are equal (have the same number of elements and contain the same elements without regards to the order of elements). Otherwise it returns False. Empty bag is only considered equal to another empty bag. This method should not change the contents of either bag.

#Dynamic Array Code

class DynamicArrayException(Exception):
    """
    Custom exception class to be used by Dynamic Array
    DO NOT CHANGE THIS METHOD IN ANY WAY
    """
    pass


class DynamicArray:
    def __init__(self, start_array=None):
        """
        Initialize new dynamic array
        DO NOT CHANGE THIS METHOD IN ANY WAY
        """
        self.size = 0
        self.capacity = 4
        self.data = [None] * self.capacity

        # populate dynamic array with initial values (if provided)
        # before using this feature, implement append() method
        if start_array is not None:
            for value in start_array:
                self.append(value)

    def __str__(self) -> str:
        """
        Return content of dynamic array in human-readable form
        DO NOT CHANGE THIS METHOD IN ANY WAY
        """
        out = "DYN_ARR Size/Cap: "
        out += str(self.size) + "/"+ str(self.capacity)
        out += " " + str(self.data[:self.size])
        return out

    def resize(self, new_capacity: int) -> None:

        if (new_capacity == 0) or (new_capacity < self.size):
            return

        new_data = [None] * new_capacity

        for i in range(self.size):
            new_data[i] = self.data[i]

        self.capacity = new_capacity
        self.data     = new_data
        return

    def append(self, value: object) -> None:

        if self.is_full():
            self.resize(self.capacity * 2)

        self.data[self.size] = value
        self.size += 1

        return

    def insert_at_index(self, index: int, value: object) -> None:

        if (index < 0) or (index > self.size):
            raise DynamicArrayException

        if self.is_full():
            self.resize(self.size * 2)


        for current_index in range(self.size, index, -1):
            self.data[current_index] = self.data[current_index - 1]


        self.data[index] = value
        self.size       += 1

        return

    def get_at_index(self, index: int) -> object:

        if (index < 0) or (index > self.size - 1):
            raise DynamicArrayException

        return self.data[index]

    def remove_at_index(self, index: int) -> None:


        if (index < 0) or (index > self.size - 1):
            raise DynamicArrayException

        if (self.size < (0.25 * self.capacity)) and self.capacity > 10:
            if self.size < 5:
                self.resize(10)
            else:
                self.resize(self.size * 2)


        for i in range(index, self.size):
            if i == (self.size - 1):
                self.data[i] = None
            else:
                self.data[i] = self.data[i + 1]


        self.size -= 1

        return

    def is_empty(self) -> bool:
 
        return self.size == 0

    def length(self) -> int:

        return self.size

    def slice(self, start_index: int, quantity: int) -> object:


        if (start_index < 0) or (start_index > self.size - 1):
            raise DynamicArrayException

  
        if (quantity < 0) or (quantity > (self.size - start_index)):
            raise DynamicArrayException


        new_array = DynamicArray()


        for i in range(start_index, (start_index + quantity)):
            new_array.append(self.data[i])

        return new_array

    def reverse(self) -> None:
 

        if self.size <= 1:
            return


        front_index = 0
        back_index  = self.size - 1


        while front_index < (self.size / 2):

            front_val = self.get_at_index(front_index)
            back_val  = self.get_at_index(back_index)


            self.remove_at_index(front_index)
            self.insert_at_index(front_index, back_val)

            self.remove_at_index(back_index)
            if back_index == self.size:
                self.append(front_val)
            else:
                self.insert_at_index(back_index, front_val)


            front_index += 1
            back_index  -= 1

        return

    def sort(self) -> None:


        if self.size <= 1:
            return


        current_index = 1


        while current_index < self.size:

            comparison_index = current_index - 1
            sorting          = True


            while sorting:

                current_val = self.get_at_index(current_index)


                if current_val < self.get_at_index(comparison_index):
                    if comparison_index == 0:
                        self.remove_at_index(current_index)
                        self.insert_at_index(0, current_val)
                        sorting = False

                    else:
                        comparison_index -= 1

                else:
                    self.remove_at_index(current_index)
                    self.insert_at_index(comparison_index + 1, current_val)
                    sorting = False

            current_index += 1

        return

    def merge(self, another_list: object) -> None:
  
        # Iterate the given list values and append
        for i in range(another_list.length()):
            self.append(another_list.get_at_index(i))

        return

    def is_full(self) -> bool:

        if self.size == self.capacity:
            return True

        return False

#Bag Starter Code

from dynamic_array import *


class Bag:
    def __init__(self, start_bag=None):
        """
        Init new bag based on Dynamic Array
        DO NOT CHANGE THIS METHOD IN ANY WAY
        """
        self.da = DynamicArray()

        # populate bag with initial values (if provided)
        # before using this feature, implement add() method
        if start_bag is not None:
            for value in start_bag:
                self.add(value)

    def __str__(self) -> str:
        """
        Return content of bag in human-readable form
        DO NOT CHANGE THIS METHOD IN ANY WAY
        """
        out = "BAG: " + str(self.da.size) + " elements. "
        out += str(self.da.data[:self.da.size])
        return out

    def add(self, value: object) -> None:
        """
        TODO: Write this implementation
        """
        return

    def remove(self, value: object) -> bool:
        """
        TODO: Write this implementation
        """
        return False

    def count(self, value: object) -> int:
        """
        TODO: Write this implementation
        """
        return 0

    def clear(self) -> None:
        """
        TODO: Write this implementation
        """
        return

    def size(self) -> int:
        """
        TODO: Write this implementation
        """
        return 0

    def equal(self, second_bag: object) -> bool:
        """
        TODO: Write this implementation
        """
        return False

##Basic Testing

if __name__ == "__main__":
    pass

##Add Example Test:

bag = Bag()

print(bag)

values = [10, 20, 30, 10, 20, 30]

for value in values:

bag.add(value)

print(bag)

#Output:

#BAG: 0 elements. []

#BAG: 6 elements. [10, 20, 30, 10, 20, 30]

#########

##Remove Example Test:

bag = Bag([1, 2, 3, 1, 2, 3, 1, 2, 3])

print(bag)

print(bag.remove(7), bag)

print(bag.remove(3), bag)

print(bag.remove(3), bag)

print(bag.remove(3), bag)

print(bag.remove(3), bag)

#Output:

#BAG: 9 elements. [1, 2, 3, 1, 2, 3, 1, 2, 3]

#False BAG: 9 elements. [1, 2, 3, 1, 2, 3, 1, 2, 3]

#True BAG: 8 elements. [1, 2, 1, 2, 3, 1, 2, 3]

#True BAG: 7 elements. [1, 2, 1, 2, 1, 2, 3]

#True BAG: 6 elements. [1, 2, 1, 2, 1, 2]

#False BAG: 6 elements. [1, 2, 1, 2, 1, 2]

#########

#Count Example Testing:

bag = Bag([1, 2, 3, 1, 2, 2])

print(bag, bag.count(1), bag.count(2), bag.count(3), bag.count(4))

#Output:

#BAG: 6 elements. [1, 2, 3, 1, 2, 2] 2 3 1 0

#########

#Clear Example Testing:

bag = Bag([1, 2, 3, 1, 2, 3])

print(bag)

bag.clear()

print(bag)

#Output:

#BAG: 6 elements. [1, 2, 3, 1, 2, 3]

#BAG: 0 elements. []

#########

#Size Example Testing:

bag = Bag([10, 20, 30, 40])

print(bag.size(), bag.remove(30), bag.size())

bag.clear()

print(bag.size())

#Output:

#4 True 3

#0

#########

#Equal Example Testing:

bag1 = Bag([1, 2, 3, 4, 5, 6])

bag2 = Bag([6, 5, 4, 3, 2, 1])

bag3 = Bag([1, 2, 3, 4, 5])

bag_empty = Bag()

print(bag1, bag2, bag3, bag_empty, sep="\n")

print(bag1.equal(bag2), bag2.equal(bag1))

print(bag1.equal(bag3), bag3.equal(bag1))

print(bag2.equal(bag3), bag3.equal(bag2))

print(bag1.equal(bag_empty), bag_empty.equal(bag1))

print(bag_empty.equal(bag_empty))

print(bag1, bag2, bag3, bag_empty, sep="\n")

#Output:

#BAG: 6 elements. [1, 2, 3, 4, 5, 6]

#BAG: 6 elements. [6, 5, 4, 3, 2, 1]

#BAG: 5 elements. [1, 2, 3, 4, 5]

#BAG: 0 elements. []

#True True

#False False

#False False

#False False

#True

#BAG: 6 elements. [1, 2, 3, 4, 5, 6]

#BAG: 6 elements. [6, 5, 4, 3, 2, 1]

#BAG: 5 elements. [1, 2, 3, 4, 5]

#BAG: 0 elements. []

Answer 1

Each method implementation has been explained below.

• add(value)

We can use the append method of the dynamic array to add elements(values) to our bag.

   def add(self, value: object) -> None:
       """
       uses append() method of dynamic array
       """
       self.da.append(value)
       return

• remove(value)

This method removes the first occurence of the value from the bag. To implement this we iterate through the dynamic array and check if the element at each index is same as the value to be removed. Once we get the index, we can remove the element by calling remove_at_index(i) method of the dynamic array and return True immediately.

   def remove(self, value: object) -> bool:
       """
       gets the index of the element and removes it
       using remove_at_index(i)
       """
       for i in range(self.da.length()):
           if self.da.get_at_index(i) == value:
               self.da.remove_at_index(i)
               return True
       return False

• count(value)

Here, again we iterate through the dynamic array. We initialize a variable n which keeps track of the count. Each time, we find our value in the dynamic array we increment n. Finally we return n, once the entire dynamic array has been checked.

   def count(self, value: object) -> int:
       """
       returns the count of element in the bag
       """
       n = 0
       for i in range(self.da.length()):
           if self.da.get_at_index(i) == value:
               n += 1
       return n

• clear()

We simply remove all the elements from the dynamic array by calling remove_at_index(i). Note, that we iterate the dynamic array from the end to start, so that indices of other elements do not change when we remove an element from the dynamic array.

   def clear(self) -> None:
       """
       clears all elements from the bag
       """
       for i in range(self.da.length()-1, -1, -1):
           self.da.remove_at_index(i)

• size()

This is simply the length of the dynamic array.

   def size(self) -> int:
       """
       returns the size of the bag
       """
       return self.da.length()

• equal(second_bag)

Here, we first compare if the sizes of the two bag's are equal. If the sizes are equal, we check if the count of each element in our bag and second_bag are equal.

   def equal(self, second_bag: object) -> bool:
       """
       compares two bags and returns True if
           they have the same size and
           they have the same elements
       """
       if self.da.length() != second_bag.da.length():
           return False

       for i in range(self.da.length()):
           element = self.da.get_at_index(i)
           if (self.count(element) != second_bag.count(element)):
               return False
       return True

Screenshot of the code (included for readability)

Output