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
|
package driver;
import java.util.ArrayList;
import java.util.List;
import dna.Data;
import dna.Gene;
import structures.Range;
public class Search {
/** Find genes in the array that overlap point "p" */
public static List<Gene> findGenes(int p, Gene[] genes){
ArrayList<Gene> list=new ArrayList<Gene>(16);
for(int i=0; i<genes.length; i++){
Gene g=genes[i];
if(g.intersectsCode(p)){
list.add(g);
}
}
return list;
}
/** Find genes in the array that overlap point "p" */
public static List<Gene> findGenesBinary(int p, Range[] ranges, boolean nearby){
ArrayList<Gene> list=null;
int a=findPointBinary(p, ranges);
Range r=ranges[a];
// System.out.println("Searching for "+p+" in "+r+"; previous range was "+ranges[a-1]);
if(!r.includes(p)){return list;}
list=new ArrayList<Gene>(16);
Gene[] genes2=(Gene[])r.obj1;
assert(genes2.length>0);
// System.out.println("Found "+genes2.length+" to consider.");
//TODO: Specify whether tx or code (etc) coverage is needed.
for(int i=0; i<genes2.length; i++){
Gene g=genes2[i];
// System.out.print("Does p overlap gene "+g.codeStart+" - "+g.codeEnd+"?");
if(g.txStart>r.b+Data.NEAR){break;}
if(nearby){
if(g.intersectsNearby(p, p)){list.add(g);}
}else{
if(g.intersectsCode(p)){list.add(g);}
}
}
return list;
}
/** Find genes in the array that overlap point "p" */
public static List<Gene> findGenesLinear(int p, Gene[] genes, Range[] ranges){
ArrayList<Gene> list=null;
int a=findPointLinear(p, ranges);
Range r=ranges[a];
// System.out.println("Searching for "+p+" in "+r+"; previous range was "+ranges[a-1]);
if(!r.includes(p)){return list;}
list=new ArrayList<Gene>(16);
Gene[] genes2=(Gene[])r.obj1;
assert(genes2.length>0);
// System.out.println("Found "+genes2.length+" to consider.");
//TODO: Specify whether tx or code (etc) coverage is needed.
for(int i=0; i<genes2.length; i++){
Gene g=genes2[i];
// System.out.print("Does p overlap gene "+g.codeStart+" - "+g.codeEnd+"?");
if(g.txStart>r.b){break;}
if(g.intersectsCode(p)){
list.add(g);
// System.out.println(" Yes.");
}
}
return list;
}
public static int findPointLinear(int p, Range[] array){
for(int i=0; i<array.length; i++){
Range r=array[i];
if(r.a>p){return i;} //Fail.
if(r.includes(p)){return i;} //Success.
}
return array.length-1;
}
public static int findPointBinary(int p, Range[] array){
assert(array!=null);
if(array.length==0){return 0;}
int result=findPointBinary(p, 0, max(0, array.length-1), array);
//TODO: Assertions
return result;
}
public static boolean containsPointBinary(int p, Range[] array, int thresh){
assert(array!=null);
if(array.length==0){return false;}
int rnum=findPointBinary(p, 0, max(0, array.length-1), array);
int p1=p-thresh, p2=p+thresh;
Range r=array[rnum];
if(p2>=r.a && p1<=r.b){return true;}
if(rnum==0 && p<r.a){return false;}
assert(p>r.b) : "\n\n"+p+"\t"+rnum+"/"+array.length+"\t"+r+"\n\n"; //Otherwise, it violated the search contract.
if(array.length<=rnum+1){return false;}
Range r2=array[rnum+1];
assert(r2.a>p) : "\n\n"+p+"\t"+rnum+"/"+array.length+"\t"+r+"\n\n"; //Otherwise, it violated the search contract.
return (p2>=r.a && p1<=r.b);
}
public static int findPointBinary(int p, int a, int b, Range[] array){
if(a>=b){
//This line should ensure that p>array[a] when p is not within any range.
//Except, of course, when p<(all ranges).
//In other words, the return is strictly the LEFT (LOWER) index when p is between two ranges.
if(a>0 && p<array[a].a){a--;}
assert(a>=0);
assert(a<array.length);
assert(array[a].includes(p) || (a==0 && p<array[a].a) ||
(p>array[a].b && (a==array.length-1 || p<array[a+1].a))) :
"a="+a+", b="+b+", p="+p+", array[a]="+array[a];
return a;
}
int mid=(a+b)/2;
Range r=array[mid];
if(r.a>p){
return findPointBinary(p, a, mid-1, array);
}else if(r.b<p){
return findPointBinary(p, mid+1, b, array);
}else{
return mid;
}
}
public static boolean overlaps(int a, Gene g){
return a>=g.txStart && a<=g.txStop;
}
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;}
private static final long min(long x, long y){return x<y ? x : y;}
private static final long max(long x, long y){return x>y ? x : y;}
}
|
