Logo
Distributed Genetic Programming Framework
print print

File org.sfc.collections.ProtectedHash.java

Here you can find all the information about the file org.sfc.collections.ProtectedHash.java. You may explore it here or download it onto your local disk.
/*
 * Copyright (c) 2006 Thomas Weise
 * 
 * E-Mail           : tweise@gmx.de
 * Creation Date    : 2006-05-24 06:39:59
 * Original Filename: org.sfc.collections.ProtectedHash.java
 * Version          : 1.0.0
 * Last modification: 2006-05-24
 *                by: Thomas Weise
 * 
 * License          : GNU LESSER GENERAL PUBLIC LICENSE
 *                    Version 2.1, February 1999
 *                    You should have received a copy of this license along
 *                    with this library; if not, write to the Free Software
 *                    Foundation, Inc., 59 Temple Place, Suite 330, Boston,
 *                    MA 02111-1307, USA or download the license under
 *                    http://www.gnu.org/copyleft/lesser.html.
 *                    
 * Warranty         : This software is provided "as is" without any
 *                    warranty; without even the implied warranty of
 *                    merchantability or fitness for a particular purpose.
 *                    See the Gnu Lesser General Public License for more
 *                    details.
 */

 
package org.sfc.collections;

import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

import org.sfc.math.Mathematics;
import org.sfc.utils.Typesafe;

/**
 * A protected hash is a hash that appears to be immutable for the outside
 * world but can be modified by its descendants using protected methods.
 * 
 * @param <KeyType>   The type of keys used.
 * @param <ValueType>  The type of values stored.
 * 
 * @author Thomas Weise
 */

public class      ProtectedHash<KeyType, ValueType> 
       extends    AbstractMap<KeyType, ValueType>
  {
/**
 * The hashs data.
 */

          Element<KeyType, ValueType>[]       m_data  ;
/**
 * The count of elements stored.
 */

          int                                 m_count ;
/**
 * The null element.
 */

          Element<KeyType, ValueType>         m_null;
/**
 * The elements.
 */

  private Set<Map.Entry<KeyType, ValueType>>  m_elements  ;
    
/**
 * Create a new protected hash.
 * @param p_initial_size  The initial hash size.
 */

  protected ProtectedHash(final int p_initial_size)
    {
    super();
    
    int l_s;
    
    if(p_initial_size > 0)
      {
      l_s = (1 << Mathematics.ld(p_initial_size));
      if(l_s != p_initial_size) l_s <<= 1;
      }
    else
      {
      l_s = 8;
      }
    
    this.m_data = Typesafe.cast(new Element[l_s]);
    }
  

/**
 * Visit all entries of this hash.
 * @param p_visitor The visitor to be carried around.
 * @return  <code>true</code> if the visitor successfully visited all
 *          elements, <code>false</code> if it aborted its visit.
 */

  public  final synchronized  boolean  visit_entries (final
                IVisitor<Entry<KeyType, ValueType>> p_visitor)
    {
    Element<KeyType, ValueType>   l_e;
    
    if(this.m_null != null)
      {
      if(!(p_visitor.visit(this.m_null))) return false;
      }
    
    for(Element<KeyType, ValueType> l_c : this.m_data)
      {
      for(l_e = l_c; l_e != null; l_e = l_e.m_next)
        {
        if(!(p_visitor.visit(l_e))) return false;
        }
      }
    
    return true;
    }
  
/**
 * Visit all keys of this hash.
 * @param p_visitor The visitor to be carried around.
 * @param p_include_null  <code>true</code> if and only if the also a
 *                        possible contained <code>null</code> should
 *                        be visited.
 * @return  <code>true</code> if the visitor successfully visited all
 *          elements, <code>false</code> if it aborted its visit.
 */

  public  final synchronized  boolean  visit_keys (
                                     final IVisitor<KeyType> p_visitor,
                                     final boolean           p_include_null)
    {
    Element<KeyType, ValueType>   l_e;
    
    if(p_include_null && (this.m_null != null))
      {
      if(!(p_visitor.visit(null))) return false;
      }
    
    for(Element<KeyType, ValueType> l_c : this.m_data)
      {
      for(l_e = l_c; l_e != null; l_e = l_e.m_next)
        {
        if(!(p_visitor.visit(l_e.m_key))) return false;
        }
      }
    
    return true;
    }
  
/**
 * Visit all keys of this hash.
 * @param p_visitor The visitor to be carried around.
 * @return  <code>true</code> if the visitor successfully visited all
 *          elements, <code>false</code> if it aborted its visit.
 */

  public  synchronized  final boolean  visit_values(
                            final IVisitor<ValueType> p_visitor)
    {
    Element<KeyType, ValueType>   l_e;
    
    if(this.m_null != null)
      {
      if(!(p_visitor.visit(this.m_null.m_value))) return false;
      }
    
    for(Element<KeyType, ValueType> l_c : this.m_data)
      {
      for(l_e = l_c; l_e != null; l_e = l_e.m_next)
        {
        if(!(p_visitor.visit(l_e.m_value))) return false;
        }
      }
    
    return true;
    }
  
/**
 * Returns a set view of the mappings contained in this map.  Each element
 * in this set is a Map.Entry.  The set is backed by the map, so changes
 * to the map are reflected in the set, and vice-versa.  (If the map is
 * modified while an iteration over the set is in progress, the results of
 * the iteration are undefined.)  The set supports element removal, which
 * removes the corresponding entry from the map, via the
 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
 * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not support
 * the <tt>add</tt> or <tt>addAll</tt> operations.
 *
 * @return a set view of the mappings contained in this map.
 */

  @Override
  public final  Set<Entry<KeyType,ValueType>> entrySet()
    {
    if(this.m_elements != null) return this.m_elements;
    return (this.m_elements = new EntrySet());
    }
  
/**
 * Returns the number of key-value mappings in this map.  If the
 * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
 * <tt>Integer.MAX_VALUE</tt>.
 *
 * @return the number of key-value mappings in this map.
 */

  @Override
  public  final int size()
    {
    return this.m_count;
    }

/**
 * Returns <tt>true</tt> if this map contains no key-value mappings.
 *
 * @return <tt>true</tt> if this map contains no key-value mappings.
 */

  @Override
  public  final boolean isEmpty()
    {
    return (this.m_count <= 0);
    }

/**
 * Returns <tt>true</tt> if this map contains a mapping for the specified
 * key.  More formally, returns <tt>true</tt> if and only if
 * this map contains a mapping for a key <tt>k</tt> such that
 * <tt>(key==null ? k==null : key.equals(k))</tt>.  (There can be
 * at most one such mapping.)
 *
 * @param p_key key whose presence in this map is to be tested.
 * @return <tt>true</tt> if this map contains a mapping for the specified
 *         key.
 */

  @Override
  public  final synchronized  boolean containsKey(final Object p_key)
    {
    Element<KeyType, ValueType>   l_e;
    
    if(p_key == null)
      {
      return (this.m_null != null);
      }
    
    for(Element<KeyType, ValueType> l_c : this.m_data)
      {
      for(l_e = l_c; l_e != null; l_e = l_e.m_next)
        {
        if(l_e.m_key.equals(p_key)) return true;
        }     
      }
    
    return false;
    }

/**
 * Returns <tt>true</tt> if this map maps one or more keys to the
 * specified value.  More formally, returns <tt>true</tt> if and only if
 * this map contains at least one mapping to a value <tt>v</tt> such that
 * <tt>(value==null ? v==null : value.equals(v))</tt>.  This operation
 * will probably require time linear in the map size for most
 * implementations of the <tt>Map</tt> interface.
 *
 * @param p_value value whose presence in this map is to be tested.
 * @return <tt>true</tt> if this map maps one or more keys to the
 *         specified value.
 */

  @Override
  public  final synchronized  boolean containsValue(final Object p_value)
    {    
    Element<KeyType, ValueType>   l_e;
    
    if(p_value == null)
      {
      for(Element<KeyType, ValueType> l_c : this.m_data)
        {
        for(l_e = l_c; l_e != null; l_e = l_e.m_next)
          {
          if(l_e.m_value == null) return true;
          }     
        }
      return false;
      }
    
    for(Element<KeyType, ValueType> l_c : this.m_data)
      {
      for(l_e = l_c; l_e != null; l_e = l_e.m_next)
        {
        if( (l_e.m_value != null) &&
            (l_e.m_value.equals(p_value)) ) return true;
        }     
      }
    
    return false;
    }

/**
 * Returns the value to which this map maps the specified key.  Returns
 * <tt>null</tt> if the map contains no mapping for this key.  A return
 * value of <tt>null</tt> 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 <tt>null</tt>.  The <tt>containsKey</tt>
 * operation may be used to distinguish these two cases.
 *
 * <p>More formally, if this map contains a mapping from a key
 * <tt>k</tt> to a value <tt>v</tt> such that <tt>(key==null ? k==null :
 * key.equals(k))</tt>, then this method returns <tt>v</tt>; otherwise
 * it returns <tt>null</tt>.  (There can be at most one such mapping.)
 *
 * @param p_key key whose associated value is to be returned.
 * @return the value to which this map maps the specified key, or
 *         <tt>null</tt> if the map contains no mapping for this key.
 * 
 * @throws NullPointerException if the key is <tt>null</tt> and this map
 *      does not permit <tt>null</tt> keys (optional).
 * 
 * @see #containsKey(Object)
 */

  @Override
  public  synchronized  final ValueType get(final Object p_key)
    {
    Element<KeyType, ValueType>   l_e;
    
    if(p_key == null)
      {
      if(this.m_null != null) return this.m_null.m_value;
      return null;
      }
    
    for(l_e = this.m_data[p_key.hashCode() & (this.m_data.length-1)];
        l_e != null; l_e = l_e.m_next)
      {
      if(l_e.m_key.equals(p_key))
        {
        return l_e.m_value;
        }
      }
    
    return null;
    }

    // Modification Operations

/**
 * does nothing
 * 
 * @param p_key key with which the specified value is to be associated.
 * @param p_value value to be associated with the specified key.
 * @return never
 * 
 * @throws UnsupportedOperationException always
 */

  @Override
  public  final ValueType put(final KeyType   p_key,
                              final ValueType p_value)
    {
    throw new UnsupportedOperationException();
    }
  
/**
 * Store a key-value pair into the hash.
 * 
 * @param p_key key with which the specified value is to be associated.
 * @param p_value value to be associated with the specified key.
 * @return previous value associated with specified key, or <tt>null</tt>
 *         if there was no mapping for key.  A <tt>null</tt> return can
 *         also indicate that the map previously associated <tt>null</tt>
 *         with the specified key, if the implementation supports
 *         <tt>null</tt> values.
 */

  protected final ValueType do_put(final KeyType   p_key,
                                   final ValueType p_value)
    {
    Element<KeyType, ValueType>   l_e, l_e2;
    Element<KeyType, ValueType>[] l_m, l_m2;
    int                           l_i, l_h, l_l, l_l2, l_z;
    ValueType                     l_v;    
    
    if(p_key == null)
      {
      if(this.m_null == null)
        {
        this.m_count++;
        l_v         = null;
        this.m_null = new Element<KeyType, ValueType>(null, p_value, null);
        }
      else
        {
        l_v                 = this.m_null.m_value;
        this.m_null.m_value = p_value;        
        }
      }
    else
      {
      l_h = p_key.hashCode();
      l_m = this.m_data;
      l_l = (l_m.length-1);
      for(l_e = l_m[l_l]; l_e != null; l_e = l_e.m_next)
        {
        if(l_e.m_key.equals(p_key))
          {
          l_v         = l_e.m_value;
          l_e.m_value = p_value;
          return l_v;
          }
        }
      
      
      if((++this.m_count) >= ((l_l<<1)/3))
        {
        l_l2 = ((l_l+1)<<1);
        l_m2 = Typesafe.cast(new Element[l_l2]);
        l_l2--;
        
        for(l_i = l_l; l_i >= 0; l_i--)
          {
          for(l_e = l_m[l_i]; l_e != null; l_e = l_e2)
            {
            l_e2        = l_e.m_next;
            l_z         = (l_e.m_key.hashCode() & l_l2);
            l_e.m_next  = l_m2[l_z];
            l_m2[l_z]   = l_e;
            }
          }
        
        this.m_data = l_m = l_m2;
        l_l         = l_l2;
        }
      
      l_h     &= l_l;
      l_m[l_h] = new Element<KeyType, ValueType>(p_key, p_value, l_m[l_h]);
      return null;
      }
    
    return l_v;
    }

/**
 * does nothing
 * @param p_key key whose mapping is to be removed from the map.
 * @return never
 *
 * @throws UnsupportedOperationException
 */

  @Override
  public  final ValueType remove(final  Object p_key)
    {
    throw new UnsupportedOperationException();
    }


/**
 * does nothing
 * @param p_t Mappings to be stored in this map.
 * 
 * @throws UnsupportedOperationException always
 */

  @Override
  public  final void putAll(Map<? extends KeyType, ? extends ValueType> p_t)
    {
    throw new UnsupportedOperationException();
    }

/**
 * does nothing
 *
 * @throws UnsupportedOperationException clear is not supported by this
 *      map.
 */

  @Override
  public  final void clear()
    {
    throw new UnsupportedOperationException();
    }

  
/**
 * The internal element class.
 * 
 * @param <KeyType2>   The type of keys used.
 * @param <ValueType2>  The type of values stored.
 *
 * @author Thomas Weise
 */

  private static  final class Element<KeyType2, ValueType2> 
                  implements  Map.Entry<KeyType2, ValueType2>
    {
/**
 * The key stored.
 */

    final KeyType2                        m_key;
/**
 * The value stored.
 */

          ValueType2                      m_value  ;
/**
 * The next element in the hash.
 */

          Element<KeyType2, ValueType2>   m_next  ;
          
/**
 * Create a new element.
 * @param p_key   The key to be stored.
 * @param p_value The value to be stored. 
 * @param p_next  The next element to be stored.
 */

    Element(final KeyType2                      p_key,
            final ValueType2                    p_value,
            final Element<KeyType2, ValueType2> p_next)
      {
      super();
      this.m_key   = p_key;
      this.m_value = p_value;
      this.m_next  = p_next;
      }
    
    
/**
 * Returns the key corresponding to this entry.
 *
 * @return the key corresponding to this entry.
 */

    public final  KeyType2  getKey()
      {
      return this.m_key;
      }

/**
 * Returns the value corresponding to this entry.  If the mapping
 * has been removed from the backing map (by the iterator's
 * <tt>remove</tt> operation), the results of this call are undefined.
 *
 * @return the value corresponding to this entry.
 */

    public final ValueType2 getValue()
      {
      return this.m_value;
      }

/**
 * does nothing
 *
 * @param p_value new value to be stored in this entry.
 * @return never
 * @throws UnsupportedOperationException always
 */

    public  final ValueType2 setValue(final ValueType2 p_value)
      {
      throw new UnsupportedOperationException();
      }

/**
 * Compares the specified object with this entry for equality.
 * Returns <tt>true</tt> if the given object is also a map entry and
 * the two entries represent the same mapping.  More formally, two
 * entries <tt>e1</tt> and <tt>e2</tt> represent the same mapping
 * if<pre>
 *     (e1.getKey()==null ?
 *      e2.getKey()==null : e1.getKey().equals(e2.getKey()))  &&
 *     (e1.getValue()==null ?
 *      e2.getValue()==null : e1.getValue().equals(e2.getValue()))
 * </pre>
 * This ensures that the <tt>equals</tt> method works properly across
 * different implementations of the <tt>Map.Entry</tt> interface.
 *
 * @param p_o object to be compared for equality with this map entry.
 * @return <tt>true</tt> if the specified object is equal to this map
 *         entry.
 */

    @Override
    public  final boolean equals(final  Object p_o)
      {
      Map.Entry<Object, Object> l_m;
      Object                    l_k, l_v;
      
      if(p_o == thisreturn true;
      if(p_o instanceof Map.Entry)
        {
        l_m = Typesafe.cast(p_o);
        l_k = l_m.getKey();
        l_v = l_m.getValue();
        
        if(l_k == null)
          {
          if(this.m_key != null) return false;
          }
        else
          {
          if(!(l_k.equals(this.m_key))) return false;
          }
        
        if(l_v == null)
          {
          if(this.m_value == null) return true;
          }
        else
          {
          if(l_v.equals(this.m_value)) return true;
          }        
        }
      
      return false;
      }

/**
 * Returns the hash code value for this map entry.  The hash code
 * of a map entry <tt>e</tt> is defined to be: <pre>
 *     (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^
 *     (e.getValue()==null ? 0 : e.getValue().hashCode())
       * </pre>
 * This ensures that <tt>e1.equals(e2)</tt> implies that
 * <tt>e1.hashCode()==e2.hashCode()</tt> for any two Entries
 * <tt>e1</tt> and <tt>e2</tt>, as required by the general
 * contract of <tt>Object.hashCode</tt>.
 *
 * @return the hash code value for this map entry.
 * @see Object#hashCode()
 * @see Object#equals(Object)
 * @see #equals(Object)
 */

    @Override
    public  final int hashCode()
      {
      return ( ((this.m_key   == null) ? 0 : this.m_key.hashCode()) ^
               ((this.m_value == null) ? 0 : this.m_value.hashCode()) );
      }
    }
  
/**
 * The internal entry set class.
 * 
 * 
 * @author Thomas Weise
 */

  private final class       EntrySet
                extends     AbstractSet<Map.Entry<KeyType, ValueType>>
    {
/**
 * Returns the number of elements in this set (its cardinality).  If this
 * set contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
 * <tt>Integer.MAX_VALUE</tt>.
 *
 * @return the number of elements in this set (its cardinality).
 */

    @Override
    public  final int size()
      {
      return ProtectedHash.this.m_count;
      }

/**
 * Returns <tt>true</tt> if this set contains no elements.
 *
 * @return <tt>true</tt> if this set contains no elements.
 */

    @Override
    public  final boolean isEmpty()
      {
      return (ProtectedHash.this.m_count <= 0);
      }

/**
 * Returns <tt>true</tt> if this set contains the specified element.  More
 * formally, returns <tt>true</tt> if and only if this set contains an
 * element <code>e</code> such that <code>(o==null ? e==null :
 * o.equals(e))</code>.
 *
 * @param p_o element whose presence in this set is to be tested.
 * @return <tt>true</tt> if this set contains the specified element.
 * @throws ClassCastException if the type of the specified element
 *         is incompatible with this set (optional).
 * @throws NullPointerException if the specified element is null and this
 *         set does not support null elements (optional).
 */

    @Override
    public  final boolean contains(final Object p_o)
      {
      Element<KeyType, ValueType> l_e;
      
      if(p_o == null) return false;
      if(p_o.equals(ProtectedHash.this.m_null)) return true;
      
      for(Element<KeyType, ValueType> l_c : ProtectedHash.this.m_data)
        {
        for(l_e = l_c; l_e != null; l_e = l_e.m_next)
          {
          if(p_o.equals(l_e)) return true;
          }
        }
      
      return false;
      }

/**
 * Returns an iterator over the elements in this set.  The elements are
 * returned in no particular order (unless this set is an instance of some
 * class that provides a guarantee).
 *
 * @return an iterator over the elements in this set.
 */

    @Override
    public  final Iterator<Map.Entry<KeyType, ValueType>> iterator()
      {
      return new ElementIterator();
      }
    }

  
/**
 * The internal entry iterator.
 *
 * @author Thomas Weise
 */

  private class   ElementIterator
          extends IteratorBase<Map.Entry<KeyType,ValueType>>
    {
/**
 * The next entry to return.
 */

    private Element<KeyType,ValueType> m_next;
/**
 * The current index.
 */

    private int                        m_index;
/**
 * The current entry to return.
 */

    private Element<KeyType,ValueType> m_current;

/**
 * Create a new element iterator.
 */

    ElementIterator()
      {       
      Element<KeyType,ValueType>[] l_t;
      int                          l_i;
      Element<KeyType,ValueType>   l_n;
            
      l_n = null;
      l_t = ProtectedHash.this.m_data;
      l_i = l_t.length;
      
      if(ProtectedHash.this.m_count > 0)
        {
        l_n = ProtectedHash.this.m_null;
        while((l_i > 0) && (l_n == null))
          {
          l_n = l_t[--l_i];
          }
        }
      
      this.m_next  = l_n;
      this.m_index = l_i;
      }

/**
 * Returns <tt>true</tt> if this list iterator has more elements when
 * traversing the list in the forward direction. (In other words, returns
 * <tt>true</tt> if <tt>next</tt> would return an element rather than
 * throwing an exception.)
 *
 * @return <tt>true</tt> if the list iterator has more elements when
 *    traversing the list in the forward direction.
 */

    public final  boolean hasNext()
      {
      return (this.m_next != null);
      }

/**
 * Returns the next element in the list.  This method may be called
 * repeatedly to iterate through the list, or intermixed with calls to
 * <tt>previous</tt> to go back and forth.  (Note that alternating calls
 * to <tt>next</tt> and <tt>previous</tt> will return the same element
 * repeatedly.)
 *
 * @return the next element in the list.
 * @exception NoSuchElementException if the iteration has no next element.
 */

    public  final Element<KeyType,ValueType> next()
      { 
      Element<KeyType,ValueType>[] l_t;
      int                          l_i;
      Element<KeyType,ValueType>   l_n, l_e;
      
      l_e = this.m_next;
      if(l_e == null) throw new NoSuchElementException();
                
      l_n = l_e.m_next;
      l_t = ProtectedHash.this.m_data;
      l_i = this.m_index;
      
      while((l_i > 0) && (l_n == null))
        {
        l_n = l_t[--l_i];
        }
      
      this.m_next    = l_n;
      this.m_index   = l_i;
      this.m_current = l_e;
      
      return l_e;
      }

/**
 * 
 * Removes from the underlying collection the last element returned by the
 * iterator (optional operation).  This method can be called only once per
 * call to <tt>next</tt>.  The behavior of an iterator is unspecified if
 * the underlying collection is modified while the iteration is in
 * progress in any way other than by calling this method.
 *
 * @exception UnsupportedOperationException if the <tt>remove</tt>
 *      operation is not supported by this Iterator.
 
 * @exception IllegalStateException if the <tt>next</tt> method has not
 *      yet been called, or the <tt>remove</tt> method has already
 *      been called after the last call to the <tt>next</tt>
 *      method.
 */

    @Override
    public final  void remove()
      {
      if(this.m_current == null)
                throw new IllegalStateException();
            
      ProtectedHash.this.remove(this.m_current.m_key);
      this.m_current = null;
      }
    }
  }

File Information:

file name:ProtectedHash.java
package:org.sfc.collections
qualified name:org.sfc.collections.ProtectedHash.java
file type:Java Source File
download location:download http://dgpf.sourceforge.net/source/org/sfc/collections/ProtectedHash.java
size:23.761 KB (24332 B)
uploaded: 2015-07-22 04:11:11 GMT+0000
last update: 2006-06-14 08:42:56 GMT+0000
last access: 2018-01-23 15:26:01 GMT+0000

statistics online since 2006-01-02.   RSS Feed
Contact us by sending an email to tweise@gmx.de to receive further information, to report errors, or to join our project.
All content on this site (http://dgpf.sourceforge.net/) is LGPL-licensed.
http://dgpf.sourceforge.net/scripts/source/source.php last modified at 2015-07-22 04:10:53 GMT+0000 served at 2018-01-23 15:26:01 GMT+0000.
Valid CSS Valid XHTML 1.1
Valid RSS SourceForge.net Logo