1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections4.trie;
18
19 import java.io.Serializable;
20 import java.util.Comparator;
21
22 /**
23 * Defines the interface to analyze {@link org.apache.commons.collections4.Trie Trie} keys on a bit level.
24 * {@link KeyAnalyzer}'s methods return the length of the key in bits, whether or not a bit is set,
25 * and bits per element in the key.
26 * <p>
27 * Additionally, a method determines if a key is a prefix of another
28 * key and returns the bit index where one key is different from another
29 * key (if the key and found key are equal than the return value is
30 * {@link #EQUAL_BIT_KEY}).
31 * </p>
32 *
33 * @param <K> the type of objects that may be compared by this analyzer
34 * @since 4.0
35 */
36 public abstract class KeyAnalyzer<K> implements Comparator<K>, Serializable {
37
38 /** Serialization version */
39 private static final long serialVersionUID = -20497563720380683L;
40
41 /**
42 * Returned by {@link #bitIndex(Object, int, int, Object, int, int)}
43 * if key's bits are all 0.
44 */
45 public static final int NULL_BIT_KEY = -1;
46
47 /**
48 * Returned by {@link #bitIndex(Object, int, int, Object, int, int)} if key and found key are equal.
49 * This is a very specific case and shouldn't happen on a regular basis.
50 */
51 public static final int EQUAL_BIT_KEY = -2;
52
53 /**
54 * Used to test a {@code bitIndex} in {@link #isOutOfBoundsIndex(int)}.
55 */
56 public static final int OUT_OF_BOUNDS_BIT_KEY = -3;
57
58 /**
59 * Returns true if bitIndex is a {@link KeyAnalyzer#EQUAL_BIT_KEY}.
60 */
61 static boolean isEqualBitKey(final int bitIndex) {
62 return bitIndex == EQUAL_BIT_KEY;
63 }
64
65 /**
66 * Returns true if bitIndex is a {@link KeyAnalyzer#NULL_BIT_KEY}.
67 */
68 static boolean isNullBitKey(final int bitIndex) {
69 return bitIndex == NULL_BIT_KEY;
70 }
71
72 /**
73 * Returns true if bitIndex is a {@link KeyAnalyzer#OUT_OF_BOUNDS_BIT_KEY}.
74 */
75 static boolean isOutOfBoundsIndex(final int bitIndex) {
76 return bitIndex == OUT_OF_BOUNDS_BIT_KEY;
77 }
78
79 /**
80 * Returns true if the given bitIndex is valid.
81 * Indices are considered valid if they're between 0 and {@link Integer#MAX_VALUE}
82 */
83 static boolean isValidBitIndex(final int bitIndex) {
84 return bitIndex >= 0;
85 }
86
87 /**
88 * Constructs a new instance.
89 */
90 public KeyAnalyzer() {
91 // empty
92 }
93
94 /**
95 * Returns the n-th different bit between key and other. This starts the comparison in
96 * key at 'offsetInBits' and goes for 'lengthInBits' bits, and compares to the other key starting
97 * at 'otherOffsetInBits' and going for 'otherLengthInBits' bits.
98 *
99 * @param key the key to use
100 * @param offsetInBits the bit offset in the key
101 * @param lengthInBits the maximum key length in bits to use
102 * @param other the other key to use
103 * @param otherOffsetInBits the bit offset in the other key
104 * @param otherLengthInBits the maximum key length in bits for the other key
105 * @return the bit index where the key and other first differ
106 */
107 public abstract int bitIndex(K key, int offsetInBits, int lengthInBits,
108 K other, int otherOffsetInBits, int otherLengthInBits);
109
110 /**
111 * Returns the number of bits per element in the key.
112 * This is only useful for variable-length keys, such as Strings.
113 *
114 * @return the number of bits per element
115 */
116 public abstract int bitsPerElement();
117
118 @Override
119 @SuppressWarnings("unchecked")
120 public int compare(final K o1, final K o2) {
121 if (o1 == null) {
122 return o2 == null ? 0 : -1;
123 }
124 if (o2 == null) {
125 return 1;
126 }
127
128 return ((Comparable<K>) o1).compareTo(o2);
129 }
130
131 /**
132 * Returns whether or not a bit is set.
133 *
134 * @param key the key to check, may not be null
135 * @param bitIndex the bit index to check
136 * @param lengthInBits the maximum key length in bits to check
137 * @return {@code true} if the bit is set in the given key and
138 * {@code bitIndex} < {@code lengthInBits}, {@code false} otherwise.
139 */
140 public abstract boolean isBitSet(K key, int bitIndex, int lengthInBits);
141
142 /**
143 * Determines whether or not the given prefix (from offset to length) is a prefix of the given key.
144 *
145 * @param prefix the prefix to check
146 * @param offsetInBits the bit offset in the key
147 * @param lengthInBits the maximum key length in bits to use
148 * @param key the key to check
149 * @return {@code true} if this is a valid prefix for the given key
150 */
151 public abstract boolean isPrefix(K prefix, int offsetInBits, int lengthInBits, K key);
152
153 /**
154 * Returns the length of the Key in bits.
155 *
156 * @param key the key
157 * @return the bit length of the key
158 */
159 public abstract int lengthInBits(K key);
160
161 }