Array

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
class Array():
def __init__(self, size=32):
self._size = size
self._items = [None] * size

def __getitem__(self, index):
return self._items[index]

def __setitem__(self, index, value):
self._items[index] = value

def __len__(self):
return self._size

def clear(self, value=None):
self._items = [value] * len(self._items)

def __iter__(self):
for item in self._items:
yield item


def test():
size = 10
a = Array(size)
a[0] = 1
assert a[0] == 1

a.clear()
assert a[0] is None


test()



LinkedList

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
class Node():
def __init__(self, value=None, next=None):
self.value, self.next = value, next


class LinkedList():
def __init__(self, maxsize=None):
self.maxsize = maxsize
self.root = Node()
self.length = 0
self.tailnode = None

def __len__(self):
return self.length

def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('Full')
node = Node(value)
tailnode = self.tailnode
if tailnode is None:
self.root.next = node
else:
tailnode.next = node
self.tailnode = node
self.length += 1

def appendleft(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('Full')
headnode = self.root.next
node = Node(value)
self.root.next = node
node.next = headnode
if self.tailnode is None:
self.tailnode = node
self.length += 1

def iter_node(self):
curnode = self.root.next
while curnode:
yield curnode
curnode = curnode.next

def __iter__(self):
for node in self.iter_node():
yield node.value

def remove(self, value):
prevnode = self.root
curnode = self.root.next
while curnode is not None:
if curnode.value == value:
prevnode.next = curnode.next
if curnode is self.tailnode:
if prevnode is self.root:
self.tailnode = None
else:
self.tailnode = prevnode
del curnode
self.length -= 1
return
prevnode = curnode
curnode = curnode.next

def find(self, value):
index = 0
for node in self.iter_node():
if node.value == value:
return index
index += 1
return -1

def popleft(self):
if self.root.next is None:
raise Exception('empty')
headnode = self.root.next
self.root.next = headnode.next
self.length -= 1
value = headnode.value
del headnode
return value

def clear(self):
for node in self.iter_node():
del node
self.root.next = None
self.length = 0


def test():
ll = LinkedList()

ll.append(0)
ll.append(1)
ll.append(2)

assert len(ll) == 3
assert ll.find(2) == 2
assert ll.find(3) == -1

ll.remove(0)
assert len(ll) == 2
assert ll.find(0) == -1

assert list(ll) == [1, 2]

ll.appendleft(0)
assert list(ll) == [0, 1, 2]
assert len(ll) == 3

headvalue = ll.popleft()
assert headvalue == 0
assert len(ll) == 2
assert list(ll) == [1, 2]

ll.clear()
assert len(ll) == 0


test()



CircularLinkedList

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
class Node():
def __init__(self, value=None, prev=None, next=None):
self.value, self.prev, self.next = value, prev, next


class CircularDoublyLinkedList():
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.next, node.prev = node, node
self.root = node
self.length = 0 # 增删操作时注意更新

def __len__(self):
return self.length

def headnode(self): # 增删操作时注意更新
return self.root.next

def tailnode(self): # 增删操作时注意更新
return self.root.prev

def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('full')
node = Node(value=value)
tailnode = self.tailnode()

tailnode.next = node
node.prev = tailnode
node.next = self.root
self.root.prev = node

self.length += 1

def appendleft(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('full')
node = Node(value=value)

if self.root.next is self.root:
node.next = self.root
node.prev = self.root
self.root.next = node
self.root.prev = node
else:
node.prev = self.root
headnode = self.root.next
node.next = headnode
headnode.prev = node
self.root.next = node
self.length += 1

def remove(self, node):
if node is self.root:
return
else:
node.prev.next = node.next
node.next.prev = node.prev
del node
self.length -= 1

def insert(self, key, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('full')

node = Node(value=value)
inserted = False
for curnode in self.iter_node():
if key == curnode.value:
node.prev = curnode
node.next = curnode.next
curnode.next.prev = node
curnode.next = node
inserted = True
break # 找到了匹配的节点并插入后,就可以退出循环了

if not inserted: # 如果没有插入节点(也就是没找到匹配的 key),则添加到链表的末尾
tailnode = self.tailnode()
node.prev = tailnode
node.next = self.root
tailnode.next = node
self.root.prev = node

self.length += 1

def iter_node(self):
if self.root.next is self.root:
return
curnode = self.root.next
while curnode.next is not self.root:
yield curnode
curnode = curnode.next
yield curnode

def __iter__(self):
for node in self.iter_node():
yield node.value

def iter_node_reverse(self):
if self.root.prev is self.root:
return
curnode = self.root.prev
while curnode.prev is not self.root:
yield curnode
curnode = curnode.prev
yield curnode


def test():
dll = CircularDoublyLinkedList()
assert len(dll) == 0

dll.append(0)
dll.append(1)
dll.append(2)

assert list(dll) == [0, 1, 2]

assert [node.value for node in dll.iter_node()] == [0, 1, 2]
assert [node.value for node in dll.iter_node_reverse()] == [2, 1, 0]

headnode = dll.headnode()
assert headnode.value == 0
dll.remove(headnode)
assert len(dll) == 2
assert [node.value for node in dll.iter_node()] == [1, 2]

dll.appendleft(0)
assert [node.value for node in dll.iter_node()] == [0, 1, 2]


test()



Queue

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
class Node():
def __init__(self, value=None, next=None):
self.value, self.next = value, next


class LinkedList():
def __init__(self, maxsize=None):
self.maxsize = maxsize
self.root = Node()
self.length = 0
self.tailnode = None

def __len__(self):
return self.length

def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('Full')
node = Node(value)
tailnode = self.tailnode
if tailnode is None:
self.root.next = node
else:
tailnode.next = node
self.tailnode = node
self.length += 1

def appendleft(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('Full')
headnode = self.root.next
node = Node(value)
self.root.next = node
node.next = headnode
if self.tailnode is None:
self.tailnode = node
self.length += 1

def iter_node(self):
curnode = self.root.next
while curnode:
yield curnode
curnode = curnode.next

def __iter__(self):
for node in self.iter_node():
yield node.value

def remove(self, value):
prevnode = self.root
curnode = self.root.next
while curnode is not None:
if curnode.value == value:
prevnode.next = curnode.next
if curnode is self.tailnode:
if prevnode is self.root:
self.tailnode = None
else:
self.tailnode = prevnode
del curnode
self.length -= 1
return
prevnode = curnode
curnode = curnode.next

def find(self, value):
index = 0
for node in self.iter_node():
if node.value == value:
return index
index += 1
return -1

def popleft(self):
if self.root.next is None:
raise Exception('empty')
headnode = self.root.next
self.root.next = headnode.next
self.length -= 1
value = headnode.value
del headnode
return value

def clear(self):
for node in self.iter_node():
del node
self.root.next = None
self.length = 0


class FullError(Exception):
pass


class EmptyError(Exception):
pass


class Queue():
def __init__(self, maxsize=None):
self.maxsize = maxsize
self._item_linked_list = LinkedList()

def __len__(self):
return len(self._item_linked_list)

def push(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise FullError('full')
return self._item_linked_list.append(value)

def pop(self):
if len(self) <= 0:
raise EmptyError('empty')
return self._item_linked_list.popleft()


def test():
import pytest
q = Queue()
q.push(0)
q.push(1)
q.push(2)

assert len(q) == 3

assert q.pop() == 0
assert q.pop() == 1
assert q.pop() == 2

with pytest.raises(EmptyError) as excinfo:
q.pop()
assert 'empty' in str(excinfo.value)



ArrayQueue

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
class Array():
def __init__(self, size=32):
self._size = size
self._items = [None] * size

def __getitem__(self, index):
return self._items[index]

def __setitem__(self, index, value):
self._items[index] = value

def __len__(self):
return self._size

def clear(self, value=None):
self._items = [value] * len(self._items)

def __iter__(self):
for item in self._items:
yield item


class FullError(Exception):
pass


class EmptyError(Exception):
pass


class ArrayQueue():
def __init__(self, maxsize):
self.maxsize = maxsize
self.array = Array(maxsize)
self.head = 0
self.tail = 0

def push(self, value):
if len(self) >= self.maxsize:
raise FullError('full')
self.array[self.head % self.maxsize] = value
self.head += 1

def pop(self):
if len(self) <= 0:
raise EmptyError('empty')
value = self.array[self.tail % self.maxsize]
self.tail += 1
return value

def __len__(self):
return self.head - self.tail


def test():
import pytest
size = 5
q = ArrayQueue(size)
for i in range(size):
q.push(i)

with pytest.raises(FullError) as excinfo:
q.push(size)
assert 'full' in str(excinfo.value)

assert len(q) == size

assert q.pop() == 0
assert q.pop() == 1

q.push(5)
assert len(q) == 4

assert q.pop() == 2
assert q.pop() == 3
assert q.pop() == 4
assert q.pop() == 5

assert len(q) == 0



Deque

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
class Node():
def __init__(self, value=None, prev=None, next=None):
self.value, self.prev, self.next = value, prev, next


class CircularDoublyLinkedList():
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.next, node.prev = node, node
self.root = node
self.length = 0 # 增删操作时注意更新

def __len__(self):
return self.length

def headnode(self): # 增删操作时注意更新
return self.root.next

def tailnode(self): # 增删操作时注意更新
return self.root.prev

def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('full')
node = Node(value=value)
tailnode = self.tailnode()

tailnode.next = node
node.prev = tailnode
node.next = self.root
self.root.prev = node

self.length += 1

def appendleft(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('full')
node = Node(value=value)

if self.root.next is self.root:
node.next = self.root
node.prev = self.root
self.root.next = node
self.root.prev = node
else:
node.prev = self.root
headnode = self.root.next
node.next = headnode
headnode.prev = node
self.root.next = node
self.length += 1

def remove(self, node):
if node is self.root:
return
else:
node.prev.next = node.next
node.next.prev = node.prev
del node
self.length -= 1

def insert(self, key, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('full')

node = Node(value=value)
inserted = False
for curnode in self.iter_node():
if key == curnode.value:
node.prev = curnode
node.next = curnode.next
curnode.next.prev = node
curnode.next = node
inserted = True
break # 找到了匹配的节点并插入后,就可以退出循环了

if not inserted: # 如果没有插入节点(也就是没找到匹配的 key),则添加到链表的末尾
tailnode = self.tailnode()
node.prev = tailnode
node.next = self.root
tailnode.next = node
self.root.prev = node

self.length += 1

def iter_node(self):
if self.root.next is self.root:
return
curnode = self.root.next
while curnode.next is not self.root:
yield curnode
curnode = curnode.next
yield curnode

def __iter__(self):
for node in self.iter_node():
yield node.value

def iter_node_reverse(self):
if self.root.prev is self.root:
return
curnode = self.root.prev
while curnode.prev is not self.root:
yield curnode
curnode = curnode.prev
yield curnode


class Deque(CircularDoublyLinkedList):

def pop(self):
if len(self) == 0:
raise Exception('empty')
tailnode = self.tailnode()
value = tailnode.value
self.remove(tailnode)
return value

def popleft(self):
if len(self) == 0:
raise Exception('empty')
headnode = self.headnode()
value = headnode.value
self.remove(headnode)
return value



Stack

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
class Node():
def __init__(self, value=None, prev=None, next=None):
self.value, self.prev, self.next = value, prev, next


class CircularDoublyLinkedList():
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.next, node.prev = node, node
self.root = node
self.length = 0 # 增删操作时注意更新

def __len__(self):
return self.length

def headnode(self): # 增删操作时注意更新
return self.root.next

def tailnode(self): # 增删操作时注意更新
return self.root.prev

def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('full')
node = Node(value=value)
tailnode = self.tailnode()

tailnode.next = node
node.prev = tailnode
node.next = self.root
self.root.prev = node

self.length += 1

def appendleft(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('full')
node = Node(value=value)

if self.root.next is self.root:
node.next = self.root
node.prev = self.root
self.root.next = node
self.root.prev = node
else:
node.prev = self.root
headnode = self.root.next
node.next = headnode
headnode.prev = node
self.root.next = node
self.length += 1

def remove(self, node):
if node is self.root:
return
else:
node.prev.next = node.next
node.next.prev = node.prev
del node
self.length -= 1

def insert(self, key, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('full')

node = Node(value=value)
inserted = False
for curnode in self.iter_node():
if key == curnode.value:
node.prev = curnode
node.next = curnode.next
curnode.next.prev = node
curnode.next = node
inserted = True
break # 找到了匹配的节点并插入后,就可以退出循环了

if not inserted: # 如果没有插入节点(也就是没找到匹配的 key),则添加到链表的末尾
tailnode = self.tailnode()
node.prev = tailnode
node.next = self.root
tailnode.next = node
self.root.prev = node

self.length += 1

def iter_node(self):
if self.root.next is self.root:
return
curnode = self.root.next
while curnode.next is not self.root:
yield curnode
curnode = curnode.next
yield curnode

def __iter__(self):
for node in self.iter_node():
yield node.value

def iter_node_reverse(self):
if self.root.prev is self.root:
return
curnode = self.root.prev
while curnode.prev is not self.root:
yield curnode
curnode = curnode.prev
yield curnode


class Deque(CircularDoublyLinkedList):

def pop(self):
if len(self) == 0:
raise Exception('empty')
tailnode = self.tailnode()
value = tailnode.value
self.remove(tailnode)
return value

def popleft(self):
if len(self) == 0:
raise Exception('empty')
headnode = self.headnode()
value = headnode.value
self.remove(headnode)
return value


class Stack():
def __init__(self):
self.deque = Deque()

def push(self, value):
return self.deque.append(value)

def pop(self):
return self.deque.pop()

def __len__(self):
return len(self.deque)

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


def test():
import pytest
s = Stack()
for i in range(3):
s.push(i)

assert len(s) == 3
assert s.pop() == 2
assert s.pop() == 1
assert s.pop() == 0

assert s.is_empty()

with pytest.raises(Exception) as excinfo:
s.pop()
assert 'empty' in str(excinfo.value)



HashTable

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
class Array():
def __init__(self, size=32, init=None):
self._size = size
self._items = [init] * size

def __getitem__(self, index):
return self._items[index]

def __setitem__(self, index, value):
self._items[index] = value

def __len__(self):
return self._size

def clear(self, value=None):
self._items = [value] * len(self._items)

def __iter__(self):
for item in self._items:
yield item


class Slot():
def __init__(self, key, value):
self.key, self.value = key, value


class HashTable():
UNUSED = None
EMPTY = Slot(None, None)

def __init__(self):
self._table = Array(8, init=HashTable.UNUSED)
self.length = 0

@property
def _load_factor(self):
return self.length / float(len(self._table))

def __len__(self):
return self.length

def _hash(self, key):
return abs(hash(key)) % len(self._table)

def _find_key(self, key):
index = self._hash(key)
_len = len(self._table)
while self._table[index] is not HashTable.UNUSED:
if self._table[index] is HashTable.EMPTY:
index = (index * 5 + 1) % _len
continue
elif self._table[index].key == key:
return index
else:
index = (index * 5 + 1) % _len
return None

def _slot_can_insert(self, index):
return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED)

def _find_slot_for_insert(self, key):
index = self._hash(key)
_len = len(self._table)
while not self._slot_can_insert(index):
index = (index * 5 + 1) % _len
return index

def __contains__(self, key):
index = self._find_key(key)
return index is not None

def add(self, key, value):
if key in self:
index = self._find_key(key)
self._table[index].value = value
return False
else:
index = self._find_slot_for_insert(key)
self._table[index] = Slot(key, value)
self.length += 1
if self._load_factor >= 0.8:
self._rehash()
return True

def _rehash(self):
old_table = self._table
newsize = len(self._table) * 2
self._table = Array(newsize, HashTable.UNUSED)
self.length = 0

for slot in old_table:
if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY:
index = self._find_slot_for_insert(slot.key)
self._table[index] = slot
self.length += 1

def get(self, key, default=None):
index = self._find_key(key)
if index is None:
return default
else:
return self._table[index].value

def remove(self, key):
index = self._find_key(key)
if index is None:
raise KeyError()
value = self._table[index].value
self.length -= 1
self._table[index] = HashTable.EMPTY
return value

def __iter__(self):
for slot in self._table:
if slot not in (HashTable.EMPTY, HashTable.UNUSED):
yield slot.key


def test():
import pytest
h = HashTable()
h.add('a', 0)
h.add('b', 1)
h.add('c', 2)
assert len(h) == 3
assert h.get('a') == 0
assert h.get('b') == 1
assert h.get('c') == 2
assert h.get('asd') is None

h.remove('a')
assert h.get('a') is None
assert sorted(list(h)) == ['b', 'c']

n = 50
for i in range(n):
h.add(i, i)

for i in range(n):
assert h.get(i) == i



dict_adt

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
class Array():
def __init__(self, size=32, init=None):
self._size = size
self._items = [init] * size

def __getitem__(self, index):
return self._items[index]

def __setitem__(self, index, value):
self._items[index] = value

def __len__(self):
return self._size

def clear(self, value=None):
self._items = [value] * len(self._items)

def __iter__(self):
for item in self._items:
yield item


class Slot():
def __init__(self, key, value):
self.key, self.value = key, value


class HashTable():
UNUSED = None
EMPTY = Slot(None, None)

def __init__(self):
self._table = Array(8, init=HashTable.UNUSED)
self.length = 0

@property
def _load_factor(self):
return self.length / float(len(self._table))

def __len__(self):
return self.length

def _hash(self, key):
return abs(hash(key)) % len(self._table)

def _find_key(self, key):
index = self._hash(key)
_len = len(self._table)
while self._table[index] is not HashTable.UNUSED:
if self._table[index] is HashTable.EMPTY:
index = (index * 5 + 1) % _len
continue
elif self._table[index].key == key:
return index
else:
index = (index * 5 + 1) % _len
return None

def _slot_can_insert(self, index):
return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED)

def _find_slot_for_insert(self, key):
index = self._hash(key)
_len = len(self._table)
while not self._slot_can_insert(index):
index = (index * 5 + 1) % _len
return index

def __contains__(self, key):
index = self._find_key(key)
return index is not None

def add(self, key, value):
if key in self:
index = self._find_key(key)
self._table[index].value = value
return False
else:
index = self._find_slot_for_insert(key)
self._table[index] = Slot(key, value)
self.length += 1
if self._load_factor >= 0.8:
self._rehash()
return True

def _rehash(self):
old_table = self._table
newsize = len(self._table) * 2
self._table = Array(newsize, HashTable.UNUSED)
self.length = 0

for slot in old_table:
if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY:
index = self._find_slot_for_insert(slot.key)
self._table[index] = slot
self.length += 1

def get(self, key, default=None):
index = self._find_key(key)
if index is None:
return default
else:
return self._table[index].value

def remove(self, key):
index = self._find_key(key)
if index is None:
raise KeyError()
value = self._table[index].value
self.length -= 1
self._table[index] = HashTable.EMPTY
return value

def __iter__(self):
for slot in self._table:
if slot not in (HashTable.EMPTY, HashTable.UNUSED):
yield slot.key


class DictADT(HashTable):

def __setitem__(self, key, value):
self.add(key, value)

def __getitem__(self, key):
if key not in self:
raise KeyError()
else:
return self.get(key)

def _iter_slot(self):
for slot in self._table:
if slot not in (HashTable.EMPTY, HashTable.UNUSED):
yield slot

def items(self):
for slot in self._iter_slot():
yield (slot.key, slot.value)

def keys(self):
for slot in self._iter_slot():
yield slot.key

def values(self):
for slot in self._iter_slot():
yield slot.value


def test():
import random
import pytest

d = DictADT()

d['a'] = 1
assert d['a'] == 1
d.remove('a')

l = list(range(30))
random.shuffle(l)
for i in l:
d.add(i, i)

for i in range(30):
assert d.get(i) == i

assert sorted(list(d.keys())) == sorted(l)



set_adt

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
class Array():
def __init__(self, size=32, init=None):
self._size = size
self._items = [init] * size

def __getitem__(self, index):
return self._items[index]

def __setitem__(self, index, value):
self._items[index] = value

def __len__(self):
return self._size

def clear(self, value=None):
self._items = [value] * len(self._items)

def __iter__(self):
for item in self._items:
yield item


class Slot():
def __init__(self, key, value):
self.key, self.value = key, value


class HashTable():
UNUSED = None
EMPTY = Slot(None, None)

def __init__(self):
self._table = Array(8, init=HashTable.UNUSED)
self.length = 0

@property
def _load_factor(self):
return self.length / float(len(self._table))

def __len__(self):
return self.length

def _hash(self, key):
return abs(hash(key)) % len(self._table)

def _find_key(self, key):
index = self._hash(key)
_len = len(self._table)
while self._table[index] is not HashTable.UNUSED:
if self._table[index] is HashTable.EMPTY:
index = (index * 5 + 1) % _len
continue
elif self._table[index].key == key:
return index
else:
index = (index * 5 + 1) % _len
return None

def _slot_can_insert(self, index):
return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED)

def _find_slot_for_insert(self, key):
index = self._hash(key)
_len = len(self._table)
while not self._slot_can_insert(index):
index = (index * 5 + 1) % _len
return index

def __contains__(self, key):
index = self._find_key(key)
return index is not None

def add(self, key, value):
if key in self:
index = self._find_key(key)
self._table[index].value = value
return False
else:
index = self._find_slot_for_insert(key)
self._table[index] = Slot(key, value)
self.length += 1
if self._load_factor >= 0.8:
self._rehash()
return True

def _rehash(self):
old_table = self._table
newsize = len(self._table) * 2
self._table = Array(newsize, HashTable.UNUSED)
self.length = 0

for slot in old_table:
if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY:
index = self._find_slot_for_insert(slot.key)
self._table[index] = slot
self.length += 1

def get(self, key, default=None):
index = self._find_key(key)
if index is None:
return default
else:
return self._table[index].value

def remove(self, key):
index = self._find_key(key)
if index is None:
raise KeyError()
value = self._table[index].value
self.length -= 1
self._table[index] = HashTable.EMPTY
return value

def __iter__(self):
for slot in self._table:
if slot not in (HashTable.EMPTY, HashTable.UNUSED):
yield slot.key


class SetADT(HashTable):

def add(self, key):
return super(SetADT, self).add(key, True)

def __and__(self, other_set):
new_set = SetADT()
for element_a in self:
if element_a in other_set:
new_set.add(element_a)
return new_set

def __sub__(self, other_set):
new_set = SetADT()
for element_a in self:
if element_a not in other_set:
new_set.add(element_a)
return new_set

def __or__(self, other_set):
new_set = SetADT()
for element_a in self:
new_set.add(element_a)
for element_b in other_set:
new_set.add(element_b)
return new_set

def __xor__(self, other_set):
return (self | other_set) - (self & other_set)


def test():
import pytest

sa = SetADT()
sa.add(1)
sa.add(2)
sa.add(3)
assert 1 in sa

sb = SetADT()
sb.add(3)
sb.add(4)
sb.add(5)

assert sorted(list(sa & sb)) == [3]
assert sorted(list(sa - sb)) == [1, 2]
assert sorted(list(sa | sb)) == [1, 2, 3, 4, 5]
assert sorted(list(sa ^ sb)) == [1, 2, 4, 5]



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
def binary_search(sorted_array, val):
if not sorted_array:
return -1

beg = 0
end = len(sorted_array) - 1

while beg <= end:
mid = beg + (end - beg) // 2
if sorted_array[mid] == val:
return mid
elif sorted_array[mid] > val:
end = mid - 1
else:
beg = mid + 1
return -1


def binary_search_recursive(sorted_array, val, beg=0, end=None):
if end is None:
end = len(sorted_array) - 1

if beg > end:
return -1

mid = beg + (end - beg) // 2

if sorted_array[mid] == val:
return mid

if sorted_array[mid] > val:
return binary_search_recursive(sorted_array, val, beg, mid - 1)
else:
return binary_search_recursive(sorted_array, val, mid + 1, end)


def test():
import pytest

asd = [1, 2, 3, 4, 5]
assert binary_search(asd, 3) == 2
assert binary_search_recursive(asd, 3) == 2

dsa = [5, 4, 3, 2, 1]
assert binary_search(asd, 3) == 2
assert binary_search_recursive(asd, 3) == 2



bubble_sort

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
import random


def bubble_sort(seq):
n = len(seq)
for i in range(n - 1):
for j in range(n - 1 - i):
if seq[j] > seq[j + 1]:
seq[j], seq[j + 1] = seq[j + 1], seq[j]


def test_bubble_sort():
seq = list(range(10))
random.shuffle(seq)
sorted_seq = sorted(seq)
bubble_sort(seq)
assert seq == sorted_seq


def select_sort(seq):
n = len(seq)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if seq[j] < seq[min_idx]:
min_idx = j
if min_idx != i:
seq[i], seq[min_idx] = seq[min_idx], seq[i]


def test_select_sort():
seq = list(range(10))
random.shuffle(seq)
sorted_seq = sorted(seq)
select_sort(seq)
assert seq == sorted_seq


def insertion_sort(seq):
n = len(seq)
for i in range(1, n):
value = seq[i]
pos = i
while pos > 0 and value < seq[pos - 1]:
seq[pos] = seq[pos - 1]
pos -= 1
seq[pos] = value


def test_insertion_sort():
seq = list(range(10))
random.shuffle(seq)
sorted_seq = sorted(seq)
insertion_sort(seq)
assert seq == sorted_seq



merge_sort

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
def merge_sort(seq):
if len(seq) <= 1:
return seq
else:
mid = int(len(seq) / 2)
left_half = merge_sort(seq[:mid])
right_half = merge_sort(seq[mid:])

new_seq = merge_sorted_list(left_half, right_half)
return new_seq


def merge_sorted_list(sorted_a, sorted_b):
length_a, length_b = len(sorted_a), len(sorted_b)
a = b = 0
new_sorted_seq = list()

while a < length_a and b < length_b:
if sorted_a[a] < sorted_b[b]:
new_sorted_seq.append(sorted_a[a])
a += 1
else:
new_sorted_seq.append(sorted_b[b])
b += 1

while a < length_a:
new_sorted_seq.append(sorted_a[a])
a += 1

while b < length_b:
new_sorted_seq.append(sorted_b[b])
b += 1

return new_sorted_seq


def test():
import random

seq = list(range(10))
random.shuffle(seq)
assert merge_sort(seq) == sorted(seq)



quick_sort

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
def quicksort(array):
if len(array) < 2:
return array
else:
pivot_index = 0
pivot = array[pivot_index]
less_part = [i for i in array[pivot_index + 1:] if i <= pivot]
great_port = [i for i in array[pivot_index + 1:] if i > pivot]
return quicksort(less_part) + [pivot] + quicksort(great_port)


def test():
import random

seq = list(range(10))
random.shuffle(seq)
assert quicksort(seq) == sorted(seq)


def partition(array, beg, end):
pivot_index = beg
pivot = array[pivot_index]
left = pivot_index + 1
right = end - 1

while True:
while left <= right and array[left] < pivot:
left += 1

while right >= left and array[right] >= pivot:
right -= 1

if left > right:
break
else:
array[left], array[right] = array[right], array[left]

array[pivot_index], array[right] = array[right], array[pivot_index]
return right


def test_partition():
l = [4, 1, 2, 8]
assert partition(l, 0, len(l)) == 2
l = [1, 2, 3, 4]
assert partition(l, 0, len(l)) == 0
l = [4, 3, 2, 1]
assert partition(l, 0, len(l)) == 3


def quicksort_inplace(array, beg, end):
if beg < end:
pivot = partition(array, beg, end)
quicksort_inplace(array, beg, pivot)
quicksort_inplace(array, pivot + 1, end)
return array


def test_quicksort_inplace():
import random

seq = list(range(10))
random.shuffle(seq)
assert quicksort_inplace(seq, 0, len(seq)) == sorted(seq)