summaryrefslogtreecommitdiff
path: root/dviware/catdvi/density.h
diff options
context:
space:
mode:
Diffstat (limited to 'dviware/catdvi/density.h')
-rw-r--r--dviware/catdvi/density.h157
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