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 structures;
import java.util.ArrayList;
import java.util.Arrays;
public class Range implements Comparable<Range>{
/** A numeric range, assuming 0-based, base-centered numbering. */
public Range(int aa, int bb){
assert(aa<=bb) : aa+">"+bb;
a=aa;
b=bb;
length=b-a+1;
}
public static Range toRange(String s){
String[] s2=s.replace("[","").replace("]","").replace("(","").replace(")","").replace(",","").split("-");
int a, b;
if(s2.length==1){
a=b=Integer.parseInt(s2[0]);
}else{
a=Integer.parseInt(s2[0]);
b=Integer.parseInt(s2[1]);
}
return new Range(a, b);
}
@Override
public int compareTo(Range other) {
if(a<other.a){return -1;}
if(a>other.a){return 1;}
if(b<other.b){return -1;}
if(b>other.b){return 1;}
return 0;
}
public boolean includes(int p){
return p>=a && p<=b;
}
public boolean intersects(int p1, int p2){
return overlap(a, b, p1, p2);
}
public boolean includes(int p1, int p2){
assert(p1<=p2);
return p1>=a && p2<=b;
}
public boolean intersects(Range other){
return intersects(other.a, other.b);
}
public boolean touches(Range other){
if(intersects(other.a, other.b)){return true;}
return b==other.a-1 || a==other.b+1;
}
public boolean includes(Range other){
return includes(other.a, other.b);
}
@Override
public boolean equals(Object other){
return equals((Range)other);
}
public Range merge(Range other){
assert(touches(other));
Range r=new Range(min(a, other.a), max(b, other.b));
assert(r.includes(this));
assert(r.includes(other));
assert(r.length<=length+other.length);
return r;
}
public boolean equals(Range other){
return a==other.a && b==other.b;
}
@Override
public int hashCode(){
return new Long(Long.rotateLeft(a, 16)^b).hashCode();
}
@Override
public String toString(){
return "("+a+(a==b ? "" : (" - "+b))+")";
}
public static boolean overlap(int a1, int b1, int a2, int b2){
assert(a1<=b1 && a2<=b2) : a1+", "+b1+", "+a2+", "+b2;
return a2<=b1 && b2>=a1;
}
public static Range[] toRanges(int[] ...arrays){
int len=0;
int[] combined=null;
if(arrays.length==1){
combined=arrays[0];
len=combined.length;
}else{
for(int i=0; i<arrays.length; i++){
len+=arrays[i].length;
}
combined=new int[len];
for(int i=0, index=0; i<arrays.length; i++){
for(int j=0; j<arrays[i].length; j++){
combined[index]=arrays[i][j];
index++;
}
}
Arrays.sort(combined);
}
ArrayList<Range> list=new ArrayList<Range>(16);
int start=combined[0], last=combined[0];
// System.out.println(Arrays.toString(combined));
for(int i=0; i<len; i++){
int x=combined[i];
if(x>last+1){
list.add(new Range(start, last));
start=last=x;
}else{
last=x;
}
}
list.add(new Range(start, last));
return list.toArray(new Range[list.size()]);
}
private static final int min(int x, int y){return x<y ? x : y;}
private static final int max(int x, int y){return x>y ? x : y;}
public final int a;
public final int b;
public final int length;
public Object obj1=null;
public Object obj2=null;
}
|
