1 /* -*-C-*-
2 ********************************************************************************
3 *
4 * File: matchtab.c (Formerly matchtab.c)
5 * Description: Match table to retain blobs that were matched.
6 * Author: Mark Seaman, OCR Technology
7 * Created: Mon Jan 29 09:00:56 1990
8 * Modified: Tue Mar 19 15:09:06 1991 (Mark Seaman) marks@hpgrlt
9 * Language: C
10 * Package: N/A
11 * Status: Experimental (Do Not Distribute)
12 *
13 * (c) Copyright 1990, Hewlett-Packard Company.
14 ** Licensed under the Apache License, Version 2.0 (the "License");
15 ** you may not use this file except in compliance with the License.
16 ** You may obtain a copy of the License at
17 ** http://www.apache.org/licenses/LICENSE-2.0
18 ** Unless required by applicable law or agreed to in writing, software
19 ** distributed under the License is distributed on an "AS IS" BASIS,
20 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
21 ** See the License for the specific language governing permissions and
22 ** limitations under the License.
23 *
24 *********************************************************************************/
25 /*----------------------------------------------------------------------
26 I n c l u d e s
27 ----------------------------------------------------------------------*/
28
29 #include "matchtab.h"
30
31 #include "blobs.h"
32 #include "callcpp.h"
33 #include "elst.h"
34 #include "freelist.h"
35 #include "ratngs.h"
36
37 /*----------------------------------------------------------------------
38 T y p e s
39 ----------------------------------------------------------------------*/
40 typedef struct _MATCH_
41 {
42 int topleft;
43 int botright;
44 BLOB_CHOICE_LIST *rating;
45 } MATCH;
46
47 /*----------------------------------------------------------------------
48 V a r i a b l e s
49 ----------------------------------------------------------------------*/
50 MATCH *match_table;
51 //?int missed_count = 0;
52
53 /*----------------------------------------------------------------------
54 M a c r o s
55 ----------------------------------------------------------------------*/
56 #define NUM_MATCH_ENTRIES 500 /* Entries in match_table */
57
58 /**********************************************************************
59 * blank_entry
60 *
61 * Test an element in the blob match table to see if it is blank.
62 * Return a non-zero value if it is blank.
63 **********************************************************************/
64
65 #define blank_entry(match_table,x) \
66 (! (match_table[x].topleft | match_table[x].botright))
67
68 /*----------------------------------------------------------------------
69 Public Function Code
70 ----------------------------------------------------------------------*/
71 /**********************************************************************
72 * init_match_table
73 *
74 * Create and clear a match table to be used to speed up the splitter.
75 **********************************************************************/
76 static int been_initialized = 0;
init_match_table()77 void init_match_table() {
78 int x;
79
80 if (been_initialized) {
81 /* Reclaim old choices */
82 for (x = 0; x < NUM_MATCH_ENTRIES; x++) {
83 if ((!blank_entry (match_table, x)) && match_table[x].rating)
84 match_table[x].rating->clear();
85 delete match_table[x].rating;
86 }
87 }
88 else {
89 /* Allocate memory once */
90 been_initialized = 1;
91 match_table = new MATCH[NUM_MATCH_ENTRIES];
92 }
93 /* Initialize the table */
94 for (x = 0; x < NUM_MATCH_ENTRIES; x++) {
95 match_table[x].topleft = 0;
96 match_table[x].botright = 0;
97 match_table[x].rating = NULL;
98 }
99 }
100
end_match_table()101 void end_match_table() {
102 if (been_initialized) {
103 init_match_table();
104 delete[] match_table;
105 match_table = NULL;
106 been_initialized = 0;
107 }
108 }
109
110
111 /**********************************************************************
112 * put_match
113 *
114 * Put a new blob and its corresponding match ratings into the match
115 * table.
116 **********************************************************************/
put_match(TBLOB * blob,BLOB_CHOICE_LIST * ratings)117 void put_match(TBLOB *blob, BLOB_CHOICE_LIST *ratings) {
118 unsigned int topleft;
119 unsigned int botright;
120 unsigned int start;
121 TPOINT tp_topleft;
122 TPOINT tp_botright;
123 int x;
124 /* Hash into table */
125 blob_bounding_box(blob, &tp_topleft, &tp_botright);
126 topleft = *(unsigned int *) &tp_topleft;
127 botright = *(unsigned int *) &tp_botright;
128 start = (topleft * botright) % NUM_MATCH_ENTRIES;
129
130 /* Look for empty */
131 x = start;
132 do {
133 if (blank_entry (match_table, x)) {
134 /* Add this entry */
135 match_table[x].topleft = topleft;
136 match_table[x].botright = botright;
137 // Copy ratings to match_table[x].rating
138 match_table[x].rating = new BLOB_CHOICE_LIST();
139 match_table[x].rating->deep_copy(ratings, &BLOB_CHOICE::deep_copy);
140 return;
141 }
142 if (++x >= NUM_MATCH_ENTRIES)
143 x = 0;
144 }
145 while (x != start);
146
147 cprintf ("error: Match table is full\n");
148 }
149
150
151 /**********************************************************************
152 * get_match
153 *
154 * Look up this blob in the match table to see if it needs to be
155 * matched. If it is not present then NULL is returned.
156 **********************************************************************/
get_match(TBLOB * blob)157 BLOB_CHOICE_LIST *get_match(TBLOB *blob) {
158 unsigned int topleft;
159 unsigned int botright;
160 TPOINT tp_topleft;
161 TPOINT tp_botright;
162 /* Do starting hash */
163 blob_bounding_box(blob, &tp_topleft, &tp_botright);
164 topleft = *(unsigned int *) &tp_topleft;
165 botright = *(unsigned int *) &tp_botright;
166 return (get_match_by_bounds (topleft, botright));
167 }
168
169
170 /**********************************************************************
171 * get_match_by_bounds
172 *
173 * Look up this blob in the match table to see if it needs to be
174 * matched. If it is not present then NULL is returned.
175 **********************************************************************/
get_match_by_bounds(unsigned int topleft,unsigned int botright)176 BLOB_CHOICE_LIST *get_match_by_bounds(unsigned int topleft,
177 unsigned int botright) {
178 unsigned int start;
179 int x;
180 /* Do starting hash */
181 start = (topleft * botright) % NUM_MATCH_ENTRIES;
182 /* Search for match */
183 x = start;
184 do {
185 /* Not found when blank */
186 if (blank_entry (match_table, x))
187 break;
188 /* Is this the match ? */
189 if (match_table[x].topleft == topleft &&
190 match_table[x].botright == botright) {
191 BLOB_CHOICE_LIST *blist = new BLOB_CHOICE_LIST();
192 blist->deep_copy(match_table[x].rating, &BLOB_CHOICE::deep_copy);
193 return blist;
194 }
195 if (++x >= NUM_MATCH_ENTRIES)
196 x = 0;
197 }
198 while (x != start);
199 return NULL;
200 }
201
202 /**********************************************************************
203 * add_to_match
204 *
205 * Update ratings list in the match_table corresponding to the given
206 * blob. The function assumes that:
207 * -- the match table contains the initial non-NULL list with choices
208 * for the given blob
209 * -- the new ratings list is a superset of the corresponding list in
210 * the match_table and the unichar ids of the blob choices in the
211 * list are unique.
212 * The entries that appear in the new ratings list and not in the
213 * old one are added to the old ratings list in the match_table.
214 **********************************************************************/
add_to_match(TBLOB * blob,BLOB_CHOICE_LIST * ratings)215 void add_to_match(TBLOB *blob, BLOB_CHOICE_LIST *ratings) {
216 unsigned int topleft;
217 unsigned int botright;
218 TPOINT tp_topleft;
219 TPOINT tp_botright;
220 blob_bounding_box(blob, &tp_topleft, &tp_botright);
221 topleft = *(unsigned int *) &tp_topleft;
222 botright = *(unsigned int *) &tp_botright;
223 unsigned int start;
224 int x;
225 /* Do starting hash */
226 start = (topleft * botright) % NUM_MATCH_ENTRIES;
227 /* Search for match */
228 x = start;
229 do {
230 if (blank_entry(match_table, x)) {
231 fprintf(stderr, "Can not update uninitialized entry in match_table\n");
232 ASSERT_HOST(!blank_entry(match_table, x));
233 }
234 if (match_table[x].topleft == topleft &&
235 match_table[x].botright == botright) {
236 // Copy new ratings to match_table[x].rating.
237 BLOB_CHOICE_IT it;
238 it.set_to_list(match_table[x].rating);
239 BLOB_CHOICE_IT new_it;
240 new_it.set_to_list(ratings);
241 assert(it.length() <= new_it.length());
242 for (it.mark_cycle_pt(), new_it.mark_cycle_pt();
243 !it.cycled_list() && !new_it.cycled_list(); new_it.forward()) {
244 if (it.data()->unichar_id() == new_it.data()->unichar_id()) {
245 it.forward();
246 } else {
247 it.add_before_stay_put(new BLOB_CHOICE(*(new_it.data())));
248 }
249 }
250 return;
251 }
252 if (++x >= NUM_MATCH_ENTRIES)
253 x = 0;
254 }
255 while (x != start);
256 }
257