1 /* catdvi - get text from DVI files 2 Copyright (C) 2000-01 Bjoern Brill <brill@fs.math.uni-frankfurt.de> 3 4 This program is free software; you can redistribute it and/or modify 5 it under the terms of the GNU General Public License as published by 6 the Free Software Foundation; either version 2 of the License, or 7 (at your option) any later version. 8 9 This program is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 GNU General Public License for more details. 13 14 You should have received a copy of the GNU General Public License 15 along with this program; if not, write to the Free Software 16 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 17 */ 18 19 #ifndef DENSITY_H 20 #define DENSITY_H 21 22 /* Implements a staircase (i.e. piecewise constant) density function 23 * on an interval [xmin, xmax]. 24 * 25 * The domain can be integral or "real" (float, double), the range should 26 * be "real". 27 * 28 * The implementation is NOT numerically sophisticated, so don't expect 29 * miracles. 30 */ 31 32 33 /* There's no need to use these two typdefs in an application. They 34 * are here for logical clarity and easy customization and can be changed 35 * as needed. 36 */ 37 #include "bytesex.h" /* for sint32 */ 38 typedef sint32 scdf_domain_t; 39 typedef double scdf_range_t; 40 41 /* convenience defs - c++ does this automatically */ 42 #ifndef __cplusplus 43 typedef struct scdf_t scdf_t; 44 typedef struct scdf_step_t scdf_step_t; 45 #endif 46 47 /* The function is stored as a (singly) linked list of steps. Its value 48 * f(x) is step.f for x in the half-open interval [step.x, step.next->x) . 49 * For technical reasons, we keep a last step with last.x = xmax and 50 * last.next = NULL. last.f is not important since any value f(xmax) will 51 * give the same integral of f. 52 * 53 * Typical applications will traverse [xmin, xmax) as a union of subintervals 54 * [x0, x1) from left to right. We try to keep this direction efficient. 55 */ 56 57 struct scdf_step_t { 58 scdf_domain_t x; 59 scdf_range_t f; 60 scdf_step_t * next; 61 }; 62 63 struct scdf_t { 64 scdf_domain_t xmin; 65 scdf_domain_t xmax; 66 scdf_step_t * head; 67 scdf_step_t * curr; 68 }; 69 70 71 void scdf_init( 72 scdf_t * this, 73 scdf_domain_t xmin, 74 scdf_domain_t xmax, 75 scdf_range_t f /* The initial (constant) value of f - usually 0 */ 76 ); 77 78 79 void scdf_done(scdf_t * this); 80 81 /* Join neighbouring steps with the same f. This should be done at the 82 * end of a sequence of operations traversing [xmin, xmax] . 83 */ 84 void scdf_normalize(scdf_t * this); 85 86 87 /* Force the density function to have at least value fmin in the interval 88 * [x0, x1). Mathematically: let g have value fmin on [x0, x1) and value 89 * (-infinity) elsewhere, then f is replaced by the pointwise maximum of 90 * f and g. 91 */ 92 void scdf_force_min_value( 93 scdf_t * this, 94 scdf_domain_t x0, 95 scdf_domain_t x1, 96 scdf_range_t fmin 97 ); 98 99 100 /* Force f to have at least integral Jmin on [x0, x1]. This is currently 101 * done by first checking if the integral is large enough anyway, and 102 * forcing f to have value at least Jmin / (x1 - x0) if not. More 103 * sophisticated (keeping f smaller in some cases) methods are possible. 104 * However, some experiments with real world data for the intended application 105 * (catdvi) have shown that: 106 * - Methods that tend to evenly distribute the density (like the 107 * one implemented here) do in almost all cases yield better results 108 * (both in terms of appearance of output and of shorter lines) than 109 * an exact "additive" method which gives rather uneven distributions. 110 * - Replacing Jmin / (x1 - x0) by a quantity deviating at most 1/128 111 * from the minimal possible value gains 1-3 columns for some lines 112 * and nothing most of the time. 113 * Since the currently implemented method is fast and seems to be nearly 114 * optimal for typical catdvi input, we'll probably stick with it. 115 */ 116 void scdf_force_min_integral( 117 scdf_t * this, 118 scdf_domain_t x0, 119 scdf_domain_t x1, 120 scdf_range_t Jmin 121 ); 122 123 124 /* Find the value of f at x */ 125 scdf_range_t scdf_eval(scdf_t * this, scdf_domain_t x); 126 127 128 /* Compute the integral of f on [x0, x1] */ 129 scdf_range_t scdf_integral(scdf_t * this, scdf_domain_t x0, scdf_domain_t x1); 130 131 132 /* Solve the equation "integral of f on [x0, x1] = J" for x1; 133 * set errno = EDOM if this is not possible. 134 * 135 * The algorithm used has to do a conversion from scdf_range_t to 136 * scdf_domain_t, which is done by casting a _positive_ value of 137 * type scdf_range_t to scdf_domain_t. This should result in rounding 138 * the return value towards (-infinity) in cases where loss of precision 139 * occurs. 140 */ 141 scdf_domain_t scdf_solve_integral_for_x1( 142 scdf_t * this, 143 scdf_domain_t x0, 144 scdf_range_t J 145 ); 146 147 /* Create new staircase function 148 * F(x) = floor(integral(f(t), t = f.xmin..x)) 149 * on the heap; return pointer to it. Abort if OOM. 150 * F obviously has the same domain of definition as f. 151 */ 152 scdf_t * scdf_floor_of_integral(scdf_t * this); 153 154 /* Dump a textual representation of f to stderr */ 155 void scdf_dump(scdf_t * this); 156 157 #endif 158