-
Notifications
You must be signed in to change notification settings - Fork 0
/
arraylist.py
99 lines (83 loc) · 3.01 KB
/
arraylist.py
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
"""
File: arraylist.py
Author: Leigh Stauffer
Project 8
"""
from arrays import Array
from abstractlist import AbstractList
class ArrayList(AbstractList):
"""Represents an array-based list."""
DEFAULT_CAPACITY = 10
def __init__(self, sourceCollection = None):
"""Sets the initial state of self, which includes the
contents of sourceCollection, if it's present."""
self._items = Array(ArrayList.DEFAULT_CAPACITY)
AbstractList.__init__(self, sourceCollection)
# Accessor methods
def __getitem__(self, i):
"""Precondition: 0 <= i < len(self)
Returns the item at position i.
Raises: IndexError if i is out of range."""
if i < 0 or i >= len(self):
raise IndexError("List index out of range")
return self._items[i]
def __iter__(self):
"""Supports iteration over a view of self."""
cursor = 0
while cursor < len(self):
yield self._items[cursor]
cursor += 1
# Mutator methods
def clear(self):
"""Makes self become empty."""
self._size = 0
self._items = Array(ArrayList.DEFAULT_CAPACITY)
self.incModCount()
def __setitem__(self, i, item):
"""Precondition: 0 <= i < len(self)
Replaces the item at position i.
Raises: IndexError if i is out of range."""
if i < 0 or i >= len(self):
raise IndexError("List index out of range")
self._items[i] = item
def _resize(self):
"""Private helper method to resize the array if necessary."""
temp = None
if len(self) == len(self._items):
temp = Array(2 * len(self._items))
elif len(self) <= len(self._items) // 4 and \
len(self._items) >= 2 * ArrayList.DEFAULT_CAPACITY:
temp = Array(len(self.items) // 2)
if temp:
for i in range(len(self)):
temp[i] = self._items[i]
self._items = temp
def insert(self, i, item):
"""Inserts the item at position i."""
self._resize()
if i < 0: i = 0
elif i > len(self): i = len(self)
if i < len(self):
for j in range(len(self), i, -1):
self._items[j] = self._items[j - 1]
self._items[i] = item
self._size += 1
self.incModCount()
def pop(self, i = None):
"""Precondition: 0 <= i < len(self)
Removes and returns the item at position i.
If i is None, i is given a default of len(self) - 1.
Raises: IndexError if i is out of range."""
if i == None: i = len(self) - 1
if i < 0 or i >= len(self):
raise IndexError("List index out of range")
item = self._items[i]
for j in range(i, len(self) - 1):
self._items[j] = self._items[j + 1]
self._size -= 1
self._resize()
self.incModCount()
return item
def listIterator(self):
"""Returns a list iterator."""
return ArrayList.ListIterator(self)