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
|
package structures;
import java.util.Arrays;
import shared.Shared;
import shared.Tools;
/**
* A set of LongLists, designed to increase LongList capacity beyond 2B.
* Auto-condenses; e.g., not intended to represent multiple copies of a value.
*
* @author Brian Bushnell
* @date January 8, 2021
*
*/
public class LongListSet{
public static void main(String[] args){
LongListSet set=new LongListSet();
set.add(1);
set.add(2);
set.add(3);
set.add(4);
set.add(5);
set.add(2);
set.add(2);
set.add(5);
System.err.println(set);
set.sort();
set.condense();
System.err.println(set);
}
public String toString(){
LongListSetIterator iter=iterator();
ByteBuilder bb=new ByteBuilder();
bb.append('[');
while(iter.hasMore()){
long x=iter.next();
bb.append(x);
bb.append(',');
}
if(bb.endsWith(',')){bb.setLength(bb.length-1);}
bb.append(']');
return bb.toString();
}
public LongListSet(){
array=new LongList[mod];
for(int i=0; i<mod; i++){
array[i]=new LongList(32);
}
nextCondense=new int[mod];
Arrays.fill(nextCondense, 64);
}
public void add(long x){
int y=(int)((x&Long.MAX_VALUE)%mod);
LongList list=array[y];
list.add(x);
if(list.size>=nextCondense[y]){
list.sort();
list.condense();
nextCondense[y]=(int)Tools.mid(nextCondense[y], list.size*2L, Shared.MAX_ARRAY_LEN);
}else{
sorted=false;
}
}
public void sort(){
if(sorted){return;}
for(LongList list : array){list.sort();}
sorted=true;
}
public void condense(){
assert(sorted) : "Sort first.";
for(LongList list : array){list.condense();}
}
public void shrinkToUnique(){
for(LongList list : array){list.shrinkToUnique();}
}
public LongListSetIterator iterator(){
return new LongListSetIterator();
}
private boolean sorted=false;
public final LongList[] array;
public final int[] nextCondense;
public static final int mod=3;
public class LongListSetIterator{
//Assumes hasMore() has already been called and returned true
public long next(){
long x=array[i].get(j);
j++;
return x;
}
public boolean hasMore(){
return findNextValid();
}
/**
* Increment and point to next valid element.
* @return true if there is a valid element.
*/
boolean advance(){
j++;
return findNextValid();
}
/**
* Point to next valid element.
* If already valid, do nothing.
* @return true if there is a valid element.
*/
boolean findNextValid(){
if(i<mod && j<array[i].size){return true;}//common case
while(i<mod){
if(j<array[i].size){return true;}
i++;
j=0;
}
return false;
}
private int i=0, j=0;
}
}
|
