edu.umn.cs.nlp.mt
Class NBestList<Element extends Scorable>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<E>
          java.util.AbstractSequentialList<Element>
              edu.umn.cs.nlp.mt.NBestList<Element>

All Implemented Interfaces:

Iterable<Element>, Collection<Element>, List<Element>

public class NBestList<Element extends Scorable>
extends AbstractSequentialList<Element>

Implementation of a n-best list with b and beta pruning.

Elements with high-valued scores are interpreted to be "better" than elements with low-valued scores.

Elements with infinite scores are not allowed in the list.

Version:

$LastChangedDate: 2007-11-14 09:28:40 -0600 (Wed, 14 Nov 2007) $

Author:

Lane Schwartz

Field Summary

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

NBestList(int b)
Represents an n-best list, as defined in Chiang (2005).

NBestList(int b, double beta, boolean acceptNaN)
Represents an n-best list, as defined in Chiang (2005).

Method Summary

boolean	add(Element e) Attempt to add an item to the list
boolean	isEmpty()
Iterator<Element>	iterator() Return an iterator capable of traversing the list in order from best element to worst element.
ListIterator<Element>	listIterator(int index)
int	size() Get the number of elements in the list.

Methods inherited from class java.util.AbstractSequentialList

add, addAll, get, remove, set

Methods inherited from class java.util.AbstractList

clear, equals, hashCode, indexOf, lastIndexOf, listIterator, removeRange, subList

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.List

addAll, contains, containsAll, remove, removeAll, retainAll, toArray, toArray

Constructor Detail

NBestList

public NBestList(int b,
                 double beta,
                 boolean acceptNaN)

Represents an n-best list, as defined in Chiang (2005).

Parameters:

beta - any item that has a score worse than beta plus the score of the best item in the list will not be added to the list

b - any item that has a score worse than the bth best item in the list will not be added to the list

acceptNaN - Determines how elements with NaN score will be treated; if true then such elements will simply not be added to the list, if false then any attempt to add such an element will cause an IllegalArgumentException to be thrown

NBestList

public NBestList(int b)

Represents an n-best list, as defined in Chiang (2005).

Equivalent to NBestList(b, Double.POSITIVE_INFINITY, false)

Parameters:

b - any item that has a score worse than the bth best item in the list will not be added to the list

Method Detail

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Collection<Element extends Scorable>

Specified by:

isEmpty in interface List<Element extends Scorable>

Overrides:

isEmpty in class AbstractCollection<Element extends Scorable>

add

public boolean add(Element e)

Attempt to add an item to the list

If Double.isInfinite(e.getScore()) is true, this method will return false

Specified by:

add in interface Collection<Element extends Scorable>

Specified by:

add in interface List<Element extends Scorable>

Overrides:

add in class AbstractList<Element extends Scorable>

Parameters:

e - item to add to the list

Returns:

true if the item was added to the list, false otherwise

size

public int size()

Get the number of elements in the list.

Implementation note: this method traverses the entire underlying linked list to calculate the size of the list

Specified by:

size in interface Collection<Element extends Scorable>

Specified by:

size in interface List<Element extends Scorable>

Specified by:

size in class AbstractCollection<Element extends Scorable>

Returns:

the number of elements in the list

iterator

public Iterator<Element> iterator()

Return an iterator capable of traversing the list in order from best element to worst element.

Specified by:

iterator in interface Iterable<Element extends Scorable>

Specified by:

iterator in interface Collection<Element extends Scorable>

Specified by:

iterator in interface List<Element extends Scorable>

Overrides:

iterator in class AbstractSequentialList<Element extends Scorable>

Returns:

an iterator for the list

listIterator

public ListIterator<Element> listIterator(int index)

Specified by:

listIterator in interface List<Element extends Scorable>

Specified by:

listIterator in class AbstractSequentialList<Element extends Scorable>