    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      https://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.trie;
    018
    019import java.io.Serializable;
    020import java.util.AbstractMap;
    021import java.util.Map;
    022import java.util.Objects;
    023
    024import org.apache.commons.collections4.Trie;
    025
    026/**
    027 * This class provides some basic {@link Trie} functionality and
    028 * utility methods for actual bitwise {@link Trie} implementations.
    029 *
    030 * @param <K> The type of the keys in this map
    031 * @param <V> The type of the values in this map
    032 * @since 4.0
    033 */
    034public abstract class AbstractBitwiseTrie<K, V> extends AbstractMap<K, V>
    035        implements Trie<K, V>, Serializable {
    036
    037    /**
    038     * A basic implementation of {@link Entry}.
    039     *
    040     * @param <K> The type of the keys in this entry.
    041     * @param <V> The type of the values in this entry.
    042     */
    043    abstract static class BasicEntry<K, V> implements Map.Entry<K, V>, Serializable {
    044
    045        private static final long serialVersionUID = -944364551314110330L;
    046
    047        /**
    048         * The entry's key.
    049         */
    050        protected K key;
    051
    052        /**
    053         * The entry's value.
    054         */
    055        protected V value;
    056
    057        BasicEntry(final K key) {
    058            this.key = key;
    059        }
    060
    061        BasicEntry(final K key, final V value) {
    062            this.key = key;
    063            this.value = value;
    064        }
    065
    066        @Override
    067        public boolean equals(final Object o) {
    068            if (o == this) {
    069                return true;
    070            }
    071            if (!(o instanceof Map.Entry)) {
    072                return false;
    073            }
    074
    075            final Map.Entry<?, ?> other = (Map.Entry<?, ?>) o;
    076            if (compare(key, other.getKey())
    077                    && compare(value, other.getValue())) {
    078                return true;
    079            }
    080            return false;
    081        }
    082
    083        @Override
    084        public K getKey() {
    085            return key;
    086        }
    087
    088        @Override
    089        public V getValue() {
    090            return value;
    091        }
    092
    093        @Override
    094        public int hashCode() {
    095            return (getKey() == null ? 0 : getKey().hashCode()) ^
    096                   (getValue() == null ? 0 : getValue().hashCode());
    097        }
    098
    099        /**
    100         * Replaces the current key and value with the provided key &amp; value.
    101         *
    102         * @param key The new key.
    103         * @param value The new value.
    104         * @return The previous value.
    105         */
    106        public V setKeyValue(final K key, final V value) {
    107            this.key = key;
    108            return setValue(value);
    109        }
    110
    111        @Override
    112        public V setValue(final V value) {
    113            final V previous = this.value;
    114            this.value = value;
    115            return previous;
    116        }
    117
    118        @Override
    119        public String toString() {
    120            return key + "=" + value;
    121        }
    122    }
    123
    124    private static final long serialVersionUID = 5826987063535505652L;
    125
    126    /**
    127     * Delegates to {@link Objects#equals(Object, Object)}.
    128     */
    129    static boolean compare(final Object a, final Object b) {
    130        return Objects.equals(a, b);
    131    }
    132
    133    /**
    134     * The {@link KeyAnalyzer} that's being used to build the PATRICIA {@link Trie}.
    135     */
    136    private final KeyAnalyzer<? super K> keyAnalyzer;
    137
    138    /**
    139     * Constructs a new {@link Trie} using the given {@link KeyAnalyzer}.
    140     *
    141     * @param keyAnalyzer  The {@link KeyAnalyzer} to use
    142     */
    143    protected AbstractBitwiseTrie(final KeyAnalyzer<? super K> keyAnalyzer) {
    144        this.keyAnalyzer = Objects.requireNonNull(keyAnalyzer, "keyAnalyzer");
    145    }
    146
    147    /**
    148     * Utility method for calling {@link KeyAnalyzer#bitIndex(Object, int, int, Object, int, int)}.
    149     */
    150    final int bitIndex(final K key, final K foundKey) {
    151        return keyAnalyzer.bitIndex(key, 0, lengthInBits(key), foundKey, 0, lengthInBits(foundKey));
    152    }
    153
    154    /**
    155     * Returns the number of bits per element in the key
    156     *
    157     * @see KeyAnalyzer#bitsPerElement()
    158     */
    159    final int bitsPerElement() {
    160        return keyAnalyzer.bitsPerElement();
    161    }
    162
    163    /**
    164     * A utility method to cast keys. It actually doesn't cast anything. It's just fooling the compiler!
    165     */
    166    @SuppressWarnings("unchecked")
    167    final K castKey(final Object key) {
    168        return (K) key;
    169    }
    170
    171    /**
    172     * Gets the {@link KeyAnalyzer} that constructed the {@link Trie}.
    173     *
    174     * @return The {@link KeyAnalyzer} used by this {@link Trie}
    175     */
    176    protected KeyAnalyzer<? super K> getKeyAnalyzer() {
    177        return keyAnalyzer;
    178    }
    179
    180    /**
    181     * Returns whether or not the given bit on the key is set or false if the key is null.
    182     *
    183     * @see KeyAnalyzer#isBitSet(Object, int, int)
    184     */
    185    final boolean isBitSet(final K key, final int bitIndex, final int lengthInBits) {
    186        if (key == null) { // root's might be null!
    187            return false;
    188        }
    189        return keyAnalyzer.isBitSet(key, bitIndex, lengthInBits);
    190    }
    191
    192    /**
    193     * A null-safe utility method for calling {@link KeyAnalyzer#compare(Object, Object)}
    194     */
    195    final boolean keysAreEqual(final K key, final K other) {
    196        if (key == null) {
    197            return other == null;
    198        }
    199        if (other == null) {
    200            return false;
    201        }
    202
    203        return keyAnalyzer.compare(key, other) == 0;
    204    }
    205
    206    /**
    207     * Returns the length of the given key in bits
    208     *
    209     * @see KeyAnalyzer#lengthInBits(Object)
    210     */
    211    final int lengthInBits(final K key) {
    212        if (key == null) {
    213            return 0;
    214        }
    215
    216        return keyAnalyzer.lengthInBits(key);
    217    }
    218
    219    @Override
    220    public String toString() {
    221        final StringBuilder buffer = new StringBuilder();
    222        buffer.append("Trie[").append(size()).append("]={\n");
    223        for (final Map.Entry<K, V> entry : entrySet()) {
    224            buffer.append("  ").append(entry).append("\n");
    225        }
    226        buffer.append("}\n");
    227        return buffer.toString();
    228    }
    229}