Logo
Distributed Genetic Programming Framework
print print

File org.dgpf.search.api.utils.WeightedSet.java

Here you can find all the information about the file org.dgpf.search.api.utils.WeightedSet.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-06-07 14:01:20
 * Original Filename: org.dgpf.search.api.utils.WeightedSet.java
 * Version          : 1.0.0
 * Last modification: 2006-06-07
 *                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.dgpf.search.api.utils;

import java.util.NoSuchElementException;
import java.util.Random;

import org.dgpf.search.api.SearchUtils;
import org.sfc.collections.Arrays;
import org.sfc.collections.IVisitor;
import org.sfc.collections.IteratorBase;
import org.sfc.io.TextWriter;

/**
 * A <code>WeightedSet</code> is a set where you can randomizedly obtain
 * individuals from with a specified weightsabilies.
 * @param <Type>  The item type.
 *
 * @author Thomas Weise
 */

public class WeightedSet<Type>  extends RandomizedList<Type> 
  {
/**
 * The serial version uid.
 */

  private static final long serialVersionUID = 1;
  
/**
 * The list of the individuals.
 */

          final Type[]         m_data   ;
/**
 * The weights.
 */

          final double[]       m_weights   ;
/**
 * The anchor of the weighted set session list.
 */

                Session       m_sessions  ;
/**
 * The original total weight.
 */

          final double        m_weight  ;
  
/**
 * Create a new weighted set. Weighted sets are fixed and cannot be
 * modified.
 * @param p_wsb The weighted set builder to use. 
 */

  public  WeightedSet(final WeightedSetBuilder<Type> p_wsb)
    {
    super();
    
    int       l_c, l_i;
    Type[]    l_d;
    double[]  l_w;
    double    l_x;
    
    l_c = p_wsb.m_count;
    l_d = Arrays.create(p_wsb.m_class, l_c);
    System.arraycopy(p_wsb.m_data, 0, l_d, 0, l_c);
    this.m_data = l_d;
    
    this.m_weights = l_w = new double[l_c];
    System.arraycopy(p_wsb.m_weights, 0, l_w, 0, l_c);
    
    if(l_c > 0)
      {    
      l_x = 0.0d;
      for(l_i = 0; l_i < l_c; l_i++)
        {
        l_x     += l_w[l_i];
        l_w[l_i] = l_x;
        }
      
      this.m_weight = l_x;    
      l_x = (1.0d / l_x);
      
      l_w[--l_c] = Double.MAX_VALUE;
      for(--l_c; l_c >= 0; l_c--)
        {
        l_w[l_c] *= l_x;
        }
      }
    else this.m_weight = 0.0d;
    }
  
/**
 * Get the probability of the item at the specified index.
 * @param p_index The index of the item to obtain.
 * @return The probability of this item to be drawn.
 */

  public  final double  get_probability (final int p_index)
    {
    double[] l_d;
    
    l_d = this.m_weights;    
    if(p_index <= 0) return l_d[0];
    if(p_index >= (l_d.length-1)) return (1.0d - l_d[p_index-1]);
    return (l_d[p_index] - l_d[p_index-1]);
    }
  
/**
 * Obtain the original total weight of this weighted set.
 * @return The original total weight of this weighted set.
 */

  public  final double  get_original_weight()
    {
    return this.m_weight;
    }
  
/**
 * Open a new session. A session allows you to step through the items of
 * this set in a randomized order according to their weight.
 * @param p_r The randomizer to be used for this session.
 * @return  The new Session object. You must close it using
 *          <code>close</code> when its no longer needed.
 *          @see Session#close()
 */

  public  final Session open_session(final Random p_r)
    {
    Session l_s;
    
main:
      {
      synchronized(this)
        {
        l_s = this.m_sessions;
        if(l_s == null) break main;
        this.m_sessions = l_s.m_se;        
        }
      l_s.m_c = this.m_data.length;
      Arrays.fill(l_s.m_done, false);
      l_s.m_r = p_r;
      return l_s;
      }
    
    return new Session(p_r);
    }

/**
 * Print the contents of this set in human-readable form to a text
 * writer.
 * @param p_tw  The text writer to print to. 
 */

  @Override
  public  final void  print (final TextWriter p_tw)
    {
    int       l_i, l_c;
    Type[]    l_t;
    double[]  l_d;
    double    l_v, l_v2;
    
    l_t = this.m_data;
    l_d = this.m_weights;
    l_c = l_t.length;
    
    if(l_c > 0)
      {
      l_c--;
      p_tw.write('(');
      l_v = 0.0d;
      for(l_i = 0; l_i < l_c; l_i++)
        {
        p_tw.write(l_t[l_i].toString());
        p_tw.write(" : ");
        l_v2 = l_d[l_i];
        p_tw.write_double(l_v2 - l_v);
        p_tw.write(", ");
        l_v = l_v2;
        }
      
      p_tw.write(l_t[l_i].toString());
      p_tw.write(" : ");
      p_tw.write_double(1.0d - l_v);
      p_tw.write(')');
      }
    }


/**
 * Obtain one random individual out of the non dominated list.
 * @param p_random  The random number generator to be used.
 * @return  The randomly selected individual.
 */

  @Override
  public final  Type get (final Random p_random)
    {
    return this.m_data[SearchUtils.random_index(this.m_weights,
                                                p_random.nextDouble())];
    }

/**
 * Returns the number of elements in this list.  If this list contains
 * more than <tt>Integer.MAX_VALUE</tt> elements, returns
 * <tt>Integer.MAX_VALUE</tt>.
 *
 * @return the number of elements in this list.
 */

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

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

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

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

  @Override
  public  final boolean contains(final  Object p_o)
    {
    if(p_o != null)
      {
      for(Type l_t : this.m_data)
        {
        if(l_t.equals(p_o)) return true;
        }
      }
    
    return false;
    }


  
/**
 * Returns the element at the specified position in this list.
 *
 * @param p_index index of element to return.
 * @return the element at the specified position in this list.
 * 
 * @throws IndexOutOfBoundsException if the index is out of range (index
 *      &lt; 0 || index &gt;= size()).
 */

  @Override
  public  final Type  get(final int p_index)
    {
    return this.m_data[p_index];
    }

/**
 * Returns the index in this list of the first occurrence of the specified
 * element, or -1 if this list does not contain this element.
 * More formally, returns the lowest index <tt>i</tt> such that
 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * @param p_o element to search for.
 * @return the index in this list of the first occurrence of the specified
 *         element, or -1 if this list does not contain this element.
 * @throws ClassCastException if the type of the specified element
 *         is incompatible with this list (optional).
 * @throws NullPointerException if the specified element is null and this
 *         list does not support null elements (optional).
 */

  @Override
  public  final int indexOf(final Object p_o)
    { 
    Type[] l_b;
    int    l_i, l_j;
    
    if(p_o == null) return -1;
    
    l_b = this.m_data;
    l_j = l_b.length;
    for(l_i = 0; l_i < l_j; l_i++)
      {
      if(l_b[l_i].equals(p_o)) return l_i;
      }
    
    return -1;
    }

/**
 * Returns the index in this list of the last occurrence of the specified
 * element, or -1 if this list does not contain this element.
 * More formally, returns the highest index <tt>i</tt> such that
 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * @param p_o element to search for.
 * @return the index in this list of the last occurrence of the specified
 *         element, or -1 if this list does not contain this element.
 * @throws ClassCastException if the type of the specified element
 *         is incompatible with this list (optional).
 * @throws NullPointerException if the specified element is null and this
 *         list does not support null elements (optional).
 */

  @Override
  public  final int lastIndexOf(final Object p_o)
    { 
    Type[] l_b;
    int    l_i;
    
    if(p_o == null) return -1;
    
    l_b = this.m_data;
    for(l_i = (l_b.length-1); l_i >= 0; l_i--)
      {
      if(l_b[l_i].equals(p_o)) return l_i;
      }
    
    return -1;
    }

/**
 * Visit all items in this weighted set.
 * @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.
 */

  @Override
  public final boolean visit(final IVisitor<Type> p_visitor)
    {
    for(Type l_t : this.m_data)
      {
      if(!(p_visitor.visit(l_t))) return false;
      }    
    return true;
    }
  
/**
 * The session class.
 * @author Thomas Weise
 */

  public  final class Session extends IteratorBase<Type>
    {
/**
 * The items already visited.
 */

          boolean[] m_done;
/**
 * The remaining individual count.
 */

          int       m_c;
/**
 * The next session.
 */

          Session   m_se;
/**
 * The randomizer to use.
 */

          Random    m_r;
          
/**
 * Create a new session.
 * @param p_r The initial randomizer.
 */

    Session(final Random p_r)
      {
      super();
      
      this.m_c    = WeightedSet.this.m_data.length;
      this.m_done = new boolean[this.m_c];
      this.m_r    = p_r;
      }
    
/**
 * Close a randomized session.
 */

    public  final void  close()
      {
      WeightedSet<Type> l_w;
      
      this.m_r = null;      
      l_w      = WeightedSet.this;
      synchronized(l_w)
        {
        this.m_se      = l_w.m_sessions;
        l_w.m_sessions = this;
        }
      }
    
    
/**
 * Returns <tt>true</tt> if the iteration has more elements. (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 iterator has more elements.
 */

   public final boolean hasNext()
     {
     return (this.m_c > 0);
     }

/**
 * Obtain the count of remaining items that can be obtained from this
 * session.
 * @return The count of remaining items that can be obtained from this
 *         session.
 */

   public final int get_remaining ()
     {
     return this.m_c;
     }
   
/**
 * Returns the next element in the iteration.  Calling this method
 * repeatedly until the {@link #hasNext()} method returns false will
 * return each element in the underlying collection exactly once.
 *
 * @return the next element in the iteration.
 * @exception NoSuchElementException iteration has no more elements.
 */

    public  final Type next()
      {
      int       l_c, l_i;
      double[]  l_d;
      boolean[] l_b;
      Random    l_r;
            
      l_c = this.m_c;
      if(l_c <= 0) throw new NoSuchElementException();
      
      l_r = this.m_r;
      
      l_b = this.m_done;
      l_d = WeightedSet.this.m_weights;
      
      do {
         l_i = SearchUtils.random_index(l_d, l_r.nextDouble());
         } while(l_b[l_i]) ;
      
      this.m_c = (l_c-1);
      l_b[l_i] = true;
      
      return WeightedSet.this.m_data[l_i];
      }
    
/**
 * Clone this list iterator.
 * @return  A perfect copy of this iterator.
 */

    @Override
    public  final Object  clone()
      {
      Session l_ws;
      
      l_ws        = ((Session)(super.clone()));
      l_ws.m_done = this.m_done.clone();
      
      return l_ws;
      }
    }
  }

File Information:

file name:WeightedSet.java
package:org.dgpf.search.api.utils
qualified name:org.dgpf.search.api.utils.WeightedSet.java
file type:Java Source File
download location:download http://dgpf.sourceforge.net/source/org/dgpf/search/api/utils/WeightedSet.java
size:12.914 KB (13224 B)
uploaded: 2012-05-02 03:11:06 GMT+0000
last update: 2006-06-15 10:25:51 GMT+0000
last access: 2012-11-21 18:41:05 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 2012-05-02 03:10:45 GMT+0000 served at 2014-07-25 03:38:03 GMT+0000.
Valid CSS Valid XHTML 1.1
Valid RSS SourceForge.net Logo