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, very specific case and shouldn't happen on a regular basis.
50 */
51 public static final int EQUAL_BIT_KEY = -2;
52
53 public static final int OUT_OF_BOUNDS_BIT_KEY = -3;
54
55 /**
56 * Returns true if bitIndex is a {@link KeyAnalyzer#EQUAL_BIT_KEY}.
57 */
58 static boolean isEqualBitKey(final int bitIndex) {
59 return bitIndex == EQUAL_BIT_KEY;
60 }
61
62 /**
63 * Returns true if bitIndex is a {@link KeyAnalyzer#NULL_BIT_KEY}.
64 */
65 static boolean isNullBitKey(final int bitIndex) {
66 return bitIndex == NULL_BIT_KEY;
67 }
68
69 /**
70 * Returns true if bitIndex is a {@link KeyAnalyzer#OUT_OF_BOUNDS_BIT_KEY}.
71 */
72 static boolean isOutOfBoundsIndex(final int bitIndex) {
73 return bitIndex == OUT_OF_BOUNDS_BIT_KEY;
74 }
75
76 /**
77 * Returns true if the given bitIndex is valid.
78 * Indices are considered valid if they're between 0 and {@link Integer#MAX_VALUE}
79 */
80 static boolean isValidBitIndex(final int bitIndex) {
81 return bitIndex >= 0;
82 }
83
84 /**
85 * Returns the n-th different bit between key and other. This starts the comparison in
86 * key at 'offsetInBits' and goes for 'lengthInBits' bits, and compares to the other key starting
87 * at 'otherOffsetInBits' and going for 'otherLengthInBits' bits.
88 *
89 * @param key the key to use
90 * @param offsetInBits the bit offset in the key
91 * @param lengthInBits the maximum key length in bits to use
92 * @param other the other key to use
93 * @param otherOffsetInBits the bit offset in the other key
94 * @param otherLengthInBits the maximum key length in bits for the other key
95 * @return the bit index where the key and other first differ
96 */
97 public abstract int bitIndex(K key, int offsetInBits, int lengthInBits,
98 K other, int otherOffsetInBits, int otherLengthInBits);
99
100 /**
101 * Returns the number of bits per element in the key.
102 * This is only useful for variable-length keys, such as Strings.
103 *
104 * @return the number of bits per element
105 */
106 public abstract int bitsPerElement();
107
108 @Override
109 @SuppressWarnings("unchecked")
110 public int compare(final K o1, final K o2) {
111 if (o1 == null) {
112 return o2 == null ? 0 : -1;
113 }
114 if (o2 == null) {
115 return 1;
116 }
117
118 return ((Comparable<K>) o1).compareTo(o2);
119 }
120
121 /**
122 * Returns whether or not a bit is set.
123 *
124 * @param key the key to check, may not be null
125 * @param bitIndex the bit index to check
126 * @param lengthInBits the maximum key length in bits to check
127 * @return {@code true} if the bit is set in the given key and
128 * {@code bitIndex} < {@code lengthInBits}, {@code false} otherwise.
129 */
130 public abstract boolean isBitSet(K key, int bitIndex, int lengthInBits);
131
132 /**
133 * Determines whether or not the given prefix (from offset to length) is a prefix of the given key.
134 *
135 * @param prefix the prefix to check
136 * @param offsetInBits the bit offset in the key
137 * @param lengthInBits the maximum key length in bits to use
138 * @param key the key to check
139 * @return {@code true} if this is a valid prefix for the given key
140 */
141 public abstract boolean isPrefix(K prefix, int offsetInBits, int lengthInBits, K key);
142
143 /**
144 * Returns the length of the Key in bits.
145 *
146 * @param key the key
147 * @return the bit length of the key
148 */
149 public abstract int lengthInBits(K key);
150
151 }