/*

 * 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

 *

 *

 * 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;

/**

 * <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>

 */

    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>

     *

     * @return {@code true} if {@code key} is present in the map

     * @throws NullPointerException if {@code key} is {@code 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>

     *

     * @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}

     */

        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 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

     */

        if ( newValue == null )

            throw new NullPointerException();

            throw new IllegalArgumentException();

        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

     */

    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 ) {

            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>

     *

     * @throws NullPointerException if {@code aKey} is {@code null}

     * @throws IllegalArgumentException if {@code aKey} is a zero-length string

     */

            throw new IllegalArgumentException();

        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

     */

    public Map<String, V> toJavaUtilMap() {

        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;

    }

}