/*
* 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 WeightedSet
is a set where you can randomizedly obtain
* individuals from with a specified weightsabilies.
* @param The item type.
*
* @author Thomas Weise
*/
public class WeightedSet extends RandomizedList
{
/**
* 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 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
* close
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 Integer.MAX_VALUE elements, returns
* Integer.MAX_VALUE.
*
* @return the number of elements in this list.
*/
@Override
public final int size()
{
return this.m_data.length;
}
/**
* Returns true if this list contains no elements.
*
* @return true if this list contains no elements.
*/
@Override
public final boolean isEmpty()
{
return (this.m_data.length <= 0);
}
/**
* Returns true if this list contains the specified element.
* More formally, returns true if and only if this list contains
* at least one element e such that
* (o==null ? e==null : o.equals(e)).
*
* @param p_o element whose presence in this list is to be tested.
* @return true 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
* < 0 || index >= 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 i such that
* (o==null ? get(i)==null : o.equals(get(i))),
* 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 i such that
* (o==null ? get(i)==null : o.equals(get(i))),
* 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 true
if the visitor successfully visited all
* elements, false
if it aborted its visit.
*/
@Override
public final boolean visit(final IVisitor 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
{
/**
* 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 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 true if the iteration has more elements. (In other
* words, returns true if next would return an element
* rather than throwing an exception.)
*
* @return true 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;
}
}
}