-
Notifications
You must be signed in to change notification settings - Fork 1
/
FastDefaultList.java
224 lines (203 loc) · 5.15 KB
/
FastDefaultList.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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
package comp2402a3;
import java.lang.reflect.Array;
import java.lang.IllegalStateException;
import java.util.AbstractList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Random;
/**
* Implements the List interface as a skiplist so that all the
* standard operations take O(log n) time
*
* TODO: Modify this so that it creates a DefaultList, which is basically
* an infinitely long list whose values start out as null
*
*/
public class FastDefaultList<T> extends AbstractList<T> {
class Node {
T x;
Node[] next;
int[] length;
int j; //index of current node
@SuppressWarnings("unchecked")
public Node(T ix, int h, int j) {
x = ix;
next = (Node[])Array.newInstance(Node.class, h+1);
length = new int[h+1];
this.j = j;
}
public int height() {
return next.length - 1;
}
/*
public int getJ() {
return this.j;
}
*/
//in the case that j must be changed in the future
public void setJ(int i) {
this.j = i;
}
}
/**
* This node sits on the left side of the skiplist
*/
protected Node sentinel;
/**
* The maximum height of any element
*/
int h;
/**
* A source of random numbers
*/
Random rand;
public FastDefaultList() {
sentinel = new Node(null, 32, 0);
h = 0;
rand = new Random(0);
}
/**
* Find the node that precedes list index i in the skiplist.
*
* @param x - the value to search for
* @return the predecessor of the node at index i or the final
* node if i exceeds size() - 1.
*/
protected Node findPred(int i) {
Node u = sentinel;
int r = h;
int j = -1; // index of the current node in list 0
while (r >= 0) {
while (u.next[r] != null && j + u.length[r] < i) {
j += u.length[r];
u = u.next[r];
}
r--;
}
return u; //now returns u and j (index)
}
public T get(int i) {
// Hint: this is too restrictive any non-negative i is allowed
//if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
if (i > size()-1 || i < 0) throw new IndexOutOfBoundsException(); //can't have a negative index
Node z = findPred(i);
if (z.next[0] != null) {
if (z.next[0].j == i) {
return z.next[0].x; //found it
}
}
return null;
}
public T set(int i, T x) {
// Hint: this is too restrictive any non-negative i is allowed
//if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
if (i > size()-1 || i < 0) throw new IndexOutOfBoundsException(); //can't have a negative index
Node z = findPred(i); T replace = null;
if (z.next[0] != null) {
if (z.next[0].j == i) {
replace = z.next[0].x;
z.next[0].x = x;
return replace;
}
}
return null;
}
/**
* Insert a new node into the skiplist
* @param i the index of the new node
* @param w the node to insert
* @return the node u that precedes v in the skiplist
*/
protected Node add(int i, Node w) {
Node u = sentinel;
int k = w.height();
int r = h;
int j = -1; // index of u
while (r >= 0) {
while (u.next[r] != null && j+u.length[r] < i) {
j += u.length[r];
u = u.next[r];
}
u.length[r]++; // accounts for new node in list 0
if (r <= k) {
w.next[r] = u.next[r];
u.next[r] = w;
w.length[r] = u.length[r] - (i - j);
u.length[r] = i - j;
}
r--;
}
return u;
}
/**
* Simulate repeatedly tossing a coin until it comes up tails.
* Note, this code will never generate a height greater than 32
* @return the number of coin tosses - 1
*/
protected int pickHeight() {
int z = rand.nextInt();
int k = 0;
int m = 1;
while ((z & m) != 0) {
k++;
m <<= 1;
}
return k;
}
public void add(int i, T x) {
// Hint: bounds checking again!
//if (i < 0 || i > n) throw new IndexOutOfBoundsException();
if (i > size()-1 || i < 0) throw new IndexOutOfBoundsException(); //can't have a negative index
Node w = new Node(x, pickHeight(), i); //so we can return j at findPred(i)
if (w.height() > h)
h = w.height();
add(i, w);
}
public T remove(int i) {
// Hint: bounds checking again!
//if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
if (i > size()-1 || i < 0) throw new IndexOutOfBoundsException(); //can't have a negative index
T x = null;
Node u = sentinel;
int r = h;
int j = -1; // index of node u
while (r >= 0) {
while (u.next[r] != null && j+u.length[r] < i) {
j += u.length[r];
u = u.next[r];
}
u.length[r]--; // for the node we are removing
if (j + u.length[r] + 1 == i && u.next[r] != null) {
x = u.next[r].x;
u.length[r] += u.next[r].length[r];
u.next[r] = u.next[r].next[r];
if (u == sentinel && u.next[r] == null)
h--;
}
r--;
}
//reset
u = sentinel; r = 0;
return x;
}
public int size() {
return Integer.MAX_VALUE;
}
public String toString() {
// This is just here to help you a bit with debugging
StringBuilder sb = new StringBuilder();
int i = -1;
Node u = sentinel;
while (u.next[0] != null) {
i += u.length[0];
u = u.next[0];
sb.append(" " + i + "=>" + u.x);
}
return sb.toString();
}
public static void main(String[] args) {
Tester.testDefaultList(new FastDefaultList<Integer>());
}
}