Compilation
===========

To compile sbbi, just run 'make'. If there are any problems, look
at the Makefile (it is very simple).

Installation
============

No installation is necessary, just run the program. You can also
copy the binary "sbbi" to a directory that is in your PATH.
A good choice is usually /usr/local/bin/ if it is writable to you.

Running
=======

To see the command-line options, run "sbbi -h" for help. The input
permutations should be provided as a sequence of positive integers,
separated by whitespace (space, tab, newline). Since both space and
newline can be used, the permutation can be stored in one row, like so:
1 4 2 3 5
It can also be stored in one 'column', like so:
1
4
2
3
5
Both types can be intermixed:
1 4 2
3 5
In any case, the whole file will be interpreted as just one permutation.

Credits
=======

Jens Stoye came up with the general idea for the improvement to Christie's
algorithm while working with Julia Mixtacki on genome rearrangement
problems.

The implementation was done by Marcel Martin.

The original algorithm is by David A. Christie [2].

The balanced binary tree is an Andersson tree, introduced by Arne
Andersson [1].

Independently of our own research, Feng and Zhu [3] proposed the same
improvement. They call the data structure a permutation tree. The idea
to split the tree into three parts to find the maximum element is taken
from their paper. A previous version of our code had its own procedure
(doing complicated tree traversals) for doing that.

The algorithm for splitting and merging balanced binary trees is described
by Robert E. Tarjan [4].

Homepage
========

The most recent version of sbbi is available at
http://BiBiServ.CeBiTec.Uni-Bielefeld.DE/sbbi/

License
=======

The code is MIT-licensed. See the source code for the complete license text.

References
==========

[1] Arne Andersson. Balanced search trees made simple.
In  Proc. Workshop on Algorithms and Data Structures, pages 60--71.
Springer Verlag, 1993.

[2] David A. Christie. Sorting permutations by block-interchanges.
Information Processing Letters 60 (1996) 165-169.

[3] Jianxing Feng and Daming Zhu. Faster Algorithms for Sorting by
Transpositions and Sorting by Block-Interchanges.
ACM Transactions on Algorithms (TALG). Volume 3, Issue 3 (August 2007).

[4] Robert Endre Tarjan. Data Structures and Network Algorithms,
Section 4.2, pages 52f. ISBN 0-89871-187-8.

alternative to [2]:
Jianxing Feng and Daming Zhu. Faster Algorithms for Sorting by Transpositions
and Sorting by Block-Interchanges. TAMC 2006, 128--137.
