Module wordwrap
wordwrap.py -- public domain code from David Eppstein
http://www.ics.uci.edu/~eppstein/software.html
Break paragraphs into lines, attempting to avoid short lines.
We use the dynamic programming idea of Knuth-Plass to find the optimal
set of breaks according to a penalty function that penalizes short lines
quadratically; this can be done in linear time via the
OnlineConcaveMinima algorithm in SMAWK.py.
D. Eppstein, August 2005.
SMAWK.py
Totally monotone matrix searching algorithms.
The offline algorithm in ConcaveMinima is from Agarwal, Klawe, Moran,
Shor, and Wilbur, Geometric applications of a matrix searching algorithm,
Algorithmica 2, pp. 195-208 (1987).
The online algorithm in OnlineConcaveMinima is from Galil and Park, A
linear time algorithm for concave one-dimensional dynamic programming,
manuscript, 1989, which simplifies earlier work on the same problem by
Wilbur (J. Algorithms 1988) and Eppstein (J. Algorithms 1990).
D. Eppstein, March 2002, significantly revised August 2005
|
|
ConcaveMinima(RowIndices,
ColIndices,
Matrix)
Search for the minimum value in each column of a matrix. |
|
|
|
|
texwrap(lines,
target=76,
longlast=False,
frenchspacing=False,
measure=<built-in function len>,
overpenalty=1000,
nlinepenalty=1000,
onewordpenalty=25,
hyphenpenalty=25)
Wrap the given text, returning a sequence of lines. |
|
|
ConcaveMinima(RowIndices,
ColIndices,
Matrix)
|
|
Search for the minimum value in each column of a matrix.
The return value is a dictionary mapping ColIndices to pairs
(value,rowindex). We break ties in favor of earlier rows.
The matrix is defined implicitly as a function, passed
as the third argument to this routine, where Matrix(i,j)
gives the matrix value at row index i and column index j.
The matrix must be concave, that is, satisfy the property
Matrix(i,j) > Matrix(i',j) => Matrix(i,j') > Matrix(i',j')
for every i<i' and j<j'; that is, in every submatrix of
the input matrix, the positions of the column minima
must be monotonically nondecreasing.
The rows and columns of the matrix are labeled by the indices
given in order by the first two arguments. In most applications,
these arguments can simply be integer ranges.
|