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.bag; 018 019 import java.io.IOException; 020 import java.io.ObjectInputStream; 021 import java.io.ObjectOutputStream; 022 import java.lang.reflect.Array; 023 import java.util.Collection; 024 import java.util.ConcurrentModificationException; 025 import java.util.Iterator; 026 import java.util.Map; 027 import java.util.Set; 028 029 import org.apache.commons.collections.Bag; 030 import org.apache.commons.collections.set.UnmodifiableSet; 031 032 /** 033 * Abstract implementation of the {@link Bag} interface to simplify the creation 034 * of subclass implementations. 035 * <p> 036 * Subclasses specify a Map implementation to use as the internal storage. 037 * The map will be used to map bag elements to a number; the number represents 038 * the number of occurrences of that element in the bag. 039 * 040 * @since Commons Collections 3.0 (previously DefaultMapBag v2.0) 041 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 042 * 043 * @author Chuck Burdick 044 * @author Michael A. Smith 045 * @author Stephen Colebourne 046 * @author Janek Bogucki 047 * @author Steve Clark 048 */ 049 public abstract class AbstractMapBag implements Bag { 050 051 /** The map to use to store the data */ 052 private transient Map map; 053 /** The current total size of the bag */ 054 private int size; 055 /** The modification count for fail fast iterators */ 056 private transient int modCount; 057 /** The modification count for fail fast iterators */ 058 private transient Set uniqueSet; 059 060 /** 061 * Constructor needed for subclass serialisation. 062 * 063 */ 064 protected AbstractMapBag() { 065 super(); 066 } 067 068 /** 069 * Constructor that assigns the specified Map as the backing store. 070 * The map must be empty and non-null. 071 * 072 * @param map the map to assign 073 */ 074 protected AbstractMapBag(Map map) { 075 super(); 076 this.map = map; 077 } 078 079 /** 080 * Utility method for implementations to access the map that backs 081 * this bag. Not intended for interactive use outside of subclasses. 082 * 083 * @return the map being used by the Bag 084 */ 085 protected Map getMap() { 086 return map; 087 } 088 089 //----------------------------------------------------------------------- 090 /** 091 * Returns the number of elements in this bag. 092 * 093 * @return current size of the bag 094 */ 095 public int size() { 096 return size; 097 } 098 099 /** 100 * Returns true if the underlying map is empty. 101 * 102 * @return true if bag is empty 103 */ 104 public boolean isEmpty() { 105 return map.isEmpty(); 106 } 107 108 /** 109 * Returns the number of occurrence of the given element in this bag 110 * by looking up its count in the underlying map. 111 * 112 * @param object the object to search for 113 * @return the number of occurrences of the object, zero if not found 114 */ 115 public int getCount(Object object) { 116 MutableInteger count = (MutableInteger) map.get(object); 117 if (count != null) { 118 return count.value; 119 } 120 return 0; 121 } 122 123 //----------------------------------------------------------------------- 124 /** 125 * Determines if the bag contains the given element by checking if the 126 * underlying map contains the element as a key. 127 * 128 * @param object the object to search for 129 * @return true if the bag contains the given element 130 */ 131 public boolean contains(Object object) { 132 return map.containsKey(object); 133 } 134 135 /** 136 * Determines if the bag contains the given elements. 137 * 138 * @param coll the collection to check against 139 * @return <code>true</code> if the Bag contains all the collection 140 */ 141 public boolean containsAll(Collection coll) { 142 if (coll instanceof Bag) { 143 return containsAll((Bag) coll); 144 } 145 return containsAll(new HashBag(coll)); 146 } 147 148 /** 149 * Returns <code>true</code> if the bag contains all elements in 150 * the given collection, respecting cardinality. 151 * 152 * @param other the bag to check against 153 * @return <code>true</code> if the Bag contains all the collection 154 */ 155 boolean containsAll(Bag other) { 156 boolean result = true; 157 Iterator it = other.uniqueSet().iterator(); 158 while (it.hasNext()) { 159 Object current = it.next(); 160 boolean contains = getCount(current) >= other.getCount(current); 161 result = result && contains; 162 } 163 return result; 164 } 165 166 //----------------------------------------------------------------------- 167 /** 168 * Gets an iterator over the bag elements. 169 * Elements present in the Bag more than once will be returned repeatedly. 170 * 171 * @return the iterator 172 */ 173 public Iterator iterator() { 174 return new BagIterator(this); 175 } 176 177 /** 178 * Inner class iterator for the Bag. 179 */ 180 static class BagIterator implements Iterator { 181 private AbstractMapBag parent; 182 private Iterator entryIterator; 183 private Map.Entry current; 184 private int itemCount; 185 private final int mods; 186 private boolean canRemove; 187 188 /** 189 * Constructor. 190 * 191 * @param parent the parent bag 192 */ 193 public BagIterator(AbstractMapBag parent) { 194 this.parent = parent; 195 this.entryIterator = parent.map.entrySet().iterator(); 196 this.current = null; 197 this.mods = parent.modCount; 198 this.canRemove = false; 199 } 200 201 public boolean hasNext() { 202 return (itemCount > 0 || entryIterator.hasNext()); 203 } 204 205 public Object next() { 206 if (parent.modCount != mods) { 207 throw new ConcurrentModificationException(); 208 } 209 if (itemCount == 0) { 210 current = (Map.Entry) entryIterator.next(); 211 itemCount = ((MutableInteger) current.getValue()).value; 212 } 213 canRemove = true; 214 itemCount--; 215 return current.getKey(); 216 } 217 218 public void remove() { 219 if (parent.modCount != mods) { 220 throw new ConcurrentModificationException(); 221 } 222 if (canRemove == false) { 223 throw new IllegalStateException(); 224 } 225 MutableInteger mut = (MutableInteger) current.getValue(); 226 if (mut.value > 1) { 227 mut.value--; 228 } else { 229 entryIterator.remove(); 230 } 231 parent.size--; 232 canRemove = false; 233 } 234 } 235 236 //----------------------------------------------------------------------- 237 /** 238 * Adds a new element to the bag, incrementing its count in the underlying map. 239 * 240 * @param object the object to add 241 * @return <code>true</code> if the object was not already in the <code>uniqueSet</code> 242 */ 243 public boolean add(Object object) { 244 return add(object, 1); 245 } 246 247 /** 248 * Adds a new element to the bag, incrementing its count in the map. 249 * 250 * @param object the object to search for 251 * @param nCopies the number of copies to add 252 * @return <code>true</code> if the object was not already in the <code>uniqueSet</code> 253 */ 254 public boolean add(Object object, int nCopies) { 255 modCount++; 256 if (nCopies > 0) { 257 MutableInteger mut = (MutableInteger) map.get(object); 258 size += nCopies; 259 if (mut == null) { 260 map.put(object, new MutableInteger(nCopies)); 261 return true; 262 } else { 263 mut.value += nCopies; 264 return false; 265 } 266 } else { 267 return false; 268 } 269 } 270 271 /** 272 * Invokes {@link #add(Object)} for each element in the given collection. 273 * 274 * @param coll the collection to add 275 * @return <code>true</code> if this call changed the bag 276 */ 277 public boolean addAll(Collection coll) { 278 boolean changed = false; 279 Iterator i = coll.iterator(); 280 while (i.hasNext()) { 281 boolean added = add(i.next()); 282 changed = changed || added; 283 } 284 return changed; 285 } 286 287 //----------------------------------------------------------------------- 288 /** 289 * Clears the bag by clearing the underlying map. 290 */ 291 public void clear() { 292 modCount++; 293 map.clear(); 294 size = 0; 295 } 296 297 /** 298 * Removes all copies of the specified object from the bag. 299 * 300 * @param object the object to remove 301 * @return true if the bag changed 302 */ 303 public boolean remove(Object object) { 304 MutableInteger mut = (MutableInteger) map.get(object); 305 if (mut == null) { 306 return false; 307 } 308 modCount++; 309 map.remove(object); 310 size -= mut.value; 311 return true; 312 } 313 314 /** 315 * Removes a specified number of copies of an object from the bag. 316 * 317 * @param object the object to remove 318 * @param nCopies the number of copies to remove 319 * @return true if the bag changed 320 */ 321 public boolean remove(Object object, int nCopies) { 322 MutableInteger mut = (MutableInteger) map.get(object); 323 if (mut == null) { 324 return false; 325 } 326 if (nCopies <= 0) { 327 return false; 328 } 329 modCount++; 330 if (nCopies < mut.value) { 331 mut.value -= nCopies; 332 size -= nCopies; 333 } else { 334 map.remove(object); 335 size -= mut.value; 336 } 337 return true; 338 } 339 340 /** 341 * Removes objects from the bag according to their count in the specified collection. 342 * 343 * @param coll the collection to use 344 * @return true if the bag changed 345 */ 346 public boolean removeAll(Collection coll) { 347 boolean result = false; 348 if (coll != null) { 349 Iterator i = coll.iterator(); 350 while (i.hasNext()) { 351 boolean changed = remove(i.next(), 1); 352 result = result || changed; 353 } 354 } 355 return result; 356 } 357 358 /** 359 * Remove any members of the bag that are not in the given 360 * bag, respecting cardinality. 361 * 362 * @param coll the collection to retain 363 * @return true if this call changed the collection 364 */ 365 public boolean retainAll(Collection coll) { 366 if (coll instanceof Bag) { 367 return retainAll((Bag) coll); 368 } 369 return retainAll(new HashBag(coll)); 370 } 371 372 /** 373 * Remove any members of the bag that are not in the given 374 * bag, respecting cardinality. 375 * @see #retainAll(Collection) 376 * 377 * @param other the bag to retain 378 * @return <code>true</code> if this call changed the collection 379 */ 380 boolean retainAll(Bag other) { 381 boolean result = false; 382 Bag excess = new HashBag(); 383 Iterator i = uniqueSet().iterator(); 384 while (i.hasNext()) { 385 Object current = i.next(); 386 int myCount = getCount(current); 387 int otherCount = other.getCount(current); 388 if (1 <= otherCount && otherCount <= myCount) { 389 excess.add(current, myCount - otherCount); 390 } else { 391 excess.add(current, myCount); 392 } 393 } 394 if (!excess.isEmpty()) { 395 result = removeAll(excess); 396 } 397 return result; 398 } 399 400 //----------------------------------------------------------------------- 401 /** 402 * Mutable integer class for storing the data. 403 */ 404 protected static class MutableInteger { 405 /** The value of this mutable. */ 406 protected int value; 407 408 /** 409 * Constructor. 410 * @param value the initial value 411 */ 412 MutableInteger(int value) { 413 this.value = value; 414 } 415 416 public boolean equals(Object obj) { 417 if (obj instanceof MutableInteger == false) { 418 return false; 419 } 420 return ((MutableInteger) obj).value == value; 421 } 422 423 public int hashCode() { 424 return value; 425 } 426 } 427 428 //----------------------------------------------------------------------- 429 /** 430 * Returns an array of all of this bag's elements. 431 * 432 * @return an array of all of this bag's elements 433 */ 434 public Object[] toArray() { 435 Object[] result = new Object[size()]; 436 int i = 0; 437 Iterator it = map.keySet().iterator(); 438 while (it.hasNext()) { 439 Object current = it.next(); 440 for (int index = getCount(current); index > 0; index--) { 441 result[i++] = current; 442 } 443 } 444 return result; 445 } 446 447 /** 448 * Returns an array of all of this bag's elements. 449 * 450 * @param array the array to populate 451 * @return an array of all of this bag's elements 452 */ 453 public Object[] toArray(Object[] array) { 454 int size = size(); 455 if (array.length < size) { 456 array = (Object[]) Array.newInstance(array.getClass().getComponentType(), size); 457 } 458 459 int i = 0; 460 Iterator it = map.keySet().iterator(); 461 while (it.hasNext()) { 462 Object current = it.next(); 463 for (int index = getCount(current); index > 0; index--) { 464 array[i++] = current; 465 } 466 } 467 if (array.length > size) { 468 array[size] = null; 469 } 470 return array; 471 } 472 473 /** 474 * Returns an unmodifiable view of the underlying map's key set. 475 * 476 * @return the set of unique elements in this bag 477 */ 478 public Set uniqueSet() { 479 if (uniqueSet == null) { 480 uniqueSet = UnmodifiableSet.decorate(map.keySet()); 481 } 482 return uniqueSet; 483 } 484 485 //----------------------------------------------------------------------- 486 /** 487 * Write the map out using a custom routine. 488 * @param out the output stream 489 * @throws IOException 490 */ 491 protected void doWriteObject(ObjectOutputStream out) throws IOException { 492 out.writeInt(map.size()); 493 for (Iterator it = map.entrySet().iterator(); it.hasNext();) { 494 Map.Entry entry = (Map.Entry) it.next(); 495 out.writeObject(entry.getKey()); 496 out.writeInt(((MutableInteger) entry.getValue()).value); 497 } 498 } 499 500 /** 501 * Read the map in using a custom routine. 502 * @param map the map to use 503 * @param in the input stream 504 * @throws IOException 505 * @throws ClassNotFoundException 506 */ 507 protected void doReadObject(Map map, ObjectInputStream in) throws IOException, ClassNotFoundException { 508 this.map = map; 509 int entrySize = in.readInt(); 510 for (int i = 0; i < entrySize; i++) { 511 Object obj = in.readObject(); 512 int count = in.readInt(); 513 map.put(obj, new MutableInteger(count)); 514 size += count; 515 } 516 } 517 518 //----------------------------------------------------------------------- 519 /** 520 * Compares this Bag to another. 521 * This Bag equals another Bag if it contains the same number of occurrences of 522 * the same elements. 523 * 524 * @param object the Bag to compare to 525 * @return true if equal 526 */ 527 public boolean equals(Object object) { 528 if (object == this) { 529 return true; 530 } 531 if (object instanceof Bag == false) { 532 return false; 533 } 534 Bag other = (Bag) object; 535 if (other.size() != size()) { 536 return false; 537 } 538 for (Iterator it = map.keySet().iterator(); it.hasNext();) { 539 Object element = it.next(); 540 if (other.getCount(element) != getCount(element)) { 541 return false; 542 } 543 } 544 return true; 545 } 546 547 /** 548 * Gets a hash code for the Bag compatible with the definition of equals. 549 * The hash code is defined as the sum total of a hash code for each element. 550 * The per element hash code is defined as 551 * <code>(e==null ? 0 : e.hashCode()) ^ noOccurances)</code>. 552 * This hash code is compatible with the Set interface. 553 * 554 * @return the hash code of the Bag 555 */ 556 public int hashCode() { 557 int total = 0; 558 for (Iterator it = map.entrySet().iterator(); it.hasNext();) { 559 Map.Entry entry = (Map.Entry) it.next(); 560 Object element = entry.getKey(); 561 MutableInteger count = (MutableInteger) entry.getValue(); 562 total += (element == null ? 0 : element.hashCode()) ^ count.value; 563 } 564 return total; 565 } 566 567 /** 568 * Implement a toString() method suitable for debugging. 569 * 570 * @return a debugging toString 571 */ 572 public String toString() { 573 if (size() == 0) { 574 return "[]"; 575 } 576 StringBuffer buf = new StringBuffer(); 577 buf.append('['); 578 Iterator it = uniqueSet().iterator(); 579 while (it.hasNext()) { 580 Object current = it.next(); 581 int count = getCount(current); 582 buf.append(count); 583 buf.append(':'); 584 buf.append(current); 585 if (it.hasNext()) { 586 buf.append(','); 587 } 588 } 589 buf.append(']'); 590 return buf.toString(); 591 } 592 593 }