/*
 Copyright 2004-2008 Paul R. Holser, Jr.  All rights reserved.
 Licensed under the Academic Free License version 3.0
 */

package joptsimple;

import java.util.Iterator;
import java.util.List;
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"</code> from the
 * map with the keys <code>"good"</code>, <code>"goo"</code>, <code>"go"</code>, and
 * <code>"g"</code>.  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"</code> using the
 * keys <code>"good"</code> and <code>"goo"</code>, and the value <code>"fish"</code>
 * with the key <code>"go"</code>.  The key <code>"g"</code> would yield
 * <code>null</code>, since it would no longer be a unique abbreviation.</p>
 *
 * <p>The data structure is much like a "trie".</p>
 *
 * @since 1.0
 * @author <a href="mailto:pholser@alumni.rice.edu">Paul Holser</a>
 * @version $Id: AbbreviationMap.java,v 1.3 2008/04/10 19:41:55 pholser Exp $
 * @see <a href="http://www.perldoc.com/perl5.8.0/lib/Text/Abbrev.html"> Perl's
 * Text::Abbrev module</a>
 */
class AbbreviationMap {
    private String key;
    private Object value;
    private final Map children = new TreeMap();
    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 aKey key to look up
     * @return {@code true} if {@code key} is present in the map
     * @throws NullPointerException if {@code key} is {@code null}
     */
    boolean contains( String aKey ) {
        return get( aKey ) != 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 aKey key to look up
     * @return the value associated with <var>aKey</var>; or <code>null</code> if there
     * is no such value or <var>aKey</var> is not a unique abbreviation of a key in the
     * map
     * @throws NullPointerException if <var>aKey</var> is <code>null</code>
     */
    Object get( String aKey ) {
        char[] chars = charsOf( aKey );

        AbbreviationMap child = this;
        for ( int i = 0; i < chars.length; ++i ) {
            child = (AbbreviationMap) child.children.get( new Character( chars[ i ] ) );
            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 aKey key to create in the map
     * @param newValue value to associate with the key
     * @throws NullPointerException if <var>aKey</var> or <var>newValue</var> is
     * <code>null</code>
     * @throws IllegalArgumentException if <var>aKey</var> is a zero-length string
     */
    void put( String aKey, Object newValue ) {
        if ( newValue == null )
            throw new NullPointerException();
        if ( aKey.length() == 0 )
            throw new IllegalArgumentException();

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

    void putAll( List keys, Object newValue ) {
        for ( Iterator iter = keys.iterator(); iter.hasNext(); )
            put( (String) iter.next(), newValue );
    }

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

        Character nextChar = new Character( chars[ offset ] );
        AbbreviationMap child = (AbbreviationMap) 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 aKey key to remove
     * @throws NullPointerException if <var>aKey</var> is <code>null</code>
     * @throws IllegalArgumentException if <var>aKey</var> is a zero-length string
     */
    void remove( String aKey ) {
        if ( aKey.length() == 0 )
            throw new IllegalArgumentException();

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

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

        Character nextChar = new Character( aKey[ offset ] );
        AbbreviationMap child = (AbbreviationMap) 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 ) {
            Map.Entry entry = (Map.Entry) children.entrySet().iterator().next();
            AbbreviationMap onlyChild = (AbbreviationMap) entry.getValue();
            value = onlyChild.value;
        }

        return true;
    }

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

        key = null;
        if ( keysBeyond == 1 ) {
            Map.Entry entry = (Map.Entry) children.entrySet().iterator().next();
            AbbreviationMap onlyChild = (AbbreviationMap) entry.getValue();
            value = onlyChild.value;
        }
        else
            value = null;

        return true;
    }

    Map toJavaUtilMap() {
        Map mappings = new TreeMap();
        addToMappings( mappings );
        return mappings;
    }

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

        for ( Iterator iter = children.values().iterator(); iter.hasNext(); )
            ( (AbbreviationMap) iter.next() ).addToMappings( mappings );
    }

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