commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From scolebou...@apache.org
Subject cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections DefaultMapEntry.java DoubleOrderedMap.java DefaultMapBag.java
Date Fri, 16 May 2003 14:24:55 GMT
scolebourne    2003/05/16 07:24:55

  Modified:    collections/src/java/org/apache/commons/collections
                        DefaultMapEntry.java DoubleOrderedMap.java
                        DefaultMapBag.java
  Log:
  Update licence and javadoc
  
  Revision  Changes    Path
  1.9       +42 -41    jakarta-commons/collections/src/java/org/apache/commons/collections/DefaultMapEntry.java
  
  Index: DefaultMapEntry.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/DefaultMapEntry.java,v
  retrieving revision 1.8
  retrieving revision 1.9
  diff -u -r1.8 -r1.9
  --- DefaultMapEntry.java	15 Aug 2002 20:04:31 -0000	1.8
  +++ DefaultMapEntry.java	16 May 2003 14:24:54 -0000	1.9
  @@ -1,13 +1,10 @@
   /*
    * $Header$
  - * $Revision$
  - * $Date$
  - *
    * ====================================================================
    *
    * The Apache Software License, Version 1.1
    *
  - * Copyright (c) 1999-2002 The Apache Software Foundation.  All rights
  + * Copyright (c) 2001-2003 The Apache Software Foundation.  All rights
    * reserved.
    *
    * Redistribution and use in source and binary forms, with or without
  @@ -23,11 +20,11 @@
    *    distribution.
    *
    * 3. The end-user documentation included with the redistribution, if
  - *    any, must include the following acknowlegement:
  + *    any, must include the following acknowledgment:
    *       "This product includes software developed by the
    *        Apache Software Foundation (http://www.apache.org/)."
  - *    Alternately, this acknowlegement may appear in the software itself,
  - *    if and wherever such third-party acknowlegements normally appear.
  + *    Alternately, this acknowledgment may appear in the software itself,
  + *    if and wherever such third-party acknowledgments normally appear.
    *
    * 4. The names "The Jakarta Project", "Commons", and "Apache Software
    *    Foundation" must not be used to endorse or promote products derived
  @@ -36,7 +33,7 @@
    *
    * 5. Products derived from this software may not be called "Apache"
    *    nor may "Apache" appear in their names without prior written
  - *    permission of the Apache Group.
  + *    permission of the Apache Software Foundation.
    *
    * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
    * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  @@ -62,31 +59,35 @@
   
   import java.util.Map;
   
  -/** A default implementation of {@link java.util.Map.Entry}
  -  *
  -  * @since 1.0
  -  * @author <a href="mailto:jstrachan@apache.org">James Strachan</a>
  -  * @author <a href="mailto:mas@apache.org">Michael A. Smith</a>
  -  */
  -  
  +/**
  + * A default implementation of {@link java.util.Map.Entry}
  + *
  + * @since Commons Collections 1.0
  + * @version $Revision$ $Date$
  + * 
  + * @author <a href="mailto:jstrachan@apache.org">James Strachan</a>
  + * @author <a href="mailto:mas@apache.org">Michael A. Smith</a>
  + */
   public class DefaultMapEntry implements Map.Entry {
       
  +    /** The key */
       private Object key;
  +    /** The value */
       private Object value;
       
       /**
  -     *  Constructs a new <Code>DefaultMapEntry</Code> with a null key
  -     *  and null value.
  +     * Constructs a new <Code>DefaultMapEntry</Code> with a null key
  +     * and null value.
        */
       public DefaultMapEntry() {
       }
   
       /**
  -     *  Constructs a new <Code>DefaultMapEntry</Code> with the given
  -     *  key and given value.
  +     * Constructs a new <Code>DefaultMapEntry</Code> with the given
  +     * key and given value.
        *
  -     *  @param key  the key for the entry, may be null
  -     *  @param value  the value for the entyr, may be null
  +     * @param key  the key for the entry, may be null
  +     * @param value  the value for the entyr, may be null
        */
       public DefaultMapEntry(Object key, Object value) {
           this.key = key;
  @@ -94,9 +95,9 @@
       }
   
       /**
  -     *  Implemented per API documentation of 
  -     *  {@link java.util.Map.Entry#equals(Object)}
  -     **/
  +     * Implemented per API documentation of 
  +     * {@link java.util.Map.Entry#equals(Object)}
  +     */
       public boolean equals(Object o) {
           if( o == null ) return false;
           if( o == this ) return true;        
  @@ -112,9 +113,9 @@
        
        
       /**
  -     *  Implemented per API documentation of 
  -     *  {@link java.util.Map.Entry#hashCode()}
  -     **/
  +     * Implemented per API documentation of 
  +     * {@link java.util.Map.Entry#hashCode()}
  +     */
       public int hashCode() {
           return ( ( getKey() == null ? 0 : getKey().hashCode() ) ^
                    ( getValue() == null ? 0 : getValue().hashCode() ) ); 
  @@ -126,19 +127,18 @@
       //-------------------------------------------------------------------------
   
       /**
  -     *  Returns the key.
  +     * Returns the key.
        *
  -     *  @return the key 
  +     * @return the key 
        */
       public Object getKey() {
           return key;
       }
   
  -
       /**
  -     *  Returns the value.
  +     * Returns the value.
        *
  -     *  @return the value
  +     * @return the value
        */
       public Object getValue() {
           return value;
  @@ -148,20 +148,21 @@
       //-------------------------------------------------------------------------    
   
       /**
  -     *  Sets the key.  This method does not modify any map.
  +     * Sets the key.  This method does not modify any map.
        *
  -     *  @param key  the new key
  +     * @param key  the new key
        */
       public void setKey(Object key) {
           this.key = key;
       }
       
  -    /** Note that this method only sets the local reference inside this object and
  -      * does not modify the original Map.
  -      *
  -      * @return the old value of the value
  -      * @param value the new value
  -      */
  +    /** 
  +     * Note that this method only sets the local reference inside this object and
  +     * does not modify the original Map.
  +     *
  +     * @return the old value of the value
  +     * @param value the new value
  +     */
       public Object setValue(Object value) {
           Object answer = this.value;
           this.value = value;
  
  
  
  1.4       +130 -157  jakarta-commons/collections/src/java/org/apache/commons/collections/DoubleOrderedMap.java
  
  Index: DoubleOrderedMap.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/DoubleOrderedMap.java,v
  retrieving revision 1.3
  retrieving revision 1.4
  diff -u -r1.3 -r1.4
  --- DoubleOrderedMap.java	12 Oct 2002 22:15:18 -0000	1.3
  +++ DoubleOrderedMap.java	16 May 2003 14:24:54 -0000	1.4
  @@ -1,13 +1,10 @@
   /*
    * $Header$
  - * $Revision$
  - * $Date$
  - *
    * ====================================================================
    *
    * The Apache Software License, Version 1.1
    *
  - * Copyright (c) 1999-2002 The Apache Software Foundation.  All rights
  + * Copyright (c) 2002-2003 The Apache Software Foundation.  All rights
    * reserved.
    *
    * Redistribution and use in source and binary forms, with or without
  @@ -23,11 +20,11 @@
    *    distribution.
    *
    * 3. The end-user documentation included with the redistribution, if
  - *    any, must include the following acknowlegement:
  + *    any, must include the following acknowledgment:
    *       "This product includes software developed by the
    *        Apache Software Foundation (http://www.apache.org/)."
  - *    Alternately, this acknowlegement may appear in the software itself,
  - *    if and wherever such third-party acknowlegements normally appear.
  + *    Alternately, this acknowledgment may appear in the software itself,
  + *    if and wherever such third-party acknowledgments normally appear.
    *
    * 4. The names "The Jakarta Project", "Commons", and "Apache Software
    *    Foundation" must not be used to endorse or promote products derived
  @@ -36,7 +33,7 @@
    *
    * 5. Products derived from this software may not be called "Apache"
    *    nor may "Apache" appear in their names without prior written
  - *    permission of the Apache Group.
  + *    permission of the Apache Software Foundation.
    *
    * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
    * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  @@ -58,11 +55,8 @@
    * <http://www.apache.org/>.
    *
    */
  -
   package org.apache.commons.collections;
   
  -
  -
   import java.util.AbstractCollection;
   import java.util.AbstractMap;
   import java.util.AbstractSet;
  @@ -73,105 +67,99 @@
   import java.util.NoSuchElementException;
   import java.util.Set;
   
  -
   /**
  -* Red-Black tree-based implementation of Map. This class guarantees
  -* that the map will be in both ascending key order and ascending
  -* value order, sorted according to the natural order for the key's
  -* and value's classes.<p>
  -*
  -* This Map is intended for applications that need to be able to look
  -* up a key-value pairing by either key or value, and need to do so
  -* with equal efficiency.<p>
  -*
  -* While that goal could be accomplished by taking a pair of TreeMaps
  -* and redirecting requests to the appropriate TreeMap (e.g.,
  -* containsKey would be directed to the TreeMap that maps values to
  -* keys, containsValue would be directed to the TreeMap that maps keys
  -* to values), there are problems with that implementation,
  -* particularly when trying to keep the two TreeMaps synchronized with
  -* each other. And if the data contained in the TreeMaps is large, the
  -* cost of redundant storage becomes significant.<p>
  -*
  -* This solution keeps the data properly synchronized and minimizes
  -* the data storage. The red-black algorithm is based on TreeMap's,
  -* but has been modified to simultaneously map a tree node by key and
  -* by value. This doubles the cost of put operations (but so does
  -* using two TreeMaps), and nearly doubles the cost of remove
  -* operations (there is a savings in that the lookup of the node to be
  -* removed only has to be performed once). And since only one node
  -* contains the key and value, storage is significantly less than that
  -* required by two TreeMaps.<p>
  -*
  -* There are some limitations placed on data kept in this Map. The
  -* biggest one is this:<p>
  -*
  -* When performing a put operation, neither the key nor the value may
  -* already exist in the Map. In the java.util Map implementations
  -* (HashMap, TreeMap), you can perform a put with an already mapped
  -* key, and neither cares about duplicate values at all ... but this
  -* implementation's put method with throw an IllegalArgumentException
  -* if either the key or the value is already in the Map.<p>
  -*
  -* Obviously, that same restriction (and consequence of failing to
  -* heed that restriction) applies to the putAll method.<p>
  -*
  -* The Map.Entry instances returned by the appropriate methods will
  -* not allow setValue() and will throw an
  -* UnsupportedOperationException on attempts to call that method.<p>
  -*
  -* New methods are added to take advantage of the fact that values are
  -* kept sorted independently of their keys:<p>
  -*
  -* Object getKeyForValue(Object value) is the opposite of get; it
  -* takes a value and returns its key, if any.<p>
  -*
  -* Object removeValue(Object value) finds and removes the specified
  -* value and returns the now un-used key.<p>
  -*
  -* Set entrySetByValue() returns the Map.Entry's in a Set whose
  -* iterator will iterate over the Map.Entry's in ascending order by
  -* their corresponding values.<p>
  -*
  -* Set keySetByValue() returns the keys in a Set whose iterator will
  -* iterate over the keys in ascending order by their corresponding
  -* values.<p>
  -*
  -* Collection valuesByValue() returns the values in a Collection whose
  -* iterator will iterate over the values in ascending order.<p>
  -*
  -* @since 2.0
  -* @author Marc Johnson (marcj at users dot sourceforge dot net)
  -*/
  -
  -// final for performance
  + * Red-Black tree-based implementation of Map. This class guarantees
  + * that the map will be in both ascending key order and ascending
  + * value order, sorted according to the natural order for the key's
  + * and value's classes.<p>
  + *
  + * This Map is intended for applications that need to be able to look
  + * up a key-value pairing by either key or value, and need to do so
  + * with equal efficiency.<p>
  + *
  + * While that goal could be accomplished by taking a pair of TreeMaps
  + * and redirecting requests to the appropriate TreeMap (e.g.,
  + * containsKey would be directed to the TreeMap that maps values to
  + * keys, containsValue would be directed to the TreeMap that maps keys
  + * to values), there are problems with that implementation,
  + * particularly when trying to keep the two TreeMaps synchronized with
  + * each other. And if the data contained in the TreeMaps is large, the
  + * cost of redundant storage becomes significant.<p>
  + *
  + * This solution keeps the data properly synchronized and minimizes
  + * the data storage. The red-black algorithm is based on TreeMap's,
  + * but has been modified to simultaneously map a tree node by key and
  + * by value. This doubles the cost of put operations (but so does
  + * using two TreeMaps), and nearly doubles the cost of remove
  + * operations (there is a savings in that the lookup of the node to be
  + * removed only has to be performed once). And since only one node
  + * contains the key and value, storage is significantly less than that
  + * required by two TreeMaps.<p>
  + *
  + * There are some limitations placed on data kept in this Map. The
  + * biggest one is this:<p>
  + *
  + * When performing a put operation, neither the key nor the value may
  + * already exist in the Map. In the java.util Map implementations
  + * (HashMap, TreeMap), you can perform a put with an already mapped
  + * key, and neither cares about duplicate values at all ... but this
  + * implementation's put method with throw an IllegalArgumentException
  + * if either the key or the value is already in the Map.<p>
  + *
  + * Obviously, that same restriction (and consequence of failing to
  + * heed that restriction) applies to the putAll method.<p>
  + *
  + * The Map.Entry instances returned by the appropriate methods will
  + * not allow setValue() and will throw an
  + * UnsupportedOperationException on attempts to call that method.<p>
  + *
  + * New methods are added to take advantage of the fact that values are
  + * kept sorted independently of their keys:<p>
  + *
  + * Object getKeyForValue(Object value) is the opposite of get; it
  + * takes a value and returns its key, if any.<p>
  + *
  + * Object removeValue(Object value) finds and removes the specified
  + * value and returns the now un-used key.<p>
  + *
  + * Set entrySetByValue() returns the Map.Entry's in a Set whose
  + * iterator will iterate over the Map.Entry's in ascending order by
  + * their corresponding values.<p>
  + *
  + * Set keySetByValue() returns the keys in a Set whose iterator will
  + * iterate over the keys in ascending order by their corresponding
  + * values.<p>
  + *
  + * Collection valuesByValue() returns the values in a Collection whose
  + * iterator will iterate over the values in ascending order.<p>
  + *
  + * @since Commons Collections 2.0
  + * @version $Revision$ $Date$
  + * 
  + * @author Marc Johnson (marcj at users dot sourceforge dot net)
  + */
   public final class DoubleOrderedMap extends AbstractMap {
  +//  final for performance
   
  -    private Node[]                rootNode           = new Node[]{ null,
  -                                                           null };
  -    private int                   nodeCount          = 0;
  -    private int                   modifications      = 0;
  -    private Set[]                 setOfKeys          = new Set[]{ null,
  -                                                           null };
  -    private Set[]                 setOfEntries       = new Set[]{ null,
  -                                                           null };
  -    private Collection[]          collectionOfValues = new Collection[]{ 
  -null,
  -                                                                         
  -null };
  -    private static final int      KEY                = 0;
  -    private static final int      VALUE              = 1;
  -    private static final int      SUM_OF_INDICES     = KEY + VALUE;
  -    private static final int      FIRST_INDEX        = 0;
  -    private static final int      NUMBER_OF_INDICES  = 2;
  -    private static final String[] dataName           = new String[]{ "key",
  -                                                                     "value" 
  -};
  +    private static final int KEY = 0;
  +    private static final int VALUE = 1;
  +    private static final int SUM_OF_INDICES = KEY + VALUE;
  +    private static final int FIRST_INDEX = 0;
  +    private static final int NUMBER_OF_INDICES = 2;
  +    private static final String[] dataName = new String[] { "key", "value" };
  +    
  +    private Node[] rootNode = new Node[] { null, null };
  +    private int nodeCount = 0;
  +    private int modifications = 0;
  +    private Set[] setOfKeys = new Set[] { null, null };
  +    private Set[] setOfEntries = new Set[] { null, null };
  +    private Collection[] collectionOfValues = new Collection[] { null, null };
   
       /**
        * Construct a new DoubleOrderedMap
        */
  -    public DoubleOrderedMap() {}
  +    public DoubleOrderedMap() {
  +    }
   
       /**
        * Constructs a new DoubleOrderedMap from an existing Map, with keys and
  @@ -179,14 +167,14 @@
        *
        * @param map the map whose mappings are to be placed in this map.
        *
  -     * @exception ClassCastException if the keys in the map are not
  +     * @throws ClassCastException if the keys in the map are not
        *                               Comparable, or are not mutually
        *                               comparable; also if the values in
        *                               the map are not Comparable, or
        *                               are not mutually Comparable
  -     * @exception NullPointerException if any key or value in the map
  +     * @throws NullPointerException if any key or value in the map
        *                                 is null
  -     * @exception IllegalArgumentException if there are duplicate keys
  +     * @throws IllegalArgumentException if there are duplicate keys
        *                                     or duplicate values in the
        *                                     map
        */
  @@ -205,9 +193,9 @@
        * @return the key to which this map maps the specified value, or
        *         null if the map contains no mapping for this value.
        *
  -     * @exception ClassCastException if the value is of an
  +     * @throws ClassCastException if the value is of an
        *                               inappropriate type for this map.
  -     * @exception NullPointerException if the value is null
  +     * @throws NullPointerException if the value is null
        */
       public Object getKeyForValue(final Object value)
               throws ClassCastException, NullPointerException {
  @@ -847,8 +835,7 @@
        * @param insertedNode the node to be inserted
        * @param index KEY or VALUE
        */
  -    private void doRedBlackInsert(final Node insertedNode, final int index) 
  -{
  +    private void doRedBlackInsert(final Node insertedNode, final int index) {
   
           Node currentNode = insertedNode;
   
  @@ -904,8 +891,7 @@
                       makeRed(getGrandParent(currentNode, index), index);
   
                       if (getGrandParent(currentNode, index) != null) {
  -                        rotateLeft(getGrandParent(currentNode, index), 
  -index);
  +                        rotateLeft(getGrandParent(currentNode, index), index);
                       }
                   }
               }
  @@ -943,11 +929,9 @@
                       rootNode[index] = replacement;
                   } else if (deletedNode
                              == deletedNode.getParent(index).getLeft(index)) {
  -                    deletedNode.getParent(index).setLeft(replacement, 
  -index);
  +                    deletedNode.getParent(index).setLeft(replacement, index);
                   } else {
  -                    deletedNode.getParent(index).setRight(replacement, 
  -index);
  +                    deletedNode.getParent(index).setRight(replacement, index);
                   }
   
                   deletedNode.setLeft(null, index);
  @@ -975,8 +959,7 @@
                           if (deletedNode
                                   == deletedNode.getParent(index)
                                       .getLeft(index)) {
  -                            deletedNode.getParent(index).setLeft(null, 
  -index);
  +                            deletedNode.getParent(index).setLeft(null, index);
                           } else {
                               deletedNode.getParent(index).setRight(null,
                                                     index);
  @@ -1016,9 +999,7 @@
                       makeRed(getParent(currentNode, index), index);
                       rotateLeft(getParent(currentNode, index), index);
   
  -                    siblingNode = getRightChild(getParent(currentNode, 
  -index),
  -                                                index);
  +                    siblingNode = getRightChild(getParent(currentNode, index), index);
                   }
   
                   if (isBlack(getLeftChild(siblingNode, index), index)
  @@ -1034,8 +1015,7 @@
                           rotateRight(siblingNode, index);
   
                           siblingNode =
  -                            getRightChild(getParent(currentNode, index),
  -                                          index);
  +                            getRightChild(getParent(currentNode, index), index);
                       }
   
                       copyColor(getParent(currentNode, index), siblingNode,
  @@ -1047,23 +1027,18 @@
                       currentNode = rootNode[index];
                   }
               } else {
  -                Node siblingNode = getLeftChild(getParent(currentNode, 
  -index),
  -                                                index);
  +                Node siblingNode = getLeftChild(getParent(currentNode, index), index);
   
                   if (isRed(siblingNode, index)) {
                       makeBlack(siblingNode, index);
                       makeRed(getParent(currentNode, index), index);
                       rotateRight(getParent(currentNode, index), index);
   
  -                    siblingNode = getLeftChild(getParent(currentNode, 
  -index),
  -                                               index);
  +                    siblingNode = getLeftChild(getParent(currentNode, index), index);
                   }
   
                   if (isBlack(getRightChild(siblingNode, index), index)
  -                        && isBlack(getLeftChild(siblingNode, index), index)) 
  -{
  +                        && isBlack(getLeftChild(siblingNode, index), index)) {
                       makeRed(siblingNode, index);
   
                       currentNode = getParent(currentNode, index);
  @@ -1074,8 +1049,7 @@
                           rotateLeft(siblingNode, index);
   
                           siblingNode =
  -                            getLeftChild(getParent(currentNode, index),
  -                                         index);
  +                            getLeftChild(getParent(currentNode, index), index);
                       }
   
                       copyColor(getParent(currentNode, index), siblingNode,
  @@ -1203,8 +1177,8 @@
        * @param index KEY or VALUE (used to put the right word in the
        *              exception message)
        *
  -     * @exception NullPointerException if o is null
  -     * @exception ClassCastException if o is not Comparable
  +     * @throws NullPointerException if o is null
  +     * @throws ClassCastException if o is not Comparable
        */
       private static void checkNonNullComparable(final Object o,
                                                  final int index) {
  @@ -1225,8 +1199,8 @@
        *
        * @param key the key to be checked
        *
  -     * @exception NullPointerException if key is null
  -     * @exception ClassCastException if key is not Comparable
  +     * @throws NullPointerException if key is null
  +     * @throws ClassCastException if key is not Comparable
        */
       private static void checkKey(final Object key) {
           checkNonNullComparable(key, KEY);
  @@ -1237,8 +1211,8 @@
        *
        * @param value the value to be checked
        *
  -     * @exception NullPointerException if value is null
  -     * @exception ClassCastException if value is not Comparable
  +     * @throws NullPointerException if value is null
  +     * @throws ClassCastException if value is not Comparable
        */
       private static void checkValue(final Object value) {
           checkNonNullComparable(value, VALUE);
  @@ -1251,8 +1225,8 @@
        * @param key the key to be checked
        * @param value the value to be checked
        *
  -     * @exception NullPointerException if key or value is null
  -     * @exception ClassCastException if key or value is not Comparable
  +     * @throws NullPointerException if key or value is null
  +     * @throws ClassCastException if key or value is not Comparable
        */
       private static void checkKeyAndValue(final Object key,
                                            final Object value) {
  @@ -1294,7 +1268,7 @@
        *
        * @param newNode the node to be inserted
        *
  -     * @exception IllegalArgumentException if the node already exists
  +     * @throws IllegalArgumentException if the node already exists
        *                                     in the value mapping
        */
       private void insertValue(final Node newNode)
  @@ -1355,9 +1329,9 @@
        * @return true if this map contains a mapping for the specified
        *         key.
        *
  -     * @exception ClassCastException if the key is of an inappropriate
  +     * @throws ClassCastException if the key is of an inappropriate
        *                               type for this map.
  -     * @exception NullPointerException if the key is null
  +     * @throws NullPointerException if the key is null
        */
       public boolean containsKey(final Object key)
               throws ClassCastException, NullPointerException {
  @@ -1392,9 +1366,9 @@
        * @return the value to which this map maps the specified key, or
        *         null if the map contains no mapping for this key.
        *
  -     * @exception ClassCastException if the key is of an inappropriate
  +     * @throws ClassCastException if the key is of an inappropriate
        *                               type for this map.
  -     * @exception NullPointerException if the key is null
  +     * @throws NullPointerException if the key is null
        */
       public Object get(final Object key)
               throws ClassCastException, NullPointerException {
  @@ -1411,12 +1385,12 @@
        *
        * @return null
        *
  -     * @exception ClassCastException if the class of the specified key
  +     * @throws ClassCastException if the class of the specified key
        *                               or value prevents it from being
        *                               stored in this map.
  -     * @exception NullPointerException if the specified key or value
  +     * @throws NullPointerException if the specified key or value
        *                                 is null
  -     * @exception IllegalArgumentException if the key duplicates an
  +     * @throws IllegalArgumentException if the key duplicates an
        *                                     existing key, or if the
        *                                     value duplicates an
        *                                     existing value
  @@ -1680,8 +1654,7 @@
                       Node      node  = lookup((Comparable) entry.getKey(),
                                                KEY);
   
  -                    if ((node != null) && node.getData(VALUE).equals(value)) 
  -{
  +                    if ((node != null) && node.getData(VALUE).equals(value)) {
                           doRedBlackDelete(node);
   
                           return true;
  @@ -1743,9 +1716,9 @@
           /**
            * @return the next element in the iteration.
            *
  -         * @exception NoSuchElementException if iteration has no more
  +         * @throws NoSuchElementException if iteration has no more
            *                                   elements.
  -         * @exception ConcurrentModificationException if the
  +         * @throws ConcurrentModificationException if the
            *                                            DoubleOrderedMap is
            *                                            modified behind
            *                                            the iterator's
  @@ -1777,12 +1750,12 @@
            * the iteration is in progress in any way other than by
            * calling this method.
            *
  -         * @exception IllegalStateException if the next method has not
  +         * @throws IllegalStateException if the next method has not
            *                                  yet been called, or the
            *                                  remove method has already
            *                                  been called after the last
            *                                  call to the next method.
  -         * @exception ConcurrentModificationException if the
  +         * @throws ConcurrentModificationException if the
            *                                            DoubleOrderedMap is
            *                                            modified behind
            *                                            the iterator's
  @@ -2000,7 +1973,7 @@
            *
            * @return does not return
            *
  -         * @exception UnsupportedOperationException
  +         * @throws UnsupportedOperationException
            */
           public Object setValue(Object ignored)
                   throws UnsupportedOperationException {
  
  
  
  1.8       +388 -359  jakarta-commons/collections/src/java/org/apache/commons/collections/DefaultMapBag.java
  
  Index: DefaultMapBag.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/DefaultMapBag.java,v
  retrieving revision 1.7
  retrieving revision 1.8
  diff -u -r1.7 -r1.8
  --- DefaultMapBag.java	13 Jan 2003 23:54:38 -0000	1.7
  +++ DefaultMapBag.java	16 May 2003 14:24:55 -0000	1.8
  @@ -1,9 +1,10 @@
   /*
    * $Header$
    * ====================================================================
  + *
    * The Apache Software License, Version 1.1
    *
  - * Copyright (c) 1999-2003 The Apache Software Foundation.  All rights
  + * Copyright (c) 2002-2003 The Apache Software Foundation.  All rights
    * reserved.
    *
    * Redistribution and use in source and binary forms, with or without
  @@ -54,7 +55,6 @@
    * <http://www.apache.org/>.
    *
    */
  -
   package org.apache.commons.collections;
   
   import java.util.ArrayList;
  @@ -72,383 +72,412 @@
    * Subclasses need only to call <code>setMap(Map)</code> in their constructor 
    * (or invoke the {@link #DefaultMapBag(java.util.Map) Map-constructor})
    * specifying a map instance that will be used to store the contents of 
  - * the bag.<P>
  - *
  + * the bag.
  + * <p>
    * The map will be used to map bag elements to a number; the number represents
  - * the number of occurrences of that element in the bag.<P>
  + * the number of occurrences of that element in the bag.
    *
    * @since Commons Collections 2.0
    * @version $Revision$ $Date$
  + * 
    * @author Chuck Burdick
    * @author <a href="mailto:mas@apache.org">Michael A. Smith</a>
  - **/
  + * @author Stephen Colebourne
  + */
   public abstract class DefaultMapBag implements Bag {
  -   private Map _map = null;
  -   private int _total = 0;
  -   private int _mods = 0;
  -
  -
  -   /**
  -    *  No-argument constructor.  
  -    *  Subclasses should invoke <code>setMap(Map)</code> in
  -    *  their constructors.
  -    */
  -   public DefaultMapBag() {
  -   }
  -   
  -   /**
  -    * @since Commons Collections 2.2
  -    */
  -   public DefaultMapBag(Map map) {
  -      setMap(map);
  -   }
  -
  -   /**
  -    *  Adds a new element to the bag by incrementing its count in the 
  -    *  underlying map.
  -    *
  -    *  @see Bag#add(Object) 
  -    */
  -   public boolean add(Object o) {
  -      return add(o, 1);
  -   }
  -
  -   /**
  -    *  Adds a new element to the bag by incrementing its count in the map.
  -    *
  -    *  @see Bag#add(Object, int)
  -    */
  -   public boolean add(Object o, int i) {
  -      _mods++;
  -      if (i > 0) {
  -         int count = (i + getCount(o));
  -         _map.put(o, new Integer(count));
  -         _total += i;
  -         return (count == i);
  -      } else {
  -         return false;
  -      }
  -   }
  -
  -   /**
  -    *  Invokes {@link #add(Object)} for each element in the given collection.
  -    *
  -    *  @see Bag#addAll(Collection)
  -    */
  -   public boolean addAll(Collection c) {
  -      boolean changed = false;
  -      Iterator i = c.iterator();
  -      while (i.hasNext()) {
  -         boolean added = add(i.next());
  -         changed = changed || added;
  -      }
  -      return changed;
  -   }
  -
  -
  -   /**
  -    *  Clears the bag by clearing the underlying map.
  -    */
  -   public void clear() {
  -      _mods++;
  -      _map.clear();
  -      _total = 0;
  -   }
  -
  -   /**
  -    *  Determines if the bag contains the given element by checking if the
  -    *  underlying map contains the element as a key.
  -    *
  -    *  @return true if the bag contains the given element
  -    */
  -   public boolean contains(Object o) {
  -      return _map.containsKey(o);
  -   }
  -
  -   public boolean containsAll(Collection c) {
  -      return containsAll(new HashBag(c));
  -   }
  -
  -   /**
  -    * Returns <code>true</code> if the bag contains all elements in
  -    * the given collection, respecting cardinality.
  -    * @see #containsAll(Collection)
  -    **/
  -   public boolean containsAll(Bag other) {
  -      boolean result = true;
  -      Iterator i = other.uniqueSet().iterator();
  -      while (i.hasNext()) {
  -         Object current = i.next();
  -         boolean contains =
  -            getCount(current) >= ((Bag)other).getCount(current);
  -         result = result && contains;
  -      }
  -      return result;
  -   }
  -
  -   /**
  -    * Returns true if the given object is not null, has the precise type 
  -    * of this bag, and contains the same number of occurrences of all the
  -    * same elements.
  -    *
  -    * @param o the object to test for equality
  -    * @return true if that object equals this bag
  -    */
  -   public boolean equals(Object o) {
  -      return (o == this || 
  -              (o != null && o.getClass().equals(this.getClass()) &&
  -               ((DefaultMapBag)o)._map.equals(this._map)));
  -   }
  -
  -   /**
  -    * Returns the hash code of the underlying map.
  -    *
  -    * @return the hash code of the underlying map
  -    */
  -   public int hashCode() {
  -      return _map.hashCode();
  -   }
  -
  -   /**
  -    * Returns true if the underlying map is empty.
  -    *
  -    * @return true if there are no elements in this bag
  -    */
  -   public boolean isEmpty() {
  -      return _map.isEmpty();
  -   }
  -
  -   public Iterator iterator() {
  -      return new BagIterator(this, extractList().iterator()); 
  -   }
  -
  -   private class BagIterator implements Iterator {
  -      private DefaultMapBag _parent = null;
  -      private Iterator _support = null;
  -      private Object _current = null;
  -      private int _mods = 0;
  -
  -      public BagIterator(DefaultMapBag parent, Iterator support) {
  -         _parent = parent;
  -         _support = support;
  -         _current = null;
  -         _mods = parent.modCount();
  -      }
  -
  -      public boolean hasNext() {
  -         return _support.hasNext();
  -      }
  -
  -      public Object next() {
  -         if (_parent.modCount() != _mods) {
  -            throw new ConcurrentModificationException();
  -         }
  -         _current = _support.next();
  -         return _current;
  -      }
  -      
  -      public void remove() {
  -         if (_parent.modCount() != _mods) {
  -            throw new ConcurrentModificationException();
  -         }
  -         _support.remove();
  -         _parent.remove(_current, 1);
  -         _mods++;
  -      }
  -   }
  -
  -   public boolean remove (Object o) {
  -      return remove(o, getCount(o));
  -   }
  -
  -   public boolean remove (Object o, int i) {
  -      _mods++;
  -      boolean result = false;
  -      int count = getCount(o);
  -      if (i <= 0) {
  -         result = false;
  -      } else if (count > i) {
  -         _map.put(o, new Integer(count - i));
  -         result = true;
  -         _total -= i;
  -      } else { // count > 0 && count <= i  
  -         // need to remove all
  -         result = (_map.remove(o) != null);
  -         _total -= count;
  -      }
  -      return result;
  -   }
  -
  -   public boolean removeAll(Collection c) {
  -      boolean result = false;
  -      if (c != null) {
  -         Iterator i = c.iterator();
  -         while (i.hasNext()) {
  -            boolean changed = remove(i.next(), 1);
  -            result = result || changed;
  -         }
  -      }
  -      return result;
  -   }
  -
  -   /**
  -    * Remove any members of the bag that are not in the given
  -    * bag, respecting cardinality.
  -    *
  -    * @return true if this call changed the collection
  -    */
  -   public boolean retainAll(Collection c) {
  -      return retainAll(new HashBag(c));
  -   }
  -
  -   /**
  -    * Remove any members of the bag that are not in the given
  -    * bag, respecting cardinality.
  -    * @see #retainAll(Collection)
  -    * @return <code>true</code> if this call changed the collection
  -    **/
  -   public boolean retainAll(Bag other) {
  -      boolean result = false;
  -      Bag excess = new HashBag();
  -      Iterator i = uniqueSet().iterator();
  -      while (i.hasNext()) {
  -         Object current = i.next();
  -         int myCount = getCount(current);
  -         int otherCount = other.getCount(current);
  -         if (1 <= otherCount && otherCount <= myCount) {
  -            excess.add(current, myCount - otherCount);
  -         } else {
  -            excess.add(current, myCount);
  -         }
  -      }
  -      if (!excess.isEmpty()) {
  -         result = removeAll(excess);
  -      }
  -      return result;
  -   }
  -
  -   /**
  -    *  Returns an array of all of this bag's elements.
  -    *
  -    *  @return an array of all of this bag's elements
  -    */
  -   public Object[] toArray() {
  -      return extractList().toArray();
  -   }
  -
  -   /**
  -    *  Returns an array of all of this bag's elements.
  -    *
  -    *  @param a  the array to populate
  -    *  @return an array of all of this bag's elements
  -    */
  -   public Object[] toArray(Object[] a) {
  -      return extractList().toArray(a);
  -   }
  -
  -   /**
  -    *  Returns the number of occurrence of the given element in this bag
  -    *  by looking up its count in the underlying map.
  -    *
  -    *  @see Bag#getCount(Object)
  -    */
  -   public int getCount(Object o) {
  -      int result = 0;
  -      Integer count = MapUtils.getInteger(_map, o);
  -      if (count != null) {
  -         result = count.intValue();
  -      }
  -      return result;
  -   }
  -
  -   /**
  -    *  Returns an unmodifiable view of the underlying map's key set.
  -    *
  -    *  @return the set of unique elements in this bag
  -    */
  -   public Set uniqueSet() {
  -      return Collections.unmodifiableSet(_map.keySet());
  -   }
  -
  -   /**
  -    *  Returns the number of elements in this bag.
  -    *
  -    *  @return the number of elements in this bag
  -    */
  -   public int size() {
  -      return _total;
  -   }
  -
  -   /**
  -    * Actually walks the bag to make sure the count is correct and
  -    * resets the running total
  -    **/
  -   protected int calcTotalSize() {
  -      _total = extractList().size();
  -      return _total;
  -   }
  -
  -   /**
  -    * Utility method for implementations to set the map that backs
  -    * this bag. Not intended for interactive use outside of
  -    * subclasses.
  -    **/
  -   protected void setMap(Map m) {
  -      _map = m;
  -   }
  -
  -   /**
  -    * Utility method for implementations to access the map that backs
  -    * this bag. Not intended for interactive use outside of
  -    * subclasses.
  -    **/
  -   protected Map getMap() {
  -      return _map;
  -   }
  -
  -   /**
  -    * Create a list for use in iteration, etc.
  -    **/
  -   private List extractList() {
  -      List result = new ArrayList();
  -      Iterator i = uniqueSet().iterator();
  -      while (i.hasNext()) {
  -         Object current = i.next();
  -         for (int index = getCount(current); index > 0; index--) {
  -            result.add(current);
  -         }
  -      }
  -      return result;
  -   }
  -
  -   /**
  -    * Return number of modifications for iterator
  -    **/
  -   private int modCount() {
  -      return _mods;
  -   }
  +    private Map _map = null;
  +    private int _total = 0;
  +    private int _mods = 0;
  +
  +    /**
  +     * No-argument constructor.  
  +     * Subclasses should invoke <code>setMap(Map)</code> in
  +     * their constructors.
  +     */
  +    public DefaultMapBag() {
  +    }
  +
  +    /**
  +     * Constructor that assigns the specified Map as the backing store.
  +     * The map must be empty.
  +     * 
  +     * @param map  the map to assign
  +     */
  +    protected DefaultMapBag(Map map) {
  +        setMap(map);
  +    }
  +
  +    /**
  +     * Adds a new element to the bag by incrementing its count in the 
  +     * underlying map.
  +     *
  +     * @param object  the object to add
  +     * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
  +     */
  +    public boolean add(Object object) {
  +        return add(object, 1);
  +    }
  +
  +    /**
  +     * Adds a new element to the bag by incrementing its count in the map.
  +     *
  +     * @param object  the object to search for
  +     * @param nCopies  the number of copies to add
  +     * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
  +     */
  +    public boolean add(Object object, int nCopies) {
  +        _mods++;
  +        if (nCopies > 0) {
  +            int count = (nCopies + getCount(object));
  +            _map.put(object, new Integer(count));
  +            _total += nCopies;
  +            return (count == nCopies);
  +        } else {
  +            return false;
  +        }
  +    }
  +
  +    /**
  +     * Invokes {@link #add(Object)} for each element in the given collection.
  +     *
  +     * @param coll  the collection to add
  +     * @return <code>true</code> if this call changed the bag
  +     */
  +    public boolean addAll(Collection coll) {
  +        boolean changed = false;
  +        Iterator i = coll.iterator();
  +        while (i.hasNext()) {
  +            boolean added = add(i.next());
  +            changed = changed || added;
  +        }
  +        return changed;
  +    }
  +
  +    /**
  +     * Clears the bag by clearing the underlying map.
  +     */
  +    public void clear() {
  +        _mods++;
  +        _map.clear();
  +        _total = 0;
  +    }
  +
  +    /**
  +     * Determines if the bag contains the given element by checking if the
  +     * underlying map contains the element as a key.
  +     *
  +     * @param object  the object to search for
  +     * @return true if the bag contains the given element
  +     */
  +    public boolean contains(Object object) {
  +        return _map.containsKey(object);
  +    }
  +
  +    /**
  +     * Determines if the bag contains the given elements.
  +     * 
  +     * @param coll  the collection to check against
  +     * @return <code>true</code> if the Bag contains all the collection
  +     */
  +    public boolean containsAll(Collection coll) {
  +        return containsAll(new HashBag(coll));
  +    }
   
       /**
  -     *  Implement a toString() method suitable for debugging
  -     **/
  +     * Returns <code>true</code> if the bag contains all elements in
  +     * the given collection, respecting cardinality.
  +     * 
  +     * @param other  the bag to check against
  +     * @return <code>true</code> if the Bag contains all the collection
  +     */
  +    public boolean containsAll(Bag other) {
  +        boolean result = true;
  +        Iterator i = other.uniqueSet().iterator();
  +        while (i.hasNext()) {
  +            Object current = i.next();
  +            boolean contains = getCount(current) >= ((Bag) other).getCount(current);
  +            result = result && contains;
  +        }
  +        return result;
  +    }
  +
  +    /**
  +     * Returns true if the given object is not null, has the precise type 
  +     * of this bag, and contains the same number of occurrences of all the
  +     * same elements.
  +     *
  +     * @param object  the object to test for equality
  +     * @return true if that object equals this bag
  +     */
  +    public boolean equals(Object object) {
  +        if (object == this) {
  +            return true;
  +        }
  +        return (object != null &&
  +                object.getClass().equals(this.getClass()) &&
  +                ((DefaultMapBag) object)._map.equals(this._map));
  +    }
  +
  +    /**
  +     * Returns the hash code of the underlying map.
  +     *
  +     * @return the hash code of the underlying map
  +     */
  +    public int hashCode() {
  +        return _map.hashCode();
  +    }
  +
  +    /**
  +     * Returns true if the underlying map is empty.
  +     *
  +     * @return true if there are no elements in this bag
  +     */
  +    public boolean isEmpty() {
  +        return _map.isEmpty();
  +    }
  +
  +    public Iterator iterator() {
  +        return new BagIterator(this, extractList().iterator());
  +    }
  +
  +    private class BagIterator implements Iterator {
  +        private DefaultMapBag _parent = null;
  +        private Iterator _support = null;
  +        private Object _current = null;
  +        private int _mods = 0;
  +
  +        public BagIterator(DefaultMapBag parent, Iterator support) {
  +            _parent = parent;
  +            _support = support;
  +            _current = null;
  +            _mods = parent.modCount();
  +        }
  +
  +        public boolean hasNext() {
  +            return _support.hasNext();
  +        }
  +
  +        public Object next() {
  +            if (_parent.modCount() != _mods) {
  +                throw new ConcurrentModificationException();
  +            }
  +            _current = _support.next();
  +            return _current;
  +        }
  +
  +        public void remove() {
  +            if (_parent.modCount() != _mods) {
  +                throw new ConcurrentModificationException();
  +            }
  +            _support.remove();
  +            _parent.remove(_current, 1);
  +            _mods++;
  +        }
  +    }
  +
  +    public boolean remove(Object object) {
  +        return remove(object, getCount(object));
  +    }
  +
  +    public boolean remove(Object object, int nCopies) {
  +        _mods++;
  +        boolean result = false;
  +        int count = getCount(object);
  +        if (nCopies <= 0) {
  +            result = false;
  +        } else if (count > nCopies) {
  +            _map.put(object, new Integer(count - nCopies));
  +            result = true;
  +            _total -= nCopies;
  +        } else { // count > 0 && count <= i  
  +            // need to remove all
  +            result = (_map.remove(object) != null);
  +            _total -= count;
  +        }
  +        return result;
  +    }
  +
  +    public boolean removeAll(Collection coll) {
  +        boolean result = false;
  +        if (coll != null) {
  +            Iterator i = coll.iterator();
  +            while (i.hasNext()) {
  +                boolean changed = remove(i.next(), 1);
  +                result = result || changed;
  +            }
  +        }
  +        return result;
  +    }
  +
  +    /**
  +     * Remove any members of the bag that are not in the given
  +     * bag, respecting cardinality.
  +     *
  +     * @param coll  the collection to retain
  +     * @return true if this call changed the collection
  +     */
  +    public boolean retainAll(Collection coll) {
  +        return retainAll(new HashBag(coll));
  +    }
  +
  +    /**
  +     * Remove any members of the bag that are not in the given
  +     * bag, respecting cardinality.
  +     * @see #retainAll(Collection)
  +     * 
  +     * @param other  the bag to retain
  +     * @return <code>true</code> if this call changed the collection
  +     */
  +    public boolean retainAll(Bag other) {
  +        boolean result = false;
  +        Bag excess = new HashBag();
  +        Iterator i = uniqueSet().iterator();
  +        while (i.hasNext()) {
  +            Object current = i.next();
  +            int myCount = getCount(current);
  +            int otherCount = other.getCount(current);
  +            if (1 <= otherCount && otherCount <= myCount) {
  +                excess.add(current, myCount - otherCount);
  +            } else {
  +                excess.add(current, myCount);
  +            }
  +        }
  +        if (!excess.isEmpty()) {
  +            result = removeAll(excess);
  +        }
  +        return result;
  +    }
  +
  +    /**
  +     * Returns an array of all of this bag's elements.
  +     *
  +     * @return an array of all of this bag's elements
  +     */
  +    public Object[] toArray() {
  +        return extractList().toArray();
  +    }
  +
  +    /**
  +     * Returns an array of all of this bag's elements.
  +     *
  +     * @param array  the array to populate
  +     * @return an array of all of this bag's elements
  +     */
  +    public Object[] toArray(Object[] array) {
  +        return extractList().toArray(array);
  +    }
  +
  +    /**
  +     * Returns the number of occurrence of the given element in this bag
  +     * by looking up its count in the underlying map.
  +     *
  +     * @param object  the object to search for
  +     * @return the number of occurrences of the object, zero if not found
  +     */
  +    public int getCount(Object object) {
  +        int result = 0;
  +        Integer count = MapUtils.getInteger(_map, object);
  +        if (count != null) {
  +            result = count.intValue();
  +        }
  +        return result;
  +    }
  +
  +    /**
  +     * Returns an unmodifiable view of the underlying map's key set.
  +     *
  +     * @return the set of unique elements in this bag
  +     */
  +    public Set uniqueSet() {
  +        return Collections.unmodifiableSet(_map.keySet());
  +    }
  +
  +    /**
  +     * Returns the number of elements in this bag.
  +     *
  +     * @return the number of elements in this bag
  +     */
  +    public int size() {
  +        return _total;
  +    }
  +
  +    /**
  +     * Actually walks the bag to make sure the count is correct and
  +     * resets the running total
  +     * 
  +     * @return the current total size
  +     */
  +    protected int calcTotalSize() {
  +        _total = extractList().size();
  +        return _total;
  +    }
  +
  +    /**
  +     * Utility method for implementations to set the map that backs
  +     * this bag. Not intended for interactive use outside of
  +     * subclasses.
  +     */
  +    protected void setMap(Map map) {
  +        if (map == null || map.isEmpty() == false) {
  +            throw new IllegalArgumentException("The map must be non-null and empty");
  +        }
  +        _map = map;
  +    }
  +
  +    /**
  +     * Utility method for implementations to access the map that backs
  +     * this bag. Not intended for interactive use outside of
  +     * subclasses.
  +     */
  +    protected Map getMap() {
  +        return _map;
  +    }
  +
  +    /**
  +     * Create a list for use in iteration, etc.
  +     */
  +    private List extractList() {
  +        List result = new ArrayList();
  +        Iterator i = uniqueSet().iterator();
  +        while (i.hasNext()) {
  +            Object current = i.next();
  +            for (int index = getCount(current); index > 0; index--) {
  +                result.add(current);
  +            }
  +        }
  +        return result;
  +    }
  +
  +    /**
  +     * Return number of modifications for iterator.
  +     * 
  +     * @return the modification count
  +     */
  +    private int modCount() {
  +        return _mods;
  +    }
  +
  +    /**
  +     * Implement a toString() method suitable for debugging.
  +     * 
  +     * @return a debugging toString
  +     */
       public String toString() {
           StringBuffer buf = new StringBuffer();
           buf.append("[");
           Iterator i = uniqueSet().iterator();
  -        while(i.hasNext()) {
  +        while (i.hasNext()) {
               Object current = i.next();
               int count = getCount(current);
               buf.append(count);
               buf.append(":");
               buf.append(current);
  -            if(i.hasNext()) {
  +            if (i.hasNext()) {
                   buf.append(",");
               }
           }
           buf.append("]");
           return buf.toString();
       }
  +    
   }
  -
  -
  -
  
  
  

---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message