blob: 19d9295672118daf1810dfd702e7148b441f1ae1 (
plain)
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
|
/* vim: set expandtab tabstop=4 shiftwidth=4 : */
import java.util.Iterator;
public class RandomizedQueue<Item> implements Iterable<Item>
{
private int n;
private Item[] items;
// construct an empty randomized queue
public RandomizedQueue()
{
n = 0;
items = (Item[]) new Object[1];
}
// is the queue empty?
public boolean isEmpty() { return n == 0; }
// return the number of items on the queue
public int size() { return n; }
// add the item
public void enqueue(Item item)
{
if (item == null) throw new java.lang.NullPointerException();
if (n == items.length)
{
Item[] copy = (Item[]) new Object[n*2];
for (int i = 0; i < n; i++)
copy[i] = items[i];
items = copy;
}
items[n++] = item;
}
// delete and return a random item
public Item dequeue()
{
if (n == 0) throw new java.util.NoSuchElementException();
int r = StdRandom.uniform(n);
Item item = items[r];
items[r] = items[--n];
items[n] = null;
if (n > 0 && n == items.length/4)
{
Item[] copy = (Item[]) new Object[items.length/2];
for (int i = 0; i < n; i++)
copy[i] = items[i];
items = copy;
}
return item;
}
// return (but do not delete) a random item
public Item sample()
{
if (n == 0) throw new java.util.NoSuchElementException();
return items[StdRandom.uniform(n)];
}
// return an independent iterator over items in random order
public Iterator<Item> iterator() { return new RandomizedQueueIterator(); }
private class RandomizedQueueIterator implements Iterator<Item>
{
// must be random !!!!
private int idx;
private int[] random;
public RandomizedQueueIterator()
{
idx = 0;
random = new int[n];
for (int i = 0; i < n; i++)
random[i] = i;
for (int i = 0; i < n; i++)
{
int r = StdRandom.uniform(i + 1);
int tmp = random[i];
random[i] = random[r];
random[r] = tmp;
}
}
public boolean hasNext()
{ return idx < n; }
public void remove()
{ throw new java.lang.UnsupportedOperationException(); }
public Item next()
{
if (idx >= n) throw new java.util.NoSuchElementException();
Item item = items[random[idx++]];
return item;
}
}
}
|
