+Show TOC
×Hide TOC

HashMap

Kind of class:	public class
Package:	com.bourre.collection
Inherits from:	none
Author:	Francis Bourre
Classpath:	com.bourre.collection.HashMap
File last modified:	Monday, 24 November 2008, 11:36:49

► View source

▼ Hide source

/*
 * Copyright the original author or authors.
 * 
 * Licensed under the MOZILLA PUBLIC LICENSE, Version 1.1 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.mozilla.org/MPL/MPL-1.1.html
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.bourre.collection
{
    import com.bourre.error.NullPointerException;
    import com.bourre.log.PixlibDebug;
    import com.bourre.log.PixlibStringifier;
    
    import flash.utils.Dictionary;    

    /**
     * An object that maps keys to values.  A map cannot contain duplicate keys;
     * each key can map to at most one value.
     * <p>
     * The "destructive" methods contained in this interface, that is, the
     * methods that modify the map on which they operate, are specified to throw
     * <code>UnsupportedOperationException</code> if this map does not support the
     * operation.  If this is the case, these methods may, but are not required
     * to, throw an <code>UnsupportedOperationException</code> if the invocation would
     * have no effect on the map.  For example, invoking the <code>putAll(Map)</code>
     * method on an unmodifiable map may, but is not required to, throw the
     * exception if the map whose mappings are to be "superimposed" is empty.
     * </p><p>
     * Some map implementations have restrictions on the keys and values they
     * may contain.  For example, some implementations prohibit null keys and
     * values, and some have restrictions on the types of their keys.  Attempting
     * to insert an ineligible key or value throws an unchecked exception,
     * typically <code>NullPointerException</code> or <code>ClassCastException</code>.
     * Attempting to query the presence of an ineligible key or value may throw an
     * exception, or it may simply return false; some implementations will exhibit
     * the former behavior and some will exhibit the latter.  More generally,
     * attempting an operation on an ineligible key or value whose completion
     * would not result in the insertion of an ineligible element into the map may
     * throw an exception or it may succeed, at the option of the implementation.
     * Such exceptions are marked as "optional" in the specification for this
     * interface.
     * </p><p>
     * Many methods in Collections Framework interfaces are defined
     * in terms of the <code>===</code> operator.  For example, the
     * specification for the <code>containsKey( key : Object )</code>
     * method says: "returns <code>true</code> if and
     * only if this map contains a mapping for a key <code>k</code> such that
     * <code>key === k</code>." This specification should
     * <i>not</i> be construed to imply that invoking <code>HashMap.containsKey</code>
     * with a non-null argument <code>key</code> will cause <code>key === k</code> to
     * be invoked for any key <code>k</code>.  Implementations are free to
     * implement optimizations whereby the <code>===</code> invocation is avoided,
     * for example, by first comparing the hash codes of the two keys.  (The
     * <code>HashCodeFactory.getKey(Object)</code> specification guarantees that two
     * objects with unequal hash codes cannot be equal.) More generally, implementations of
     * the various Collections Framework interfaces are free to take advantage of
     * the specified behavior of underlying <code>Object</code> methods wherever the
     * implementor deems it appropriate.
     * </p>
     * @author  Francis Bourre
     */
    public class HashMap 
    {
        /**
         * Number of mappings currently in this map
         */
        protected var _n : uint;
        
        /**
         * A dictionnary which stores the mapping (key - value)
         * for this map.
         */
        protected var _oKeyDico : Dictionary;
        
        /**
         * A dictionnary which store the mapping (value - 
         * occurrences count) for this map.
         */
        protected var _oValueDico : Dictionary;
        
        /**
         * Creates a new empty hash map object.
         */
        public function HashMap ()
        {
            _init();
        }
        
        /**
         * Realize the concret initialization for this map
         */
        protected function _init () : void
        {
            _n = 0;
            _oKeyDico = new Dictionary ( true );
            _oValueDico = new Dictionary ( true );
        }
        
        /**
         * Removes all of the mappings from this map (optional operation).
         * The map will be empty after this call returns.
         */
        public function clear() : void
        {
            _init();
        }
        
        /**
         * Returns <code>true</code> if this map contains no key-value mappings.
         *
         * @return <code>true</code> if this map contains no key-value mappings
         */
        public function isEmpty () : Boolean
        {
            return ( _n == 0 );
        }
        
        /**
         * Returns <code>true</code> if this map contains a mapping for the specified
         * key.  More formally, returns <code>true</code> if and only if
         * this map contains a mapping for a key <code>k</code> such that
         * <code>key === k</code>.  (There can be at most one such mapping.)
         *
         * @param    key     key object whose presence in this map is to be tested
         * @return     <code>true</code> if this map contains a mapping for the specified
         *             key
         * @throws     <code>NullPointerException</code> ‚Äî  if the specified key is null
         */
        public function containsKey ( key : * ) : Boolean
        {
            if( key == null )
            {
                var msg :String = this + ".containsKey() failed. key can't be null";
                PixlibDebug.ERROR ( msg );
                throw new NullPointerException ( msg );
            }

            return _oKeyDico[ key ] != null;
        }

        /**
         * Returns <code>true</code> if this map maps one or more keys to the
         * specified value.  More formally, returns <code>true</code> if and only if
         * this map contains at least one mapping to a value <code>v</code> such that
         * <code>(value === v)</code>.
         * 
         * @param    value    value whose presence in this map is to be tested
         * @return <code>true</code> if this map maps one or more keys to the
         *         specified value
         */
        public function containsValue ( value : * ) : Boolean
        {
            return _oValueDico[ value ] != null;
        }

        /**
         * Associates the specified value with the specified key in this map
         * (optional operation).  If the map previously contained a mapping for
         * the key, the old value is replaced by the specified value.  (A map
         * <code>m</code> is said to contain a mapping for a key <code>k</code> 
         * if and only if <code>m.containsKey(k)</code> would return
         * <code>true</code>.)
         *
         * @param    key     key with which the specified value is to be associated
         * @param    value     value to be associated with the specified key
         * @return     the previous value associated with <code>key</code>, or
         *             <code>null</code> if there was no mapping for <code>key</code>.
         *             (A <code>null</code> return can also indicate that the map
         *             previously associated <code>null</code> with <code>key</code>,
         *             if the implementation supports <code>null</code> values.)
         * @throws     <code>NullPointerException</code> ‚Äî  if the specified key or value is null
         */
        public function put ( key : *, value : * ) : *
        {
            if ( key != null )
            {
                var oldVal : * = null;
                
                if ( containsKey( key ) ) oldVal = remove( key );
                
                _n++;
                var count : uint = _oValueDico[ value ];
                _oValueDico[ value ] = (count > 0) ? count+1 : 1;
                _oKeyDico[ key ] = value;
                
                return oldVal;

            } else
            {
                var msg : String = this + ".put() failed. key can't be null";
                PixlibDebug.ERROR ( msg );
                throw new NullPointerException ( msg );
            }
        }

        /**
         * Returns the value to which the specified key is mapped,
         * or <code>null</code> if this map contains no mapping for the key.
         * <p>
         * More formally, if this map contains a mapping from a key
         * <code>k</code> to a value <code>v</code> such that 
         * <code>(key === k)</code>, then this method returns <code>v</code>; otherwise
         * it returns <code>null</code>.  (There can be at most one such mapping.)
         * </p><p>
         * As this map permits null values, a return value of <code>null</code>
         * does not <i>necessarily</i> indicate that the map contains no mapping
         * for the key; it's also possible that the map explicitly maps the key to
         * <code>null</code>. The <code>containsKey</code> operation may be used
         * to distinguish these two cases.
         * </p>
         * @param    key     the key whose associated value is to be returned
         * @return     the value to which the specified key is mapped, or
         *             <code>null</code> if this map contains no mapping for the key
         * @throws     <code>NullPointerException</code> ‚Äî  if the specified key is null
         */
        public function get ( key : * ) : *
        {
            if( key == null )
            {
                var msg : String = this + ".get() failed. key can't be null";
                PixlibDebug.ERROR ( msg );
                throw new NullPointerException ( msg );
            }

            return _oKeyDico[ key ];
        }
        
        /**
         * Removes the mapping for a key from this map if it is present
         * (optional operation). More formally, if this map contains a mapping
         * from key <code>k</code> to value <code>v</code> such that
         * <code>(key === k)</code>, that mapping is removed. 
         * (The map can contain at most one such mapping.)
         * <p>
         * Returns the value to which this map previously associated the key,
         * or <code>null</code> if the map contained no mapping for the key.
         * </p><p>
         * As this map permits null values, then a return value of
         * <code>null</code> does not <i>necessarily</i> indicate that the map
         * contained no mapping for the key; it's also possible that the map
         * explicitly mapped the key to <code>null</code>.
         * </p><p>
         * The map will not contain a mapping for the specified key once the
         * call returns.
         * </p>
         * @param    key        key whose mapping is to be removed from the map
         * @return     the previous value associated with <code>key</code>, or
         *             <code>null</code> if there was no mapping for <code>key</code>.
         * @throws     <code>NullPointerException</code> ‚Äî  if the specified key is null 
         */
        public function remove ( key : * ) : *
        {
            var value : *;
            
            if ( containsKey( key ) ) 
            {
                _n--;
                value = _oKeyDico[ key ];

                var count : uint = _oValueDico[ value ];
                if (count > 1)
                {
                    _oValueDico[ value ] = count - 1;

                } else
                {
                    delete _oValueDico[ value ];
                }
                
                delete _oKeyDico[ key ];
            }
            
            return value;
        }
        
        /**
         * Returns the number of key-value mappings in this map.
         *
         * @return the number of key-value mappings in this map
         */
        public function size () : Number
        {
            return _n;
        }
        
        /**
         * Returns an <code>Array</code> view of the keys contained in this map.
         *
         * @return an array view of the keys contained in this map
         */
        public function getKeys () : Array
        {
            var a : Array = new Array();
            for ( var key : * in _oKeyDico ) a.push( key );
            return a;
        }

        /**
         * Returns an <code>Array</code> view of the values contained in this map.
         *
         * @return an array view of the values contained in this map
         */
        public function getValues () : Array
        {
            var a : Array = new Array();
            for each ( var value : * in _oKeyDico ) a.push( value );
            return a;
        }

        /**
         * Returns the string representation of this instance.
         * 
         * @return the string representation of this instance
         */
        public function toString () : String 
        {
            return PixlibStringifier.stringify( this );
        }
    }
}

An object that maps keys to values. A map cannot contain duplicate keys;
each key can map to at most one value.

The "destructive" methods contained in this interface, that is, the
methods that modify the map on which they operate, are specified to throw

UnsupportedOperationException if this map does not support the
operation. If this is the case, these methods may, but are not required
to, throw an UnsupportedOperationException if the invocation would
have no effect on the map. For example, invoking the putAll(Map)method on an unmodifiable map may, but is not required to, throw the
exception if the map whose mappings are to be "superimposed" is empty.

Some map implementations have restrictions on the keys and values they
may contain. For example, some implementations prohibit null keys and
values, and some have restrictions on the types of their keys. Attempting
to insert an ineligible key or value throws an unchecked exception,
typically NullPointerException or ClassCastException.
Attempting to query the presence of an ineligible key or value may throw an
exception, or it may simply return false; some implementations will exhibit
the former behavior and some will exhibit the latter. More generally,
attempting an operation on an ineligible key or value whose completion
would not result in the insertion of an ineligible element into the map may
throw an exception or it may succeed, at the option of the implementation.
Such exceptions are marked as "optional" in the specification for this
interface.

Many methods in Collections Framework interfaces are defined
in terms of the === operator. For example, the
specification for the containsKey( key : Object )method says: "returns true if and
only if this map contains a mapping for a key k such that

key === k." This specification should
not be construed to imply that invoking HashMap.containsKeywith a non-null argument key will cause key === k to
be invoked for any key k. Implementations are free to
implement optimizations whereby the === invocation is avoided,
for example, by first comparing the hash codes of the two keys. (The

HashCodeFactory.getKey(Object) specification guarantees that two
objects with unequal hash codes cannot be equal.) More generally, implementations of
the various Collections Framework interfaces are free to take advantage of
the specified behavior of underlying Object methods wherever the
implementor deems it appropriate.

Summary

Constructor

HashMap

Instance methods

clear : void
- Removes all of the mappings from this map (optional operation).
isEmpty : Boolean
- Returns true if this map contains no key-value mappings.
containsKey (key:*) : Boolean
- Returns true if this map contains a mapping for the specified
containsValue (value:*) : Boolean
- Returns true if this map maps one or more keys to the
put (key:*, value:*) : *
- Associates the specified value with the specified key in this map
get (key:*) : *
- Returns the value to which the specified key is mapped,
remove (key:*) : *
- Removes the mapping for a key from this map if it is present
size : Number
- Returns the number of key-value mappings in this map.
getKeys : Array
- Returns an Array view of the keys contained in this map.
getValues : Array
- Returns an Array view of the values contained in this map.
toString : String
- Returns the string representation of this instance.

Constructor

HashMap

public function HashMap (

)

Creates a new empty hash map object.

Instance methods

clear

public function clear (

) : void

Removes all of the mappings from this map (optional operation).
The map will be empty after this call returns.

containsKey

public function containsKey (

key:*) : Boolean

Returns true if this map contains a mapping for the specified
key. More formally, returns true if and only if
this map contains a mapping for a key k such that

key === k. (There can be at most one such mapping.)

Parameters:

key:

key object whose presence in this map is to be tested

Returns:

true if this map contains a mapping for the specified
key

Throws:

{VISDOC_LINK_0}NullPointerException — if the specified key is null

containsValue

public function containsValue (

value:*) : Boolean

Returns true if this map maps one or more keys to the
specified value. More formally, returns true if and only if
this map contains at least one mapping to a value v such that

(value === v).

Parameters:

value:

value whose presence in this map is to be tested

Returns:

true if this map maps one or more keys to the
specified value

get

public function get (

key:*) : *

Returns the value to which the specified key is mapped,
or null if this map contains no mapping for the key.

More formally, if this map contains a mapping from a key

k to a value v such that

(key === k), then this method returns v; otherwise
it returns null. (There can be at most one such mapping.)

As this map permits null values, a return value of nulldoes not necessarily indicate that the map contains no mapping
for the key; it's also possible that the map explicitly maps the key to

null. The containsKey operation may be used
to distinguish these two cases.

Parameters:

key:

the key whose associated value is to be returned

Returns:

the value to which the specified key is mapped, or
null if this map contains no mapping for the key

Throws:

{VISDOC_LINK_0}NullPointerException — if the specified key is null

getKeys

public function getKeys (

) : Array

Returns an Array view of the keys contained in this map.

Returns:

an array view of the keys contained in this map

getValues

public function getValues (

) : Array

Returns an Array view of the values contained in this map.

Returns:

an array view of the values contained in this map

isEmpty

public function isEmpty (

) : Boolean

Returns true if this map contains no key-value mappings.

Returns:

true if this map contains no key-value mappings

put

public function put (

key:*, value:*) : *

Associates the specified value with the specified key in this map
(optional operation). If the map previously contained a mapping for
the key, the old value is replaced by the specified value. (A map

m is said to contain a mapping for a key k
if and only if m.containsKey(k) would return

true.)

Parameters:

key :

key with which the specified value is to be associated

value:

value to be associated with the specified key

Returns:

the previous value associated with key, or
null if there was no mapping for key.
(A null return can also indicate that the map
previously associated null with key,
if the implementation supports null values.)

Throws:

{VISDOC_LINK_0}NullPointerException — if the specified key or value is null

remove

public function remove (

key:*) : *

Removes the mapping for a key from this map if it is present
(optional operation). More formally, if this map contains a mapping
from key k to value v such that

(key === k), that mapping is removed.
(The map can contain at most one such mapping.)

Returns the value to which this map previously associated the key,
or null if the map contained no mapping for the key.

As this map permits null values, then a return value of

null does not necessarily indicate that the map
contained no mapping for the key; it's also possible that the map
explicitly mapped the key to null.

The map will not contain a mapping for the specified key once the
call returns.

Parameters:

key:

key whose mapping is to be removed from the map

Returns:

the previous value associated with key, or
null if there was no mapping for key.

Throws:

{VISDOC_LINK_0}NullPointerException — if the specified key is null

size

public function size (

) : Number

Returns the number of key-value mappings in this map.

Returns:

the number of key-value mappings in this map

toString

public function toString (

) : String

Returns the string representation of this instance.

Returns:

the string representation of this instance