diff options
Diffstat (limited to 'dviware/catdvi/density.h')
-rw-r--r-- | dviware/catdvi/density.h | 157 |
1 files changed, 157 insertions, 0 deletions
diff --git a/dviware/catdvi/density.h b/dviware/catdvi/density.h new file mode 100644 index 0000000000..ae15febbdf --- /dev/null +++ b/dviware/catdvi/density.h @@ -0,0 +1,157 @@ +/* catdvi - get text from DVI files + Copyright (C) 2000-01 Bjoern Brill <brill@fs.math.uni-frankfurt.de> + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. +*/ + +#ifndef DENSITY_H +#define DENSITY_H + +/* Implements a staircase (i.e. piecewise constant) density function + * on an interval [xmin, xmax]. + * + * The domain can be integral or "real" (float, double), the range should + * be "real". + * + * The implementation is NOT numerically sophisticated, so don't expect + * miracles. + */ + + +/* There's no need to use these two typdefs in an application. They + * are here for logical clarity and easy customization and can be changed + * as needed. + */ +#include "bytesex.h" /* for sint32 */ +typedef sint32 scdf_domain_t; +typedef double scdf_range_t; + +/* convenience defs - c++ does this automatically */ +#ifndef __cplusplus +typedef struct scdf_t scdf_t; +typedef struct scdf_step_t scdf_step_t; +#endif + +/* The function is stored as a (singly) linked list of steps. Its value + * f(x) is step.f for x in the half-open interval [step.x, step.next->x) . + * For technical reasons, we keep a last step with last.x = xmax and + * last.next = NULL. last.f is not important since any value f(xmax) will + * give the same integral of f. + * + * Typical applications will traverse [xmin, xmax) as a union of subintervals + * [x0, x1) from left to right. We try to keep this direction efficient. + */ + +struct scdf_step_t { + scdf_domain_t x; + scdf_range_t f; + scdf_step_t * next; +}; + +struct scdf_t { + scdf_domain_t xmin; + scdf_domain_t xmax; + scdf_step_t * head; + scdf_step_t * curr; +}; + + +void scdf_init( + scdf_t * this, + scdf_domain_t xmin, + scdf_domain_t xmax, + scdf_range_t f /* The initial (constant) value of f - usually 0 */ +); + + +void scdf_done(scdf_t * this); + +/* Join neighbouring steps with the same f. This should be done at the + * end of a sequence of operations traversing [xmin, xmax] . + */ +void scdf_normalize(scdf_t * this); + + +/* Force the density function to have at least value fmin in the interval + * [x0, x1). Mathematically: let g have value fmin on [x0, x1) and value + * (-infinity) elsewhere, then f is replaced by the pointwise maximum of + * f and g. + */ +void scdf_force_min_value( + scdf_t * this, + scdf_domain_t x0, + scdf_domain_t x1, + scdf_range_t fmin +); + + +/* Force f to have at least integral Jmin on [x0, x1]. This is currently + * done by first checking if the integral is large enough anyway, and + * forcing f to have value at least Jmin / (x1 - x0) if not. More + * sophisticated (keeping f smaller in some cases) methods are possible. + * However, some experiments with real world data for the intended application + * (catdvi) have shown that: + * - Methods that tend to evenly distribute the density (like the + * one implemented here) do in almost all cases yield better results + * (both in terms of appearance of output and of shorter lines) than + * an exact "additive" method which gives rather uneven distributions. + * - Replacing Jmin / (x1 - x0) by a quantity deviating at most 1/128 + * from the minimal possible value gains 1-3 columns for some lines + * and nothing most of the time. + * Since the currently implemented method is fast and seems to be nearly + * optimal for typical catdvi input, we'll probably stick with it. + */ +void scdf_force_min_integral( + scdf_t * this, + scdf_domain_t x0, + scdf_domain_t x1, + scdf_range_t Jmin +); + + +/* Find the value of f at x */ +scdf_range_t scdf_eval(scdf_t * this, scdf_domain_t x); + + +/* Compute the integral of f on [x0, x1] */ +scdf_range_t scdf_integral(scdf_t * this, scdf_domain_t x0, scdf_domain_t x1); + + +/* Solve the equation "integral of f on [x0, x1] = J" for x1; + * set errno = EDOM if this is not possible. + * + * The algorithm used has to do a conversion from scdf_range_t to + * scdf_domain_t, which is done by casting a _positive_ value of + * type scdf_range_t to scdf_domain_t. This should result in rounding + * the return value towards (-infinity) in cases where loss of precision + * occurs. + */ +scdf_domain_t scdf_solve_integral_for_x1( + scdf_t * this, + scdf_domain_t x0, + scdf_range_t J +); + +/* Create new staircase function + * F(x) = floor(integral(f(t), t = f.xmin..x)) + * on the heap; return pointer to it. Abort if OOM. + * F obviously has the same domain of definition as f. + */ +scdf_t * scdf_floor_of_integral(scdf_t * this); + +/* Dump a textual representation of f to stderr */ +void scdf_dump(scdf_t * this); + +#endif |