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; 018 019 import java.util.ArrayList; 020 import java.util.Collection; 021 import java.util.ConcurrentModificationException; 022 import java.util.Iterator; 023 import java.util.List; 024 import java.util.Map; 025 import java.util.Set; 026 027 import org.apache.commons.collections.set.UnmodifiableSet; 028 029 /** 030 * A skeletal implementation of the {@link Bag} 031 * interface to minimize the effort required for target implementations. 032 * Subclasses need only to call <code>setMap(Map)</code> in their constructor 033 * (or invoke the Map constructor) specifying a map instance that will be used 034 * to store the contents of the bag. 035 * <p> 036 * The map will be used to map bag elements to a number; the number represents 037 * the number of occurrences of that element in the bag. 038 * 039 * @deprecated Moved to bag subpackage as AbstractMapBag. Due to be removed in v4.0. 040 * @since Commons Collections 2.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 */ 048 public abstract class DefaultMapBag implements Bag { 049 private Map _map = null; 050 private int _total = 0; 051 private int _mods = 0; 052 053 /** 054 * No-argument constructor. 055 * Subclasses should invoke <code>setMap(Map)</code> in 056 * their constructors. 057 */ 058 public DefaultMapBag() { 059 } 060 061 /** 062 * Constructor that assigns the specified Map as the backing store. 063 * The map must be empty. 064 * 065 * @param map the map to assign 066 */ 067 protected DefaultMapBag(Map map) { 068 setMap(map); 069 } 070 071 /** 072 * Adds a new element to the bag by incrementing its count in the 073 * underlying map. 074 * 075 * @param object the object to add 076 * @return <code>true</code> if the object was not already in the <code>uniqueSet</code> 077 */ 078 public boolean add(Object object) { 079 return add(object, 1); 080 } 081 082 /** 083 * Adds a new element to the bag by incrementing its count in the map. 084 * 085 * @param object the object to search for 086 * @param nCopies the number of copies to add 087 * @return <code>true</code> if the object was not already in the <code>uniqueSet</code> 088 */ 089 public boolean add(Object object, int nCopies) { 090 _mods++; 091 if (nCopies > 0) { 092 int count = (nCopies + getCount(object)); 093 _map.put(object, new Integer(count)); 094 _total += nCopies; 095 return (count == nCopies); 096 } else { 097 return false; 098 } 099 } 100 101 /** 102 * Invokes {@link #add(Object)} for each element in the given collection. 103 * 104 * @param coll the collection to add 105 * @return <code>true</code> if this call changed the bag 106 */ 107 public boolean addAll(Collection coll) { 108 boolean changed = false; 109 Iterator i = coll.iterator(); 110 while (i.hasNext()) { 111 boolean added = add(i.next()); 112 changed = changed || added; 113 } 114 return changed; 115 } 116 117 /** 118 * Clears the bag by clearing the underlying map. 119 */ 120 public void clear() { 121 _mods++; 122 _map.clear(); 123 _total = 0; 124 } 125 126 /** 127 * Determines if the bag contains the given element by checking if the 128 * underlying map contains the element as a key. 129 * 130 * @param object the object to search for 131 * @return true if the bag contains the given element 132 */ 133 public boolean contains(Object object) { 134 return _map.containsKey(object); 135 } 136 137 /** 138 * Determines if the bag contains the given elements. 139 * 140 * @param coll the collection to check against 141 * @return <code>true</code> if the Bag contains all the collection 142 */ 143 public boolean containsAll(Collection coll) { 144 return containsAll(new HashBag(coll)); 145 } 146 147 /** 148 * Returns <code>true</code> if the bag contains all elements in 149 * the given collection, respecting cardinality. 150 * 151 * @param other the bag to check against 152 * @return <code>true</code> if the Bag contains all the collection 153 */ 154 public boolean containsAll(Bag other) { 155 boolean result = true; 156 Iterator i = other.uniqueSet().iterator(); 157 while (i.hasNext()) { 158 Object current = i.next(); 159 boolean contains = getCount(current) >= other.getCount(current); 160 result = result && contains; 161 } 162 return result; 163 } 164 165 /** 166 * Returns true if the given object is not null, has the precise type 167 * of this bag, and contains the same number of occurrences of all the 168 * same elements. 169 * 170 * @param object the object to test for equality 171 * @return true if that object equals this bag 172 */ 173 public boolean equals(Object object) { 174 if (object == this) { 175 return true; 176 } 177 if (object instanceof Bag == false) { 178 return false; 179 } 180 Bag other = (Bag) object; 181 if (other.size() != size()) { 182 return false; 183 } 184 for (Iterator it = _map.keySet().iterator(); it.hasNext();) { 185 Object element = it.next(); 186 if (other.getCount(element) != getCount(element)) { 187 return false; 188 } 189 } 190 return true; 191 } 192 193 /** 194 * Returns the hash code of the underlying map. 195 * 196 * @return the hash code of the underlying map 197 */ 198 public int hashCode() { 199 return _map.hashCode(); 200 } 201 202 /** 203 * Returns true if the underlying map is empty. 204 * 205 * @return true if there are no elements in this bag 206 */ 207 public boolean isEmpty() { 208 return _map.isEmpty(); 209 } 210 211 public Iterator iterator() { 212 return new BagIterator(this, extractList().iterator()); 213 } 214 215 static class BagIterator implements Iterator { 216 private DefaultMapBag _parent = null; 217 private Iterator _support = null; 218 private Object _current = null; 219 private int _mods = 0; 220 221 public BagIterator(DefaultMapBag parent, Iterator support) { 222 _parent = parent; 223 _support = support; 224 _current = null; 225 _mods = parent.modCount(); 226 } 227 228 public boolean hasNext() { 229 return _support.hasNext(); 230 } 231 232 public Object next() { 233 if (_parent.modCount() != _mods) { 234 throw new ConcurrentModificationException(); 235 } 236 _current = _support.next(); 237 return _current; 238 } 239 240 public void remove() { 241 if (_parent.modCount() != _mods) { 242 throw new ConcurrentModificationException(); 243 } 244 _support.remove(); 245 _parent.remove(_current, 1); 246 _mods++; 247 } 248 } 249 250 public boolean remove(Object object) { 251 return remove(object, getCount(object)); 252 } 253 254 public boolean remove(Object object, int nCopies) { 255 _mods++; 256 boolean result = false; 257 int count = getCount(object); 258 if (nCopies <= 0) { 259 result = false; 260 } else if (count > nCopies) { 261 _map.put(object, new Integer(count - nCopies)); 262 result = true; 263 _total -= nCopies; 264 } else { // count > 0 && count <= i 265 // need to remove all 266 result = (_map.remove(object) != null); 267 _total -= count; 268 } 269 return result; 270 } 271 272 public boolean removeAll(Collection coll) { 273 boolean result = false; 274 if (coll != null) { 275 Iterator i = coll.iterator(); 276 while (i.hasNext()) { 277 boolean changed = remove(i.next(), 1); 278 result = result || changed; 279 } 280 } 281 return result; 282 } 283 284 /** 285 * Remove any members of the bag that are not in the given 286 * bag, respecting cardinality. 287 * 288 * @param coll the collection to retain 289 * @return true if this call changed the collection 290 */ 291 public boolean retainAll(Collection coll) { 292 return retainAll(new HashBag(coll)); 293 } 294 295 /** 296 * Remove any members of the bag that are not in the given 297 * bag, respecting cardinality. 298 * @see #retainAll(Collection) 299 * 300 * @param other the bag to retain 301 * @return <code>true</code> if this call changed the collection 302 */ 303 public boolean retainAll(Bag other) { 304 boolean result = false; 305 Bag excess = new HashBag(); 306 Iterator i = uniqueSet().iterator(); 307 while (i.hasNext()) { 308 Object current = i.next(); 309 int myCount = getCount(current); 310 int otherCount = other.getCount(current); 311 if (1 <= otherCount && otherCount <= myCount) { 312 excess.add(current, myCount - otherCount); 313 } else { 314 excess.add(current, myCount); 315 } 316 } 317 if (!excess.isEmpty()) { 318 result = removeAll(excess); 319 } 320 return result; 321 } 322 323 /** 324 * Returns an array of all of this bag's elements. 325 * 326 * @return an array of all of this bag's elements 327 */ 328 public Object[] toArray() { 329 return extractList().toArray(); 330 } 331 332 /** 333 * Returns an array of all of this bag's elements. 334 * 335 * @param array the array to populate 336 * @return an array of all of this bag's elements 337 */ 338 public Object[] toArray(Object[] array) { 339 return extractList().toArray(array); 340 } 341 342 /** 343 * Returns the number of occurrence of the given element in this bag 344 * by looking up its count in the underlying map. 345 * 346 * @param object the object to search for 347 * @return the number of occurrences of the object, zero if not found 348 */ 349 public int getCount(Object object) { 350 int result = 0; 351 Integer count = MapUtils.getInteger(_map, object); 352 if (count != null) { 353 result = count.intValue(); 354 } 355 return result; 356 } 357 358 /** 359 * Returns an unmodifiable view of the underlying map's key set. 360 * 361 * @return the set of unique elements in this bag 362 */ 363 public Set uniqueSet() { 364 return UnmodifiableSet.decorate(_map.keySet()); 365 } 366 367 /** 368 * Returns the number of elements in this bag. 369 * 370 * @return the number of elements in this bag 371 */ 372 public int size() { 373 return _total; 374 } 375 376 /** 377 * Actually walks the bag to make sure the count is correct and 378 * resets the running total 379 * 380 * @return the current total size 381 */ 382 protected int calcTotalSize() { 383 _total = extractList().size(); 384 return _total; 385 } 386 387 /** 388 * Utility method for implementations to set the map that backs 389 * this bag. Not intended for interactive use outside of 390 * subclasses. 391 */ 392 protected void setMap(Map map) { 393 if (map == null || map.isEmpty() == false) { 394 throw new IllegalArgumentException("The map must be non-null and empty"); 395 } 396 _map = map; 397 } 398 399 /** 400 * Utility method for implementations to access the map that backs 401 * this bag. Not intended for interactive use outside of 402 * subclasses. 403 */ 404 protected Map getMap() { 405 return _map; 406 } 407 408 /** 409 * Create a list for use in iteration, etc. 410 */ 411 private List extractList() { 412 List result = new ArrayList(); 413 Iterator i = uniqueSet().iterator(); 414 while (i.hasNext()) { 415 Object current = i.next(); 416 for (int index = getCount(current); index > 0; index--) { 417 result.add(current); 418 } 419 } 420 return result; 421 } 422 423 /** 424 * Return number of modifications for iterator. 425 * 426 * @return the modification count 427 */ 428 private int modCount() { 429 return _mods; 430 } 431 432 /** 433 * Implement a toString() method suitable for debugging. 434 * 435 * @return a debugging toString 436 */ 437 public String toString() { 438 StringBuffer buf = new StringBuffer(); 439 buf.append("["); 440 Iterator i = uniqueSet().iterator(); 441 while (i.hasNext()) { 442 Object current = i.next(); 443 int count = getCount(current); 444 buf.append(count); 445 buf.append(":"); 446 buf.append(current); 447 if (i.hasNext()) { 448 buf.append(","); 449 } 450 } 451 buf.append("]"); 452 return buf.toString(); 453 } 454 455 }