1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.trie.analyzer;
18
19 import org.apache.commons.collections4.trie.KeyAnalyzer;
20
21
22
23
24
25
26 public class StringKeyAnalyzer extends KeyAnalyzer<String> {
27
28 private static final long serialVersionUID = -7032449491269434877L;
29
30
31 public static final StringKeyAnalyzer INSTANCE = new StringKeyAnalyzer();
32
33
34 public static final int LENGTH = Character.SIZE;
35
36
37 private static final int MSB = 0x8000;
38
39
40 private static int mask(final int bit) {
41 return MSB >>> bit;
42 }
43
44 @Override
45 public int bitIndex(final String key, final int offsetInBits, final int lengthInBits,
46 final String other, final int otherOffsetInBits, final int otherLengthInBits) {
47
48 boolean allNull = true;
49
50 if (offsetInBits % LENGTH != 0 || otherOffsetInBits % LENGTH != 0
51 || lengthInBits % LENGTH != 0 || otherLengthInBits % LENGTH != 0) {
52 throw new IllegalArgumentException("The offsets and lengths must be at Character boundaries");
53 }
54
55 final int beginIndex1 = offsetInBits / LENGTH;
56 final int beginIndex2 = otherOffsetInBits / LENGTH;
57
58 final int endIndex1 = beginIndex1 + lengthInBits / LENGTH;
59 final int endIndex2 = beginIndex2 + otherLengthInBits / LENGTH;
60
61 final int length = Math.max(endIndex1, endIndex2);
62
63
64
65
66 char k = 0, f = 0;
67 for (int i = 0; i < length; i++) {
68 final int index1 = beginIndex1 + i;
69 final int index2 = beginIndex2 + i;
70
71 if (index1 >= endIndex1) {
72 k = 0;
73 } else {
74 k = key.charAt(index1);
75 }
76
77 if (other == null || index2 >= endIndex2) {
78 f = 0;
79 } else {
80 f = other.charAt(index2);
81 }
82
83 if (k != f) {
84 final int x = k ^ f;
85 return i * LENGTH + Integer.numberOfLeadingZeros(x) - LENGTH;
86 }
87
88 if (k != 0) {
89 allNull = false;
90 }
91 }
92
93
94 if (allNull) {
95 return NULL_BIT_KEY;
96 }
97
98
99 return EQUAL_BIT_KEY;
100 }
101
102 @Override
103 public int bitsPerElement() {
104 return LENGTH;
105 }
106
107 @Override
108 public boolean isBitSet(final String key, final int bitIndex, final int lengthInBits) {
109 if (key == null || bitIndex >= lengthInBits) {
110 return false;
111 }
112
113 final int index = bitIndex / LENGTH;
114 final int bit = bitIndex % LENGTH;
115
116 return (key.charAt(index) & mask(bit)) != 0;
117 }
118
119 @Override
120 public boolean isPrefix(final String prefix, final int offsetInBits,
121 final int lengthInBits, final String key) {
122 if (offsetInBits % LENGTH != 0 || lengthInBits % LENGTH != 0) {
123 throw new IllegalArgumentException(
124 "Cannot determine prefix outside of Character boundaries");
125 }
126
127 final String s1 = prefix.substring(offsetInBits / LENGTH, lengthInBits / LENGTH);
128 return key.startsWith(s1);
129 }
130
131 @Override
132 public int lengthInBits(final String key) {
133 return key != null ? key.length() * LENGTH : 0;
134 }
135 }