index/zsets.c

   1 /*
   2  * Copyright (C) 1994-2000, Index Data
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: zsets.c,v $
   7  * Revision 1.28  2000-07-07 12:49:20  adam
   8  * Optimized resultSetInsert{Rank,Sort}.
   9  *
  10  * Revision 1.27  2000/04/05 09:49:36  adam
  11  * On Unix, zebra/z'mbol uses automake.
  12  *
  13  * Revision 1.26  2000/03/20 19:08:36  adam
  14  * Added remote record import using Z39.50 extended services and Segment
  15  * Requests.
  16  *
  17  * Revision 1.25  2000/03/15 15:00:31  adam
  18  * First work on threaded version.
  19  *
  20  * Revision 1.24  1999/11/04 15:00:45  adam
  21  * Implemented delete result set(s).
  22  *
  23  * Revision 1.23  1999/05/26 07:49:13  adam
  24  * C++ compilation.
  25  *
  26  * Revision 1.22  1999/02/02 14:51:15  adam
  27  * Updated WIN32 code specific sections. Changed header.
  28  *
  29  * Revision 1.21  1998/11/16 16:03:46  adam
  30  * Moved loggin utilities to Yaz. Was implemented in file zlogs.c.
  31  *
  32  * Revision 1.20  1998/11/16 10:10:53  adam
  33  * Fixed problem with zebraPosSetCreate that occurred when positions were
  34  * less than 1.
  35  *
  36  * Revision 1.19  1998/09/22 10:48:22  adam
  37  * Minor changes in search API.
  38  *
  39  * Revision 1.18  1998/09/22 10:03:45  adam
  40  * Changed result sets to be persistent in the sense that they can
  41  * be re-searched if needed.
  42  * Fixed memory leak in rsm_or.
  43  *
  44  * Revision 1.17  1998/06/23 15:33:36  adam
  45  * Added feature to specify sort criteria in query (type 7 specifies
  46  * sort flags).
  47  *
  48  * Revision 1.16  1998/05/20 10:12:24  adam
  49  * Implemented automatic EXPLAIN database maintenance.
  50  * Modified Zebra to work with ASN.1 compiled version of YAZ.
  51  *
  52  * Revision 1.15  1998/03/05 08:45:14  adam
  53  * New result set model and modular ranking system. Moved towards
  54  * descent server API. System information stored as "SGML" records.
  55  *
  56  * Revision 1.14  1998/02/10 16:39:15  adam
  57  * Minor change.
  58  *
  59  * Revision 1.13  1998/02/10 12:03:06  adam
  60  * Implemented Sort.
  61  *
  62  * Revision 1.12  1997/09/25 14:57:36  adam
  63  * Windows NT port.
  64  *
  65  * Revision 1.11  1996/12/23 15:30:46  adam
  66  * Work on truncation.
  67  * Bug fix: result sets weren't deleted after server shut down.
  68  *
  69  * Revision 1.10  1995/10/30 15:08:08  adam
  70  * Bug fixes.
  71  *
  72  * Revision 1.9  1995/10/17  18:02:14  adam
  73  * New feature: databases. Implemented as prefix to words in dictionary.
  74  *
  75  * Revision 1.8  1995/10/10  13:59:25  adam
  76  * Function rset_open changed its wflag parameter to general flags.
  77  *
  78  * Revision 1.7  1995/10/06  14:38:01  adam
  79  * New result set method: r_score.
  80  * Local no (sysno) and score is transferred to retrieveCtrl.
  81  *
  82  * Revision 1.6  1995/09/28  09:19:49  adam
  83  * xfree/xmalloc used everywhere.
  84  * Extract/retrieve method seems to work for text records.
  85  *
  86  * Revision 1.5  1995/09/27  16:17:32  adam
  87  * More work on retrieve.
  88  *
  89  * Revision 1.4  1995/09/07  13:58:36  adam
  90  * New parameter: result-set file descriptor (RSFD) to support multiple
  91  * positions within the same result-set.
  92  * Boolean operators: and, or, not implemented.
  93  * Result-set references.
  94  *
  95  * Revision 1.3  1995/09/06  16:11:19  adam
  96  * Option: only one word key per file.
  97  *
  98  * Revision 1.2  1995/09/06  10:33:04  adam
  99  * More work on present. Some log messages removed.
 100  *
 101  * Revision 1.1  1995/09/05  15:28:40  adam
 102  * More work on search engine.
 103  *
 104  */
 105 #include <stdio.h>
 106 #include <assert.h>
 107 #ifdef WIN32
 108 #include <io.h>
 109 #else
 110 #include <unistd.h>
 111 #endif
 112
 113 #include "zserver.h"
 114 #include <rstemp.h>
 115
 116 #define SORT_IDX_ENTRYSIZE 64
 117 #define ZSET_SORT_MAX_LEVEL 3
 118
 119 struct zebra_set {
 120     char *name;
 121     RSET rset;
 122     NMEM nmem;
 123     int hits;
 124     int num_bases;
 125     char **basenames;
 126     Z_RPNQuery *rpn;
 127     struct zset_sort_info *sort_info;
 128     struct zebra_set *next;
 129 };
 130
 131 struct zset_sort_entry {
 132     int sysno;
 133     int score;
 134     char buf[ZSET_SORT_MAX_LEVEL][SORT_IDX_ENTRYSIZE];
 135 };
 136
 137 struct zset_sort_info {
 138     int max_entries;
 139     int num_entries;
 140     struct zset_sort_entry *all_entries;
 141     struct zset_sort_entry **entries;
 142 };
 143
 144 ZebraSet resultSetAddRPN (ZebraHandle zh, ODR input, ODR output,
 145                           Z_RPNQuery *rpn, int num_bases, char **basenames,
 146                           const char *setname)
 147 {
 148     ZebraSet zebraSet;
 149
 150     zh->errCode = 0;
 151     zh->errString = NULL;
 152     zh->hits = 0;
 153
 154     zebraSet = resultSetAdd (zh, setname, 1);
 155     if (!zebraSet)
 156         return 0;
 157     zebraSet->rpn = 0;
 158     zebraSet->num_bases = num_bases;
 159     zebraSet->basenames = basenames;
 160     zebraSet->nmem = odr_extract_mem (input);
 161
 162     zebraSet->rset = rpn_search (zh, output->mem, rpn,
 163                                  zebraSet->num_bases,
 164                                  zebraSet->basenames, zebraSet->name,
 165                                  zebraSet);
 166     zh->hits = zebraSet->hits;
 167     if (zebraSet->rset)
 168         zebraSet->rpn = rpn;
 169     return zebraSet;
 170 }
 171
 172 ZebraSet resultSetAdd (ZebraHandle zh, const char *name, int ov)
 173 {
 174     ZebraSet s;
 175     int i;
 176
 177     for (s = zh->sets; s; s = s->next)
 178         if (!strcmp (s->name, name))
 179             break;
 180     if (s)
 181     {
 182         logf (LOG_DEBUG, "updating result set %s", name);
 183         if (!ov)
 184             return NULL;
 185         if (s->rset)
 186             rset_delete (s->rset);
 187         if (s->nmem)
 188             nmem_destroy (s->nmem);
 189     }
 190     else
 191     {
 192         logf (LOG_DEBUG, "adding result set %s", name);
 193         s = (ZebraSet) xmalloc (sizeof(*s));
 194         s->next = zh->sets;
 195         zh->sets = s;
 196         s->name = (char *) xmalloc (strlen(name)+1);
 197         strcpy (s->name, name);
 198
 199         s->sort_info = (struct zset_sort_info *)
 200             xmalloc (sizeof(*s->sort_info));
 201         s->sort_info->max_entries = 1000;
 202         s->sort_info->entries = (struct zset_sort_entry **)
 203             xmalloc (sizeof(*s->sort_info->entries) *
 204                      s->sort_info->max_entries);
 205         s->sort_info->all_entries = (struct zset_sort_entry *)
 206             xmalloc (sizeof(*s->sort_info->all_entries) *
 207                      s->sort_info->max_entries);
 208         for (i = 0; i < s->sort_info->max_entries; i++)
 209             s->sort_info->entries[i] = s->sort_info->all_entries + i;
 210     }
 211     s->rset = 0;
 212     s->nmem = 0;
 213     return s;
 214 }
 215
 216 ZebraSet resultSetGet (ZebraHandle zh, const char *name)
 217 {
 218     ZebraSet s;
 219
 220     for (s = zh->sets; s; s = s->next)
 221         if (!strcmp (s->name, name))
 222         {
 223             if (!s->rset && s->rpn)
 224             {
 225                 NMEM nmem = nmem_create ();
 226                 s->rset =
 227                     rpn_search (zh, nmem, s->rpn, s->num_bases,
 228                                 s->basenames, s->name, s);
 229                 nmem_destroy (nmem);
 230
 231             }
 232             return s;
 233         }
 234     return NULL;
 235 }
 236
 237 void resultSetDestroy (ZebraHandle zh, int num, char **names,int *statuses)
 238 {
 239     ZebraSet *ss = &zh->sets;
 240     int i;
 241
 242     if (statuses)
 243         for (i = 0; i<num; i++)
 244             statuses[i] = Z_DeleteStatus_resultSetDidNotExist;
 245     zh->errCode = 0;
 246     zh->errString = NULL;
 247     while (*ss)
 248     {
 249         int i = -1;
 250         ZebraSet s = *ss;
 251         if (num >= 0)
 252         {
 253             for (i = 0; i<num; i++)
 254                 if (!strcmp (s->name, names[i]))
 255                 {
 256                     if (statuses)
 257                         statuses[i] = Z_DeleteStatus_success;
 258                     i = -1;
 259                     break;
 260                 }
 261         }
 262         if (i < 0)
 263         {
 264             *ss = s->next;
 265
 266             xfree (s->sort_info->all_entries);
 267             xfree (s->sort_info->entries);
 268             xfree (s->sort_info);
 269
 270             if (s->nmem)
 271                 nmem_destroy (s->nmem);
 272             rset_delete (s->rset);
 273             xfree (s->name);
 274             xfree (s);
 275         }
 276         else
 277             ss = &s->next;
 278     }
 279 }
 280
 281 ZebraPosSet zebraPosSetCreate (ZebraHandle zh, const char *name,
 282                                int num, int *positions)
 283 {
 284     ZebraSet sset;
 285     ZebraPosSet sr;
 286     RSET rset;
 287     int i;
 288     struct zset_sort_info *sort_info;
 289
 290     if (!(sset = resultSetGet (zh, name)))
 291         return NULL;
 292     if (!(rset = sset->rset))
 293         return NULL;
 294     sr = (ZebraPosSet) xmalloc (sizeof(*sr) * num);
 295     for (i = 0; i<num; i++)
 296     {
 297         sr[i].sysno = 0;
 298         sr[i].score = -1;
 299     }
 300     sort_info = sset->sort_info;
 301     if (sort_info)
 302     {
 303         int position;
 304
 305         for (i = 0; i<num; i++)
 306         {
 307             position = positions[i];
 308             if (position > 0 && position <= sort_info->num_entries)
 309             {
 310                 logf (LOG_DEBUG, "got pos=%d (sorted)", position);
 311                 sr[i].sysno = sort_info->entries[position-1]->sysno;
 312                 sr[i].score = sort_info->entries[position-1]->score;
 313             }
 314         }
 315     }
 316     /* did we really get all entries using sort ? */
 317     for (i = 0; i<num; i++)
 318     {
 319         if (!sr[i].sysno)
 320             break;
 321     }
 322     if (i < num) /* nope, get the rest, unsorted - sorry */
 323     {
 324         int position = 0;
 325         int num_i = 0;
 326         int psysno = 0;
 327         int term_index;
 328         RSFD rfd;
 329         struct it_key key;
 330
 331         if (sort_info)
 332             position = sort_info->num_entries;
 333         while (num_i < num && positions[num_i] < position)
 334             num_i++;
 335         rfd = rset_open (rset, RSETF_READ);
 336         while (num_i < num && rset_read (rset, rfd, &key, &term_index))
 337         {
 338             if (key.sysno != psysno)
 339             {
 340                 psysno = key.sysno;
 341                 if (sort_info)
 342                 {
 343                     /* determine we alreay have this in our set */
 344                     for (i = sort_info->num_entries; --i >= 0; )
 345                         if (psysno == sort_info->entries[i]->sysno)
 346                             break;
 347                     if (i >= 0)
 348                         continue;
 349                 }
 350                 position++;
 351                 assert (num_i < num);
 352                 if (position == positions[num_i])
 353                 {
 354                     sr[num_i].sysno = psysno;
 355                     logf (LOG_DEBUG, "got pos=%d (unsorted)", position);
 356                     sr[num_i].score = -1;
 357                     num_i++;
 358                 }
 359             }
 360         }
 361         rset_close (rset, rfd);
 362     }
 363     return sr;
 364 }
 365
 366 void zebraPosSetDestroy (ZebraHandle zh, ZebraPosSet records, int num)
 367 {
 368     xfree (records);
 369 }
 370
 371 struct sortKeyInfo {
 372     int relation;
 373     int attrUse;
 374 };
 375
 376 void resultSetInsertSort (ZebraHandle zh, ZebraSet sset,
 377                           struct sortKeyInfo *criteria, int num_criteria,
 378                           int sysno)
 379 {
 380     struct zset_sort_entry this_entry;
 381     struct zset_sort_entry *new_entry = NULL;
 382     struct zset_sort_info *sort_info = sset->sort_info;
 383     int i, j;
 384
 385     sortIdx_sysno (zh->service->sortIdx, sysno);
 386     for (i = 0; i<num_criteria; i++)
 387     {
 388         sortIdx_type (zh->service->sortIdx, criteria[i].attrUse);
 389         sortIdx_read (zh->service->sortIdx, this_entry.buf[i]);
 390     }
 391     i = sort_info->num_entries;
 392     while (--i >= 0)
 393     {
 394         int rel = 0;
 395         for (j = 0; j<num_criteria; j++)
 396         {
 397             rel = memcmp (this_entry.buf[j], sort_info->entries[i]->buf[j],
 398                           SORT_IDX_ENTRYSIZE);
 399             if (rel)
 400                 break;
 401         }
 402         if (!rel)
 403             break;
 404         if (criteria[j].relation == 'A')
 405         {
 406             if (rel > 0)
 407                 break;
 408         }
 409         else if (criteria[j].relation == 'D')
 410         {
 411             if (rel < 0)
 412                 break;
 413         }
 414     }
 415     ++i;
 416     j = sort_info->max_entries;
 417     if (i == j)
 418         return;
 419
 420     if (sort_info->num_entries == j)
 421         --j;
 422     else
 423         j = (sort_info->num_entries)++;
 424     new_entry = sort_info->entries[j];
 425     while (j != i)
 426     {
 427         sort_info->entries[j] = sort_info->entries[j-1];
 428         --j;
 429     }
 430     sort_info->entries[i] = new_entry;
 431     assert (new_entry);
 432     for (i = 0; i<num_criteria; i++)
 433         memcpy (new_entry->buf[i], this_entry.buf[i], SORT_IDX_ENTRYSIZE);
 434     new_entry->sysno = sysno;
 435     new_entry->score = -1;
 436 }
 437
 438 void resultSetInsertRank (ZebraHandle zh, struct zset_sort_info *sort_info,
 439                           int sysno, int score, int relation)
 440 {
 441     struct zset_sort_entry *new_entry = NULL;
 442     int i, j;
 443
 444     i = sort_info->num_entries;
 445     while (--i >= 0)
 446     {
 447         int rel = 0;
 448
 449         rel = score - sort_info->entries[i]->score;
 450
 451         if (relation == 'D')
 452         {
 453             if (rel >= 0)
 454                 break;
 455         }
 456         else if (relation == 'A')
 457         {
 458             if (rel <= 0)
 459                 break;
 460         }
 461     }
 462     ++i;
 463     j = sort_info->max_entries;
 464     if (i == j)
 465         return;
 466
 467     if (sort_info->num_entries == j)
 468         --j;
 469     else
 470         j = (sort_info->num_entries)++;
 471
 472     new_entry = sort_info->entries[j];
 473     while (j != i)
 474     {
 475         sort_info->entries[j] = sort_info->entries[j-1];
 476         --j;
 477     }
 478     sort_info->entries[i] = new_entry;
 479     assert (new_entry);
 480     new_entry->sysno = sysno;
 481     new_entry->score = score;
 482 }
 483
 484 void resultSetSort (ZebraHandle zh, NMEM nmem,
 485                     int num_input_setnames, const char **input_setnames,
 486                     const char *output_setname,
 487                     Z_SortKeySpecList *sort_sequence, int *sort_status)
 488 {
 489     ZebraSet sset;
 490     RSET rset;
 491
 492     if (num_input_setnames == 0)
 493     {
 494         zh->errCode = 208;
 495         return ;
 496     }
 497     if (num_input_setnames > 1)
 498     {
 499         zh->errCode = 230;
 500         return;
 501     }
 502     logf (LOG_DEBUG, "result set sort input=%s output=%s",
 503           *input_setnames, output_setname);
 504     sset = resultSetGet (zh, input_setnames[0]);
 505     if (!sset)
 506     {
 507         zh->errCode = 30;
 508         zh->errString = nmem_strdup (nmem, input_setnames[0]);
 509         return;
 510     }
 511     if (!(rset = sset->rset))
 512     {
 513         zh->errCode = 30;
 514         zh->errString = nmem_strdup (nmem, input_setnames[0]);
 515         return;
 516     }
 517     if (strcmp (output_setname, input_setnames[0]))
 518     {
 519         rset = rset_dup (rset);
 520         sset = resultSetAdd (zh, output_setname, 1);
 521         sset->rset = rset;
 522     }
 523     resultSetSortSingle (zh, nmem, sset, rset, sort_sequence, sort_status);
 524 }
 525
 526 void resultSetSortSingle (ZebraHandle zh, NMEM nmem,
 527                           ZebraSet sset, RSET rset,
 528                           Z_SortKeySpecList *sort_sequence, int *sort_status)
 529 {
 530     int i, psysno = 0;
 531     struct it_key key;
 532     struct sortKeyInfo sort_criteria[3];
 533     int num_criteria;
 534     int term_index;
 535     RSFD rfd;
 536
 537     logf (LOG_DEBUG, "resultSetSortSingle start");
 538     sset->sort_info->num_entries = 0;
 539
 540     sset->hits = 0;
 541     num_criteria = sort_sequence->num_specs;
 542     if (num_criteria > 3)
 543         num_criteria = 3;
 544     for (i = 0; i < num_criteria; i++)
 545     {
 546         Z_SortKeySpec *sks = sort_sequence->specs[i];
 547         Z_SortKey *sk;
 548
 549         if (*sks->sortRelation == Z_SortRelation_ascending)
 550             sort_criteria[i].relation = 'A';
 551         else if (*sks->sortRelation == Z_SortRelation_descending)
 552             sort_criteria[i].relation = 'D';
 553         else
 554         {
 555             zh->errCode = 214;
 556             return;
 557         }
 558         if (sks->sortElement->which == Z_SortElement_databaseSpecific)
 559         {
 560             zh->errCode = 210;
 561             return;
 562         }
 563         else if (sks->sortElement->which != Z_SortElement_generic)
 564         {
 565             zh->errCode = 237;
 566             return;
 567         }
 568         sk = sks->sortElement->u.generic;
 569         switch (sk->which)
 570         {
 571         case Z_SortKey_sortField:
 572             logf (LOG_DEBUG, "Sort: key %d is of type sortField", i+1);
 573             zh->errCode = 207;
 574             return;
 575         case Z_SortKey_elementSpec:
 576             logf (LOG_DEBUG, "Sort: key %d is of type elementSpec", i+1);
 577             zh->errCode = 207;
 578             return;
 579         case Z_SortKey_sortAttributes:
 580             logf (LOG_DEBUG, "Sort: key %d is of type sortAttributes", i+1);
 581             sort_criteria[i].attrUse =
 582                 zebra_maps_sort (zh->service->zebra_maps,
 583                                  sk->u.sortAttributes);
 584             logf (LOG_DEBUG, "use value = %d", sort_criteria[i].attrUse);
 585             if (sort_criteria[i].attrUse == -1)
 586             {
 587                 zh->errCode = 116;
 588                 return;
 589             }
 590             if (sortIdx_type (zh->service->sortIdx, sort_criteria[i].attrUse))
 591             {
 592                 zh->errCode = 207;
 593                 return;
 594             }
 595             break;
 596         }
 597     }
 598     rfd = rset_open (rset, RSETF_READ);
 599     while (rset_read (rset, rfd, &key, &term_index))
 600     {
 601         if (key.sysno != psysno)
 602         {
 603             (sset->hits)++;
 604             psysno = key.sysno;
 605             resultSetInsertSort (zh, sset,
 606                                  sort_criteria, num_criteria, psysno);
 607         }
 608     }
 609     rset_close (rset, rfd);
 610
 611     *sort_status = Z_SortStatus_success;
 612     logf (LOG_DEBUG, "resultSetSortSingle end");
 613 }
 614
 615 RSET resultSetRef (ZebraHandle zh, Z_ResultSetId *resultSetId)
 616 {
 617     ZebraSet s;
 618
 619     if ((s = resultSetGet (zh, resultSetId)))
 620         return s->rset;
 621     return NULL;
 622 }
 623
 624 void resultSetRank (ZebraHandle zh, ZebraSet zebraSet, RSET rset)
 625 {
 626     int kno = 0;
 627     struct it_key key;
 628     RSFD rfd;
 629     int term_index, i;
 630     ZebraRankClass rank_class;
 631     struct rank_control *rc;
 632     struct zset_sort_info *sort_info;
 633
 634     sort_info = zebraSet->sort_info;
 635     sort_info->num_entries = 0;
 636     zebraSet->hits = 0;
 637     rfd = rset_open (rset, RSETF_READ);
 638
 639     logf (LOG_DEBUG, "resultSetRank");
 640     for (i = 0; i < rset->no_rset_terms; i++)
 641         logf (LOG_DEBUG, "term=\"%s\" cnt=%d type=%s",
 642               rset->rset_terms[i]->name,
 643               rset->rset_terms[i]->nn,
 644               rset->rset_terms[i]->flags);
 645
 646     rank_class = zebraRankLookup (zh, "rank-1");
 647     rc = rank_class->control;
 648
 649     if (rset_read (rset, rfd, &key, &term_index))
 650     {
 651         int psysno = key.sysno;
 652         int score;
 653         void *handle =
 654             (*rc->begin) (zh, rank_class->class_handle, rset);
 655         (zebraSet->hits)++;
 656         do
 657         {
 658             kno++;
 659             if (key.sysno != psysno)
 660             {
 661                 score = (*rc->calc) (handle, psysno);
 662
 663                 resultSetInsertRank (zh, sort_info, psysno, score, 'A');
 664                 (zebraSet->hits)++;
 665                 psysno = key.sysno;
 666             }
 667             (*rc->add) (handle, key.seqno, term_index);
 668         }
 669         while (rset_read (rset, rfd, &key, &term_index));
 670         score = (*rc->calc) (handle, psysno);
 671         resultSetInsertRank (zh, sort_info, psysno, score, 'A');
 672         (*rc->end) (zh, handle);
 673     }
 674     rset_close (rset, rfd);
 675     logf (LOG_DEBUG, "%d keys, %d distinct sysnos", kno, zebraSet->hits);
 676 }
 677
 678 ZebraRankClass zebraRankLookup (ZebraHandle zh, const char *name)
 679 {
 680     ZebraRankClass p = zh->service->rank_classes;
 681     while (p && strcmp (p->control->name, name))
 682         p = p->next;
 683     if (p && !p->init_flag)
 684     {
 685         if (p->control->create)
 686             p->class_handle = (*p->control->create)(zh->service);
 687         p->init_flag = 1;
 688     }
 689     return p;
 690 }
 691
 692 void zebraRankInstall (ZebraService zh, struct rank_control *ctrl)
 693 {
 694     ZebraRankClass p = (ZebraRankClass) xmalloc (sizeof(*p));
 695     p->control = (struct rank_control *) xmalloc (sizeof(*p->control));
 696     memcpy (p->control, ctrl, sizeof(*p->control));
 697     p->control->name = xstrdup (ctrl->name);
 698     p->init_flag = 0;
 699     p->next = zh->rank_classes;
 700     zh->rank_classes = p;
 701 }
 702
 703 void zebraRankDestroy (ZebraService zh)
 704 {
 705     ZebraRankClass p = zh->rank_classes;
 706     while (p)
 707     {
 708         ZebraRankClass p_next = p->next;
 709         if (p->init_flag && p->control->destroy)
 710             (*p->control->destroy)(zh, p->class_handle);
 711         xfree (p->control->name);
 712         xfree (p->control);
 713         xfree (p);
 714         p = p_next;
 715     }
 716     zh->rank_classes = NULL;
 717 }