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 org.apache.thrift;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
/**
* IntRangeSet is a specialized Set<Integer> implementation designed
* specifically to make the generated validate() method calls faster. It groups
* the set values into ranges, and in the contains() call, it does
* num ranges * 2 comparisons max. For the common case, which is a single,
* contiguous range, this approach is about 60% faster than using a HashSet. If
* you had a very ragged value set, like all the odd numbers, for instance,
* then you would end up with pretty poor running time.
*/
public class IntRangeSet implements Set<Integer> {
/**
* This array keeps the bounds of each extent in alternating cells, always
* increasing. Example: [0,5,10,15], which corresponds to 0-5, 10-15.
*/
private int[] extents;
/**
* We'll keep a duplicate, real HashSet around internally to satisfy some of
* the other set operations.
*/
private Set<Integer> realSet = new HashSet<Integer>();
public IntRangeSet(int... values) {
Arrays.sort(values);
List<Integer> extent_list = new ArrayList<Integer>();
int ext_start = values[0];
int ext_end_so_far = values[0];
for (int i = 1; i < values.length; i++) {
realSet.add(values[i]);
if (values[i] == ext_end_so_far + 1) {
// advance the end so far
ext_end_so_far = values[i];
} else {
// create an extent for everything we saw so far, move on to the next one
extent_list.add(ext_start);
extent_list.add(ext_end_so_far);
ext_start = values[i];
ext_end_so_far = values[i];
}
}
extent_list.add(ext_start);
extent_list.add(ext_end_so_far);
extents = new int[extent_list.size()];
for (int i = 0; i < extent_list.size(); i++) {
extents[i] = extent_list.get(i);
}
}
public boolean add(Integer i) {
throw new UnsupportedOperationException();
}
public void clear() {
throw new UnsupportedOperationException();
}
public boolean addAll(Collection<? extends Integer> arg0) {
throw new UnsupportedOperationException();
}
/**
* While this method is here for Set interface compatibility, you should avoid
* using it. It incurs boxing overhead! Use the int method directly, instead.
*/
public boolean contains(Object arg0) {
return contains(((Integer)arg0).intValue());
}
/**
* This is much faster, since it doesn't stop at Integer on the way through.
* @param val the value you want to check set membership for
* @return true if val was found, false otherwise
*/
public boolean contains(int val) {
for (int i = 0; i < extents.length / 2; i++) {
if (val < extents[i*2]) {
return false;
} else if (val <= extents[i*2+1]) {
return true;
}
}
return false;
}
public boolean containsAll(Collection<?> arg0) {
for (Object o : arg0) {
if (!contains(o)) {
return false;
}
}
return true;
}
public boolean isEmpty() {
return realSet.isEmpty();
}
public Iterator<Integer> iterator() {
return realSet.iterator();
}
public boolean remove(Object arg0) {
throw new UnsupportedOperationException();
}
public boolean removeAll(Collection<?> arg0) {
throw new UnsupportedOperationException();
}
public boolean retainAll(Collection<?> arg0) {
throw new UnsupportedOperationException();
}
public int size() {
return realSet.size();
}
public Object[] toArray() {
return realSet.toArray();
}
public <T> T[] toArray(T[] arg0) {
return realSet.toArray(arg0);
}
@Override
public String toString() {
String buf = "";
for (int i = 0; i < extents.length / 2; i++) {
if (i != 0) {
buf += ", ";
}
buf += "[" + extents[i*2] + "," + extents[i*2+1] + "]";
}
return buf;
}
}
|
