001: /*****************************************************************************
002: * Source code information
003: * -----------------------
004: * Original author Ian Dickinson, HP Labs Bristol
005: * Author email Ian.Dickinson@hp.com
006: * Package Jena
007: * Created 5 Jan 2001
008: * Filename $RCSfile: OneToManyMap.java,v $
009: * Revision $Revision: 1.15 $
010: * Release status Preview-release $State: Exp $
011: *
012: * Last modified on $Date: 2008/01/02 12:07:44 $
013: * by $Author: andy_seaborne $
014: *
015: * (c) Copyright 2001, 2002, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
016: * See end of file for details
017: *****************************************************************************/package com.hp.hpl.jena.util;
018:
019: // Imports
020: ///////////////
021: import java.util.*;
022:
023: import com.hp.hpl.jena.util.iterator.NullIterator;
024:
025: /**
026: * An extension to a standard map that supports one-to-many mappings: that is, there
027: * may be zero, one or many values corresponding to a given key.
028: *
029: * @author Ian Dickinson, HP Labs (<a href="mailto:Ian.Dickinson@hp.com">email</a>)
030: * @version CVS info: $Id: OneToManyMap.java,v 1.15 2008/01/02 12:07:44 andy_seaborne Exp $
031: */
032: public class OneToManyMap implements Map {
033: // Constants
034: //////////////////////////////////
035:
036: // Static variables
037: //////////////////////////////////
038:
039: // Instance variables
040: //////////////////////////////////
041:
042: /** Encapsulated hash table stores the values */
043: private Map m_table = new HashMap();
044:
045: // Constructors
046: //////////////////////////////////
047:
048: /**
049: * <p>Construct a new empty one-to-many map</p>
050: */
051: public OneToManyMap() {
052: }
053:
054: /**
055: * <p>Construct a new one-to-many map whose contents are
056: * initialised from the existing map.</p>
057: *
058: * @param map An existing one-to-many map
059: */
060: public OneToManyMap(OneToManyMap map) {
061: // copy the contents of the existing map
062: // note we can't just use the copying constructor for hashmap
063: // as we don't want to share the arraylists that are the key values
064: for (Iterator i = map.keySet().iterator(); i.hasNext();) {
065: Object key = i.next();
066:
067: for (Iterator j = map.getAll(key); j.hasNext();) {
068: put(key, j.next());
069: }
070: }
071: }
072:
073: // External signature methods
074: //////////////////////////////////
075:
076: /**
077: * Clear all entries from the map.
078: */
079: public void clear() {
080: m_table.clear();
081: }
082:
083: /**
084: * Answer true if the map contains the given value as a key.
085: *
086: * @param key The key object to test for
087: * @return True or false
088: */
089: public boolean containsKey(Object key) {
090: return m_table.containsKey(key);
091: }
092:
093: /**
094: * Answer true if the map contains the given object as a value
095: * stored against any key. Note that this is quite an expensive
096: * operation in the current implementation.
097: *
098: * @param value The value to test for
099: * @return True if the value is in the map
100: */
101: public boolean containsValue(Object value) {
102: for (Iterator values = m_table.values().iterator(); values
103: .hasNext();) {
104: Object x = values.next();
105:
106: if (x.equals(value)) {
107: return true;
108: } else if (x instanceof List && ((List) x).contains(value)) {
109: return true;
110: }
111: }
112:
113: return false;
114: }
115:
116: /**
117: * <p>Answer true if this mapping contains the pair
118: * <code>(key, value)</code>.</p>
119: * @param key A key object
120: * @param value A value object
121: * @return True if <code>key</code> has <code>value</code>
122: * as one of its values in this mapping
123: */
124: public boolean contains(Object key, Object value) {
125: for (Iterator i = getAll(key); i.hasNext();) {
126: if (i.next().equals(value)) {
127: return true;
128: }
129: }
130: return false;
131: }
132:
133: /**
134: * Answer a set of the mappings in this map. Each member of the set will
135: * be a Map.Entry value.
136: *
137: * @return A Set of the mappings as Map.Entry values.
138: */
139: public Set entrySet() {
140: Set s = CollectionFactory.createHashedSet();
141:
142: for (Iterator e0 = m_table.keySet().iterator(); e0.hasNext();) {
143: Object key = e0.next();
144: List values = (List) m_table.get(key);
145:
146: // add each key-value pair to the result set
147: for (ListIterator e1 = values.listIterator(); e1.hasNext();) {
148: s.add(new Entry(key, e1.next()));
149: }
150: }
151:
152: return s;
153: }
154:
155: /**
156: * Compares the specified object with this map for equality.
157: * Returns true if the given object is also a map and the two Maps
158: * represent the same mappings. More formally, two maps t1 and t2 represent
159: * the same mappings if t1.entrySet().equals(t2.entrySet()).
160: *
161: * This ensures that the equals method works properly across different
162: * implementations of the Map interface.
163: *
164: * @param o The object to be compared for equality with this map.
165: * @return True if the specified object is equal to this map.
166: */
167: public boolean equals(Object o) {
168: if (o instanceof java.util.Map) {
169: return entrySet().equals(((Map) o).entrySet());
170: } else
171: return false;
172: }
173:
174: /**
175: * Get a value for this key. Since this map is explicitly designed to
176: * allow there to be more than one mapping per key, this method will return
177: * an undetermined instance of the mapping. If no mapping exists, or the
178: * selected value is null, null is returned.
179: *
180: * @param key The key to access the map.
181: * @return One of the values this key corresponds to, or null.
182: * @see #getAll
183: */
184: public Object get(Object key) {
185: ArrayList entry = (ArrayList) m_table.get(key);
186:
187: if (entry != null) {
188: if (!entry.isEmpty()) {
189: return entry.get(0);
190: }
191: }
192:
193: // not present
194: return null;
195: }
196:
197: /**
198: * Answer an iterator over all of the values for the given key. An iterator
199: * is always supplied, even if the key is not present.
200: *
201: * @param key The key object
202: * @return An iterator over all of the values for this key in the map
203: */
204: public Iterator getAll(Object key) {
205: ArrayList entry = (ArrayList) m_table.get(key);
206: return (entry != null) ? entry.iterator()
207: : NullIterator.instance;
208: }
209:
210: /**
211: * Returns the hash code value for this map. The hash code of a map is
212: * defined to be the sum of the hashCodes of each entry in the map's
213: * entrySet view. This ensures that t1.equals(t2) implies
214: * that t1.hashCode()==t2.hashCode() for any two maps t1 and t2,
215: * as required by the general contract of Object.hashCode
216: */
217: public int hashCode() {
218: int hc = 0;
219:
220: for (Iterator i = entrySet().iterator(); i.hasNext();) {
221: hc ^= i.next().hashCode();
222: }
223:
224: return hc;
225: }
226:
227: /**
228: * Answer true if the map is empty of key-value mappings.
229: *
230: * @return True if there are no entries.
231: */
232: public boolean isEmpty() {
233: return m_table.isEmpty();
234: }
235:
236: /**
237: * Answer a set of the keys in this map
238: *
239: * @return The keys of the map as a Set
240: */
241: public Set keySet() {
242: return m_table.keySet();
243: }
244:
245: /**
246: * Associates the given value with the given key. Since this map formulation
247: * allows many values for one key, previous associations with the key are not
248: * lost. Consequently, the method always returns null (since the replaced value
249: * is not defined).
250: *
251: * @param key The key object
252: * @param value The value object
253: * @return Null.
254: */
255: public Object put(Object key, Object value) {
256: ArrayList entries = (ArrayList) m_table.get(key);
257: entries = entries == null ? new ArrayList() : entries;
258:
259: // add the new value to the list of values held against this key
260: entries.add(value);
261: m_table.put(key, entries);
262:
263: return null;
264: }
265:
266: /**
267: * <p>Put all entries from one map into this map. Tests for m being a
268: * OneToManyMap, and, if so, copies all of the entries for each key.</p>
269: * @param m The map whose contents are to be copied into this map
270: */
271: public void putAll(Map m) {
272: boolean many = (m instanceof OneToManyMap);
273:
274: for (Iterator i = m.keySet().iterator(); i.hasNext();) {
275: Object key = i.next();
276: if (many) {
277: for (Iterator j = ((OneToManyMap) m).getAll(key); j
278: .hasNext();) {
279: put(key, j.next());
280: }
281: } else {
282: put(key, m.get(key));
283: }
284: }
285: }
286:
287: /**
288: * Remove all of the associations for the given key. If only a specific
289: * association is to be removed, use {@link #remove( java.lang.Object, java.lang.Object )}
290: * instead. Has no effect if the key is not present in the map. Since no
291: * single specific association with the key is defined, this method always
292: * returns null.
293: *
294: * @param key All associations with this key will be removed
295: * @return null
296: */
297: public Object remove(Object key) {
298: m_table.remove(key);
299: return null;
300: }
301:
302: /**
303: * <p>Remove the specific association between the given key and value. Has
304: * no effect if the association is not present in the map. If all values
305: * for a particular key have been removed post removing this particular
306: * association, the key will no longer appear as a key in the map.</p>
307: *
308: * @param key The key object
309: * @param value The value object
310: */
311: public void remove(Object key, Object value) {
312: List entries = (List) m_table.get(key);
313:
314: if (entries != null) {
315: entries.remove(value);
316:
317: if (entries.isEmpty()) {
318: m_table.remove(key);
319: }
320: }
321: }
322:
323: /**
324: * <p>Answer the number of key-value mappings in the map</p>
325: * @return The number of key-value pairs.
326: */
327: public int size() {
328: int size = 0;
329:
330: for (Iterator i = m_table.keySet().iterator(); i.hasNext();) {
331: size += ((List) m_table.get(i.next())).size();
332: }
333:
334: return size;
335: }
336:
337: /**
338: * <p>Returns a collection view of the values contained in this map.
339: * Specifically, this will be a set, so duplicate values that appear
340: * for multiple keys are suppressed.</p>
341: * @return A set of the values contained in this map.
342: */
343: public Collection values() {
344: Set s = CollectionFactory.createHashedSet();
345:
346: for (Iterator e = m_table.keySet().iterator(); e.hasNext();) {
347: s.addAll((List) m_table.get(e.next()));
348: }
349:
350: return s;
351: }
352:
353: /**
354: * <p>Answer a string representation of this map. This can be quite a long string for
355: * large maps.<p>
356: */
357: public String toString() {
358: StringBuffer buf = new StringBuffer("OneToManyMap{");
359: String sep = "";
360:
361: for (Iterator i = keySet().iterator(); i.hasNext();) {
362: Object key = i.next();
363: buf.append(sep);
364: buf.append(key);
365: buf.append("={");
366:
367: String sep1 = "";
368: for (Iterator j = getAll(key); j.hasNext();) {
369: buf.append(sep1);
370: buf.append(j.next());
371: sep1 = ",";
372: }
373: buf.append("}");
374: sep = ",";
375: }
376: buf.append("}");
377: return buf.toString();
378: }
379:
380: // Internal implementation methods
381: //////////////////////////////////////
382:
383: // Inner classes
384: //////////////////////////////////////
385:
386: //////////////////////////////////
387:
388: //==============================================================================
389: // Inner class definitions
390: //==============================================================================
391:
392: /**
393: * Helper class to implement the Map.Entry interface to enumerate entries in the map
394: */
395: public static class Entry implements Map.Entry {
396: /** My key object */
397: private Object m_key = null;
398:
399: /** My value object */
400: private Object m_value = null;
401:
402: /**
403: * Constructor - save the key and value
404: */
405: private Entry(Object key, Object value) {
406: m_key = key;
407: m_value = value;
408: }
409:
410: /**
411: * Compares the specified object with this entry for equality. Returns true if the given
412: * object is also a map entry and the two entries represent the same mapping.
413: * More formally, two entries e1 and e2 represent the same mapping if
414: * <code><pre>
415: * (e1.getKey()==null ?
416: * e2.getKey()==null : e1.getKey().equals(e2.getKey())) &&
417: * (e1.getValue()==null ?
418: * e2.getValue()==null : e1.getValue().equals(e2.getValue()))
419: * </pre></code>
420: *
421: * This ensures that the equals method works properly across different implementations of the Map.Entry interface.
422: *
423: * @param x The object to compare against
424: * @return True if the given object is equal to this Map.Entry object.
425: */
426: public boolean equals(Object x) {
427: if (x instanceof java.util.Map.Entry) {
428: Map.Entry e1 = (Map.Entry) x;
429:
430: return (e1.getKey() == null ? m_key == null : e1
431: .getKey().equals(m_key))
432: && (e1.getValue() == null ? m_value == null
433: : e1.getValue().equals(m_value));
434: } else
435: return false;
436: }
437:
438: /**
439: * Answer the key for the entry
440: *
441: * @return The key object
442: */
443: public Object getKey() {
444: return m_key;
445: }
446:
447: /**
448: * Answer the value for the entry
449: *
450: * @return The value object
451: */
452: public Object getValue() {
453: return m_value;
454: }
455:
456: /**
457: * Set the value, which writes through to the map. Not implemented.
458: */
459: public Object setValue(Object value)
460: throws UnsupportedOperationException {
461: throw new UnsupportedOperationException("not implemented");
462: }
463:
464: /**
465: * Returns the hash code value for this map entry.
466: * The hash code of a map entry e is defined to be:
467: * (e.getKey()==null ? 0 : e.getKey().hashCode()) ^
468: * (e.getValue()==null ? 0 : e.getValue().hashCode())
469: *
470: * This ensures that e1.equals(e2) implies that e1.hashCode()==e2.hashCode() for any two
471: * Entries e1 and e2, as required by the general contract of Object.hashCode.
472: */
473: public int hashCode() {
474: return (getKey() == null ? 0 : getKey().hashCode())
475: ^ (getValue() == null ? 0 : getValue().hashCode());
476: }
477:
478: }
479:
480: }
481:
482: /*
483: * All rights reserved.
484: *
485: * Redistribution and use in source and binary forms, with or without
486: * modification, are permitted provided that the following conditions
487: * are met:
488: * 1. Redistributions of source code must retain the above copyright
489: * notice, this list of conditions and the following disclaimer.
490: * 2. Redistributions in binary form must reproduce the above copyright
491: * notice, this list of conditions and the following disclaimer in the
492: * documentation and/or other materials provided with the distribution.
493: * 3. The name of the author may not be used to endorse or promote products
494: * derived from this software without specific prior written permission.
495: *
496: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
497: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
498: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
499: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
500: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
501: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
502: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
503: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
504: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
505: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
506: */
|