/*
 * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

/*
 * This file is available under and governed by the GNU General Public
 * License version 2 only, as published by the Free Software Foundation.
 * However, the following notice accompanied the original version of this
 * file:
 *
 * 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 jdk.internal.joptsimple.internal;

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

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:
  
  abbreviations.put( "good", "bye" );
  

would make it such that you could retrieve the value "bye" from the map using the keys "good", "goo", "go", and "g". A subsequent invocation of:
  
  abbreviations.put( "go", "fish" );
  

would make it such that you could retrieve the value "bye" using the keys "good" and "goo", and the value "fish" using the key "go". The key "g" would yield null, since it would no longer be a unique abbreviation.
The data structure is much like a "trie".
Author:
Paul Holser
Type parameters:
<V> – a constraint on the types of the values in the map
See Also:
Perl's Text::Abbrev module
Radix tree/**
 * <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;

    
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.
Params:
key – key to look up
Throws:
NullPointerException – if key is null
Returns:
true if key is present in the map/**
     * <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;
    }

    
Answers the value associated with the given key.  The key can be a unique
abbreviation of a key that is in the map. 
Params:
key – key to look up
Throws:
NullPointerException – if aKey is null
Returns:
the value associated with aKey; or null if there is no such value or aKey is not a unique abbreviation of a key in the map/**
     * <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;
    }

    
Associates a given value with a given key.  If there was a previous
association, the old value is replaced with the new one.
Params:
key – key to create in the map
newValue – value to associate with the key
Throws:
NullPointerException – if aKey or newValue is null
IllegalArgumentException – if aKey is a zero-length string/**
     * <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 );
    }

    
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.
Params:
keys – keys to create in the map
newValue – value to associate with the key
Throws:
NullPointerException – if keys or newValue is null
IllegalArgumentException – if any of keys is a zero-length string/**
     * <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;
    }

    
If the map contains the given key, dissociates the key from its value.
Params:
key – key to remove
Throws:
NullPointerException – if aKey is null
IllegalArgumentException – if aKey is a zero-length string/**
     * <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.
Returns:
a Java map corresponding to this abbreviation map/**
     * 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;
    }
}