Three Implementations of a Bag in Python
Tags: python, algorithms, datastructures, computerscience
Published: 2020-04-05 22:32:48

One of the first data structures discussed in Sedgewick's Algorithms is the Bag. A Bag is a data structure, which holds an unordered collection. We say unordered because it is in contrast to ordered collections like conventional arrays. Because we are not concerned with order, we can store the elements in any way we want.

This article will discuss three different implementations of Bag, each using a different internal data structure. By using different internal data structures, a clearer picture is created on the value of these interfaces, and can also help identify time complexity trade-offs.

## The Bag Interface

The image below describes a Bag interface in Java:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/w0yo9rvsozc08aqr2qcx.png)

It describes five operations:

1. The constructor `Bag()` takes zero arguments
2. The method `add(item)` inserts an item into the Bag.
3. The method `isEmpty()` tells us if the Bag is empty.
4. The method `size()` tells us the size of the Bag.
5. The interface `Iterable<Item>` in Java allows the use of the `for .. in ..` loop.

## Implementing `Iterable` in Python

Unlike Java, Python does not have a formal concept of a typed interface. However, it does have facilities to allow an object to be iterable, much like Java, using the `__iter__` and `_next__`. The following is an example of how these methods work in Python:

```python
class DoubleYourNumber:
  def __init__(self, start=0, stop=10):
    self.start = start
    self.stop  = stop
  def __iter__(self):
    self.current = self.start
    return self
  def __next__(self):
    if self.current <= self.stop:
      value = self.current * 2
      self.current += 1
      return value
    else:
      raise StopIteration
```

The above is an example of a class that supports the [Python Iterator](https://wiki.python.org/moin/Iterator) interface. Below is an example of how this class could be used to iterate:

```python
>>> for value in  DoubleYourNumber(stop=5):
...    print(value)
...
0
2
4
6
8
10
```

You can get the same effect by using `iter` and `next` directly on the iterator object:

```python
>>> doubler = DoubleYourNumber(stop=5)
>>> iter_doubler = iter(doubler)
>>> next(iter_doubler)
0
>>> next(iter_doubler)
2
>>> next(iter_doubler)
4
>>> next(iter_doubler)
6
>>> next(iter_doubler)
8
>>> next(iter_doubler)
10
>>> next(iter_doubler)
Traceback (most recent call last):
...
StopIteration
```

In a way, you can think of iterators as following this `while` loop pattern:

```python
iter_object = iter(object)

while True:
  try:
    value = next(iter_object)
    # Do something with `value`
  except StopIteration:
    break # Leave the infinite while loop
```

We'll be using this pattern in our implementations of Bag.

## Unit Testing a Bag

Since we don't have a formal interface, we can instead rely on unit testing to confirm the implementation is useful for our needs. Below is a set of tests that we can use to verify our implementation.

```python
import unittest

from bag_implementation import Bag

class BagUnitTest(unittest.TestCase):
  def test_new_bag_is_empty(self):
    """
    A Bag should initially be empty.
    """
    bag = Bag()
    self.assertEqual(bag.is_empty(), True)

  def test_add_increases_size_by_one(self):
    """
    Calling bag.add(...) should increase it's size by one.
    """
    bag = Bag()
    bag.add(1)
    self.assertEqual(bag.size(), 1)

  def test_bag_can_be_iterated_over(self):
    """
    Bag uses the iterable Python interface.
    """
    bag = Bag()
    for i in [1,2,3]:
      bag.add(i)

    sum = 0
    for i in bag:
      sum += i

    self.assertEqual(sum, 6)
```


## Creating a Bag Using the Built-In `list`

The first implementation of Bag is mostly a wrapper around `list`. Since `list` is an ordered collection, if we drop the ordered constraint `list` can be used as an unordered collection. Below is a possible implementation using `list`:

```python
class BagWithList(object):
  def __init__(self):
    self.collection = list()

  def add(self, item):
    self.collection.append(item)

  def size(self):
    return len(self.collection)

  def is_empty(self):
    return len(self.collection) == 0

  def __iter__(self):
    return iter(self.collection)
```

[The official Python wiki](https://wiki.python.org) has a [page on the time complexity](https://wiki.python.org/moin/TimeComplexity) of some of the built-in data structures. In particular, the `list` operations has the following big-O in the average case:

| Version | Operation  | Big-O |
|---------|------------|-------|
| `list`  | Append     | O(1)  |
| `list`  | Get Length | O(1)  |
| `list`  | Iteration  | O(n)  |

Also this data structure uses O(n) space.

## Using a Linked List

By default Python does not come with a version of a linked list as a native data structure. Causing us to write our own below, with a custom iterator.

```python
class LinkedListNode(object):
  def __init__(self, value):
    self.value     = value
    self.next_node = None

  def add(self, value):
    if self.next_node == None:
      self.next_node = LinkedListNode(value)
    else:
      self.next_node.add(value)

  def size(self):
    if self.next_node == None:
      return 1
    else:
      return 1 + self.next_node.size()

  def __iter__(self):
    return LinkedListIter(self)

class LinkedListIter(object):
  def __init__(self, current_node):
    self.current_node = current_node

  def __next__(self):
    if self.current_node == None:
      raise StopIteration
    else:
      value = self.current_node.value
      self.current_node = self.current_node.next_node
      return value
```

We could use this implementation of a Linked List in our implementation of a Bag.

```python
class BagWithLinkedList(object):
  def __init__(self):
    self.linked_list = None

  def add(self, value):
    if self.linked_list == None:
      self.linked_list = LinkedListNode(value)
    else:
      self.linked_list.add(value)

  def size(self):
    if self.linked_list == None:
      return 0
    else:
      return self.linked_list.size()

  def is_empty(self):
    return self.linked_list == None

  def __iter__(self):
    if self.linked_list == None:
      return iter([])
    else:
      return iter(self.linked_list)
```

The time complexity of these methods are not as attractive as the previous. There are other use cases for linked lists that show how to use it effectively. Despite this, it still uses O(n) space complexity, as the `list` version did.

| Version     | Operation  | Big-O |
|-------------|------------|-------|
| Linked List | Append     | O(n)  |
| Linked List | Get Length | O(n)  |
| Linked List | Iteration  | O(n)  |

## Using `defaultdict` from `collections` as a Multiset

A set is a commonly known mathematical object. A set is only concerned with membership, or whether an element belongs to collection or not. Like bags, sets are unordered. However, unlike bags, they only allow an element to appear once. If we relax this constraint, and keep track of the number of times an element appears, then we have a [multiset](https://en.wikipedia.org/wiki/Multiset).

Multisets appear in C++ as a [built-in data structure](https://en.wikipedia.org/wiki/Associative_containers). However, Python does not have anything named as a multiset. Instead, there is `collections.Counter` and `collections.defaultdict`. The former keeps track of both counts and the insertion order. We only need to keep track of counts, so we will use `defaultdict` with a default value of `0` by using `defaultdict(int)`.

```python
from collections import defaultdict

class Multiset(object):
  def __init__(self):
    self.counts = defaultdict(int)
    self.total = 0    

  def add(self, item):
    self.counts[item] += 1
    self.total += 1

  def size(self):
    return self.total

class MultisetIterator(object):
  def __init__(self, multiset):
    self.multiset   = multiset
    self.keys       = list(multiset.counts.keys()) # Choose a fixed ordering
    self.key_index  = 0 # Current `keys` index
    self.key_repeat = 0 # Number of times we've repeated the current key

  def current_key(self):
    return self.keys[self.key_index]

  def current_count(self):
    return self.multiset.counts[self.current_key()]

  def __next__(self):
    key   = self.current_key()
    count = self.current_count()

    if self.key_repeat == count:
      if self.key_index + 1 < len(self.keys):
        self.key_index += 1
        self.key_repeat = 0
      else:
        raise StopIteration

    self.key_repeat += 1
    return self.current_key()
```

Next, we use our `Multiset` in the implementation of `Bag`.

```python
class BagWithMultiset(object):
  def __init__(self):
    self.multiset = Multiset()

  def add(self, item):
    self.multiset.add(item)

  def size(self):
    return self.multiset.size()

  def is_empty(self):
    return self.multiset.size() == 0

  def __iter__(self):
    return MultisetIterator(self.multiset)
```

This version of Bag might be the most performant, given the time and space complexity.

| Version  | Operation  | Big-O Average Case | Big-O Worst Case |
|----------|------------|--------------------|------------------|
| Multiset | Append     | O(1)               | O(n)             |
| Multiset | Get Length | O(1)               | O(1)             |
| Multiset | Iteration  | O(n)               | O(n)             |

These results are almost on par with the `list` implementation. Perhaps the worst case for appending, is worth revisiting. However, the space complexity is not O(n), but in fact O(k) where k is the number of unique elements in the collection. If there are many repeated values, this might be more advantageous than the two other versions of Bag.

## Conclusion

We covered the basics of Python iterators, and considered three different versions of `Bag`: one using `list`, one using our hand-rolled linked list implementation, and finally a version of a multiset using Python's `defaultdict`. This data structure is not very common, and does not have many advantages to ordered arrays. Nevertheless, because of its simplicity, we can use the Bag data structure as an introduction to algorithms.

With that.. happy algorithming, friends!