Algorithms in the std lib

[bearophile]

Seeing how the Phobos is being worked on, I think it's a good moment to think about other things that it can eventually contain.
In all the languages that I use I slowly create a lib of algorithms and data structures and similar stuff.

Every programmer has special needs that require external modules, a standard lib can't contain everything. But often you can find two levels of needs: a more general one and a more specialized one. For example in the std lib of Python you can find lazy generators of permutations and combinators. They are often useful, but they can't be enough for people that work a lot with with combinatorics. Such people have to write or download a module with much more specific stuff.

So I think the std lib of D may enjoy some more algorithms, to fulfill better the "general needs".
Some of the following algorithms may be already present in Phobos and/or Tango, in such case please ignore them.

The following stuff is already implemented in my dlibs, and I use it:

bisect:
  Return the index where to insert item x in an array a, assuming a is sorted. 

isInSorted:
  Given a sorted array, an item, and an optional key callable (like the key of bisect()), used a binary search and answers true if the item is present, false otherwise.

binomial(n, k)
factorial
combinations/xcombinations
permutations/xpermutations
subsets/xsubsets
xlexicalPermutations
apply (see lisp)
mapApply(map an apply on an iterable)

convexHull2D
polygonCentroid
RGB2HSV
HSBV2RGB
floodFill

all/any
  (all or any of the items of an iterable are true or is true a given predicate on them)

nextPow2
isPow2
powMod

reverseBits
  Quickly reverse the bits in a ubyte/uint. 


partition/xpartition
  splits an iterable in sub-iterables of fixed length

gcd

xprimes (yields primes lazily at hyper speed)

nrank
median/medianObj

thousands(n)  (1000000 => "1_000_000")
joinArray
xsplit
numSorted (smart sort foo1x comes before foo10x)

allEqual
filterAA (associative arrays)
get a.get(2, "def") ==> "def" (for associative arrays)

rotateLeft/rotateRight (for arrays)
AAintersection

maxs
  Given an iterable 'iter', return a new array of the equally maximum items of 'iter'.
mins

xgroupBy/xgroupBync
  This is really useful: it takes an iterable and an optional predicate. This iterable object yields consecutive key(item) and group arrays from the given iterable that have the same result or are all true or all false (it can also yield just the group arrays, or it can yield the index too).

pop (removes last of an array/AA and returns it)
prepend (for arrays, adds at the start)

There is a refined function to flatten nested iterables.

----------------

The following stuff is present in my Python "bag of tricks", I'll probably want to translate them for D1 too:

baseConvert (base[1,64] => base[1, 64])
To convert numbers to strings from/to any base.

K-means

IntervalMap (map of intervals, a kind of associative data structure)

toposort (topological sort, already in Graph below, but also as a single external function for simpler usages).

Odict (associative array where items are also ordered according to the insertion order, they are in a double linked list)

mean
mode
stdev

digitalLine
  Brensenham line algorithm, returns an iterator of (x,y) coords (not useful for the screen)
digitalCircle
segmentSegmentIntersection

triangleContains (predicate, is point into triangle?)

A directed Graph data structure, the class contains most common graph algorithms.
http://sourceforge.net/projects/pynetwork/
(I have already partially implemented this in D1).

-----------------

You may want to add some things to this list, or to remove things you think aren't useful enough for lot of people.

Bye,
bearophile

IntervalMap (map of intervals, a kind of associative data structure)

toposort (topological sort, already in Graph below, but also as a single external function for simpler usages).

Odict (associative array where items are also ordered according to the insertion order, they are in a double linked list)

mean
mode
stdev

digitalLine
  Brensenham line algorithm, returns an iterator of (x,y) coords (not useful for the screen)
digitalCircle
segmentSegmentIntersection

triangleContains (predicate, is point into triangle?)

A directed Graph data structure, the class contains most common graph algorithms.
http://sourceforge.net/projects/pynetwork/
(I have already partially implemented this in D1).

-----------------

You may want to add some things to this list, or to remove things you think aren't useful enough for lot of people.Soggetto: Algorithms in the std lib

Seeing how the Phobos is being worked on, I think it's a good moment to think about other things that it can eventually contain.
In all the languages that I use I slowly create a lib of algorithms and data structures and similar stuff.

Every programmer has special needs that require external modules, a standard lib can't contain everything. But often you can find two levels of needs: a more general one and a more specialized one. For example in the std lib of Python you can find lazy generators of permutations and combinators. They are often useful, but they can't be enough for people that work a lot with with combinatorics. Such people have to write or download a module with much more specific stuff.

So I think the std lib of D may enjoy some more algorithms, to fulfill better the "general needs".
Some of the following algorithms may be already present in Phobos and/or Tango, in such case please ignore them.

The following stuff is already implemented in my dlibs, and I use it:

bisect:
  Return the index where to insert item x in an array a, assuming a is sorted. 

isInSorted:
  Given a sorted array, an item, and an optional key callable (like the key of bisect()), used a binary search and answers true if the item is present, false otherwise.

binomial(n, k)
factorial
combinations/xcombinations
permutations/xpermutations
subsets/xsubsets
xlexicalPermutations
apply (see lisp)
mapApply(map an apply on an iterable)

convexHull2D
polygonCentroid
RGB2HSV
HSBV2RGB
floodFill

all/any
  (all or any of the items of an iterable are true or is true a given predicate on them)

nextPow2
isPow2
powMod

reverseBits
  Quickly reverse the bits in a ubyte/uint. 


partition/xpartition
  splits an iterable in sub-iterables of fixed length

gcd

xprimes (yields primes lazily at hyper speed)

nrank
median/medianObj

thousands(n)  (1000000 => "1_000_000")
joinArray
xsplit
numSorted (smart sort foo1x comes before foo10x)

allEqual
filterAA (associative arrays)
get a.get(2, "def") ==> "def" (for associative arrays)

rotateLeft/rotateRight (for arrays)
AAintersection

maxs
  Given an iterable 'iter', return a new array of the equally maximum items of 'iter'.
mins

xgroupBy/xgroupBync
  This is really useful: it takes an iterable and an optional predicate. This iterable object yields consecutive key(item) and group arrays from the given iterable that have the same result or are all true or all false (it can also yield just the group arrays, or it can yield the index too).

pop (removes last of an array/AA and returns it)
prepend (for arrays, adds at the start)

There is a refined function to flatten nested iterables.

----------------

The following stuff is present in my Python "bag of tricks", I'll write some of this for D1 too:

baseConvert (base[1,64] => base[1, 64])
To convert numbers to strings from/to any base.

K-means

IntervalMap (map of intervals, a kind of associative data structure)

toposort (topological sort, already in Graph below, but also as a single external function for simpler usages).

Odict (associative array where items are also ordered according to the insertion order, they are in a double linked list)

mean
mode
stdev

digitalLine
  Brensenham line algorithm, returns an iterator of (x,y) coords (not useful for the screen)
digitalCircle
segmentSegmentIntersection

triangleContains (predicate, is point into triangle?)

A directed Graph data structure, the class contains most common graph algorithms.
http://sourceforge.net/projects/pynetwork/
(I have already partially implemented this in D1).

-----------------

You may want to add some things to this list, or to remove things you think aren't useful enough for lot of people.

Bye,
bearophile