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 * https://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 import org.apache.commons.collections4.Trie;
23
24 /**
25 * Defines the interface to analyze {@link Trie Trie} keys on a bit level.
26 * {@link KeyAnalyzer}'s methods return the length of the key in bits, whether or not a bit is set,
27 * and bits per element in the key.
28 * <p>
29 * Additionally, a method determines if a key is a prefix of another
30 * key and returns the bit index where one key is different from another
31 * key (if the key and found key are equal than the return value is
32 * {@link #EQUAL_BIT_KEY}).
33 * </p>
34 *
35 * @param <K> The type of objects that may be compared by this analyzer
36 * @since 4.0
37 */
38 public abstract class KeyAnalyzer<K> implements Comparator<K>, Serializable {
39
40 /** Serialization version */
41 private static final long serialVersionUID = -20497563720380683L;
42
43 /**
44 * Returned by {@link #bitIndex(Object, int, int, Object, int, int)}
45 * if key's bits are all 0.
46 */
47 public static final int NULL_BIT_KEY = -1;
48
49 /**
50 * Returned by {@link #bitIndex(Object, int, int, Object, int, int)} if key and found key are equal.
51 * This is a very specific case and shouldn't happen on a regular basis.
52 */
53 public static final int EQUAL_BIT_KEY = -2;
54
55 /**
56 * Used to test a {@code bitIndex} in {@link #isOutOfBoundsIndex(int)}.
57 */
58 public static final int OUT_OF_BOUNDS_BIT_KEY = -3;
59
60 /**
61 * Returns true if bitIndex is a {@link KeyAnalyzer#EQUAL_BIT_KEY}.
62 */
63 static boolean isEqualBitKey(final int bitIndex) {
64 return bitIndex == EQUAL_BIT_KEY;
65 }
66
67 /**
68 * Returns true if bitIndex is a {@link KeyAnalyzer#NULL_BIT_KEY}.
69 */
70 static boolean isNullBitKey(final int bitIndex) {
71 return bitIndex == NULL_BIT_KEY;
72 }
73
74 /**
75 * Returns true if bitIndex is a {@link KeyAnalyzer#OUT_OF_BOUNDS_BIT_KEY}.
76 */
77 static boolean isOutOfBoundsIndex(final int bitIndex) {
78 return bitIndex == OUT_OF_BOUNDS_BIT_KEY;
79 }
80
81 /**
82 * Returns true if the given bitIndex is valid.
83 * Indices are considered valid if they're between 0 and {@link Integer#MAX_VALUE}
84 */
85 static boolean isValidBitIndex(final int bitIndex) {
86 return bitIndex >= 0;
87 }
88
89 /**
90 * Constructs a new instance.
91 */
92 public KeyAnalyzer() {
93 // empty
94 }
95
96 /**
97 * Returns the n-th different bit between key and other. This starts the comparison in
98 * key at 'offsetInBits' and goes for 'lengthInBits' bits, and compares to the other key starting
99 * at 'otherOffsetInBits' and going for 'otherLengthInBits' bits.
100 *
101 * @param key The key to use
102 * @param offsetInBits The bit offset in the key
103 * @param lengthInBits The maximum key length in bits to use
104 * @param other The other key to use
105 * @param otherOffsetInBits The bit offset in the other key
106 * @param otherLengthInBits The maximum key length in bits for the other key
107 * @return The bit index where the key and other first differ
108 */
109 public abstract int bitIndex(K key, int offsetInBits, int lengthInBits,
110 K other, int otherOffsetInBits, int otherLengthInBits);
111
112 /**
113 * Returns the number of bits per element in the key.
114 * This is only useful for variable-length keys, such as Strings.
115 *
116 * @return The number of bits per element
117 */
118 public abstract int bitsPerElement();
119
120 @Override
121 @SuppressWarnings("unchecked")
122 public int compare(final K o1, final K o2) {
123 if (o1 == null) {
124 return o2 == null ? 0 : -1;
125 }
126 if (o2 == null) {
127 return 1;
128 }
129
130 return ((Comparable<K>) o1).compareTo(o2);
131 }
132
133 /**
134 * Returns whether or not a bit is set.
135 *
136 * @param key The key to check, may not be null
137 * @param bitIndex The bit index to check
138 * @param lengthInBits The maximum key length in bits to check
139 * @return {@code true} if the bit is set in the given key and
140 * {@code bitIndex} < {@code lengthInBits}, {@code false} otherwise.
141 */
142 public abstract boolean isBitSet(K key, int bitIndex, int lengthInBits);
143
144 /**
145 * Determines whether or not the given prefix (from offset to length) is a prefix of the given key.
146 *
147 * @param prefix The prefix to check
148 * @param offsetInBits The bit offset in the key
149 * @param lengthInBits The maximum key length in bits to use
150 * @param key The key to check
151 * @return {@code true} if this is a valid prefix for the given key
152 */
153 public abstract boolean isPrefix(K prefix, int offsetInBits, int lengthInBits, K key);
154
155 /**
156 * Returns the length of the Key in bits.
157 *
158 * @param key The key
159 * @return The bit length of the key
160 */
161 public abstract int lengthInBits(K key);
162
163 }