Algorithm-and-Data-Structure/DataStructure/DynamicArray.java at master · lemidia/Algorithm-and-Data-Structure · 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
116
117
118
119
120
121
122
123
124
125
126
/**
 * A generic dynamic array implementation
 *
 * @author William Fiset, william.alexandre.fiset@gmail.com
 */

@SuppressWarnings("unchecked")
publicclassDynamicArray<T> implementsIterable<T> {

privateT[] arr;
privateintlen = 0; // length user thinks array is
privateintcapacity = 0; // Actual array size

publicDynamicArray() {
this(16);
 }

publicDynamicArray(intcapacity) {
if (capacity < 0) thrownewIllegalArgumentException("Illegal Capacity: " + capacity);
this.capacity = capacity;
arr = (T[]) newObject[capacity];
 }

publicintsize() {
returnlen;
 }

publicbooleanisEmpty() {
returnsize() == 0;
 }

publicTget(intindex) {
returnarr[index];
 }

publicvoidset(intindex, Telem) {
arr[index] = elem;
 }

publicvoidclear() {
for (inti = 0; i < len; i++) arr[i] = null;
len = 0;
 }

publicvoidadd(Telem) {

// Time to resize!
if (len + 1 >= capacity) {
if (capacity == 0) capacity = 1;
elsecapacity *= 2; // double the size
T[] new_arr = (T[]) newObject[capacity];
for (inti = 0; i < len; i++) new_arr[i] = arr[i];
arr = new_arr; // arr has extra nulls padded
 }

arr[len++] = elem;
 }

// Removes an element at the specified index in this array.
publicTremoveAt(intrm_index) {
if (rm_index >= len || rm_index < 0) thrownewIndexOutOfBoundsException();
Tdata = arr[rm_index];
T[] new_arr = (T[]) newObject[len - 1];
for (inti = 0, j = 0; i < len; i++, j++)
if (i == rm_index) j--; // Skip over rm_index by fixing j temporarily
elsenew_arr[j] = arr[i];
arr = new_arr;
capacity = --len;
returndata;
 }

publicbooleanremove(Objectobj) {
intindex = indexOf(obj);
if (index == -1) returnfalse;
removeAt(index);
returntrue;
 }

publicintindexOf(Objectobj) {
for (inti = 0; i < len; i++) {
if (obj == null) {
if (arr[i] == null) returni;
 } else {
if (obj.equals(arr[i])) returni;
 }
 }
return -1;
 }

publicbooleancontains(Objectobj) {
returnindexOf(obj) != -1;
 }

// Iterator is still fast but not as fast as iterative for loop
@Override
publicjava.util.Iterator<T> iterator() {
returnnewjava.util.Iterator<T>() {
intindex = 0;

@Override
publicbooleanhasNext() {
returnindex < len;
 }

@Override
publicTnext() {
returnarr[index++];
 }

@Override
publicvoidremove() {
thrownewUnsupportedOperationException();
 }
 };
 }

@Override
publicStringtoString() {
if (len == 0) return"[]";
else {
StringBuildersb = newStringBuilder(len).append("[");
for (inti = 0; i < len - 1; i++) sb.append(arr[i] + ", ");
returnsb.append(arr[len - 1] + "]").toString();
 }
 }
}