001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.commons.collections.bidimap; 018 019 import java.io.IOException; 020 import java.io.ObjectInputStream; 021 import java.io.ObjectOutputStream; 022 import java.io.Serializable; 023 import java.util.ArrayList; 024 import java.util.Comparator; 025 import java.util.Iterator; 026 import java.util.ListIterator; 027 import java.util.Map; 028 import java.util.SortedMap; 029 import java.util.TreeMap; 030 031 import org.apache.commons.collections.BidiMap; 032 import org.apache.commons.collections.OrderedBidiMap; 033 import org.apache.commons.collections.OrderedMap; 034 import org.apache.commons.collections.OrderedMapIterator; 035 import org.apache.commons.collections.ResettableIterator; 036 import org.apache.commons.collections.SortedBidiMap; 037 import org.apache.commons.collections.map.AbstractSortedMapDecorator; 038 039 /** 040 * Implementation of <code>BidiMap</code> that uses two <code>TreeMap</code> instances. 041 * <p> 042 * The setValue() method on iterators will succeed only if the new value being set is 043 * not already in the bidimap. 044 * <p> 045 * When considering whether to use this class, the {@link TreeBidiMap} class should 046 * also be considered. It implements the interface using a dedicated design, and does 047 * not store each object twice, which can save on memory use. 048 * <p> 049 * NOTE: From Commons Collections 3.1, all subclasses will use <code>TreeMap</code> 050 * and the flawed <code>createMap</code> method is ignored. 051 * 052 * @since Commons Collections 3.0 053 * @version $Id: DualTreeBidiMap.java 646777 2008-04-10 12:33:15Z niallp $ 054 * 055 * @author Matthew Hawthorne 056 * @author Stephen Colebourne 057 */ 058 public class DualTreeBidiMap 059 extends AbstractDualBidiMap implements SortedBidiMap, Serializable { 060 061 /** Ensure serialization compatibility */ 062 private static final long serialVersionUID = 721969328361809L; 063 /** The comparator to use */ 064 protected final Comparator comparator; 065 066 /** 067 * Creates an empty <code>DualTreeBidiMap</code> 068 */ 069 public DualTreeBidiMap() { 070 super(new TreeMap(), new TreeMap()); 071 this.comparator = null; 072 } 073 074 /** 075 * Constructs a <code>DualTreeBidiMap</code> and copies the mappings from 076 * specified <code>Map</code>. 077 * 078 * @param map the map whose mappings are to be placed in this map 079 */ 080 public DualTreeBidiMap(Map map) { 081 super(new TreeMap(), new TreeMap()); 082 putAll(map); 083 this.comparator = null; 084 } 085 086 /** 087 * Constructs a <code>DualTreeBidiMap</code> using the specified Comparator. 088 * 089 * @param comparator the Comparator 090 */ 091 public DualTreeBidiMap(Comparator comparator) { 092 super(new TreeMap(comparator), new TreeMap(comparator)); 093 this.comparator = comparator; 094 } 095 096 /** 097 * Constructs a <code>DualTreeBidiMap</code> that decorates the specified maps. 098 * 099 * @param normalMap the normal direction map 100 * @param reverseMap the reverse direction map 101 * @param inverseBidiMap the inverse BidiMap 102 */ 103 protected DualTreeBidiMap(Map normalMap, Map reverseMap, BidiMap inverseBidiMap) { 104 super(normalMap, reverseMap, inverseBidiMap); 105 this.comparator = ((SortedMap) normalMap).comparator(); 106 } 107 108 /** 109 * Creates a new instance of this object. 110 * 111 * @param normalMap the normal direction map 112 * @param reverseMap the reverse direction map 113 * @param inverseMap the inverse BidiMap 114 * @return new bidi map 115 */ 116 protected BidiMap createBidiMap(Map normalMap, Map reverseMap, BidiMap inverseMap) { 117 return new DualTreeBidiMap(normalMap, reverseMap, inverseMap); 118 } 119 120 //----------------------------------------------------------------------- 121 public Comparator comparator() { 122 return ((SortedMap) maps[0]).comparator(); 123 } 124 125 public Object firstKey() { 126 return ((SortedMap) maps[0]).firstKey(); 127 } 128 129 public Object lastKey() { 130 return ((SortedMap) maps[0]).lastKey(); 131 } 132 133 public Object nextKey(Object key) { 134 if (isEmpty()) { 135 return null; 136 } 137 if (maps[0] instanceof OrderedMap) { 138 return ((OrderedMap) maps[0]).nextKey(key); 139 } 140 SortedMap sm = (SortedMap) maps[0]; 141 Iterator it = sm.tailMap(key).keySet().iterator(); 142 it.next(); 143 if (it.hasNext()) { 144 return it.next(); 145 } 146 return null; 147 } 148 149 public Object previousKey(Object key) { 150 if (isEmpty()) { 151 return null; 152 } 153 if (maps[0] instanceof OrderedMap) { 154 return ((OrderedMap) maps[0]).previousKey(key); 155 } 156 SortedMap sm = (SortedMap) maps[0]; 157 SortedMap hm = sm.headMap(key); 158 if (hm.isEmpty()) { 159 return null; 160 } 161 return hm.lastKey(); 162 } 163 164 //----------------------------------------------------------------------- 165 /** 166 * Obtains an ordered map iterator. 167 * <p> 168 * This implementation copies the elements to an ArrayList in order to 169 * provide the forward/backward behaviour. 170 * 171 * @return a new ordered map iterator 172 */ 173 public OrderedMapIterator orderedMapIterator() { 174 return new BidiOrderedMapIterator(this); 175 } 176 177 public SortedBidiMap inverseSortedBidiMap() { 178 return (SortedBidiMap) inverseBidiMap(); 179 } 180 181 public OrderedBidiMap inverseOrderedBidiMap() { 182 return (OrderedBidiMap) inverseBidiMap(); 183 } 184 185 //----------------------------------------------------------------------- 186 public SortedMap headMap(Object toKey) { 187 SortedMap sub = ((SortedMap) maps[0]).headMap(toKey); 188 return new ViewMap(this, sub); 189 } 190 191 public SortedMap tailMap(Object fromKey) { 192 SortedMap sub = ((SortedMap) maps[0]).tailMap(fromKey); 193 return new ViewMap(this, sub); 194 } 195 196 public SortedMap subMap(Object fromKey, Object toKey) { 197 SortedMap sub = ((SortedMap) maps[0]).subMap(fromKey, toKey); 198 return new ViewMap(this, sub); 199 } 200 201 //----------------------------------------------------------------------- 202 /** 203 * Internal sorted map view. 204 */ 205 protected static class ViewMap extends AbstractSortedMapDecorator { 206 /** The parent bidi map. */ 207 final DualTreeBidiMap bidi; 208 209 /** 210 * Constructor. 211 * @param bidi the parent bidi map 212 * @param sm the subMap sorted map 213 */ 214 protected ViewMap(DualTreeBidiMap bidi, SortedMap sm) { 215 // the implementation is not great here... 216 // use the maps[0] as the filtered map, but maps[1] as the full map 217 // this forces containsValue and clear to be overridden 218 super((SortedMap) bidi.createBidiMap(sm, bidi.maps[1], bidi.inverseBidiMap)); 219 this.bidi = (DualTreeBidiMap) map; 220 } 221 222 public boolean containsValue(Object value) { 223 // override as default implementation jumps to [1] 224 return bidi.maps[0].containsValue(value); 225 } 226 227 public void clear() { 228 // override as default implementation jumps to [1] 229 for (Iterator it = keySet().iterator(); it.hasNext();) { 230 it.next(); 231 it.remove(); 232 } 233 } 234 235 public SortedMap headMap(Object toKey) { 236 return new ViewMap(bidi, super.headMap(toKey)); 237 } 238 239 public SortedMap tailMap(Object fromKey) { 240 return new ViewMap(bidi, super.tailMap(fromKey)); 241 } 242 243 public SortedMap subMap(Object fromKey, Object toKey) { 244 return new ViewMap(bidi, super.subMap(fromKey, toKey)); 245 } 246 } 247 248 //----------------------------------------------------------------------- 249 /** 250 * Inner class MapIterator. 251 */ 252 protected static class BidiOrderedMapIterator implements OrderedMapIterator, ResettableIterator { 253 254 /** The parent map */ 255 protected final AbstractDualBidiMap parent; 256 /** The iterator being decorated */ 257 protected ListIterator iterator; 258 /** The last returned entry */ 259 private Map.Entry last = null; 260 261 /** 262 * Constructor. 263 * @param parent the parent map 264 */ 265 protected BidiOrderedMapIterator(AbstractDualBidiMap parent) { 266 super(); 267 this.parent = parent; 268 iterator = new ArrayList(parent.entrySet()).listIterator(); 269 } 270 271 public boolean hasNext() { 272 return iterator.hasNext(); 273 } 274 275 public Object next() { 276 last = (Map.Entry) iterator.next(); 277 return last.getKey(); 278 } 279 280 public boolean hasPrevious() { 281 return iterator.hasPrevious(); 282 } 283 284 public Object previous() { 285 last = (Map.Entry) iterator.previous(); 286 return last.getKey(); 287 } 288 289 public void remove() { 290 iterator.remove(); 291 parent.remove(last.getKey()); 292 last = null; 293 } 294 295 public Object getKey() { 296 if (last == null) { 297 throw new IllegalStateException("Iterator getKey() can only be called after next() and before remove()"); 298 } 299 return last.getKey(); 300 } 301 302 public Object getValue() { 303 if (last == null) { 304 throw new IllegalStateException("Iterator getValue() can only be called after next() and before remove()"); 305 } 306 return last.getValue(); 307 } 308 309 public Object setValue(Object value) { 310 if (last == null) { 311 throw new IllegalStateException("Iterator setValue() can only be called after next() and before remove()"); 312 } 313 if (parent.maps[1].containsKey(value) && 314 parent.maps[1].get(value) != last.getKey()) { 315 throw new IllegalArgumentException("Cannot use setValue() when the object being set is already in the map"); 316 } 317 return parent.put(last.getKey(), value); 318 } 319 320 public void reset() { 321 iterator = new ArrayList(parent.entrySet()).listIterator(); 322 last = null; 323 } 324 325 public String toString() { 326 if (last != null) { 327 return "MapIterator[" + getKey() + "=" + getValue() + "]"; 328 } else { 329 return "MapIterator[]"; 330 } 331 } 332 } 333 334 // Serialization 335 //----------------------------------------------------------------------- 336 private void writeObject(ObjectOutputStream out) throws IOException { 337 out.defaultWriteObject(); 338 out.writeObject(maps[0]); 339 } 340 341 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 342 in.defaultReadObject(); 343 maps[0] = new TreeMap(comparator); 344 maps[1] = new TreeMap(comparator); 345 Map map = (Map) in.readObject(); 346 putAll(map); 347 } 348 349 }