Coverage Report - joptsimple.internal.AbbreviationMap
 
Classes in this File Line Coverage Branch Coverage Complexity
AbbreviationMap
100%
75/75
100%
48/48
3.417
 
 1  
 /*
 2  
  The MIT License
 3  
 
 4  
  Copyright (c) 2004-2015 Paul R. Holser, Jr.
 5  
 
 6  
  Permission is hereby granted, free of charge, to any person obtaining
 7  
  a copy of this software and associated documentation files (the
 8  
  "Software"), to deal in the Software without restriction, including
 9  
  without limitation the rights to use, copy, modify, merge, publish,
 10  
  distribute, sublicense, and/or sell copies of the Software, and to
 11  
  permit persons to whom the Software is furnished to do so, subject to
 12  
  the following conditions:
 13  
 
 14  
  The above copyright notice and this permission notice shall be
 15  
  included in all copies or substantial portions of the Software.
 16  
 
 17  
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 18  
  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 19  
  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 20  
  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 21  
  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 22  
  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 23  
  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 24  
 */
 25  
 
 26  
 package joptsimple.internal;
 27  
 
 28  
 import java.util.Map;
 29  
 import java.util.TreeMap;
 30  
 
 31  
 /**
 32  
  * <p>A map whose keys are strings; when a key/value pair is added to the map, the longest unique abbreviations of that
 33  
  * key are added as well, and associated with the value. Thus:</p>
 34  
  *
 35  
  * <pre>
 36  
  *   <code>
 37  
  *   abbreviations.put( "good", "bye" );
 38  
  *   </code>
 39  
  * </pre>
 40  
  *
 41  
  * <p>would make it such that you could retrieve the value {@code "bye"} from the map using the keys {@code "good"},
 42  
  * {@code "goo"}, {@code "go"}, and {@code "g"}. A subsequent invocation of:</p>
 43  
  * <pre>
 44  
  *   <code>
 45  
  *   abbreviations.put( "go", "fish" );
 46  
  *   </code>
 47  
  * </pre>
 48  
  *
 49  
  * <p>would make it such that you could retrieve the value {@code "bye"} using the keys {@code "good"} and
 50  
  * {@code "goo"}, and the value {@code "fish"} using the key {@code "go"}.  The key {@code "g"} would yield
 51  
  * {@code null}, since it would no longer be a unique abbreviation.</p>
 52  
  *
 53  
  * <p>The data structure is much like a "trie".</p>
 54  
  *
 55  
  * @param <V> a constraint on the types of the values in the map
 56  
  * @author <a href="mailto:pholser@alumni.rice.edu">Paul Holser</a>
 57  
  * @see <a href="http://perldoc.perl.org/Text/Abbrev.html">Perl's Text::Abbrev module</a>
 58  
  * @see <a href="https://en.wikipedia.org/wiki/Radix_tree">Radix tree</a>
 59  
  */
 60  7436
 public class AbbreviationMap<V> {
 61  
     private String key;
 62  
     private V value;
 63  7436
     private final Map<Character, AbbreviationMap<V>> children = new TreeMap<Character, AbbreviationMap<V>>();
 64  
     private int keysBeyond;
 65  
 
 66  
     /**
 67  
      * <p>Tells whether the given key is in the map, or whether the given key is a unique
 68  
      * abbreviation of a key that is in the map.</p>
 69  
      *
 70  
      * @param aKey key to look up
 71  
      * @return {@code true} if {@code key} is present in the map
 72  
      * @throws NullPointerException if {@code key} is {@code null}
 73  
      */
 74  
     public boolean contains( String aKey ) {
 75  590
         return get( aKey ) != null;
 76  
     }
 77  
 
 78  
     /**
 79  
      * <p>Answers the value associated with the given key.  The key can be a unique
 80  
      * abbreviation of a key that is in the map. </p>
 81  
      *
 82  
      * @param aKey key to look up
 83  
      * @return the value associated with {@code aKey}; or {@code null} if there is no
 84  
      * such value or {@code aKey} is not a unique abbreviation of a key in the map
 85  
      * @throws NullPointerException if {@code aKey} is {@code null}
 86  
      */
 87  
     public V get( String aKey ) {
 88  1712
         char[] chars = charsOf( aKey );
 89  
 
 90  1711
         AbbreviationMap<V> child = this;
 91  9576
         for ( char each : chars ) {
 92  7947
             child = child.children.get( each );
 93  7947
             if ( child == null )
 94  82
                 return null;
 95  
         }
 96  
 
 97  1629
         return child.value;
 98  
     }
 99  
 
 100  
     /**
 101  
      * <p>Associates a given value with a given key.  If there was a previous
 102  
      * association, the old value is replaced with the new one.</p>
 103  
      *
 104  
      * @param aKey key to create in the map
 105  
      * @param newValue value to associate with the key
 106  
      * @throws NullPointerException if {@code aKey} or {@code newValue} is {@code null}
 107  
      * @throws IllegalArgumentException if {@code aKey} is a zero-length string
 108  
      */
 109  
     public void put( String aKey, V newValue ) {
 110  1797
         if ( newValue == null )
 111  1
             throw new NullPointerException();
 112  1796
         if ( aKey.length() == 0 )
 113  1
             throw new IllegalArgumentException();
 114  
 
 115  1794
         char[] chars = charsOf( aKey );
 116  1794
         add( chars, newValue, 0, chars.length );
 117  1794
     }
 118  
 
 119  
     /**
 120  
      * <p>Associates a given value with a given set of keys.  If there was a previous
 121  
      * association, the old value is replaced with the new one.</p>
 122  
      *
 123  
      * @param keys keys to create in the map
 124  
      * @param newValue value to associate with the key
 125  
      * @throws NullPointerException if {@code keys} or {@code newValue} is {@code null}
 126  
      * @throws IllegalArgumentException if any of {@code keys} is a zero-length string
 127  
      */
 128  
     public void putAll( Iterable<String> keys, V newValue ) {
 129  1516
         for ( String each : keys )
 130  1729
             put( each, newValue );
 131  1516
     }
 132  
 
 133  
     private boolean add( char[] chars, V newValue, int offset, int length ) {
 134  10868
         if ( offset == length ) {
 135  1794
             value = newValue;
 136  1794
             boolean wasAlreadyAKey = key != null;
 137  1794
             key = new String( chars );
 138  1794
             return !wasAlreadyAKey;
 139  
         }
 140  
 
 141  9074
         char nextChar = chars[ offset ];
 142  9074
         AbbreviationMap<V> child = children.get( nextChar );
 143  9074
         if ( child == null ) {
 144  7021
             child = new AbbreviationMap<V>();
 145  7021
             children.put( nextChar, child );
 146  
         }
 147  
 
 148  9074
         boolean newKeyAdded = child.add( chars, newValue, offset + 1, length );
 149  
 
 150  9074
         if ( newKeyAdded )
 151  7322
             ++keysBeyond;
 152  
 
 153  9074
         if ( key == null )
 154  8977
             value = keysBeyond > 1 ? null : newValue;
 155  
 
 156  9074
         return newKeyAdded;
 157  
     }
 158  
 
 159  
     /**
 160  
      * <p>If the map contains the given key, dissociates the key from its value.</p>
 161  
      *
 162  
      * @param aKey key to remove
 163  
      * @throws NullPointerException if {@code aKey} is {@code null}
 164  
      * @throws IllegalArgumentException if {@code aKey} is a zero-length string
 165  
      */
 166  
     public void remove( String aKey ) {
 167  12
         if ( aKey.length() == 0 )
 168  1
             throw new IllegalArgumentException();
 169  
 
 170  10
         char[] keyChars = charsOf( aKey );
 171  10
         remove( keyChars, 0, keyChars.length );
 172  10
     }
 173  
 
 174  
     private boolean remove( char[] aKey, int offset, int length ) {
 175  39
         if ( offset == length )
 176  8
             return removeAtEndOfKey();
 177  
 
 178  31
         char nextChar = aKey[ offset ];
 179  31
         AbbreviationMap<V> child = children.get( nextChar );
 180  31
         if ( child == null || !child.remove( aKey, offset + 1, length ) )
 181  7
             return false;
 182  
 
 183  24
         --keysBeyond;
 184  24
         if ( child.keysBeyond == 0 )
 185  6
             children.remove( nextChar );
 186  24
         if ( keysBeyond == 1 && key == null )
 187  6
             setValueToThatOfOnlyChild();
 188  
 
 189  24
         return true;
 190  
     }
 191  
 
 192  
     private void setValueToThatOfOnlyChild() {
 193  8
         Map.Entry<Character, AbbreviationMap<V>> entry = children.entrySet().iterator().next();
 194  8
         AbbreviationMap<V> onlyChild = entry.getValue();
 195  8
         value = onlyChild.value;
 196  8
     }
 197  
 
 198  
     private boolean removeAtEndOfKey() {
 199  8
         if ( key == null )
 200  2
             return false;
 201  
 
 202  6
         key = null;
 203  6
         if ( keysBeyond == 1 )
 204  2
             setValueToThatOfOnlyChild();
 205  
         else
 206  4
             value = null;
 207  
 
 208  6
         return true;
 209  
     }
 210  
 
 211  
     /**
 212  
      * Gives a Java map representation of this abbreviation map.
 213  
      *
 214  
      * @return a Java map corresponding to this abbreviation map
 215  
      */
 216  
     public Map<String, V> toJavaUtilMap() {
 217  775
         Map<String, V> mappings = new TreeMap<String, V>();
 218  775
         addToMappings( mappings );
 219  775
         return mappings;
 220  
     }
 221  
 
 222  
     private void addToMappings( Map<String, V> mappings ) {
 223  14534
         if ( key != null )
 224  2784
             mappings.put( key, value );
 225  
 
 226  14534
         for ( AbbreviationMap<V> each : children.values() )
 227  13759
             each.addToMappings( mappings );
 228  14534
     }
 229  
 
 230  
     private static char[] charsOf( String aKey ) {
 231  3516
         char[] chars = new char[ aKey.length() ];
 232  3515
         aKey.getChars( 0, aKey.length(), chars, 0 );
 233  3515
         return chars;
 234  
     }
 235  
 }