1
2
3
4 package net.sf.bddbddb;
5
6 import java.util.Comparator;
7 import java.util.Iterator;
8 import java.util.LinkedList;
9 import java.util.List;
10 import java.util.NoSuchElementException;
11 import java.util.StringTokenizer;
12 import java.io.BufferedReader;
13 import java.io.FileReader;
14 import java.io.IOException;
15 import java.math.BigInteger;
16 import jwutil.collections.SortedArraySet;
17 import jwutil.collections.SortedIntArraySet;
18 import jwutil.util.Assert;
19
20 /***
21 * LSRelation
22 *
23 * @author jwhaley
24 * @version $Id: LSRelation.java 649 2006-09-16 05:51:04Z joewhaley $
25 */
26 public class LSRelation extends Relation {
27
28 /***
29 * Reference to solver.
30 */
31 LSSolver solver;
32
33 /***
34 * Holds the actual data. Only one of these is non-null.
35 */
36 SortedIntArraySet intSet;
37 SortedArraySet objSet;
38
39 /***
40 * Number of bits used for each attribute.
41 */
42 int[] bits;
43
44 /***
45 * Add tuple to this relation.
46 *
47 * @param t tuple to add
48 * @return whether relation has changed
49 */
50 public boolean add(BigInteger[] t) {
51 if (objSet != null) return objSet.add(t);
52 else return intSet.add(compress(t));
53 }
54
55 /***
56 * Extract packed value x into given array.
57 *
58 * @param arr array to extract into
59 * @param x packed value
60 */
61 protected void extract(BigInteger[] arr, int x) {
62 for (int k = 0; k < bits.length; ++k) {
63 arr[k] = BigInteger.valueOf(x & ((1 << bits[k]) - 1));
64 x >>>= bits[k];
65 }
66 }
67
68 /***
69 * Compress the given array into a packed value.
70 *
71 * @param arr array to compress
72 * @return packed value
73 */
74 protected int compress(BigInteger[] arr) {
75 int result = 0;
76 for (int k = 0; k < bits.length; ++k) {
77 if (arr[k].bitLength() > bits[k])
78 throw new InternalError(arr[k]+" too big for "+bits[k]+" bits");
79 result <<= bits[k];
80 result |= arr[k].intValue();
81 }
82 return result;
83 }
84
85 /***
86 * Construct a new LSRelation.
87 *
88 * @param solver solver object
89 * @param name relation name
90 * @param attributes relation attributes
91 */
92 LSRelation(LSSolver solver, String name, List attributes) {
93 super(solver, name, attributes);
94 this.solver = solver;
95 }
96
97
98
99
100 public void initialize() {
101 int totalBits = 0;
102 bits = new int[attributes.size()];
103 int k = 0;
104 for (Iterator i = attributes.iterator(); i.hasNext(); ++k) {
105 Attribute a = (Attribute) i.next();
106 bits[k] = a.attributeDomain.size.bitLength();
107 totalBits += bits[k];
108 }
109 if (totalBits < 32) intSet = new SortedIntArraySet();
110 else objSet = (SortedArraySet) SortedArraySet.FACTORY.makeSet(TUPLE_COMPARATOR);
111 }
112
113 public static final TupleComparator TUPLE_COMPARATOR = new TupleComparator();
114
115 public static class TupleComparator implements Comparator {
116
117 private TupleComparator() { }
118
119 public int compare(Object arg0, Object arg1) {
120 BigInteger[] a = (BigInteger[]) arg0;
121 BigInteger[] b = (BigInteger[]) arg1;
122 for (int i = 0; i < a.length; ++i) {
123 int v = a[i].compareTo(b[i]);
124 if (v != 0) return v;
125 }
126 return 0;
127 }
128
129 }
130
131 BDDSolver temp;
132
133
134
135
136 public void load() throws IOException {
137 if (temp == null) {
138 temp = new BDDSolver();
139 try {
140 temp.load(solver.inputFilename);
141 } catch (Exception x) {
142 x.printStackTrace();
143 }
144 }
145 Relation r = temp.getRelation(name);
146 r.load();
147 TupleIterator i = r.iterator();
148 while (i.hasNext()) {
149 this.add(i.nextTuple());
150 }
151 }
152
153
154
155
156 public void loadTuples() throws IOException {
157 loadTuples(solver.basedir + name + ".tuples");
158 if (solver.NOISY) solver.out.println("Loaded tuples from file: " + name + ".tuples");
159 }
160
161 List checkInfoLine(String filename, String s, boolean order, boolean ex) throws IOException {
162
163 return null;
164 }
165
166
167
168
169 public void loadTuples(String filename) throws IOException {
170 Assert._assert(isInitialized);
171 BufferedReader in = null;
172 try {
173 in = new BufferedReader(new FileReader(filename));
174
175 String s = in.readLine();
176 if (s == null) return;
177 if (!s.startsWith("# ")) {
178 solver.err.println("Tuple file \""+filename+"\" is missing header line, using default.");
179 } else {
180 checkInfoLine(filename, s, true, true);
181 }
182 while (s != null) {
183 if (s.length() == 0) continue;
184 if (s.startsWith("#")) continue;
185 parseTuple(s);
186 s = in.readLine();
187 }
188 } finally {
189 if (in != null) in.close();
190 }
191 updateNegated();
192 }
193
194 /***
195 * Updated the negated form of this relation.
196 */
197 void updateNegated() {
198 if (negated != null) {
199
200 }
201 }
202
203 void parseTuple(BigInteger[] t, int i, String s) {
204 if (i == t.length) {
205 add(t);
206 return;
207 }
208 int z = s.indexOf(' ');
209 String v = (z < 0) ? s : s.substring(0, z);
210 if (z <= 0) s = "";
211 else s = s.substring(z+1);
212 BigInteger l, m;
213 if (v.equals("*")) {
214 Attribute a = (Attribute) attributes.get(i);
215 l = BigInteger.ZERO;
216 m = a.attributeDomain.size.subtract(BigInteger.ONE);
217 } else {
218 int x = v.indexOf('-');
219 if (x < 0) {
220 t[i] = new BigInteger(v);
221 parseTuple(t, i+1, s);
222 return;
223 } else {
224 l = new BigInteger(v.substring(0, x));
225 m = new BigInteger(v.substring(x + 1));
226 }
227 }
228 while (l.compareTo(m) <= 0) {
229 t[i] = l;
230 parseTuple(t, i+1, s);
231 l = l.add(BigInteger.ONE);
232 }
233 }
234
235 /***
236 * Parse the given tuple string and add it to the relation.
237 *
238 * @param s tuple string
239 */
240 void parseTuple(String s) {
241 BigInteger[] t = new BigInteger[attributes.size()];
242 if (s.indexOf('-') >= 0 || s.indexOf('*') >= 0) {
243 parseTuple(t, 0, s);
244 return;
245 }
246 StringTokenizer st = new StringTokenizer(s);
247 for (int i = 0; i < t.length; ++i) {
248 String v = st.nextToken();
249 t[i] = new BigInteger(v);
250 }
251 add(t);
252 }
253
254
255
256
257 public void save() throws IOException {
258
259
260 }
261
262
263
264
265 public void saveTuples() throws IOException {
266
267
268 }
269
270
271
272
273 public void saveTuples(String filename) throws IOException {
274
275
276 }
277
278
279
280
281 public Relation copy() {
282 List a = new LinkedList(attributes);
283 Relation that = solver.createRelation(name + '\'', a);
284 return that;
285 }
286
287
288
289
290 public void free() {
291 intSet = null; objSet = null;
292 }
293
294
295
296
297 public double dsize() {
298 if (intSet != null) return intSet.size();
299 else return objSet.size();
300 }
301
302 BigInteger[] getTuple(BigInteger[] arr, int k) {
303 if (intSet != null) {
304 int x = intSet.get(k);
305 extract(arr, x);
306 return arr;
307 } else {
308 BigInteger[] x = (BigInteger[]) objSet.get(k++);
309 return x;
310 }
311 }
312
313
314
315
316 public TupleIterator iterator() {
317 return new TupleIterator() {
318 int k = 0;
319 BigInteger[] arr;
320 { if (intSet != null) arr = new BigInteger[attributes.size()]; }
321 public BigInteger[] nextTuple() {
322 if ((long)k == size()) throw new NoSuchElementException();
323 return getTuple(arr, k++);
324 }
325 public boolean hasNext() {
326 return (long)k < size();
327 }
328 };
329 }
330
331
332
333
334 public TupleIterator iterator(final int k) {
335 return new TupleIterator() {
336 int n = 0;
337 BigInteger[] arr;
338 { if (intSet != null) arr = new BigInteger[attributes.size()]; }
339 void gotoNext(BigInteger currVal) {
340 while (n < arr.length) {
341 arr = getTuple(arr, n);
342 if (!arr[k].equals(currVal)) return;
343 ++n;
344 }
345 }
346 public BigInteger[] nextTuple() {
347 if ((long)n == size()) throw new NoSuchElementException();
348 arr = getTuple(arr, n);
349 gotoNext(arr[k]);
350 return new BigInteger[] { arr[k] };
351 }
352 public boolean hasNext() {
353 return (long)n < size();
354 }
355 };
356 }
357
358
359
360
361 public TupleIterator iterator(final int k, final BigInteger j) {
362 return new TupleIterator() {
363 int n = 0;
364 BigInteger[] arr;
365 { if (intSet != null) arr = new BigInteger[attributes.size()]; }
366 void gotoNext() {
367 while (n < arr.length) {
368 arr = getTuple(arr, n);
369 if (arr[k].equals(j)) return;
370 ++n;
371 }
372 throw new NoSuchElementException();
373 }
374 public BigInteger[] nextTuple() {
375 gotoNext();
376 return arr;
377 }
378 public boolean hasNext() {
379 return (long)n < size();
380 }
381 };
382 }
383
384
385
386
387 public TupleIterator iterator(final BigInteger[] j) {
388 return new TupleIterator() {
389 int n = 0;
390 BigInteger[] arr;
391 { if (intSet != null) arr = new BigInteger[attributes.size()]; }
392 void gotoNext() {
393 outer:
394 while (n < arr.length) {
395 arr = getTuple(arr, n);
396 for (int k = 0; k < j.length; ++k) {
397 if (j[k].signum() >= 0 && !arr[k].equals(j)) {
398 ++n;
399 continue outer;
400 }
401 }
402 return;
403 }
404 throw new NoSuchElementException();
405 }
406 public BigInteger[] nextTuple() {
407 gotoNext();
408 return arr;
409 }
410 public boolean hasNext() {
411 return (long)n < size();
412 }
413 };
414 }
415
416
417
418
419 public boolean contains(int k, BigInteger j) {
420 for (TupleIterator i = iterator(); i.hasNext(); ) {
421 BigInteger[] t = i.nextTuple();
422 if (t[k].equals(j)) return true;
423 }
424 return false;
425 }
426
427 public String verboseToString() {
428 StringBuffer sb = new StringBuffer();
429 sb.append(super.toString());
430 sb.append("[");
431 boolean any = false;
432 for(Iterator it = getAttributes().iterator(); it.hasNext(); ){
433 any = true;
434 Attribute a = (Attribute) it.next();
435 sb.append(a + ",");
436 }
437 if(any)
438 sb.deleteCharAt(sb.length() - 1);
439 sb.append("]");
440
441 return sb.toString();
442 }
443
444 }