    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 *      http://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    abstract static class BasicEntry<K, V> implements Map.Entry<K, V>, Serializable {
    041
    042        private static final long serialVersionUID = -944364551314110330L;
    043
    044        protected K key;
    045
    046        protected V value;
    047
    048        BasicEntry(final K key) {
    049            this.key = key;
    050        }
    051
    052        BasicEntry(final K key, final V value) {
    053            this.key = key;
    054            this.value = value;
    055        }
    056
    057        @Override
    058        public boolean equals(final Object o) {
    059            if (o == this) {
    060                return true;
    061            }
    062            if (!(o instanceof Map.Entry)) {
    063                return false;
    064            }
    065
    066            final Map.Entry<?, ?> other = (Map.Entry<?, ?>) o;
    067            if (compare(key, other.getKey())
    068                    && compare(value, other.getValue())) {
    069                return true;
    070            }
    071            return false;
    072        }
    073
    074        @Override
    075        public K getKey() {
    076            return key;
    077        }
    078
    079        @Override
    080        public V getValue() {
    081            return value;
    082        }
    083
    084        @Override
    085        public int hashCode() {
    086            return (getKey() == null ? 0 : getKey().hashCode()) ^
    087                   (getValue() == null ? 0 : getValue().hashCode());
    088        }
    089
    090        /**
    091         * Replaces the current key and value with the provided key &amp; value.
    092         */
    093        public V setKeyValue(final K key, final V value) {
    094            this.key = key;
    095            return setValue(value);
    096        }
    097
    098        @Override
    099        public V setValue(final V value) {
    100            final V previous = this.value;
    101            this.value = value;
    102            return previous;
    103        }
    104
    105        @Override
    106        public String toString() {
    107            return key + "=" + value;
    108        }
    109    }
    110
    111    private static final long serialVersionUID = 5826987063535505652L;
    112
    113    /**
    114     * Delegates to {@link Objects#equals(Object, Object)}.
    115     */
    116    static boolean compare(final Object a, final Object b) {
    117        return Objects.equals(a, b);
    118    }
    119
    120    /**
    121     * The {@link KeyAnalyzer} that's being used to build the PATRICIA {@link Trie}.
    122     */
    123    private final KeyAnalyzer<? super K> keyAnalyzer;
    124
    125    /**
    126     * Constructs a new {@link Trie} using the given {@link KeyAnalyzer}.
    127     *
    128     * @param keyAnalyzer  the {@link KeyAnalyzer} to use
    129     */
    130    protected AbstractBitwiseTrie(final KeyAnalyzer<? super K> keyAnalyzer) {
    131        this.keyAnalyzer = Objects.requireNonNull(keyAnalyzer, "keyAnalyzer");
    132    }
    133
    134    /**
    135     * Utility method for calling {@link KeyAnalyzer#bitIndex(Object, int, int, Object, int, int)}.
    136     */
    137    final int bitIndex(final K key, final K foundKey) {
    138        return keyAnalyzer.bitIndex(key, 0, lengthInBits(key), foundKey, 0, lengthInBits(foundKey));
    139    }
    140
    141    /**
    142     * Returns the number of bits per element in the key
    143     *
    144     * @see KeyAnalyzer#bitsPerElement()
    145     */
    146    final int bitsPerElement() {
    147        return keyAnalyzer.bitsPerElement();
    148    }
    149
    150    /**
    151     * A utility method to cast keys. It actually doesn't cast anything. It's just fooling the compiler!
    152     */
    153    @SuppressWarnings("unchecked")
    154    final K castKey(final Object key) {
    155        return (K) key;
    156    }
    157
    158    /**
    159     * A utility method for calling {@link KeyAnalyzer#compare(Object, Object)}
    160     */
    161    final boolean compareKeys(final K key, final K other) {
    162        if (key == null) {
    163            return other == null;
    164        }
    165        if (other == null) {
    166            return false;
    167        }
    168
    169        return keyAnalyzer.compare(key, other) == 0;
    170    }
    171
    172    /**
    173     * Returns the {@link KeyAnalyzer} that constructed the {@link Trie}.
    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     * Returns the length of the given key in bits
    194     *
    195     * @see KeyAnalyzer#lengthInBits(Object)
    196     */
    197    final int lengthInBits(final K key) {
    198        if (key == null) {
    199            return 0;
    200        }
    201
    202        return keyAnalyzer.lengthInBits(key);
    203    }
    204
    205    @Override
    206    public String toString() {
    207        final StringBuilder buffer = new StringBuilder();
    208        buffer.append("Trie[").append(size()).append("]={\n");
    209        for (final Map.Entry<K, V> entry : entrySet()) {
    210            buffer.append("  ").append(entry).append("\n");
    211        }
    212        buffer.append("}\n");
    213        return buffer.toString();
    214    }
    215}