-
Notifications
You must be signed in to change notification settings - Fork 14
/
CustomArrayList.java
152 lines (120 loc) · 4.01 KB
/
CustomArrayList.java
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
package by.andd3dfx.collections.custom;
import lombok.RequiredArgsConstructor;
import java.util.Arrays;
import java.util.Iterator;
/**
* @see <a href="https://youtu.be/u7Vyh567ljs">Video solution</a>
*/
public class CustomArrayList<T> implements Iterable<T> {
private static final int DEFAULT_INITIAL_SIZE = 10;
private static final float RESIZE_FACTOR = 1.75f;
private static final float INVERSE_RESIZE_FACTOR = 1 / RESIZE_FACTOR;
private T[] array;
private int size = 0;
public CustomArrayList() {
this(DEFAULT_INITIAL_SIZE);
}
public CustomArrayList(int length) {
array = (T[]) new Object[length];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void set(int index, T value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException(String.format("Wrong index: %d", index));
}
array[index] = value;
}
public void add(T value) {
add(size, value);
}
public void add(int index, T value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
if (size == array.length) {
int oldLength = array.length;
int newLength = Math.round(RESIZE_FACTOR * oldLength);
var newArray = (T[]) new Object[newLength];
System.arraycopy(array, 0, newArray, 0, size);
array = newArray;
System.out.println("Inner array size increased: %s->%s".formatted(oldLength, newLength));
}
if (index < size) {
System.arraycopy(array, index, array, index + 1, size - index);
}
array[index] = value;
size++;
}
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException(String.format("Wrong index: %d", index));
}
return array[index];
}
public T remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException(String.format("Wrong index: %d", index));
}
var result = array[index];
System.arraycopy(array, index + 1, array, index, size - index);
size--;
if (size < array.length / 2 && array.length > DEFAULT_INITIAL_SIZE) {
int oldLength = array.length;
int newLength = Math.round(INVERSE_RESIZE_FACTOR * oldLength);
var newArray = (T[]) new Object[newLength];
System.arraycopy(array, 0, newArray, 0, size);
array = newArray;
System.out.println("Inner array size decreased: %s->%s".formatted(oldLength, newLength));
}
return result;
}
public boolean remove(T value) {
var i = 0;
while (i < size) {
T currValue = array[i];
if (checkEquality(value, currValue)) {
remove(i);
return true;
}
i++;
}
return false;
}
private boolean checkEquality(T value1, T value2) {
if (value1 == null) {
return value2 == null;
}
return value1.equals(value2);
}
public void clear() {
array = (T[]) new Object[DEFAULT_INITIAL_SIZE];
size = 0;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(array, size));
}
@Override
public Iterator<T> iterator() {
return new CustomIterator(array, size);
}
@RequiredArgsConstructor
public class CustomIterator<E> implements Iterator<E> {
private final E[] array;
private final int size;
private int curr = 0;
@Override
public boolean hasNext() {
return curr < size;
}
@Override
public E next() {
return array[curr++];
}
}
}