001: /*
002: This source file is part of Smyle, a database library.
003: For up-to-date information, see http://www.drjava.de/smyle
004: Copyright (C) 2001 Stefan Reich (doc@drjava.de)
005:
006: This library is free software; you can redistribute it and/or
007: modify it under the terms of the GNU Lesser General Public
008: License as published by the Free Software Foundation; either
009: version 2.1 of the License, or (at your option) any later version.
010:
011: This library is distributed in the hope that it will be useful,
012: but WITHOUT ANY WARRANTY; without even the implied warranty of
013: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: Lesser General Public License for more details.
015:
016: You should have received a copy of the GNU Lesser General Public
017: License along with this library; if not, write to the Free Software
018: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019:
020: For full license text, see doc/license/lgpl.txt in this distribution
021: */
022:
023: package drjava.smyle.core;
024:
025: import org.artsProject.mcop.*;
026: import drjava.smyle.meta.*;
027:
028: public class UniversalKey implements Comparable<UniversalKey> {
029: int[] data;
030:
031: public static final UniversalKey MIN = new UniversalKey(0x80000000);
032:
033: public static class MarDemar implements
034: drjava.smyle.core.MarDemar<UniversalKey> {
035: public void marshal(Buffer b, UniversalKey key) {
036: b.writeLong(key.data.length);
037: for (int i = 0; i < key.data.length; i++)
038: b.writeLong(key.data[i]);
039: }
040:
041: public UniversalKey read(Buffer b) {
042: return new UniversalKey(b);
043: }
044: }
045:
046: public UniversalKey(String s) {
047: init(s);
048: }
049:
050: private void init(String s) {
051: Buffer b = new Buffer(Buffer.stringToBytes(s));
052: while ((b.remaining() % 4) != 0)
053: b.writeByte((byte) 0);
054: init(b, b.remaining() >> 2);
055: }
056:
057: void init(Buffer b) {
058: init(b, b.readLong());
059: }
060:
061: void init(Buffer b, int n) {
062: while (n != 0 && b.peekLong((n - 1) * 4) == 0)
063: --n;
064: data = new int[n];
065: for (int i = 0; i < n; i++)
066: data[i] = b.readLong();
067: }
068:
069: public UniversalKey(int i) {
070: init(i);
071: }
072:
073: private void init(int i) {
074: Buffer b = new Buffer();
075: b.writeLong(i ^ 0x80000000);
076: init(b, 1);
077: }
078:
079: public UniversalKey(long l) {
080: init(l);
081: }
082:
083: private void init(long l) {
084: Buffer b = new Buffer();
085: b.writeLongLong(l ^ 0x8000000000000000L);
086: init(b, 2);
087: }
088:
089: public UniversalKey(Object o) {
090: if (o instanceof String)
091: init((String) o);
092: else if (o instanceof Integer)
093: init(((Integer) o).intValue());
094: else if (o instanceof Long)
095: init(((Long) o).longValue());
096: else if (o instanceof ComparableBoolean)
097: init(o == ComparableBoolean.TRUE ? 1 : 0);
098: else if (o instanceof Buffer)
099: init((Buffer) o);
100: else if (o == null)
101: init(0x7FFFFFFF);
102: else
103: throw new RuntimeException("Illegal argument: " + o);
104: }
105:
106: private UniversalKey(Buffer b, int n) {
107: init(b, n);
108: }
109:
110: private UniversalKey(int[] data, int n) {
111: this .data = new int[n];
112: System.arraycopy(data, 0, this .data, 0, n);
113: }
114:
115: private UniversalKey(int[] data) {
116: this .data = data;
117: }
118:
119: /** create a multidimensional key (interleaved) */
120: public static UniversalKey mergeDimensions(Object[] os) {
121: int n = os.length;
122: if (n == 1)
123: if (os[0] instanceof UniversalKey)
124: return (UniversalKey) os[0];
125: else
126: return new UniversalKey(os[0]);
127: UniversalKey[] keys = new UniversalKey[n];
128: int len = 0;
129: for (int i = 0; i < n; i++) {
130: keys[i] = os[i] instanceof UniversalKey ? (UniversalKey) os[i]
131: : new UniversalKey(os[i]);
132: len = Math.max(len, keys[i].data.length);
133: }
134: len *= n;
135:
136: Buffer b = new Buffer();
137: for (int j = 0, bit = 0; j < len; j++) {
138: int x = 0;
139: for (int k = 0; k < 32; k++, bit++) {
140: int c = bit % n, d = (bit / n) >> 5;
141: if (d < keys[c].data.length
142: && (keys[c].data[d] & (1 << (31 - (bit / n) & 31))) != 0)
143: x |= 1 << (31 - k);
144: }
145: b.writeLong(x);
146: }
147: return new UniversalKey(b, b.remaining() / 4);
148: }
149:
150: /** create a multidimensional key (non-interleaved) */
151: public static UniversalKey concatDimensions(Object[] os) {
152: int n = os.length;
153: UniversalKey[] keys = new UniversalKey[n];
154: int len = 0;
155: for (int i = 0; i < n; i++) {
156: keys[i] = os[i] instanceof UniversalKey ? (UniversalKey) os[i]
157: : new UniversalKey(os[i]);
158: //System.out.println("Key length="+keys[i].data.length);
159: len += keys[i].data.length;
160: }
161: int[] data = new int[len];
162: int l = 0;
163: for (int i = 0; i < n; i++) {
164: System.arraycopy(keys[i].data, 0, data, l,
165: keys[i].data.length);
166: l += keys[i].data.length;
167: }
168: return new UniversalKey(data);
169: }
170:
171: public int compareTo(UniversalKey k) {
172: return compareTo(k, 0);
173: }
174:
175: public int compareTo(UniversalKey k, int fromBit) {
176: int[] kdata = k.data;
177: int l = Math.min(data.length, kdata.length);
178: int byt = fromBit >> 5;
179: if (byt < l) {
180: int mask = (fromBit & 31) == 0 ? -1
181: : (1 << (32 - (fromBit & 31))) - 1;
182: int a = (data[byt] & mask) ^ 0x80000000, b = (kdata[byt] & mask) ^ 0x80000000;
183: if (a < b)
184: return -1;
185: else if (a > b)
186: return 1;
187:
188: for (int i = byt + 1; i < l; i++) {
189: a = data[i] ^ 0x80000000;
190: b = kdata[i] ^ 0x80000000;
191: if (a < b)
192: return -1;
193: else if (a > b)
194: return 1;
195: }
196: }
197: //System.out.println(this+"<>"+k+"="+(data.length-l));
198: for (int i = l; i < data.length; i++)
199: if (data[i] != 0)
200: return 1;
201: for (int i = l; i < kdata.length; i++)
202: if (kdata[i] != 0)
203: return -1;
204: return 0;
205: }
206:
207: public boolean equals(Object o) {
208: if (!(o instanceof UniversalKey))
209: return false;
210: return compareTo((UniversalKey) o) == 0;
211: }
212:
213: public String toString() {
214: Buffer b = new Buffer();
215: for (int i = 0; i < data.length; i++)
216: b.writeLong(data[i]);
217: return b.toString();
218: }
219:
220: private static int extract2(int u) {
221: return (u & (1 << 30)) >> 15 | (u & (1 << 28)) >> 14
222: | (u & (1 << 26)) >> 13 | (u & (1 << 24)) >> 12
223: | (u & (1 << 22)) >> 11 | (u & (1 << 20)) >> 10
224: | (u & (1 << 18)) >> 9 | (u & (1 << 16)) >> 8
225: | (u & (1 << 14)) >> 7 | (u & (1 << 12)) >> 6
226: | (u & (1 << 10)) >> 5 | (u & (1 << 8)) >> 4
227: | (u & (1 << 6)) >> 3 | (u & (1 << 4)) >> 2
228: | (u & (1 << 2)) >> 1 | (u & (1 << 0));
229: }
230:
231: public UniversalKey extractDimension(int i, int n) {
232: if (n == 1)
233: return this ;
234: Buffer b = new Buffer();
235: if (n == 2) {
236: for (int j = 0; j < data.length; j += 2) {
237: int x = (extract2(data[j] >> (1 - i)) << 16)
238: | (j + 1 < data.length ? extract2(data[j + 1] >> (1 - i))
239: : 0);
240: b.writeLong(x);
241: }
242: } else {
243: int len = (data.length + n - 1) / n;
244: for (int j = 0, bit = 0; j < len; j++) {
245: int x = 0;
246: for (int k = 0; k < 32; k++, bit++) {
247: int d = (bit * n + i) >> 5;
248: if (d < data.length
249: && (data[d] & (1 << (31 - (bit * n + i) & 31))) != 0)
250: x |= 1 << (31 - k);
251: }
252: b.writeLong(x);
253: }
254: }
255: return new UniversalKey(b, b.remaining() >> 2);
256: }
257:
258: public UniversalKey cut(int maxBytes) {
259: int max = (maxBytes + 3) >> 2;
260: //System.out.println("maxBytes="+maxBytes+", len="+data.length);
261: if (data.length <= max)
262: return this ;
263: return new UniversalKey(data, max);
264: }
265:
266: /** create a key that is greater than or equal to all other keys of that length */
267: public static UniversalKey max(int bytes) {
268: int n = (bytes + 3) >> 2;
269: int data[] = new int[n];
270: for (int i = 0; i < n; i++)
271: data[i] = 0xFFFFFFFF;
272: return new UniversalKey(data);
273: }
274:
275: /** min-max is a real range
276: kMin/kMax is a kind of bitmask (00=must be 0, 11=must be 1, 01=don't care)
277: */
278: public static boolean inRange(UniversalKey kMin, UniversalKey kMax,
279: UniversalKey min, UniversalKey max) {
280: if (min == null)
281: return kMin.compareTo(max) <= 0;
282: if (max == null)
283: return kMax.compareTo(min) >= 0;
284: int len = Math.max(
285: Math.max(kMin.data.length, kMax.data.length), Math.max(
286: min.data.length, max.data.length));
287: int i;
288:
289: // narrowing phase
290: for (i = 0; i < len * 32; i++) {
291: boolean c = min.getBit(i), d = max.getBit(i);
292: if (c != d)
293: break;
294: if (kMin.getBit(i) == !c && kMax.getBit(i) == !c)
295: return false;
296: }
297:
298: // comparison phase
299: if (kMin.compareTo(max, i) > 0)
300: return false;
301: if (kMax.compareTo(min, i) < 0)
302: return false;
303: return true;
304: }
305:
306: public boolean getBit(int i) {
307: if (i >= data.length * 32)
308: return false;
309: return (data[i >> 5] & (1 << (31 - (i)))) != 0;
310: }
311: }
|