Happy new year.
[idzebra-moved-to-github.git] / util / snippet.c
1 /* This file is part of the Zebra server.
2    Copyright (C) 1994-2011 Index Data
3
4 Zebra is free software; you can redistribute it and/or modify it under
5 the terms of the GNU General Public License as published by the Free
6 Software Foundation; either version 2, or (at your option) any later
7 version.
8
9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 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., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
17
18 */
19
20 #include <stddef.h>
21 #include <string.h>
22 #include <yaz/nmem.h>
23 #include <yaz/log.h>
24 #include <yaz/wrbuf.h>
25 #include <idzebra/snippet.h>
26
27 struct zebra_snippets {
28     NMEM nmem;
29     zebra_snippet_word *front;
30     zebra_snippet_word *tail;
31 };
32
33 zebra_snippets *zebra_snippets_create(void)
34 {
35     NMEM nmem = nmem_create();
36     zebra_snippets *l = nmem_malloc(nmem, sizeof(*l));
37     l->nmem = nmem;
38     l->front = l->tail = 0;
39     return l;
40 }
41
42 void zebra_snippets_destroy(zebra_snippets *l)
43 {
44     if (l)
45         nmem_destroy(l->nmem);
46 }
47
48 void zebra_snippets_append(zebra_snippets *l,
49                            zint seqno, int ws, int ord, const char *term)
50 {
51     zebra_snippets_append_match(l, seqno, ws, ord, term, strlen(term), 0);
52 }
53
54 void zebra_snippets_appendn(zebra_snippets *l,
55                             zint seqno, int ws, int ord, const char *term,
56                             size_t term_len)
57 {
58     zebra_snippets_append_match(l, seqno, ws, ord, term, term_len, 0);
59 }
60
61
62 void zebra_snippets_append_match(zebra_snippets *l,
63                                  zint seqno, int ws, int ord,
64                                  const char *term, size_t term_len,
65                                  int match)
66 {
67     struct zebra_snippet_word *w = nmem_malloc(l->nmem, sizeof(*w));
68
69     w->next = 0;
70     w->prev = l->tail;
71     if (l->tail)
72     {
73         l->tail->next = w;
74     }
75     else
76     {
77         l->front = w;
78     }
79     l->tail = w;
80
81     w->seqno = seqno;
82     w->ws = ws;
83     w->ord = ord;
84     w->term = nmem_malloc(l->nmem, term_len+1);
85     memcpy(w->term, term, term_len);
86     w->term[term_len] = '\0';
87     w->match = match;
88     w->mark = 0;
89 }
90
91 zebra_snippet_word *zebra_snippets_list(zebra_snippets *l)
92 {
93     return l->front;
94 }
95
96 const zebra_snippet_word *zebra_snippets_constlist(const zebra_snippets *l)
97 {
98     return l->front;
99 }
100
101 void zebra_snippets_log(const zebra_snippets *l, int log_level, int all)
102 {
103     zebra_snippet_word *w;
104     for (w = l->front; w; w = w->next)
105     {
106         WRBUF wr_term = wrbuf_alloc();
107         wrbuf_puts_escaped(wr_term, w->term);
108
109         if (all || w->mark)
110             yaz_log(log_level, "term='%s'%s mark=%d seqno=" ZINT_FORMAT " ord=%d",
111                     wrbuf_cstr(wr_term), 
112                     (w->match && !w->ws ? "*" : ""), w->mark,
113                     w->seqno, w->ord);
114         wrbuf_destroy(wr_term);
115     }
116 }
117
118 zebra_snippets *zebra_snippets_window(const zebra_snippets *doc,
119                                       const zebra_snippets *hit,
120                                       int window_size)
121 {
122     int ord = -1;
123     zebra_snippets *result = zebra_snippets_create();
124     if (window_size == 0)
125         window_size = 1000000;
126
127     while(1)
128     {
129         zint window_start;
130         zint first_seq_no_best_window = 0;
131         zint last_seq_no_best_window = 0;
132         int number_best_window = 0;
133         const zebra_snippet_word *hit_w, *doc_w;
134         int min_ord = 0; /* not set yet */
135
136         for (hit_w = zebra_snippets_constlist(hit); hit_w; hit_w = hit_w->next)
137             if (hit_w->ord > ord &&
138                 (min_ord == 0 || hit_w->ord < min_ord))
139             {
140                 min_ord = hit_w->ord;
141             }
142         if (min_ord == 0)
143             break;
144         ord = min_ord;
145
146         for (hit_w = zebra_snippets_constlist(hit); hit_w; hit_w = hit_w->next)
147         {
148             if (hit_w->ord == ord)
149             {
150                 const zebra_snippet_word *look_w = hit_w;
151                 int number_this = 0;
152                 zint seq_no_last = 0;
153                 while (look_w && look_w->seqno < hit_w->seqno + window_size)
154                 {
155                     if (look_w->ord == ord)
156                     {
157                         seq_no_last = look_w->seqno;
158                         number_this++;
159                     }
160                     look_w = look_w->next;
161                 }
162                 if (number_this > number_best_window)
163                 {
164                     number_best_window = number_this;
165                     first_seq_no_best_window = hit_w->seqno;
166                     last_seq_no_best_window = seq_no_last;
167                 }
168             }
169         }
170         yaz_log(YLOG_DEBUG, "ord=%d", ord);
171         yaz_log(YLOG_DEBUG, "first_seq_no_best_window=" ZINT_FORMAT,
172                 first_seq_no_best_window);
173         yaz_log(YLOG_DEBUG, "last_seq_no_best_window=" ZINT_FORMAT,
174                 last_seq_no_best_window);
175         yaz_log(YLOG_DEBUG, "number_best_window=%d", number_best_window);
176
177         window_start = (first_seq_no_best_window + last_seq_no_best_window -
178                         window_size) / 2;
179         for (doc_w = zebra_snippets_constlist(doc); doc_w; doc_w = doc_w->next)
180             if (doc_w->ord == ord
181                 && doc_w->seqno >= window_start
182                 && doc_w->seqno < window_start + window_size)
183             {
184                 int match = 0;
185                 for (hit_w = zebra_snippets_constlist(hit); hit_w;
186                      hit_w = hit_w->next)
187                 {
188                     if (hit_w->ord == ord && hit_w->seqno == doc_w->seqno)
189                         
190                     {
191                         match = 1;
192                         break;
193                     }
194                 }
195                 zebra_snippets_append_match(result, doc_w->seqno,
196                                             doc_w->ws,
197                                             ord, doc_w->term, 
198                                             strlen(doc_w->term), match);
199             }
200     }
201     return result;
202 }
203
204 static void zebra_snippets_clear(zebra_snippets *sn)
205 {
206     zebra_snippet_word *w;
207
208     for (w = zebra_snippets_list(sn); w; w = w->next)
209     {
210         w->mark = 0;
211         w->match = 0;
212     }
213 }
214
215 const struct zebra_snippet_word *zebra_snippets_lookup(
216     const zebra_snippets *doc, const zebra_snippets *hit)
217 {
218     const zebra_snippet_word *hit_w;
219     for (hit_w = zebra_snippets_constlist(hit); hit_w; hit_w = hit_w->next)
220     {
221         const zebra_snippet_word *doc_w;
222         for (doc_w = zebra_snippets_constlist(doc); doc_w; doc_w = doc_w->next)
223         {
224             if (doc_w->ord == hit_w->ord && doc_w->seqno == hit_w->seqno
225                 && !doc_w->ws)
226             {
227                 return doc_w;
228             }
229         }
230     }
231     return 0;
232 }
233
234 void zebra_snippets_ring(zebra_snippets *doc, const zebra_snippets *hit,
235                          int before, int after)
236 {
237     int ord = -1;
238
239     zebra_snippets_clear(doc);
240     while (1)
241     {
242         const zebra_snippet_word *hit_w;
243         zebra_snippet_word *doc_w;
244         int min_ord = 0; /* not set yet */
245
246         for (hit_w = zebra_snippets_constlist(hit); hit_w; hit_w = hit_w->next)
247             if (hit_w->ord > ord &&
248                 (min_ord == 0 || hit_w->ord < min_ord))
249             {
250                 min_ord = hit_w->ord;
251             }
252         if (min_ord == 0)
253             break;
254         ord = min_ord;
255
256         for (hit_w = zebra_snippets_constlist(hit); hit_w; hit_w = hit_w->next)
257         {
258             if (hit_w->ord == ord)
259             {
260                 for (doc_w = zebra_snippets_list(doc); doc_w; doc_w = doc_w->next)
261                 {
262                     if (doc_w->ord == ord && doc_w->seqno == hit_w->seqno
263                         && !doc_w->ws)
264                     {
265                         doc_w->match = 1;
266                         doc_w->mark = 1;
267                         break;
268                     }
269                     
270                 }
271                 /* mark following terms */
272                 if (doc_w)
273                 {
274                     zebra_snippet_word *w = doc_w->next;
275                     while (w)
276                         if (w->ord == ord
277                             && hit_w->seqno - before < w->seqno 
278                             && hit_w->seqno + after > w->seqno)
279                         {
280                             w->mark = 1;
281                             w = w->next;
282                         }
283                         else
284                             break;
285                 }
286                 /* mark preceding terms */
287                 if (doc_w)
288                 {
289                     zebra_snippet_word *w = doc_w->prev;
290                     while (w)
291                         if (w->ord == ord
292                             && hit_w->seqno - before < w->seqno 
293                             && hit_w->seqno + after > w->seqno)
294                         {
295                             w->mark = 1;
296                             w = w->prev;
297                         }
298                         else
299                             break;
300                 }
301             }
302         }
303     }
304 }
305
306                          
307 /*
308  * Local variables:
309  * c-basic-offset: 4
310  * c-file-style: "Stroustrup"
311  * indent-tabs-mode: nil
312  * End:
313  * vim: shiftwidth=4 tabstop=8 expandtab
314  */
315