29 * However, the following notice accompanied the original version of this |
29 * However, the following notice accompanied the original version of this |
30 * file: |
30 * file: |
31 * |
31 * |
32 * The MIT License |
32 * The MIT License |
33 * |
33 * |
34 * Copyright (c) 2004-2014 Paul R. Holser, Jr. |
34 * Copyright (c) 2004-2015 Paul R. Holser, Jr. |
35 * |
35 * |
36 * Permission is hereby granted, free of charge, to any person obtaining |
36 * Permission is hereby granted, free of charge, to any person obtaining |
37 * a copy of this software and associated documentation files (the |
37 * a copy of this software and associated documentation files (the |
38 * "Software"), to deal in the Software without restriction, including |
38 * "Software"), to deal in the Software without restriction, including |
39 * without limitation the rights to use, copy, modify, merge, publish, |
39 * without limitation the rights to use, copy, modify, merge, publish, |
82 * |
82 * |
83 * <p>The data structure is much like a "trie".</p> |
83 * <p>The data structure is much like a "trie".</p> |
84 * |
84 * |
85 * @param <V> a constraint on the types of the values in the map |
85 * @param <V> a constraint on the types of the values in the map |
86 * @author <a href="mailto:pholser@alumni.rice.edu">Paul Holser</a> |
86 * @author <a href="mailto:pholser@alumni.rice.edu">Paul Holser</a> |
87 * @see <a href="http://www.perldoc.com/perl5.8.0/lib/Text/Abbrev.html">Perl's Text::Abbrev module</a> |
87 * @see <a href="http://perldoc.perl.org/Text/Abbrev.html">Perl's Text::Abbrev module</a> |
|
88 * @see <a href="https://en.wikipedia.org/wiki/Radix_tree">Radix tree</a> |
88 */ |
89 */ |
89 public class AbbreviationMap<V> { |
90 public class AbbreviationMap<V> implements OptionNameMap<V> { |
|
91 private final Map<Character, AbbreviationMap<V>> children = new TreeMap<>(); |
|
92 |
90 private String key; |
93 private String key; |
91 private V value; |
94 private V value; |
92 private final Map<Character, AbbreviationMap<V>> children = new TreeMap<Character, AbbreviationMap<V>>(); |
|
93 private int keysBeyond; |
95 private int keysBeyond; |
94 |
96 |
95 /** |
97 /** |
96 * <p>Tells whether the given key is in the map, or whether the given key is a unique |
98 * <p>Tells whether the given key is in the map, or whether the given key is a unique |
97 * abbreviation of a key that is in the map.</p> |
99 * abbreviation of a key that is in the map.</p> |
98 * |
100 * |
99 * @param aKey key to look up |
101 * @param key key to look up |
100 * @return {@code true} if {@code key} is present in the map |
102 * @return {@code true} if {@code key} is present in the map |
101 * @throws NullPointerException if {@code key} is {@code null} |
103 * @throws NullPointerException if {@code key} is {@code null} |
102 */ |
104 */ |
103 public boolean contains( String aKey ) { |
105 @Override |
104 return get( aKey ) != null; |
106 public boolean contains(String key) { |
|
107 return get(key) != null; |
105 } |
108 } |
106 |
109 |
107 /** |
110 /** |
108 * <p>Answers the value associated with the given key. The key can be a unique |
111 * <p>Answers the value associated with the given key. The key can be a unique |
109 * abbreviation of a key that is in the map. </p> |
112 * abbreviation of a key that is in the map. </p> |
110 * |
113 * |
111 * @param aKey key to look up |
114 * @param key key to look up |
112 * @return the value associated with {@code aKey}; or {@code null} if there is no |
115 * @return the value associated with {@code aKey}; or {@code null} if there is no |
113 * such value or {@code aKey} is not a unique abbreviation of a key in the map |
116 * such value or {@code aKey} is not a unique abbreviation of a key in the map |
114 * @throws NullPointerException if {@code aKey} is {@code null} |
117 * @throws NullPointerException if {@code aKey} is {@code null} |
115 */ |
118 */ |
116 public V get( String aKey ) { |
119 @Override |
117 char[] chars = charsOf( aKey ); |
120 public V get( String key ) { |
|
121 char[] chars = charsOf( key ); |
118 |
122 |
119 AbbreviationMap<V> child = this; |
123 AbbreviationMap<V> child = this; |
120 for ( char each : chars ) { |
124 for ( char each : chars ) { |
121 child = child.children.get( each ); |
125 child = child.children.get( each ); |
122 if ( child == null ) |
126 if ( child == null ) |
128 |
132 |
129 /** |
133 /** |
130 * <p>Associates a given value with a given key. If there was a previous |
134 * <p>Associates a given value with a given key. If there was a previous |
131 * association, the old value is replaced with the new one.</p> |
135 * association, the old value is replaced with the new one.</p> |
132 * |
136 * |
133 * @param aKey key to create in the map |
137 * @param key key to create in the map |
134 * @param newValue value to associate with the key |
138 * @param newValue value to associate with the key |
135 * @throws NullPointerException if {@code aKey} or {@code newValue} is {@code null} |
139 * @throws NullPointerException if {@code aKey} or {@code newValue} is {@code null} |
136 * @throws IllegalArgumentException if {@code aKey} is a zero-length string |
140 * @throws IllegalArgumentException if {@code aKey} is a zero-length string |
137 */ |
141 */ |
138 public void put( String aKey, V newValue ) { |
142 @Override |
|
143 public void put( String key, V newValue ) { |
139 if ( newValue == null ) |
144 if ( newValue == null ) |
140 throw new NullPointerException(); |
145 throw new NullPointerException(); |
141 if ( aKey.length() == 0 ) |
146 if ( key.length() == 0 ) |
142 throw new IllegalArgumentException(); |
147 throw new IllegalArgumentException(); |
143 |
148 |
144 char[] chars = charsOf( aKey ); |
149 char[] chars = charsOf(key); |
145 add( chars, newValue, 0, chars.length ); |
150 add( chars, newValue, 0, chars.length ); |
146 } |
151 } |
147 |
152 |
148 /** |
153 /** |
149 * <p>Associates a given value with a given set of keys. If there was a previous |
154 * <p>Associates a given value with a given set of keys. If there was a previous |
152 * @param keys keys to create in the map |
157 * @param keys keys to create in the map |
153 * @param newValue value to associate with the key |
158 * @param newValue value to associate with the key |
154 * @throws NullPointerException if {@code keys} or {@code newValue} is {@code null} |
159 * @throws NullPointerException if {@code keys} or {@code newValue} is {@code null} |
155 * @throws IllegalArgumentException if any of {@code keys} is a zero-length string |
160 * @throws IllegalArgumentException if any of {@code keys} is a zero-length string |
156 */ |
161 */ |
|
162 @Override |
157 public void putAll( Iterable<String> keys, V newValue ) { |
163 public void putAll( Iterable<String> keys, V newValue ) { |
158 for ( String each : keys ) |
164 for ( String each : keys ) |
159 put( each, newValue ); |
165 put( each, newValue ); |
160 } |
166 } |
161 |
167 |
168 } |
174 } |
169 |
175 |
170 char nextChar = chars[ offset ]; |
176 char nextChar = chars[ offset ]; |
171 AbbreviationMap<V> child = children.get( nextChar ); |
177 AbbreviationMap<V> child = children.get( nextChar ); |
172 if ( child == null ) { |
178 if ( child == null ) { |
173 child = new AbbreviationMap<V>(); |
179 child = new AbbreviationMap<>(); |
174 children.put( nextChar, child ); |
180 children.put( nextChar, child ); |
175 } |
181 } |
176 |
182 |
177 boolean newKeyAdded = child.add( chars, newValue, offset + 1, length ); |
183 boolean newKeyAdded = child.add( chars, newValue, offset + 1, length ); |
178 |
184 |
186 } |
192 } |
187 |
193 |
188 /** |
194 /** |
189 * <p>If the map contains the given key, dissociates the key from its value.</p> |
195 * <p>If the map contains the given key, dissociates the key from its value.</p> |
190 * |
196 * |
191 * @param aKey key to remove |
197 * @param key key to remove |
192 * @throws NullPointerException if {@code aKey} is {@code null} |
198 * @throws NullPointerException if {@code aKey} is {@code null} |
193 * @throws IllegalArgumentException if {@code aKey} is a zero-length string |
199 * @throws IllegalArgumentException if {@code aKey} is a zero-length string |
194 */ |
200 */ |
195 public void remove( String aKey ) { |
201 @Override |
196 if ( aKey.length() == 0 ) |
202 public void remove( String key ) { |
|
203 if ( key.length() == 0 ) |
197 throw new IllegalArgumentException(); |
204 throw new IllegalArgumentException(); |
198 |
205 |
199 char[] keyChars = charsOf( aKey ); |
206 char[] keyChars = charsOf(key); |
200 remove( keyChars, 0, keyChars.length ); |
207 remove( keyChars, 0, keyChars.length ); |
201 } |
208 } |
202 |
209 |
203 private boolean remove( char[] aKey, int offset, int length ) { |
210 private boolean remove( char[] aKey, int offset, int length ) { |
204 if ( offset == length ) |
211 if ( offset == length ) |
240 /** |
247 /** |
241 * Gives a Java map representation of this abbreviation map. |
248 * Gives a Java map representation of this abbreviation map. |
242 * |
249 * |
243 * @return a Java map corresponding to this abbreviation map |
250 * @return a Java map corresponding to this abbreviation map |
244 */ |
251 */ |
|
252 @Override |
245 public Map<String, V> toJavaUtilMap() { |
253 public Map<String, V> toJavaUtilMap() { |
246 Map<String, V> mappings = new TreeMap<String, V>(); |
254 Map<String, V> mappings = new TreeMap<>(); |
247 addToMappings( mappings ); |
255 addToMappings( mappings ); |
248 return mappings; |
256 return mappings; |
249 } |
257 } |
250 |
258 |
251 private void addToMappings( Map<String, V> mappings ) { |
259 private void addToMappings( Map<String, V> mappings ) { |