1 /* Copyright (c) 2008 Sascha Kohlmann
2 *
3 * This program is free software: you can redistribute it and/or modify
4 * it under the terms of the GNU Affero General Public License as published by
5 * the Free Software Foundation, either version 3 of the License, or
6 * (at your option) any later version.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU Affero General Public License for more details.
12 *
13 * You should have received a copy of the GNU Affero General Public License
14 * along with this program. If not, see <http://www.gnu.org/licenses/>.
15 */
16 package net.sf.eos.trie;
17
18 import net.sf.eos.trie.PatriciaTrie.KeyAnalyzer;
19
20 public class ByteArrayKeyAnalyzer implements KeyAnalyzer<byte[]> {
21
22 private static final int LENGTH = 8;
23 private static final int[] BITS = createIntBitMask(LENGTH);
24
25 private static final int[] createIntBitMask(int bitCount) {
26 final int[] bits = new int[bitCount];
27 for(int i = 0; i < bitCount; i++) {
28 bits[i] = 1 << (bitCount - i - 1);
29 }
30 return bits;
31 }
32
33 public int bitsPerElement() {
34 return LENGTH;
35 }
36
37 public boolean isBitSet(final byte[] key,
38 final int keyLength,
39 final int bitIndex) {
40 if (key == null || bitIndex >= keyLength) {
41 return false;
42 }
43
44 int index = bitIndex / BITS.length;
45 int bit = bitIndex - index * BITS.length;
46 return (key[index] & BITS[bit]) != 0;
47 }
48
49 public boolean isPrefix(final byte[] prefix,
50 final int offset,
51 final int length,
52 final byte[] key) {
53 if(offset % LENGTH != 0 || length % LENGTH != 0) {
54 throw new IllegalArgumentException("Cannot determine prefix outside"
55 + " of character boundaries");
56 }
57 // String s1 = prefix.subSequence(offset / 16, length / 16).toString();
58 // String s2 = key.toString();
59 // return s2.startsWith(s1);
60
61 final int start = offset / LENGTH;
62 final int end = start + length / LENGTH;
63
64 for (int i = start, j = 0; i < end; i++, j++) {
65 if (prefix[i] != key[j]) {
66 return false;
67 }
68 }
69 return true;
70 }
71
72 public int length(final byte[] key) {
73 return (key != null ? key.length * LENGTH : 0);
74 }
75
76 public int compare(final byte[] o1, final byte[] o2) {
77 if (o1.length != o2.length) {
78 return o1.length - o2.length;
79 }
80 assert o1.length == o2.length;
81 for (int i = 0; i < o1.length; i++) {
82 if (o1[i] != o2[1]) {
83 return o1[i] - o2[i];
84 }
85 }
86 return 0;
87 }
88
89 public int bitIndex(final byte[] key, final int keyOff,
90 final int keyLength, final byte[] found,
91 final int foundOff, final int foundKeyLength) {
92 boolean allNull = true;
93
94 if(keyOff % LENGTH != 0 || foundOff % LENGTH != 0
95 || keyLength % LENGTH != 0 || foundKeyLength % LENGTH != 0)
96 throw new IllegalArgumentException("offsets & lengths must be at "
97 + "character boundaries");
98
99 // try {
100 // System.out.println("\nkey: .......... " + new String(key, "UTF-8"));
101 // System.out.println("found: ........ " + (found != null
102 // ? new String(found, "UTF-8")
103 // : null));
104 // } catch (final UnsupportedEncodingException e) {
105 // e.printStackTrace();
106 // }
107 // System.out.println("key.length: ... " + key.length);
108 // System.out.println("found.length: . " + (found != null ? found.length
109 // : null));
110 // System.out.println("keyOff: ....... " + keyOff);
111 // System.out.println("keyLength: .... " + keyLength);
112 // System.out.println("foundOff: ..... " + foundOff);
113 // System.out.println("foundKeyLength: " + foundKeyLength);
114
115 final int off1 = keyOff / LENGTH;
116 final int off2 = foundOff / LENGTH;
117 final int len1 = keyLength / LENGTH + off1;
118 final int len2 = foundKeyLength / LENGTH + off2;
119 final int length = Math.max(len1, len2);
120
121 // System.out.println("off1: ......... " + off1);
122 // System.out.println("off2: ......... " + off2);
123 // System.out.println("len1: ......... " + len1);
124 // System.out.println("len2: ......... " + len2);
125 // System.out.println("length: ....... " + length);
126
127 // Look at each character, and if they're different
128 // then figure out which bit makes the difference
129 // and return it.
130 int k = 0, f = 0;
131 for(int i = 0; i < length; i++) {
132 final int kOff = i + off1;
133 final int fOff = i + off2;
134 // System.out.println(i + ". kOff: ......... " + kOff);
135 // System.out.println(i + ". fOff: ......... " + fOff);
136
137 if(kOff >= len1) {
138 k = 0;
139 } else {
140 k = key[kOff];
141 if (k < 0) {
142 k = Math.abs(k) * 2;
143 }
144 }
145 // System.out.println(i + ". k: ............ " + k);
146
147 if(found == null || fOff >= len2) {
148 f = 0;
149 } else {
150 f = found[fOff];
151 if (f < 0) {
152 f = Math.abs(f) * 2;
153 }
154 }
155 // System.out.println(i + ". f: ............ " + f);
156
157 if(k != f) {
158 final int x = k ^ f;
159 // System.out.println(i + ". x: ............ " + x);
160 final int retval =
161 i * LENGTH + (Integer.numberOfLeadingZeros(x) - LENGTH);
162 // System.out.println(i + ". retval: ....... " + retval);
163 return retval;
164 }
165
166 if(k != 0) {
167 allNull = false;
168 }
169 }
170
171 if (allNull) {
172 return KeyAnalyzer.NULL_BIT_KEY;
173 }
174
175 return KeyAnalyzer.EQUAL_BIT_KEY;
176 }
177 }