DataAlgoHub/Data_structures/arrray.py at main · yaaa3ser/DataAlgoHub · GitHub

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
class DynamicArray:
    def __init__(self, capacity = 1):
        self.size = 0
        self.capacity = capacity
        self.arr = [None] * capacity

    def retrieve(self):
        for i in range(self.size):
            print(self.arr[i], end = " ")
        print()

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

    def is_full(self):
        return self.size == self.capacity

    def at(self, index):
        if index < 0 or index >= self.size:
            return "Index out of bounds"
        return self.arr[index]
    # private method
    def __resize(self, new_capacity):
        new_arr = [None] * new_capacity
        for i in range(self.size):
            new_arr[i] = self.arr[i]
        self.arr = new_arr
        self.capacity = new_capacity

    def push(self, item):
        if self.is_full():
            self.__resize(self.capacity * 2)
        self.arr[self.size] = item
        self.size+=1

    def insert(self, index, item):
        if self.is_full():
            self.__resize(self.capacity * 2)
        if index < 0 or index >= self.size:
            return "Index out of bounds"
        for i in range (self.size, index, -1):
            self.arr[i] = self.arr[i-1]
        self.arr[index] = item
        self.size+=1
    # remove from end, return value
    def pop(self):
        if self.is_empty():
            return "Array is empty"
        self.size-=1
        if self.size < self.capacity // 4:
            self.__resize(self.capacity // 2)
        return self.arr[self.size]
    # delete item at index, shifting all trailing elements left
    def delete(self, index):
        if self.is_empty():
            return "Array is empty"
        if index < 0 or index >= self.size:
            return "Index out of bounds"
        for i in range(index, self.size-1):
            self.arr[i] = self.arr[i+1]
        self.size-=1
    # looks for value and removes index holding it (even if in multiple places)
    def remove(self, item):
        if self.is_empty():
            return "Array is empty"
        i = 0
        while i < self.size:
            if self.arr[i] == item:
                self.delete(i)
                # don't increment i here, since the next item may also be the same
            else:
                i += 1

    # looks for value and returns first index with that value, -1 if not found
    def find(self, item):
        if self.is_empty():
            return "Array is empty"
        for i in range(self.size):
            if self.arr[i] == item:
                return i
        return -1


# "============================================="
# "================= TESTING ==================="
# "============================================="
# arr = DynamicArray()
# print(arr.size)
# print(arr.capacity)
# print(arr.is_empty())
# arr.push(5)
# arr.push(4)
# print(arr.capacity)
# print(arr.is_full())
# arr.push(7)
# print(arr.capacity)
# print(arr.is_full())
# arr.retrieve()
# arr.insert(1, 6)
# arr.retrieve()
# arr.insert(3, 64)
# arr.retrieve()
# arr.pop()
# arr.retrieve()
# assert (arr.at(4) == "Index out of bounds")
# arr.delete(0)
# arr.retrieve()
# arr.push(3)
# arr.push(3)
# arr.push(3)
# arr.retrieve()
# arr.remove(3)
# arr.retrieve()
# print(arr.find(3))
# print(arr.find(6))