[[PageOutline]] 
= Libraries =

Looking to contribute to the Fortress library effort, but don't know where to start?  Look no further!  Any library coding you do for Fortress will of course be appreciated, but we're particularly keen to solicit contributions in these areas:

== Collection Classes == #collection-classes
[[TracNav]]

There are two basic versions of the collections hierarchy: an immutable one, which must be implemented by every single Collections type, and a mutable one, which is not supported by every collection type.  Note that every collection operation must appear to be `atomic` from the perspective of client code.  For completely immutable collections this will not be an issue.  For collections which make use of mutation, either because they provide the mutable collection interface or because they make use of mutation internally, this requires a certain amount of care.  It is simplest to declare all the methods on these objects to be atomic.  In practice, of course, there are more efficient (but much trickier) ways of writing collection types to provide the appearance of atomicity.

=== Some collection data structures we would love to see ===

 * Red-Black trees (important: must include a merge / union operation)
 * Digital tries
 * Hash tables
 * BDDs, as sets, maps, and relations.
 * B-Trees
 * Sets based on sorted lists
 * Any other good set or map data structure.  See [source:trunk/Library/Set.fss] and [source:trunk/Library/Map.fss] for appropriate pure apis; these use weight-balanced trees.
 * ~~Prefix trees~~ (see [source:trunk/Library/PrefixSet.fss PrefixSet.fss] and [source:trunk/Library/PrefixMap.fss PrefixMap.fss]) and suffix trees
 * Queues (pure queues supported by [source:trunk/Library/PureList.fss PureList.fss] and [source:trunk/Library/ArrayList.fss ArrayList.fss])
 * Deques (pure deques supported by [source:trunk/Library/PureList.fss PureList.fss] and [source:trunk/Library/ArrayList.fss ArrayList.fss])
 * ~~Finger trees~~ (see [source:trunk/Library/PureList.fss PureList.fss])
 * ~~Array-based lists~~ (see [source:trunk/Library/ArrayList.fss ArrayList.fss])
 * ~~Priority queues~~ (see [source:trunk/Library/Heap.fss Heap.fss], though better implementations welcome)
 * ~~Catenable deques~~ (again see [source:trunk/Library/PureList.fss PureList.fss] and [source:trunk/Library/ArrayList.fss ArrayList.fss])
 * ~~Pure Skip Lists~~ (see [source:trunk/Library/SkipList.fss SkipList.fss] courtesy of Michael Spiegel)
 * Simple bindings to give a mutable interface to an immutable collection of a particular type, and vice versa (the latter should be easy).
 * Simple binding to turn a map implementation into a bag implementation by storing counts of occurrences of elements.
 * Simple binding to turn a map into a set using void values.
 * Simple binding to turn a map and a set into a relation.

=== The collection hierarchy (current proposal) ===

{{{
Collection
    Multiset
        List
            Tree
                SortedTree
            SortedList
                SortedTree
                SortedListWithNoDuplicates
            ListWithNoDuplicates
                SortedListWithNoDuplicates
            Array1D
        Set = MultisetWithNoDuplicates
            SetWithComplements
                SetOverFiniteDomain
        SortedMultiset
            SortedList
        Histogram
        Array
            Array1D
            Array2D
            Array3D
            ...
    RelationCollection
        Relation
            Map
            SortedRelation
                SortedMap
        MapCollection
            Map
                SortedMap
                    Array1D
                Array
            SortedMapCollection
                SortedMap
        SortedRelationCollection
            SortedRelation
            SortedMapCollection
    SortedCollection
        SortedList
        SortedRelationCollection
}}}

=== A collection API ===

We haven't yet fixed a base class for collections, but here is some of the basic functionality a collection might contain.  These are all written in method style; since the interpreter doesn't currently support functional methods, operators will be defined to call through to methods.  Note that many of these will have default implementations, and usually want to be specialized for arguments of the same collection type rather than for generic collections.

Immutable:
 * Must extend `Generator` as appropriate, and provide a `generate` method.
 * A vararg factory, and another factory which takes a generator as an argument.  These should probably be overloadings of the same  function (a braketing operator where appropriate).
 * An empty collection of appropriate name and type (and eventually with a coercion from `Empty`).  This could be a 0-argument invocation of the factory.
 * `opr =`, in terms of `opr =` on elements (all mentions of !"equal!" here mean !"according to `opr =`!").
 * `toString()`
 * `add(x)` to add a single element `x` and return a new collection; by default it adds to the front of an ordered collection.
 * `addEnd(x)` to add a single element `x` and return a new collection; by default it adds to the end of an ordered collection.
 * `adjoin(c)` returns a new collection containing the elements of this collection and the elements of `c`; this collection comes first if they are ordered.  This corresponds to `opr UNION` on sets.  For parallelism it is important to make this efficient.
 * `adjoinDisjoint(c)` works as `adjoin` but requires that `c` be nonoverlapping with the present collection.
 * `remove(x)` returns a new collection in which all occurrences of `x` (in the sense of `opr =`) have been removed.
 * `removeFirst(x)` returns a new collection in which one occence of `x` (the first, if ordered) has been removed.
 * `disjoin(c)` returns a new collection containing the elements of this collection, with any elements `opr =` to those in `c` removed.  This  is equivalent to set difference on sets.  If order matters, it is preserved in the new collection.
 * `intersect(c)` returns a new collection containing the elements of this collection which also occur in `c`.  This is equivalent to intersection on sets.  Again, if order matters it is preserved in the new collection.
 * `contains(x)` returns true if the collection contains an element `opr =` to `x`.  This is equivalent to `opr ELEM`
 * `isEmpty()` returns true if the collection is empty.
 * `overlaps(c)` returns true if the collection has any elements in common with `c`.
 * `size()` returns the number of elements in the collection.
 * `occurrencesOf(x)` returns the number of occurrences of element `x` in the collection.
 * `first()` returns the first element of the collection (which can be arbitrary if the collection is unordered).
 * `firstRest()` returns a pair of the first element and the remainder of the collection with the first element removed.
 * `last()` returns the last element of the collection (again arbitrary if the collection is unordered).
 * `initLast()` returns a pair of the collection without the last element, and the last element.
 * `opr [i:ZZ32]` and `indices` generator for ordered collections (0-indexed access).
 * `opr [k:K]` and `indices` generator for maps.
 * `indexOf(x)`, index of first occurrence of `x` in an ordered collection.
 * `values()` collection for a map.
 * `inverse()` convert a map or relation to a relation

For maps and relations, most of the above methods are in terms of keys.  Insertion should take a (key,value) pair.

The mutable interface is much the same, but adds "To" to adders, so we get `addTo` and `addToEnd` and `adjoinTo`, and adds "From" to removers, so we get `removeFrom` and `firstFrom`.  In both cases the return type is `()` to avoid confusion with the non-mutable functionality.

== Numeric libraries and solvers == #numerics

 * Useful transcendental functions currently lacking: hyperbolics, Gaussian error functions, Bessel functions, etc.
 * Complex numbers
 * Rational numbers
 * Polynomials
 * Quaternions
 * Infinite-precision real arithmetic
 * Implicit numeric differentiation (in which derivatives are computed alongside point data)
 * Root finding of various sorts (Newton's method, binary decomposition, etc.)
 * FFT
 * Cholesky factorization
 * Anything in BLAS, LAPACK, and LINPACK
 * Realistic conjugate gradient implementations with preconditioners
 * Eigenvalue methods of all kinds
 * Linear programming, dense and sparse
 * Integer linear programming

== Sparse grid representations == #sparse-grids

 * Mesh representations and !DeLaunay triangulation
 * Multigrid representations, with refinement methods
 * Space-partitioning representations such as quad- and oct-trees

== Bindings to existing Java functionality == #java-bindings

 * Binary input and output
 * Efficient numeric arrays
 * Bindings to existing libraries such as ATLAS and FFTW (requires JNI + implementation hacking, but well worth it)

== Input and Output == #io

 * A `printf` or Fortran `format` equivalent
 * Pretty printing library
 * Combinator-based parser library