forked from patmorin/ods
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathArrayStack.java
More file actions
138 lines (122 loc) · 2.89 KB
/
ArrayStack.java
File metadata and controls
138 lines (122 loc) · 2.89 KB
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
package ods;
import java.util.AbstractList;
import java.util.Collection;
/**
* This is a copy of the JCF class ArrayList. It implements the List
* interface as a single array a. Elements are stored at positions
* a[0],...,a[size()-1]. Doubling/halving is used to resize the array
* a when necessary.
* @author morin
*
* @param <T> the type of objects stored in the List
*/
public class ArrayStack<T> extends AbstractList<T> {
/**
* keeps track of the class of objects we store
*/
Factory<T> f;
/**
* The array used to store elements
*/
T[] a;
/**
* The number of elements stored
*/
int n;
/**
* Resize the internal array
*/
protected void resize() {
T[] b = f.newArray(Math.max(n*2,1));
for (int i = 0; i < n; i++) {
b[i] = a[i];
}
a = b;
}
/**
* Resize the internal array
*/
protected void resize(int nn) {
T[] b = f.newArray(nn);
for (int i = 0; i < n; i++) {
b[i] = a[i];
}
a = b;
}
/**
* Constructor
* @param t0 the type of objects that are stored in this list
*/
public ArrayStack(Class<T> t) {
f = new Factory<T>(t);
a = f.newArray(1);
n = 0;
}
public T get(int i) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
return a[i];
}
public int size() {
return n;
}
public T set(int i, T x) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
T y = a[i];
a[i] = x;
return y;
}
public void add(int i, T x) {
if (i < 0 || i > n) throw new IndexOutOfBoundsException();
if (n + 1 > a.length) resize();
for (int j = n; j > i; j--)
a[j] = a[j-1];
a[i] = x;
n++;
}
public T remove(int i) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
T x = a[i];
for (int j = i; j < n-1; j++)
a[j] = a[j+1];
n--;
if (a.length >= 3*n) resize();
return x;
}
// The following methods are not strictly necessary. The parent
// class, AbstractList, has default implementations of them, but
// our implementations are more efficient - especially addAll
/**
* A small optimization for a frequently used method
*/
public boolean add(T x) {
if (n + 1 > a.length) resize();
a[n++] = x;
return true;
}
/**
* We override addAll because AbstractList implements it by
* repeated calls to add(i,x), which can take time
* O(size()*c.size()). This happens, for example, when i = 0.
* This version takes time O(size() + c.size()).
*/
public boolean addAll(int i, Collection<? extends T> c) {
if (i < 0 || i > n) throw new IndexOutOfBoundsException();
int k = c.size();
if (n + k > a.length) resize(2*(n+k));
for (int j = n+k-1; j >= i+k; j--)
a[j] = a[j-k];
for (T x : c)
a[i++] = x;
n += k;
return true;
}
/**
* We override this method because AbstractList implements by
* repeated calls to remove(size()), which takes O(size()) time.
* This implementation runs in O(1) time.
*/
public void clear() {
n = 0;
resize();
}
}