[Biojava-dev] WeightedSet
Michael Heuer
heuermh at acm.org
Tue Jun 15 12:36:24 EDT 2004
Apply the following diff to my last email.
< boolean addAll(Map<E,W> t);
---
> boolean addAll(Map<? extends E,W> t);
< boolean set(E e, W w);
---
> W set(E e, W w);
michael
On Tue, 15 Jun 2004, Michael Heuer wrote:
> Hello Mark,
>
> Very cool, I have used something similar for scoring and ranking objects.
> I am troubled by the fact that your design and mine are not really sets
> and not really maps, but share some API of both.
>
> Maybe if we use an interface like the following, (Xxx and Xxx.Yyy because
> I haven't had enough coffee yet this morning to come up with proper names)
>
>
> import java.util.Map;
> import java.util.Set;
> import java.util.Collection;
>
> public interface Xxx<E,W extends Number>
> {
>
> /**
> * Clear the elements in this xxx.
> */
> void clear();
>
> /**
> * Add the specified element to this xxx
> * at the specified weight.
> */
> boolean add(E e, W w);
>
> /**
> * Add all of the elements and weights in the specified
> * map of elements to weights to this xxx.
> */
> boolean addAll(Map<E,W> t);
>
> /**
> * Set the weight for the specified element in this xxx
> * to <code>w</code>.
> */
> boolean set(E e, W w);
>
> /**
> * Remove the specified element from this xxx.
> */
> boolean remove(E e);
>
> /**
> * Remove all of the elements in this xxx contained
> * in the specified collection of elements.
> */
> boolean removeAll(Collection<E> coll);
>
> /**
> * Remove all of the elements in this xxx not contained in the
> * specified collection of elements.
> */
> boolean retainAll(Collection<E> coll);
>
> /**
> * Randomly sample an element from this xxx according
> * to its normalized weight.
> */
> E sample();
>
> /**
> * Return the weight for the specified element in
> * this xxx.
> */
> W weight(E e);
>
> /**
> * Return the normalized weight for the specified
> * element in this xxx.
> */
> W normalizedWeight(E e);
>
> /**
> * Return the sum of the weights in this xxx.
> */
> W totalWeight();
>
> /**
> * Return an integer rank for the specified element in this
> * xxx based on its weight.
> */
> int rank(E e);
>
> /**
> * Return a set view of the elements in this xxx.
> */
> Set<E> elements();
>
> /**
> * Return a collection view of the weights in this xxx.
> */
> Collection<W> weights();
>
> /**
> * Return a yyy set view of the elements and weights in this
> * xxx.
> */
> Set<Yyy<E,W>> yyySet();
>
>
> /**
> * Tuple of (element, weight).
> */
> interface Yyy<E,W>
> {
> E getElement();
> W getWeight();
> void setWeight(W w);
> }
> }
>
> michael
>
>
> On Tue, 15 Jun 2004 mark.schreiber at group.novartis.com wrote:
>
> > Hi all -
> >
> > Below is a Set and a Test that are inspired by the BioJava Distribution
> > objects. The WeightedSet is very much like a Distribution but contains
> > Objects which have associated weights. Importantly you can sample these
> > objects in the same way you can sample a Distribution. The major
> > difference is that the WeightedSet can contain any object and not just
> > Symbols.
> >
> > I have found these useful for doing random (or weighted) sampling of
> > objects (which are not symbols) for various applications. I could be
> > included in the utils section of biojava if others think it will be useful
> > although it is not specifically for biological applications.
> >
> > The test class shows the expected usage and behaivour
> >
> >
> >
> > !!!-----CODE STARTS HERE-----!!!
> >
> > import java.util.*;
> >
> > /**
> > * <p>Inspred by the BioJava Distribution objects the WeightedSet is a map
> > from
> > * a Key to a Weight. Unlike Distributions the Keys do not have to be
> > Symbols.
> > * </p>
> > *
> > * <p>When Objects are added or their weights are set then the weights are
> > internally
> > * normalized to 1.0</p>
> > *
> > * @author Mark Schreiber
> > * @version 1.0
> > */
> >
> > public class WeightedSet extends AbstractSet implements
> > java.io.Serializable{
> > private HashMap key2Weight;
> > double totalWeight;
> >
> > public WeightedSet() {
> > key2Weight = new HashMap();
> > }
> >
> > /**
> > * Converts the Set to a map from key <code>Objects</code> to
> > <code>Double</code>
> > * weights.
> > * @return a Map with all the key-weight mappings. Weights are not
> > normalized in this map.
> > */
> > public Map asMap(){
> > return key2Weight;
> > }
> >
> > /**
> > * Randomly samples an <code>Object</code> from the <code>Set</code>
> > according
> > * to its weight.
> > * @return the Object sampled.
> > */
> > public Object sample(){
> > double p = Math.random();
> > for (Iterator i = this.iterator(); i.hasNext(); ) {
> > Object o = i.next();
> > double weight = getWeight(o);
> >
> > p -= weight;
> > if(p <= 0.0){
> > return o;
> > }
> > }
> > throw new org.biojava.bio.BioError("Cannot sample an object, does this
> > set contain any objects?");
> > }
> >
> > /**
> > * Determines the normalized weight for <code>o</code>
> > * @param o the <code>Object</code> you want to know the weight of
> > * @return the normalized weight
> > * @throws NoSuchElementException if <code>o</code> is not found in this
> > set
> > */
> > public double getWeight(Object o) throws NoSuchElementException{
> > if(!( key2Weight.containsKey(o)))
> > throw new NoSuchElementException(o+" not found in this
> > WeightedSet");
> >
> > Double d = (Double)key2Weight.get(o);
> > if(totalWeight == 0.0)
> > return 0.0;
> >
> >
> > return d.doubleValue() / totalWeight;
> > }
> >
> > /**
> > * The total weight that has been added to this Set.
> > * @return the total weight (the value that can be used for normalizing)
> > */
> > protected double getTotalWeight(){
> > return totalWeight;
> > }
> >
> > /**
> > * Sets the weight of an <code>Object</code>. If the <code>Object</code>
> > is
> > * not in this <code>Set</code> then it is added.
> > * @param o the <code>Object</code>
> > * @param w the weight.
> > * @throws IllegalArgumentException if <code>w</code> is < 0.0
> > */
> > public void setWeight(Object o, double w){
> > if(w < 0.0){
> > throw new IllegalArgumentException("Weight must be >= 0.0");
> > }
> > if(key2Weight.containsKey(o)){
> > remove(o);
> > }
> > totalWeight += w;
> > key2Weight.put(o, new Double(w));
> > }
> >
> > public boolean contains(Object o) {
> > return key2Weight.containsKey(o);
> > }
> >
> > public boolean remove(Object o) {
> > if(key2Weight.containsKey(o)){
> > totalWeight -= ((Double)key2Weight.get(o)).doubleValue();
> > key2Weight.remove(o);
> > return true;
> > }
> > return false;
> > }
> >
> > public boolean isEmpty() {
> > return key2Weight.isEmpty();
> > }
> > public boolean retainAll(Collection c) {
> > boolean b = false;
> > Collection toRemove = new ArrayList();
> >
> > for (Iterator i = iterator(); i.hasNext(); ) {
> > Object item = i.next();
> > if(c.contains(item) == false){
> > b = true;
> > toRemove.add(item);
> > }
> > }
> >
> > removeAll(toRemove);
> >
> > return b;
> > }
> >
> > /**
> > * Adds a new <code>Object</code> with a weight of zero. Equivalent to
> > * setWeight(o, 0.0);
> > * @param o the object to add.
> > * @return true if this Object has not been added before.
> > */
> > public boolean add(Object o) {
> > boolean b = !(key2Weight.containsKey(o));
> > setWeight(o, 0.0);
> > return b;
> > }
> > public int size() {
> > return key2Weight.size();
> > }
> >
> > public boolean containsAll(Collection c) {
> > if(size() == 0)
> > return false;
> >
> > for (Iterator i = iterator(); i.hasNext(); ) {
> > Object item = i.next();
> > if(!(key2Weight.containsKey(item))){
> > return false;
> > }
> > }
> > return true;
> > }
> > public Object[] toArray() {
> > Object[] o = new Object[size()];
> > int j = 0;
> > for (Iterator i = iterator(); i.hasNext(); ) {
> > o[j++] = i.next();
> > }
> >
> > return o;
> > }
> >
> > public void clear() {
> > key2Weight = new HashMap();
> > totalWeight = 0.0;
> > }
> > public Iterator iterator() {
> > return key2Weight.keySet().iterator();
> > }
> >
> > public boolean addAll(Collection c) {
> > boolean b = false;
> >
> > for (Iterator i = c.iterator(); i.hasNext(); ) {
> >
> > Object item = i.next();
> > if(!(key2Weight.containsKey(item)))
> > b = true;
> >
> > add(item);
> > }
> > return b;
> > }
> > }
> >
> > !!!!-------TEST CODE STARTS HERE -------!!!!
> >
> > import junit.framework.*;
> > import java.util.*;
> >
> > public class TestWeightedSet
> > extends TestCase {
> > private WeightedSet weightedSet = null;
> >
> > public TestWeightedSet(String name) {
> > super(name);
> > }
> >
> > protected void setUp() throws Exception {
> > super.setUp();
> >
> > weightedSet = new WeightedSet();
> > }
> >
> > protected void tearDown() throws Exception {
> > weightedSet = null;
> > super.tearDown();
> > }
> >
> >
> > public void testAdd() {
> > Object o = new Object();
> > boolean expectedReturn = true;
> > boolean actualReturn = weightedSet.add(o);
> > assertEquals("return value", expectedReturn, actualReturn);
> > assertTrue(weightedSet.getWeight(o) == 0.0);
> > assertTrue(weightedSet.size() == 1);
> >
> > actualReturn = weightedSet.add(o);
> > expectedReturn = false;
> > assertEquals("return value", expectedReturn, actualReturn);
> > assertTrue(weightedSet.size() == 1);
> > }
> >
> > public void testAddAll() {
> > List c = new ArrayList();
> > Object o = new Object();
> > String s = "";
> >
> > c.add(o); c.add(s);
> >
> > boolean expectedReturn = true;
> > boolean actualReturn = weightedSet.addAll(c);
> > assertEquals("return value", expectedReturn, actualReturn);
> > assertTrue(weightedSet.size() == 2);
> > assertTrue(weightedSet.getWeight(o) == 0.0);
> > assertTrue(weightedSet.getWeight(s) == 0.0);
> > }
> >
> > public void testAsMap() {
> > weightedSet.add("one");
> >
> > Map m = weightedSet.asMap();
> > assertTrue(m.containsKey("one"));
> > Double expectedReturn = new Double(0.0);
> > Double actualReturn = (Double)m.get("one");
> > assertEquals("return value", expectedReturn, actualReturn);
> > }
> >
> > public void testClear() {
> > weightedSet.setWeight("one", 0.5);
> > weightedSet.setWeight("two", 0.5);
> > weightedSet.clear();
> > assertTrue(weightedSet.getTotalWeight() == 0.0);
> > assertTrue(weightedSet.contains("one") == false);
> > assertTrue(weightedSet.contains("two") == false);
> > }
> >
> > public void testContains() {
> > Object o = new Object();
> > boolean expectedReturn = false;
> > boolean actualReturn = weightedSet.contains(o);
> > assertEquals("return value", expectedReturn, actualReturn);
> >
> > weightedSet.add(o);
> > expectedReturn = true;
> > actualReturn = weightedSet.contains(o);
> > assertEquals("return value", expectedReturn, actualReturn);
> > }
> >
> > public void testContainsAll() {
> > List c = new ArrayList();
> > Object o = new Object();
> > String s = "";
> >
> > c.add(o);
> > c.add(s);
> >
> >
> > boolean expectedReturn = false;
> > boolean actualReturn = weightedSet.containsAll(c);
> > assertEquals("return value", expectedReturn, actualReturn);
> >
> > weightedSet.addAll(c);
> > expectedReturn = true;
> > actualReturn = weightedSet.containsAll(c);
> > assertEquals("return value", expectedReturn, actualReturn);
> > }
> >
> > public void testGetTotalWeight() {
> > Double expectedReturn = new Double(1.5);
> > weightedSet.setWeight("one", 0.5);
> > weightedSet.setWeight("two", 0.5);
> > weightedSet.setWeight("three", 0.5);
> > Double actualReturn = new Double(weightedSet.getTotalWeight());
> > assertEquals("return value", expectedReturn, actualReturn);
> > }
> >
> > public void testGetWeight() throws NoSuchElementException {
> > weightedSet.setWeight("one", 0.5);
> > weightedSet.setWeight("two", 0.5);
> > weightedSet.setWeight("three", 0.5);
> > weightedSet.setWeight("four", 0.5);
> >
> > Double expectedReturn = new Double(0.25);
> > Double actualReturn = new Double(weightedSet.getWeight("one"));
> > assertEquals("return value", expectedReturn, actualReturn);
> > }
> >
> > public void testIsEmpty() {
> > weightedSet.setWeight("four", 0.5);
> > boolean expectedReturn = false;
> > boolean actualReturn = weightedSet.isEmpty();
> > assertEquals("return value", expectedReturn, actualReturn);
> > }
> >
> >
> > public void testRemove() {
> > weightedSet.setWeight("one", 0.5);
> > weightedSet.setWeight("two", 0.5);
> > weightedSet.setWeight("three", 0.5);
> > weightedSet.setWeight("four", 0.5);
> > weightedSet.setWeight("five", 0.5);
> >
> > weightedSet.remove("one");
> > assertTrue(weightedSet.getTotalWeight() == 2.0);
> > assertTrue(weightedSet.getWeight("five") == 0.25);
> > }
> >
> > public void testRetainAll() {
> > weightedSet.setWeight("one", 0.5);
> > weightedSet.setWeight("two", 0.5);
> > weightedSet.setWeight("three", 0.5);
> > weightedSet.setWeight("four", 0.5);
> > weightedSet.setWeight("five", 0.5);
> >
> > Collection c = new ArrayList();
> > c.add("one"); c.add("two");
> >
> > boolean expectedReturn = true;
> > boolean actualReturn = weightedSet.retainAll(c);
> > assertEquals("return value", expectedReturn, actualReturn);
> >
> > assertTrue(weightedSet.contains("one"));
> > assertTrue(weightedSet.containsAll(c));
> > assertTrue(! weightedSet.contains("three"));
> > }
> >
> > public void testSample() {
> > weightedSet.setWeight("one", 0.5);
> > Object expectedReturn = "one";
> > Object actualReturn = weightedSet.sample();
> > assertEquals("return value", expectedReturn, actualReturn);
> >
> > weightedSet.setWeight("two", 4.5);
> > }
> >
> > public void testSetWeight() {
> > Object o = "one";
> > double w = 0.3;
> > weightedSet.setWeight(o, w);
> >
> > assertTrue(weightedSet.getTotalWeight() == 0.3);
> > assertTrue(weightedSet.getWeight(o) == 1.0);
> > }
> >
> > public void testSetWeight2(){
> > Object o = "one";
> > double w = 2.5;
> > weightedSet.setWeight(o, w);
> >
> > assertTrue(weightedSet.getTotalWeight() == 2.5);
> > assertTrue(weightedSet.getWeight(o) == 1.0);
> > }
> >
> > public void testSetWeight3(){
> > Object o = "one";
> > double w = 2.5;
> > Object p = "two";
> > double x = 2.5;
> >
> > weightedSet.setWeight(o, w);
> > assertTrue(weightedSet.getTotalWeight() == 2.5);
> > assertTrue(weightedSet.getWeight(o) == 1.0);
> > weightedSet.setWeight(p, x);
> > assertTrue(weightedSet.getTotalWeight() == 5.0);
> > assertTrue(weightedSet.getWeight(o) == 0.5);
> > assertTrue(weightedSet.getWeight(p) == 0.5);
> > }
> >
> > public void testSize() {
> > int expectedReturn = 0;
> > int actualReturn = weightedSet.size();
> > assertEquals("return value", expectedReturn, actualReturn);
> >
> > weightedSet.setWeight("one", 0.5);
> > weightedSet.setWeight("two", 0.5);
> > weightedSet.setWeight("three", 0.5);
> > weightedSet.setWeight("four", 0.5);
> > weightedSet.setWeight("five", 0.5);
> >
> > expectedReturn = 5;
> > actualReturn = weightedSet.size();
> > assertEquals("return value", expectedReturn, actualReturn);
> >
> > }
> > }
> > _______________________________________________
> > biojava-dev mailing list
> > biojava-dev at biojava.org
> > http://biojava.org/mailman/listinfo/biojava-dev
> >
>
> _______________________________________________
> biojava-dev mailing list
> biojava-dev at biojava.org
> http://biojava.org/mailman/listinfo/biojava-dev
>
More information about the biojava-dev
mailing list