| /* |
| * Copyright 2003-2004 The Apache Software Foundation |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.commons.collections.bidimap; |
| |
| import java.io.IOException; |
| import java.io.ObjectInputStream; |
| import java.io.ObjectOutputStream; |
| import java.io.Serializable; |
| import java.util.ArrayList; |
| import java.util.Comparator; |
| import java.util.Iterator; |
| import java.util.ListIterator; |
| import java.util.Map; |
| import java.util.SortedMap; |
| import java.util.TreeMap; |
| |
| import org.apache.commons.collections.BidiMap; |
| import org.apache.commons.collections.OrderedBidiMap; |
| import org.apache.commons.collections.OrderedMap; |
| import org.apache.commons.collections.OrderedMapIterator; |
| import org.apache.commons.collections.ResettableIterator; |
| import org.apache.commons.collections.SortedBidiMap; |
| import org.apache.commons.collections.map.AbstractSortedMapDecorator; |
| |
| /** |
| * Implementation of <code>BidiMap</code> that uses two <code>TreeMap</code> instances. |
| * <p> |
| * The setValue() method on iterators will succeed only if the new value being set is |
| * not already in the bidimap. |
| * <p> |
| * When considering whether to use this class, the {@link TreeBidiMap} class should |
| * also be considered. It implements the interface using a dedicated design, and does |
| * not store each object twice, which can save on memory use. |
| * <p> |
| * NOTE: From Commons Collections 3.1, all subclasses will use <code>TreeMap</code> |
| * and the flawed <code>createMap</code> method is ignored. |
| * |
| * @since Commons Collections 3.0 |
| * @version $Id: DualTreeBidiMap.java,v 1.1 2009/05/27 22:16:32 mparker Exp $ |
| * |
| * @author Matthew Hawthorne |
| * @author Stephen Colebourne |
| */ |
| public class DualTreeBidiMap |
| extends AbstractDualBidiMap implements SortedBidiMap, Serializable { |
| |
| /** Ensure serialization compatibility */ |
| private static final long serialVersionUID = 721969328361809L; |
| /** The comparator to use */ |
| protected final Comparator comparator; |
| |
| /** |
| * Creates an empty <code>DualTreeBidiMap</code> |
| */ |
| public DualTreeBidiMap() { |
| super(new TreeMap(), new TreeMap()); |
| this.comparator = null; |
| } |
| |
| /** |
| * Constructs a <code>DualTreeBidiMap</code> and copies the mappings from |
| * specified <code>Map</code>. |
| * |
| * @param map the map whose mappings are to be placed in this map |
| */ |
| public DualTreeBidiMap(Map map) { |
| super(new TreeMap(), new TreeMap()); |
| putAll(map); |
| this.comparator = null; |
| } |
| |
| /** |
| * Constructs a <code>DualTreeBidiMap</code> using the specified Comparator. |
| * |
| * @param comparator the Comparator |
| */ |
| public DualTreeBidiMap(Comparator comparator) { |
| super(new TreeMap(comparator), new TreeMap(comparator)); |
| this.comparator = comparator; |
| } |
| |
| /** |
| * Constructs a <code>DualTreeBidiMap</code> that decorates the specified maps. |
| * |
| * @param normalMap the normal direction map |
| * @param reverseMap the reverse direction map |
| * @param inverseBidiMap the inverse BidiMap |
| */ |
| protected DualTreeBidiMap(Map normalMap, Map reverseMap, BidiMap inverseBidiMap) { |
| super(normalMap, reverseMap, inverseBidiMap); |
| this.comparator = ((SortedMap) normalMap).comparator(); |
| } |
| |
| /** |
| * Creates a new instance of this object. |
| * |
| * @param normalMap the normal direction map |
| * @param reverseMap the reverse direction map |
| * @param inverseMap the inverse BidiMap |
| * @return new bidi map |
| */ |
| protected BidiMap createBidiMap(Map normalMap, Map reverseMap, BidiMap inverseMap) { |
| return new DualTreeBidiMap(normalMap, reverseMap, inverseMap); |
| } |
| |
| //----------------------------------------------------------------------- |
| public Comparator comparator() { |
| return ((SortedMap) maps[0]).comparator(); |
| } |
| |
| public Object firstKey() { |
| return ((SortedMap) maps[0]).firstKey(); |
| } |
| |
| public Object lastKey() { |
| return ((SortedMap) maps[0]).lastKey(); |
| } |
| |
| public Object nextKey(Object key) { |
| if (isEmpty()) { |
| return null; |
| } |
| if (maps[0] instanceof OrderedMap) { |
| return ((OrderedMap) maps[0]).nextKey(key); |
| } |
| SortedMap sm = (SortedMap) maps[0]; |
| Iterator it = sm.tailMap(key).keySet().iterator(); |
| it.next(); |
| if (it.hasNext()) { |
| return it.next(); |
| } |
| return null; |
| } |
| |
| public Object previousKey(Object key) { |
| if (isEmpty()) { |
| return null; |
| } |
| if (maps[0] instanceof OrderedMap) { |
| return ((OrderedMap) maps[0]).previousKey(key); |
| } |
| SortedMap sm = (SortedMap) maps[0]; |
| SortedMap hm = sm.headMap(key); |
| if (hm.isEmpty()) { |
| return null; |
| } |
| return hm.lastKey(); |
| } |
| |
| //----------------------------------------------------------------------- |
| /** |
| * Obtains an ordered map iterator. |
| * <p> |
| * This implementation copies the elements to an ArrayList in order to |
| * provide the forward/backward behaviour. |
| * |
| * @return a new ordered map iterator |
| */ |
| public OrderedMapIterator orderedMapIterator() { |
| return new BidiOrderedMapIterator(this); |
| } |
| |
| public SortedBidiMap inverseSortedBidiMap() { |
| return (SortedBidiMap) inverseBidiMap(); |
| } |
| |
| public OrderedBidiMap inverseOrderedBidiMap() { |
| return (OrderedBidiMap) inverseBidiMap(); |
| } |
| |
| //----------------------------------------------------------------------- |
| public SortedMap headMap(Object toKey) { |
| SortedMap sub = ((SortedMap) maps[0]).headMap(toKey); |
| return new ViewMap(this, sub); |
| } |
| |
| public SortedMap tailMap(Object fromKey) { |
| SortedMap sub = ((SortedMap) maps[0]).tailMap(fromKey); |
| return new ViewMap(this, sub); |
| } |
| |
| public SortedMap subMap(Object fromKey, Object toKey) { |
| SortedMap sub = ((SortedMap) maps[0]).subMap(fromKey, toKey); |
| return new ViewMap(this, sub); |
| } |
| |
| //----------------------------------------------------------------------- |
| /** |
| * Internal sorted map view. |
| */ |
| protected static class ViewMap extends AbstractSortedMapDecorator { |
| /** The parent bidi map. */ |
| final DualTreeBidiMap bidi; |
| |
| /** |
| * Constructor. |
| * @param bidi the parent bidi map |
| * @param sm the subMap sorted map |
| */ |
| protected ViewMap(DualTreeBidiMap bidi, SortedMap sm) { |
| // the implementation is not great here... |
| // use the maps[0] as the filtered map, but maps[1] as the full map |
| // this forces containsValue and clear to be overridden |
| super((SortedMap) bidi.createBidiMap(sm, bidi.maps[1], bidi.inverseBidiMap)); |
| this.bidi = (DualTreeBidiMap) map; |
| } |
| |
| public boolean containsValue(Object value) { |
| // override as default implementation jumps to [1] |
| return bidi.maps[0].containsValue(value); |
| } |
| |
| public void clear() { |
| // override as default implementation jumps to [1] |
| for (Iterator it = keySet().iterator(); it.hasNext();) { |
| it.next(); |
| it.remove(); |
| } |
| } |
| |
| public SortedMap headMap(Object toKey) { |
| return new ViewMap(bidi, super.headMap(toKey)); |
| } |
| |
| public SortedMap tailMap(Object fromKey) { |
| return new ViewMap(bidi, super.tailMap(fromKey)); |
| } |
| |
| public SortedMap subMap(Object fromKey, Object toKey) { |
| return new ViewMap(bidi, super.subMap(fromKey, toKey)); |
| } |
| } |
| |
| //----------------------------------------------------------------------- |
| /** |
| * Inner class MapIterator. |
| */ |
| protected static class BidiOrderedMapIterator implements OrderedMapIterator, ResettableIterator { |
| |
| /** The parent map */ |
| protected final AbstractDualBidiMap parent; |
| /** The iterator being decorated */ |
| protected ListIterator iterator; |
| /** The last returned entry */ |
| private Map.Entry last = null; |
| |
| /** |
| * Constructor. |
| * @param parent the parent map |
| */ |
| protected BidiOrderedMapIterator(AbstractDualBidiMap parent) { |
| super(); |
| this.parent = parent; |
| iterator = new ArrayList(parent.entrySet()).listIterator(); |
| } |
| |
| public boolean hasNext() { |
| return iterator.hasNext(); |
| } |
| |
| public Object next() { |
| last = (Map.Entry) iterator.next(); |
| return last.getKey(); |
| } |
| |
| public boolean hasPrevious() { |
| return iterator.hasPrevious(); |
| } |
| |
| public Object previous() { |
| last = (Map.Entry) iterator.previous(); |
| return last.getKey(); |
| } |
| |
| public void remove() { |
| iterator.remove(); |
| parent.remove(last.getKey()); |
| last = null; |
| } |
| |
| public Object getKey() { |
| if (last == null) { |
| throw new IllegalStateException("Iterator getKey() can only be called after next() and before remove()"); |
| } |
| return last.getKey(); |
| } |
| |
| public Object getValue() { |
| if (last == null) { |
| throw new IllegalStateException("Iterator getValue() can only be called after next() and before remove()"); |
| } |
| return last.getValue(); |
| } |
| |
| public Object setValue(Object value) { |
| if (last == null) { |
| throw new IllegalStateException("Iterator setValue() can only be called after next() and before remove()"); |
| } |
| if (parent.maps[1].containsKey(value) && |
| parent.maps[1].get(value) != last.getKey()) { |
| throw new IllegalArgumentException("Cannot use setValue() when the object being set is already in the map"); |
| } |
| return parent.put(last.getKey(), value); |
| } |
| |
| public void reset() { |
| iterator = new ArrayList(parent.entrySet()).listIterator(); |
| last = null; |
| } |
| |
| public String toString() { |
| if (last != null) { |
| return "MapIterator[" + getKey() + "=" + getValue() + "]"; |
| } else { |
| return "MapIterator[]"; |
| } |
| } |
| } |
| |
| // Serialization |
| //----------------------------------------------------------------------- |
| private void writeObject(ObjectOutputStream out) throws IOException { |
| out.defaultWriteObject(); |
| out.writeObject(maps[0]); |
| } |
| |
| private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { |
| in.defaultReadObject(); |
| maps[0] = new TreeMap(comparator); |
| maps[1] = new TreeMap(comparator); |
| Map map = (Map) in.readObject(); |
| putAll(map); |
| } |
| |
| } |