/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.collections4.trie;

import java.io.Serializable;
import java.util.Comparator;

Defines the interface to analyze Trie keys on a bit level. KeyAnalyzer's methods return the length of the key in bits, whether or not a bit is set, and bits per element in the key. 
 Additionally, a method determines if a key is a prefix of another key and returns the bit index where one key is different from another key (if the key and found key are equal than the return value is KeyAnalyzer<K>.EQUAL_BIT_KEY). 
Type parameters:
<K> – the type of objects that may be compared by this analyzer
Since:
4.0/**
 * Defines the interface to analyze {@link org.apache.commons.collections4.Trie Trie} keys on a bit level.
 * {@link KeyAnalyzer}'s methods return the length of the key in bits, whether or not a bit is set,
 * and bits per element in the key.
 * <p>
 * Additionally, a method determines if a key is a prefix of another
 * key and returns the bit index where one key is different from another
 * key (if the key and found key are equal than the return value is
 * {@link #EQUAL_BIT_KEY}).
 * </p>
 *
 * @param <K> the type of objects that may be compared by this analyzer
 * @since 4.0
 */
public abstract class KeyAnalyzer<K> implements Comparator<K>, Serializable {

    
Serialization version /** Serialization version */
    private static final long serialVersionUID = -20497563720380683L;

    
Returned by bitIndex(Object, int, int, Object, int, int) if key's bits are all 0. /**
     * Returned by {@link #bitIndex(Object, int, int, Object, int, int)}
     * if key's bits are all 0.
     */
    public static final int NULL_BIT_KEY = -1;

    
Returned by bitIndex(Object, int, int, Object, int, int) if key and found key are equal. This is a very very specific case and shouldn't happen on a regular basis. /**
     * Returned by {@link #bitIndex(Object, int, int, Object, int, int)} if key and found key are equal.
     * This is a very very specific case and shouldn't happen on a regular basis.
     */
    public static final int EQUAL_BIT_KEY = -2;

    public static final int OUT_OF_BOUNDS_BIT_KEY = -3;

    
Returns true if bitIndex is a OUT_OF_BOUNDS_BIT_KEY. /**
     * Returns true if bitIndex is a {@link KeyAnalyzer#OUT_OF_BOUNDS_BIT_KEY}.
     */
    static boolean isOutOfBoundsIndex(final int bitIndex) {
        return bitIndex == OUT_OF_BOUNDS_BIT_KEY;
    }

    
Returns true if bitIndex is a EQUAL_BIT_KEY. /**
     * Returns true if bitIndex is a {@link KeyAnalyzer#EQUAL_BIT_KEY}.
     */
    static boolean isEqualBitKey(final int bitIndex) {
        return bitIndex == EQUAL_BIT_KEY;
    }

    
Returns true if bitIndex is a NULL_BIT_KEY. /**
     * Returns true if bitIndex is a {@link KeyAnalyzer#NULL_BIT_KEY}.
     */
    static boolean isNullBitKey(final int bitIndex) {
        return bitIndex == NULL_BIT_KEY;
    }

    
Returns true if the given bitIndex is valid. Indices are considered valid if they're between 0 and Integer.MAX_VALUE /**
     * Returns true if the given bitIndex is valid.
     * Indices are considered valid if they're between 0 and {@link Integer#MAX_VALUE}
     */
    static boolean isValidBitIndex(final int bitIndex) {
        return bitIndex >= 0;
    }

    
Returns the number of bits per element in the key.
This is only useful for variable-length keys, such as Strings.
Returns:
the number of bits per element/**
     * Returns the number of bits per element in the key.
     * This is only useful for variable-length keys, such as Strings.
     *
     * @return the number of bits per element
     */
    public abstract int bitsPerElement();

    
Returns the length of the Key in bits.
Params:
key –  the key
Returns:
the bit length of the key/**
     * Returns the length of the Key in bits.
     *
     * @param key  the key
     * @return the bit length of the key
     */
    public abstract int lengthInBits(K key);

    
Returns whether or not a bit is set.
Params:
key –  the key to check, may not be null
bitIndex –  the bit index to check
lengthInBits –  the maximum key length in bits to check
Returns:
true if the bit is set in the given key and bitIndex < lengthInBits, false otherwise./**
     * Returns whether or not a bit is set.
     *
     * @param key  the key to check, may not be null
     * @param bitIndex  the bit index to check
     * @param lengthInBits  the maximum key length in bits to check
     * @return {@code true} if the bit is set in the given key and
     *   {@code bitIndex} &lt; {@code lengthInBits}, {@code false} otherwise.
     */
    public abstract boolean isBitSet(K key, int bitIndex, int lengthInBits);

    
Returns the n-th different bit between key and other. This starts the comparison in
key at 'offsetInBits' and goes for 'lengthInBits' bits, and compares to the other key starting
at 'otherOffsetInBits' and going for 'otherLengthInBits' bits.
Params:
key –  the key to use
offsetInBits –  the bit offset in the key
lengthInBits –  the maximum key length in bits to use
other –  the other key to use
otherOffsetInBits –  the bit offset in the other key
otherLengthInBits –  the maximum key length in bits for the other key
Returns:
the bit index where the key and other first differ/**
     * Returns the n-th different bit between key and other. This starts the comparison in
     * key at 'offsetInBits' and goes for 'lengthInBits' bits, and compares to the other key starting
     * at 'otherOffsetInBits' and going for 'otherLengthInBits' bits.
     *
     * @param key  the key to use
     * @param offsetInBits  the bit offset in the key
     * @param lengthInBits  the maximum key length in bits to use
     * @param other  the other key to use
     * @param otherOffsetInBits  the bit offset in the other key
     * @param otherLengthInBits  the maximum key length in bits for the other key
     * @return the bit index where the key and other first differ
     */
    public abstract int bitIndex(K key, int offsetInBits, int lengthInBits,
                                 K other, int otherOffsetInBits, int otherLengthInBits);

    
Determines whether or not the given prefix (from offset to length) is a prefix of the given key.
Params:
prefix –  the prefix to check
offsetInBits –  the bit offset in the key
lengthInBits –  the maximum key length in bits to use
key –  the key to check
Returns:
true if this is a valid prefix for the given key/**
     * Determines whether or not the given prefix (from offset to length) is a prefix of the given key.
     *
     * @param prefix  the prefix to check
     * @param offsetInBits  the bit offset in the key
     * @param lengthInBits  the maximum key length in bits to use
     * @param key  the key to check
     * @return {@code true} if this is a valid prefix for the given key
     */
    public abstract boolean isPrefix(K prefix, int offsetInBits, int lengthInBits, K key);

    @Override
    @SuppressWarnings("unchecked")
    public int compare(final K o1, final K o2) {
        if (o1 == null) {
            return o2 == null ? 0 : -1;
        } else if (o2 == null) {
            return 1;
        }

        return ((Comparable<K>) o1).compareTo(o2);
    }

}