path: root/third_party/java/jopt-simple/src/main/java/joptsimple/internal/AbbreviationMap.java

/*
 The MIT License

 Copyright (c) 2004-2015 Paul R. Holser, Jr.

 Permission is hereby granted, free of charge, to any person obtaining
 a copy of this software and associated documentation files (the
 "Software"), to deal in the Software without restriction, including
 without limitation the rights to use, copy, modify, merge, publish,
 distribute, sublicense, and/or sell copies of the Software, and to
 permit persons to whom the Software is furnished to do so, subject to
 the following conditions:

 The above copyright notice and this permission notice shall be
 included in all copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

package joptsimple.internal;

import java.util.Map;
import java.util.TreeMap;

/**
 * <p>A map whose keys are strings; when a key/value pair is added to the map, the longest unique abbreviations of that
 * key are added as well, and associated with the value. Thus:</p>
 *
 * <pre>
 *   <code>
 *   abbreviations.put( "good", "bye" );
 *   </code>
 * </pre>
 *
 * <p>would make it such that you could retrieve the value {@code "bye"} from the map using the keys {@code "good"},
 * {@code "goo"}, {@code "go"}, and {@code "g"}. A subsequent invocation of:</p>
 * <pre>
 *   <code>
 *   abbreviations.put( "go", "fish" );
 *   </code>
 * </pre>
 *
 * <p>would make it such that you could retrieve the value {@code "bye"} using the keys {@code "good"} and
 * {@code "goo"}, and the value {@code "fish"} using the key {@code "go"}.  The key {@code "g"} would yield
 * {@code null}, since it would no longer be a unique abbreviation.</p>
 *
 * <p>The data structure is much like a "trie".</p>
 *
 * @param <V> a constraint on the types of the values in the map
 * @author <a href="mailto:pholser@alumni.rice.edu">Paul Holser</a>
 * @see <a href="http://perldoc.perl.org/Text/Abbrev.html">Perl's Text::Abbrev module</a>
 * @see <a href="https://en.wikipedia.org/wiki/Radix_tree">Radix tree</a>
 */
public class AbbreviationMap<V> implements OptionNameMap<V> {
    private final Map<Character, AbbreviationMap<V>> children = new TreeMap<>();

    private String key;
    private V value;
    private int keysBeyond;

    /**
     * <p>Tells whether the given key is in the map, or whether the given key is a unique
     * abbreviation of a key that is in the map.</p>
     *
     * @param key key to look up
     * @return {@code true} if {@code key} is present in the map
     * @throws NullPointerException if {@code key} is {@code null}
     */
    @Override
    public boolean contains(String key) {
        return get(key) != null;
    }

    /**
     * <p>Answers the value associated with the given key.  The key can be a unique
     * abbreviation of a key that is in the map. </p>
     *
     * @param key key to look up
     * @return the value associated with {@code aKey}; or {@code null} if there is no
     * such value or {@code aKey} is not a unique abbreviation of a key in the map
     * @throws NullPointerException if {@code aKey} is {@code null}
     */
    @Override
    public V get( String key ) {
        char[] chars = charsOf( key );

        AbbreviationMap<V> child = this;
        for ( char each : chars ) {
            child = child.children.get( each );
            if ( child == null )
                return null;
        }

        return child.value;
    }

    /**
     * <p>Associates a given value with a given key.  If there was a previous
     * association, the old value is replaced with the new one.</p>
     *
     * @param key key to create in the map
     * @param newValue value to associate with the key
     * @throws NullPointerException if {@code aKey} or {@code newValue} is {@code null}
     * @throws IllegalArgumentException if {@code aKey} is a zero-length string
     */
    @Override
    public void put( String key, V newValue ) {
        if ( newValue == null )
            throw new NullPointerException();
        if ( key.length() == 0 )
            throw new IllegalArgumentException();

        char[] chars = charsOf(key);
        add( chars, newValue, 0, chars.length );
    }

    /**
     * <p>Associates a given value with a given set of keys.  If there was a previous
     * association, the old value is replaced with the new one.</p>
     *
     * @param keys keys to create in the map
     * @param newValue value to associate with the key
     * @throws NullPointerException if {@code keys} or {@code newValue} is {@code null}
     * @throws IllegalArgumentException if any of {@code keys} is a zero-length string
     */
    @Override
    public void putAll( Iterable<String> keys, V newValue ) {
        for ( String each : keys )
            put( each, newValue );
    }

    private boolean add( char[] chars, V newValue, int offset, int length ) {
        if ( offset == length ) {
            value = newValue;
            boolean wasAlreadyAKey = key != null;
            key = new String( chars );
            return !wasAlreadyAKey;
        }

        char nextChar = chars[ offset ];
        AbbreviationMap<V> child = children.get( nextChar );
        if ( child == null ) {
            child = new AbbreviationMap<>();
            children.put( nextChar, child );
        }

        boolean newKeyAdded = child.add( chars, newValue, offset + 1, length );

        if ( newKeyAdded )
            ++keysBeyond;

        if ( key == null )
            value = keysBeyond > 1 ? null : newValue;

        return newKeyAdded;
    }

    /**
     * <p>If the map contains the given key, dissociates the key from its value.</p>
     *
     * @param key key to remove
     * @throws NullPointerException if {@code aKey} is {@code null}
     * @throws IllegalArgumentException if {@code aKey} is a zero-length string
     */
    @Override
    public void remove( String key ) {
        if ( key.length() == 0 )
            throw new IllegalArgumentException();

        char[] keyChars = charsOf(key);
        remove( keyChars, 0, keyChars.length );
    }

    private boolean remove( char[] aKey, int offset, int length ) {
        if ( offset == length )
            return removeAtEndOfKey();

        char nextChar = aKey[ offset ];
        AbbreviationMap<V> child = children.get( nextChar );
        if ( child == null || !child.remove( aKey, offset + 1, length ) )
            return false;

        --keysBeyond;
        if ( child.keysBeyond == 0 )
            children.remove( nextChar );
        if ( keysBeyond == 1 && key == null )
            setValueToThatOfOnlyChild();

        return true;
    }

    private void setValueToThatOfOnlyChild() {
        Map.Entry<Character, AbbreviationMap<V>> entry = children.entrySet().iterator().next();
        AbbreviationMap<V> onlyChild = entry.getValue();
        value = onlyChild.value;
    }

    private boolean removeAtEndOfKey() {
        if ( key == null )
            return false;

        key = null;
        if ( keysBeyond == 1 )
            setValueToThatOfOnlyChild();
        else
            value = null;

        return true;
    }

    /**
     * Gives a Java map representation of this abbreviation map.
     *
     * @return a Java map corresponding to this abbreviation map
     */
    @Override
    public Map<String, V> toJavaUtilMap() {
        Map<String, V> mappings = new TreeMap<>();
        addToMappings( mappings );
        return mappings;
    }

    private void addToMappings( Map<String, V> mappings ) {
        if ( key != null )
            mappings.put( key, value );

        for ( AbbreviationMap<V> each : children.values() )
            each.addToMappings( mappings );
    }

    private static char[] charsOf( String aKey ) {
        char[] chars = new char[ aKey.length() ];
        aKey.getChars( 0, aKey.length(), chars, 0 );
        return chars;
    }
}