001: /*
002: Copyright 2004-2007 Paul R. Holser, Jr. All rights reserved.
003: Licensed under the Academic Free License version 3.0
004: */
005:
006: package joptsimple;
007:
008: import java.util.Iterator;
009: import java.util.Map;
010: import java.util.TreeMap;
011:
012: /**
013: * <p>A map whose keys are strings; when a key/value pair is added to the map,
014: * the longest unique abbreviations of that key are added as well, and associated with
015: * the value. Thus:</p>
016: * <pre>
017: * abbreviations.put( "good", "bye" );
018: * </pre>
019: * <p>would make it such that you could retrieve the value <code>"bye"</code> from the
020: * map with the keys <code>"good"</code>, <code>"goo"</code>, <code>"go"</code>, and
021: * <code>"g"</code>. A subsequent invocation of:
022: * <pre>
023: * abbreviations.put( "go", "fish" );
024: * </pre>
025: * would make it such that you could retrieve the value <code>"bye"</code> using the keys
026: * <code>"good"</code> and <code>"goo"</code>, and the value <code>"fish"</code> with the
027: * key <code>"go"</code>. The key <code>"g"</code> would yield <code>null</code>, since
028: * it would no longer be a unique abbreviation.</p>
029: * <p>The data structure is much like a "trie".</p>
030: *
031: * @since 1.0
032: * @author <a href="mailto:pholser@alumni.rice.edu">Paul Holser</a>
033: * @version $Id: AbbreviationMap.java,v 1.24 2007/04/21 22:25:14 pholser Exp $
034: * @see <a href="http://www.perldoc.com/perl5.8.0/lib/Text/Abbrev.html"> Perl's
035: * Text::Abbrev module</a>
036: */
037: class AbbreviationMap {
038: private String key;
039: private Object value;
040: private final Map children = new TreeMap();
041: private int keysBeyond;
042:
043: /**
044: * Tells whether the given key is in the map, or whether the given key is a unique
045: * abbreviation of a key that is in the map.
046: *
047: * @param aKey key to look up
048: * @return {@code true} if {@code key} is present in the map
049: * @throws NullPointerException if {@code key} is {@code null}
050: */
051: boolean contains(String aKey) {
052: return get(aKey) != null;
053: }
054:
055: /**
056: * Answers the value associated with the given key. The key can be a unique
057: * abbreviation of a key that is in the map.
058: *
059: * @param aKey key to look up
060: * @return the value associated with {@code key}; or {@code null} if there is no
061: * such value or {@code key} is not a unique abbreviation of a key in the map
062: * @throws NullPointerException if {@code key} is {@code null}
063: */
064: Object get(String aKey) {
065: char[] chars = charsOf(aKey);
066:
067: AbbreviationMap child = this ;
068: for (int i = 0; i < chars.length; ++i) {
069: child = (AbbreviationMap) child.children.get(new Character(
070: chars[i]));
071: if (child == null)
072: return null;
073: }
074:
075: return child.value;
076: }
077:
078: /**
079: * Associates a given value with a given key. If there was a previous association,
080: * the old value is replaced with the new one.
081: *
082: * @param aKey key to create in the map
083: * @param newValue value to associate with the key
084: * @throws NullPointerException if {@code key} or {@code newValue} is {@code null}
085: * @throws IllegalArgumentException if {@code key} is a zero-length string
086: * TODO: make zero-length keys legal.
087: */
088: void put(String aKey, Object newValue) {
089: if (newValue == null)
090: throw new NullPointerException();
091: if (aKey.length() == 0)
092: throw new IllegalArgumentException();
093:
094: char[] chars = charsOf(aKey);
095: add(chars, newValue, 0, chars.length);
096: }
097:
098: private boolean add(char[] chars, Object newValue, int offset,
099: int length) {
100: if (offset == length) {
101: value = newValue;
102: boolean wasAlreadyAKey = key != null;
103: key = new String(chars);
104: return !wasAlreadyAKey;
105: }
106:
107: Character nextChar = new Character(chars[offset]);
108: AbbreviationMap child = (AbbreviationMap) children
109: .get(nextChar);
110: if (child == null) {
111: child = new AbbreviationMap();
112: children.put(nextChar, child);
113: }
114:
115: boolean newKeyAdded = child.add(chars, newValue, offset + 1,
116: length);
117:
118: if (newKeyAdded)
119: ++keysBeyond;
120:
121: if (key == null)
122: value = keysBeyond > 1 ? null : newValue;
123:
124: return newKeyAdded;
125: }
126:
127: /**
128: * If the map contains the given key, dissociates the key from its value; otherwise,
129: * does nothing.
130: *
131: * @param aKey key to remove
132: * @throws NullPointerException if {@code key} is {@code null}
133: * @throws IllegalArgumentException if {@code key} is a zero-length string
134: */
135: void remove(String aKey) {
136: if (aKey.length() == 0)
137: throw new IllegalArgumentException();
138:
139: char[] chars = charsOf(aKey);
140: remove(chars, 0, chars.length);
141: }
142:
143: private boolean remove(char[] chars, int offset, int length) {
144: if (offset == length) {
145: if (key == null)
146: return false;
147:
148: key = null;
149: if (keysBeyond == 1) {
150: Map.Entry entry = (Map.Entry) children.entrySet()
151: .iterator().next();
152: AbbreviationMap onlyChild = (AbbreviationMap) entry
153: .getValue();
154: value = onlyChild.value;
155: } else
156: value = null;
157:
158: return true;
159: }
160:
161: Character nextChar = new Character(chars[offset]);
162: AbbreviationMap child = (AbbreviationMap) children
163: .get(nextChar);
164: if (child == null)
165: return false;
166: if (!child.remove(chars, offset + 1, length))
167: return false;
168:
169: --keysBeyond;
170: if (child.keysBeyond == 0)
171: children.remove(nextChar);
172: if (keysBeyond == 1 && key == null) {
173: Map.Entry entry = (Map.Entry) children.entrySet()
174: .iterator().next();
175: AbbreviationMap onlyChild = (AbbreviationMap) entry
176: .getValue();
177: value = onlyChild.value;
178: }
179:
180: return true;
181: }
182:
183: Map toJavaUtilMap() {
184: Map mappings = new TreeMap();
185: addToMappings(mappings);
186: return mappings;
187: }
188:
189: private void addToMappings(Map mappings) {
190: if (key != null)
191: mappings.put(key, value);
192:
193: for (Iterator it = children.values().iterator(); it.hasNext();)
194: ((AbbreviationMap) it.next()).addToMappings(mappings);
195: }
196:
197: private static char[] charsOf(String aKey) {
198: char[] chars = new char[aKey.length()];
199: aKey.getChars(0, aKey.length(), chars, 0);
200: return chars;
201: }
202: }
|