basetypes

Type Members

1. class EmptyHeap[T, HC <: HeapCollector[T, HC]] extends LeftistHeap[T, HC]

   

   Use this class to construct new heaps

2. trait HeapCollector[-T, HC] extends AnyRef

   

   A general interface for collecting informations about elements stored in a heap (in particular, in a LeftistHeap).

   A general interface for collecting informations about elements stored in a heap (in particular, in a LeftistHeap). This class can be seen as a monomoid morphism, mapping a heap (seen as a multiset or monoid) to something else.

3. final class IdealInt extends AnyRef

   

4. final class IdealRat extends Ordered[IdealRat]

   

   Naive implementation of rational numbers

5. abstract class LeftistHeap[T, HC <: HeapCollector[T, HC]] extends Iterable[T] with IterableLike[T, LeftistHeap[T, HC]]

   

   This class implements the leftist heap, see "Functional Data Structures" by Chris Okasaki

6. class MultiSet[A] extends (A) ⇒ Int

   

   A simple class to represent multisets

7. case class Node[T, HC <: HeapCollector[T, HC]](data: T, left: LeftistHeap[T, HC], right: LeftistHeap[T, HC], emptyHeap: LeftistHeap[T, HC])(implicit ord: Ordering[T]) extends LeftistHeap[T, HC] with Product with Serializable

   

   Class for non-empty heaps.

   Class for non-empty heaps. We also keep a reference to the empty heap to avoid creating new objects (ugly ... there should really be explicit Node-classes for nodes with no or only one child)

8. class SortedIterator[A, HC <: HeapCollector[A, HC]] extends Iterator[A]

   

   Class for iterating the elements of a heap in increasing order

9. class TestIdealInt extends APTestCase

   

10. class TestLeftistHeap extends APTestCase

    

11. case class Tree[D](d: D, children: List[Tree[D]]) extends Product with Serializable

    

    Polymorphic class for representing finite trees, with unbounded branching.

12. class UnionFind[D] extends Cloneable

    

    A simple, textbook implementation of a union-find data structure.

13. class UnsortedIterator[A, HC <: HeapCollector[A, HC]] extends Iterator[A]