1/*-
2 * See the file LICENSE for redistribution information.
3 *
4 * Copyright (c) 2002,2008 Oracle.  All rights reserved.
5 *
6 * $Id: KeyRange.java,v 1.6 2008/02/19 19:41:51 mark Exp $
7 */
8
9package com.sleepycat.util.keyrange;
10
11import java.util.Comparator;
12
13import com.sleepycat.db.DatabaseEntry;
14
15/**
16 * Encapsulates a key range for use with a RangeCursor.
17 */
18public class KeyRange {
19
20    /*
21     * We can return the same byte[] for 0 length arrays.
22     */
23    public static final byte[] ZERO_LENGTH_BYTE_ARRAY = new byte[0];
24
25    Comparator comparator;
26    DatabaseEntry beginKey;
27    DatabaseEntry endKey;
28    boolean singleKey;
29    boolean beginInclusive;
30    boolean endInclusive;
31
32    /**
33     * Creates an unconstrained key range.
34     */
35    public KeyRange(Comparator comparator) {
36        this.comparator = comparator;
37    }
38
39    /**
40     * Creates a range for a single key.
41     */
42    public KeyRange subRange(DatabaseEntry key)
43        throws KeyRangeException {
44
45        if (!check(key)) {
46            throw new KeyRangeException("singleKey out of range");
47        }
48        KeyRange range = new KeyRange(comparator);
49        range.beginKey = key;
50        range.endKey = key;
51        range.beginInclusive = true;
52        range.endInclusive = true;
53        range.singleKey = true;
54        return range;
55    }
56
57    /**
58     * Creates a range that is the intersection of this range and the given
59     * range parameters.
60     */
61    public KeyRange subRange(DatabaseEntry beginKey, boolean beginInclusive,
62                             DatabaseEntry endKey, boolean endInclusive)
63        throws KeyRangeException {
64
65        if (beginKey == null) {
66            beginKey = this.beginKey;
67            beginInclusive = this.beginInclusive;
68        } else if (!check(beginKey, beginInclusive)) {
69            throw new KeyRangeException("beginKey out of range");
70        }
71        if (endKey == null) {
72            endKey = this.endKey;
73            endInclusive = this.endInclusive;
74        } else if (!check(endKey, endInclusive)) {
75            throw new KeyRangeException("endKey out of range");
76        }
77        KeyRange range = new KeyRange(comparator);
78        range.beginKey = beginKey;
79        range.endKey = endKey;
80        range.beginInclusive = beginInclusive;
81        range.endInclusive = endInclusive;
82        return range;
83    }
84
85    /**
86     * Returns whether this is a single-key range.
87     */
88    public final boolean isSingleKey() {
89        return singleKey;
90    }
91
92    /**
93     * Returns the key of a single-key range, or null if not a single-key
94     * range.
95     */
96    public final DatabaseEntry getSingleKey() {
97
98        return singleKey ? beginKey : null;
99    }
100
101    /**
102     * Returns whether this range has a begin or end bound.
103     */
104    public final boolean hasBound() {
105
106        return endKey != null || beginKey != null;
107    }
108
109    /**
110     * Formats this range as a string for debugging.
111     */
112    public String toString() {
113
114        return "[KeyRange " + beginKey + ' ' + beginInclusive +
115                              endKey + ' ' + endInclusive +
116                              (singleKey ? " single" : "");
117    }
118
119    /**
120     * Returns whether a given key is within range.
121     */
122    public boolean check(DatabaseEntry key) {
123
124        if (singleKey) {
125            return (compare(key, beginKey) == 0);
126        } else {
127            return checkBegin(key, true) && checkEnd(key, true);
128        }
129    }
130
131    /**
132     * Returns whether a given key is within range.
133     */
134    public boolean check(DatabaseEntry key, boolean inclusive) {
135
136        if (singleKey) {
137            return (compare(key, beginKey) == 0);
138        } else {
139            return checkBegin(key, inclusive) && checkEnd(key, inclusive);
140        }
141    }
142
143    /**
144     * Returns whether the given key is within range with respect to the
145     * beginning of the range.
146     *
147     * <p>The inclusive parameter should be true for checking a key read from
148     * the database; this will require that the key is within range.  When
149     * inclusive=false the key is allowed to be equal to the beginKey for the
150     * range; this is used for checking a new exclusive bound of a
151     * sub-range.</p>
152     *
153     * <p>Note that when inclusive=false and beginInclusive=true our check is
154     * not exactly correct because in theory we should allow the key to be "one
155     * less" than the existing bound; however, checking for "one less"  is
156     * impossible so we do the best we can and test the bounds
157     * conservatively.</p>
158     */
159    public boolean checkBegin(DatabaseEntry key, boolean inclusive) {
160
161        if (beginKey == null) {
162            return true;
163        } else if (!beginInclusive && inclusive) {
164            return compare(key, beginKey) > 0;
165        } else {
166            return compare(key, beginKey) >= 0;
167        }
168    }
169
170    /**
171     * Returns whether the given key is within range with respect to the
172     * end of the range.  See checkBegin for details.
173     */
174    public boolean checkEnd(DatabaseEntry key, boolean inclusive) {
175
176        if (endKey == null) {
177            return true;
178        } else if (!endInclusive && inclusive) {
179            return compare(key, endKey) < 0;
180        } else {
181            return compare(key, endKey) <= 0;
182        }
183    }
184
185    /**
186     * Compares two keys, using the user comparator if there is one.
187     */
188    public int compare(DatabaseEntry key1, DatabaseEntry key2) {
189
190        if (comparator != null) {
191            return comparator.compare(getByteArray(key1), getByteArray(key2));
192        } else {
193            return compareBytes
194                    (key1.getData(), key1.getOffset(), key1.getSize(),
195                     key2.getData(), key2.getOffset(), key2.getSize());
196
197        }
198    }
199
200    /**
201     * Copies a byte array.
202     */
203    public static byte[] copyBytes(byte[] bytes) {
204
205        byte[] a = new byte[bytes.length];
206        System.arraycopy(bytes, 0, a, 0, a.length);
207        return a;
208    }
209
210    /**
211     * Compares two keys as unsigned byte arrays, which is the default
212     * comparison used by JE/DB.
213     */
214    public static int compareBytes(byte[] data1, int offset1, int size1,
215                                   byte[] data2, int offset2, int size2) {
216
217        for (int i = 0; i < size1 && i < size2; i++) {
218
219            int b1 = 0xFF & data1[offset1 + i];
220            int b2 = 0xFF & data2[offset2 + i];
221            if (b1 < b2)
222                return -1;
223            else if (b1 > b2)
224                return 1;
225        }
226
227        if (size1 < size2)
228            return -1;
229        else if (size1 > size2)
230            return 1;
231        else
232            return 0;
233    }
234
235    /**
236     * Compares two byte arrays for equality.
237     */
238    public static boolean equalBytes(byte[] data1, int offset1, int size1,
239                                     byte[] data2, int offset2, int size2) {
240        if (size1 != size2) {
241            return false;
242        }
243        for (int i = 0; i < size1; i += 1) {
244            if (data1[i + offset1] != data2[i + offset2]) {
245                return false;
246            }
247        }
248        return true;
249    }
250
251    /**
252     * Returns a copy of an entry.
253     */
254    public static DatabaseEntry copy(DatabaseEntry from) {
255        return new DatabaseEntry(getByteArray(from));
256    }
257
258    /**
259     * Copies one entry to another.
260     */
261    public static void copy(DatabaseEntry from, DatabaseEntry to) {
262        to.setData(getByteArray(from));
263        to.setOffset(0);
264    }
265
266    /**
267     * Returns an entry's byte array, copying it if the entry offset is
268     * non-zero.
269     */
270    public static byte[] getByteArray(DatabaseEntry entry) {
271	return getByteArrayInternal(entry, Integer.MAX_VALUE);
272    }
273
274    public static byte[] getByteArray(DatabaseEntry entry, int maxBytes) {
275	return getByteArrayInternal(entry, maxBytes);
276    }
277
278    private static byte[] getByteArrayInternal(DatabaseEntry entry,
279					       int maxBytes) {
280
281        byte[] bytes = entry.getData();
282        if (bytes == null) return null;
283        int size = Math.min(entry.getSize(), maxBytes);
284	byte[] data;
285	if (size == 0) {
286	    data = ZERO_LENGTH_BYTE_ARRAY;
287	} else {
288	    data = new byte[size];
289	    System.arraycopy(bytes, entry.getOffset(), data, 0, size);
290	}
291        return data;
292    }
293
294    /**
295     * Returns the two DatabaseEntry objects have the same data value.
296     */
297    public static boolean equalBytes(DatabaseEntry e1, DatabaseEntry e2) {
298
299        if (e1 == null && e2 == null) {
300            return true;
301        }
302        if (e1 == null || e2 == null) {
303            return false;
304        }
305
306        byte[] d1 = e1.getData();
307        byte[] d2 = e2.getData();
308        int s1 = e1.getSize();
309        int s2 = e2.getSize();
310        int o1 = e1.getOffset();
311        int o2 = e2.getOffset();
312
313        if (d1 == null && d2 == null) {
314            return true;
315        }
316        if (d1 == null || d2 == null) {
317            return false;
318        }
319        if (s1 != s2) {
320            return false;
321        }
322        for (int i = 0; i < s1; i += 1) {
323            if (d1[o1 + i] != d2[o2 + i]) {
324                return false;
325            }
326        }
327        return true;
328    }
329
330    /**
331     * Converts the byte array of this thang to space-separated integers,
332     * and suffixed by the record number if applicable.
333     *
334     * @param dbt the thang to convert.
335     *
336     * @return the resulting string.
337     */
338    public static String toString(DatabaseEntry dbt) {
339
340        int len = dbt.getOffset() + dbt.getSize();
341        StringBuffer buf = new StringBuffer(len * 2);
342        byte[] data = dbt.getData();
343        for (int i = dbt.getOffset(); i < len; i++) {
344            String num = Integer.toHexString(data[i]);
345            if (num.length() < 2) buf.append('0');
346            buf.append(num);
347        }
348        return buf.toString();
349    }
350}
351