forked from UWPCE-PythonCert/IntroToPython-2014
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsparse_array.py
More file actions
62 lines (50 loc) · 1.91 KB
/
sparse_array.py
File metadata and controls
62 lines (50 loc) · 1.91 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
"""
example of emulating a sequence
"""
class SparseArray(object):
def __init__(self, my_array=()):
self.length = len(my_array)
self.sparse_array = self.convert_to_sparse(my_array)
def convert_to_sparse(self, my_array):
sparse_array = {}
for index, number in enumerate(my_array):
if number:
sparse_array[index] = number
return sparse_array
def __len__(self):
return self.length
def __getitem__(self, key):
try:
return self.sparse_array[key]
except KeyError:
if key >= self.length:
raise IndexError('array index out of range')
return 0
def __setitem__(self, key, value):
if key > self.length:
raise IndexError('array assignment index out of range')
if value != 0:
self.sparse_array[key] = value
else:
# if the value is being set to zero, we probably need to
# remove a key from our dictionary.
self.sparse_array.pop(key, None)
def __delitem__(self, key):
# we probably need to move the keys if we are not deleting the last
# number, use pop in case it was a zero
if key == self.length - 1:
self.sparse_array.pop(key, None)
else:
# since we need to adjust all of the keys after the one we are
# deleting, probably most efficient to create a new dictionary
new_dict = {}
for k, v in self.sparse_array.iteritems():
if k >= key:
new_dict[k - 1] = v
else:
new_dict[k] = v
# note we don't want to do update, since we need to make sure we are
# getting rid of the old keys, when we moved the value to a new key
self.sparse_array = new_dict
# length is now one shorter
self.length -= 1