forked from phuang07/python_algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbag.py
More file actions
92 lines (73 loc) · 2.6 KB
/
Copy pathbag.py
File metadata and controls
92 lines (73 loc) · 2.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""This module implements a bag or multiset data structure.
A bag or multiset is a generalization of the set data structure which allows
repeated or duplicate items to be stored. Items can only be added to the bag
and may not be removed. When the items in the bag are iterated there is not
restriction on the ordering of the items.
In this module, the implementation of bag is similar to a linked list based
stack implementation. In the linked list based implementation, the bag object
need to keep track of only the head node. Each node contains an item and a link
to the next node.
.. note:: Python' has a built-in class `collections.Counter
<https://docs.python.org/2/library/collections.html#collections.Counter>`_
which is similar to a bag or multiset. instead of adding an item, 1 need to
be added with the counter associated with that item and elements return all
items (including duplicates) in the bag.
Complexity:
* add -- O(1)
"""
class _Node(object):
""" An internal class that represents a node with a single item
and links to other nodes.
"""
def __init__(self, item):
self.item = item
self.next = None
class Bag(object):
"""An implementation of a bag or multiset with linked list."""
def __init__(self):
"""Initializes an empty bag."""
self._head = None
self._size = 0
@property
def size(self):
"""The number of items in the bag."""
return self._size
def isEmpty(self):
"""Check if the bag is empty.
Returns:
True if the bag is empty.
False otherwise.
"""
return self._size == 0
def add(self, item):
"""Inserts an item to the bag."""
n = _Node(item)
n.next = self._head
self._head = n
self._size += 1
def __iter__(self):
"""Return iterator for the bag."""
current = self._head
while current:
yield current.item
current = current.next
def __str__(self):
"""String representation of the bag."""
return " ".join([str(item) for item in self])
def __repr__(self):
"""Representation of the bag."""
return "Bag(" + str(self) + ")"
if __name__ == "__main__":
print("Bag using linked list")
b = Bag()
while True:
n = int(raw_input("Enter a number to add to the bag"
"or enter 0 to exit:"))
if n:
b.add(n)
print("Added: " + str(n))
print("Current bag: " + str(b))
else:
break