/*

  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.4 2008/05/23 15:02:43 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 )

             setValueToThatOfOnlyChild();

         return true;

     }

     private void setValueToThatOfOnlyChild() {

         Map.Entry entry = (Map.Entry) children.entrySet().iterator().next();

         AbbreviationMap onlyChild = (AbbreviationMap) entry.getValue();

         value = onlyChild.value;

     }

     private boolean removeAtEndOfKey() {

         if ( key == null )

             return false;

         key = null;

         if ( keysBeyond == 1 )

             setValueToThatOfOnlyChild();

         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;

     }

 }