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 * Returns the n-th different bit between key and other. This starts the comparison in
89 * key at 'offsetInBits' and goes for 'lengthInBits' bits, and compares to the other key starting
90 * at 'otherOffsetInBits' and going for 'otherLengthInBits' bits.
91 *
92 * @param key the key to use
93 * @param offsetInBits the bit offset in the key
94 * @param lengthInBits the maximum key length in bits to use
95 * @param other the other key to use
96 * @param otherOffsetInBits the bit offset in the other key
97 * @param otherLengthInBits the maximum key length in bits for the other key
98 * @return the bit index where the key and other first differ
99 */
100 public abstract int bitIndex(K key, int offsetInBits, int lengthInBits,
101 K other, int otherOffsetInBits, int otherLengthInBits);
102
103 /**
104 * Returns the number of bits per element in the key.
105 * This is only useful for variable-length keys, such as Strings.
106 *
107 * @return the number of bits per element
108 */
109 public abstract int bitsPerElement();
110
111 @Override
112 @SuppressWarnings("unchecked")
113 public int compare(final K o1, final K o2) {
114 if (o1 == null) {
115 return o2 == null ? 0 : -1;
116 }
117 if (o2 == null) {
118 return 1;
119 }
120
121 return ((Comparable<K>) o1).compareTo(o2);
122 }
123
124 /**
125 * Returns whether or not a bit is set.
126 *
127 * @param key the key to check, may not be null
128 * @param bitIndex the bit index to check
129 * @param lengthInBits the maximum key length in bits to check
130 * @return {@code true} if the bit is set in the given key and
131 * {@code bitIndex} < {@code lengthInBits}, {@code false} otherwise.
132 */
133 public abstract boolean isBitSet(K key, int bitIndex, int lengthInBits);
134
135 /**
136 * Determines whether or not the given prefix (from offset to length) is a prefix of the given key.
137 *
138 * @param prefix the prefix to check
139 * @param offsetInBits the bit offset in the key
140 * @param lengthInBits the maximum key length in bits to use
141 * @param key the key to check
142 * @return {@code true} if this is a valid prefix for the given key
143 */
144 public abstract boolean isPrefix(K prefix, int offsetInBits, int lengthInBits, K key);
145
146 /**
147 * Returns the length of the Key in bits.
148 *
149 * @param key the key
150 * @return the bit length of the key
151 */
152 public abstract int lengthInBits(K key);
153
154 }