ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/bioseg/trunk/bioseg.c
Revision: 1
Committed: Tue Aug 14 22:49:05 2007 UTC (12 years ago) by kmr
Original Path: bioseg.c
File size: 22820 byte(s)
Log Message:
Initial bioseg checkin.

Line File contents
1 /*
2 This file contains the implementation of the BIOSEG PostgreSQL type. The
3 implementation is a copy of the SEG type from the contrib directory in the
4 PostgreSQL source, which has been changed to represent ranges of integers.
5 The anticipated use of this type is to represent contiguous intervals of a
6 biological sequence.
7
8 SEG code written Gene Selkov, Jr.
9
10 Changes for BIOSEG written by Kim Rutherford <kmr@flymine.org>.
11 */
12
13 #include "postgres.h"
14
15 #include <stdlib.h>
16 #include <errno.h>
17 #include <limits.h>
18
19 #include "access/gist.h"
20 #include "access/skey.h"
21 #include "utils/builtins.h"
22
23 #include "biosegdata.h"
24
25 #ifdef INTERBASE_COORDS
26 #define BIOSEG bioseg0
27 #define BIOSEG_PREFIX(x) bioseg0 ## x
28 #else
29 #define BIOSEG bioseg
30 #define BIOSEG_PREFIX(x) bioseg ## x
31 #endif
32
33 PG_MODULE_MAGIC;
34
35 extern int BIOSEG_PREFIX(_yyparse)();
36 extern void BIOSEG_PREFIX(_yyerror)(const char *message);
37 extern void BIOSEG_PREFIX(_scanner_init)(const char *str);
38 extern void BIOSEG_PREFIX(_scanner_finish)(void);
39
40 /*
41 ** Input/Output routines
42 */
43 SEG *BIOSEG_PREFIX(_in)(char *str);
44 char *BIOSEG_PREFIX(_out)(SEG * seg);
45 SEG *BIOSEG_PREFIX(_create)(int32 lower, int32 upper);
46 int32 BIOSEG_PREFIX(_lower)(SEG * seg);
47 int32 BIOSEG_PREFIX(_upper)(SEG * seg);
48 int32 BIOSEG_PREFIX(_center)(SEG * seg);
49
50 /*
51 ** GiST support methods
52 */
53 bool BIOSEG_PREFIX(_gist_consistent)(GISTENTRY *entry, SEG * query, StrategyNumber strategy);
54 GISTENTRY *BIOSEG_PREFIX(_gist_compress)(GISTENTRY *entry);
55 GISTENTRY *BIOSEG_PREFIX(_gist_decompress)(GISTENTRY *entry);
56 float *BIOSEG_PREFIX(_gist_penalty)(GISTENTRY *origentry, GISTENTRY *newentry, float *result);
57 GIST_SPLITVEC *BIOSEG_PREFIX(_gist_picksplit)(GistEntryVector *entryvec, GIST_SPLITVEC *v);
58 bool BIOSEG_PREFIX(_gist_leaf_consistent)(SEG * key, SEG * query, StrategyNumber strategy);
59 bool BIOSEG_PREFIX(_gist_internal_consistent)(SEG * key, SEG * query, StrategyNumber strategy);
60 SEG *BIOSEG_PREFIX(_gist_union)(GistEntryVector *entryvec, int *sizep);
61 SEG *BIOSEG_PREFIX(_gist_binary_union)(SEG * r1, SEG * r2, int *sizep);
62 bool *BIOSEG_PREFIX(_gist_same)(SEG * b1, SEG * b2, bool *result);
63
64
65 /*
66 ** R-tree support functions
67 */
68 bool BIOSEG_PREFIX(_same)(SEG * a, SEG * b);
69 bool BIOSEG_PREFIX(_contains_int)(SEG * a, int *b);
70 bool BIOSEG_PREFIX(_contains)(SEG * a, SEG * b);
71 bool BIOSEG_PREFIX(_contained)(SEG * a, SEG * b);
72 bool BIOSEG_PREFIX(_overlap)(SEG * a, SEG * b);
73 bool BIOSEG_PREFIX(_left)(SEG * a, SEG * b);
74 bool BIOSEG_PREFIX(_over_left)(SEG * a, SEG * b);
75 bool BIOSEG_PREFIX(_right)(SEG * a, SEG * b);
76 bool BIOSEG_PREFIX(_over_right)(SEG * a, SEG * b);
77 void BIOSEG_PREFIX(_rt_size)(SEG * a, int32 *sz);
78 int32 BIOSEG_PREFIX(_size)(SEG * a);
79
80 static SEG *BIOSEG_PREFIX(_inter)(SEG * a, SEG * b);
81 static SEG *BIOSEG_PREFIX(_union)(SEG * a, SEG * b);
82
83 /*
84 ** Various operators
85 */
86 int32 BIOSEG_PREFIX(_cmp)(SEG * a, SEG * b);
87 bool BIOSEG_PREFIX(_lt)(SEG * a, SEG * b);
88 bool BIOSEG_PREFIX(_le)(SEG * a, SEG * b);
89 bool BIOSEG_PREFIX(_gt)(SEG * a, SEG * b);
90 bool BIOSEG_PREFIX(_ge)(SEG * a, SEG * b);
91 bool BIOSEG_PREFIX(_different)(SEG * a, SEG * b);
92 Datum BIOSEG_PREFIX(_joinsel)(PG_FUNCTION_ARGS);
93 Datum BIOSEG_PREFIX(_sel)(PG_FUNCTION_ARGS);
94 Datum BIOSEG_PREFIX(_contsel)(PG_FUNCTION_ARGS);
95 Datum BIOSEG_PREFIX(_contjoinsel)(PG_FUNCTION_ARGS);
96
97
98 static int get_dots(char **str);
99 static int get_int(char **str, int32 *result);
100
101
102 /*****************************************************************************
103 * Input/Output functions
104 *****************************************************************************/
105
106 int MAX_DIGITS = 10;
107
108 SEG *
109 BIOSEG_PREFIX(_in)(char *str)
110 {
111 int32 lower;
112 int32 upper;
113
114 if (!get_int(&str, &lower)) {
115 return NULL;
116 }
117
118 if (str[0] == 0) {
119 upper = lower;
120 } else {
121 if (!get_dots(&str)) {
122 ereport(ERROR,
123 (errcode(ERRCODE_SYNTAX_ERROR),
124 errmsg("bad bioseg representation"),
125 errdetail("number followed by something other than ..: %s", str)));
126 return NULL;
127 }
128
129 if (!get_int(&str, &upper)) {
130 ereport(ERROR,
131 (errcode(ERRCODE_SYNTAX_ERROR),
132 errmsg("bad bioseg representation"),
133 errdetail("number\"..\" followed by something other than a number: %s", str)));
134 return NULL;
135 }
136
137 if (lower > upper) {
138 ereport(ERROR,
139 (errcode(ERRCODE_SYNTAX_ERROR),
140 errmsg("bad bioseg representation"),
141 errdetail("lower limit of range greater than upper")));
142 return NULL;
143 }
144
145 if (str[0] != 0) {
146 ereport(ERROR,
147 (errcode(ERRCODE_SYNTAX_ERROR),
148 errmsg("bad bioseg representation"),
149 errdetail("garbage at end of string: %s", str)));
150 return NULL;
151 }
152 }
153
154 {
155 SEG *result = palloc(sizeof(SEG));
156
157 result->lower = lower;
158 result->upper = upper;
159 return result;
160 }
161 }
162
163 #ifdef INTERBASE_COORDS
164 #define MIN_LOWER 0l
165 #else
166 #define MIN_LOWER 1l
167 #endif
168
169 int get_int(char **strp, int32 *result) {
170 char *return_pos;
171 long int long_result = -1;
172
173 if (!(*strp)[0]) {
174 ereport(ERROR,
175 (errcode(ERRCODE_SYNTAX_ERROR),
176 errmsg("bad bioseg representation"),
177 errdetail("end of string found when expecting an integer")));
178 return 0;
179 }
180
181 errno = 0;
182
183 long_result = strtol(*strp, &return_pos, 0);
184
185 if (errno == ERANGE && (long_result == LONG_MAX || long_result == LONG_MIN)) {
186 ereport(ERROR,
187 (errcode(ERRCODE_SYNTAX_ERROR),
188 errmsg("bad bioseg representation"),
189 errdetail("integer at: %s is out of range", *strp)));
190 return 0;
191 }
192
193 if (errno != 0 && long_result == 0) {
194 ereport(ERROR,
195 (errcode(ERRCODE_SYNTAX_ERROR),
196 errmsg("bad bioseg representation"),
197 errdetail("unable to read an integer: %s", strerror(errno))));
198 return 0;
199 }
200
201 if (*strp == return_pos) {
202 ereport(ERROR,
203 (errcode(ERRCODE_SYNTAX_ERROR),
204 errmsg("bad bioseg representation"),
205 errdetail("no integer found at: %s", *strp)));
206 return 0;
207 }
208
209 if (long_result < MIN_LOWER) {
210 ereport(ERROR,
211 (errcode(ERRCODE_SYNTAX_ERROR),
212 errmsg("bad bioseg representation"),
213 errdetail("integer %ld at: %s is out of range - must be >= %ld", long_result, *strp, MIN_LOWER)));
214 return 0;
215 }
216
217 if (long_result > INT_MAX) {
218 ereport(ERROR,
219 (errcode(ERRCODE_SYNTAX_ERROR),
220 errmsg("bad bioseg representation"),
221 errdetail("integer %ld at: %s is out of range - must be <= %d", long_result, *strp, UINT_MAX)));
222 return 0;
223 }
224
225 *strp = return_pos;
226 *result = long_result;
227
228 return 1;
229 }
230
231 int
232 get_dots(char **strp)
233 {
234 if ((*strp)[0] == '.') {
235 (*strp)++;
236 if ((*strp)[0] == '.') {
237 (*strp)++;
238 if ((*strp)[0] == '.') {
239 // allow for "10...20"
240 (*strp)++;
241 }
242 return 1;
243 } else {
244 return 0;
245 }
246 } else {
247 return 0;
248 }
249 }
250
251 char *
252 BIOSEG_PREFIX(_out)(SEG * bioseg)
253 {
254 char *result;
255 char *p;
256
257 if (bioseg == NULL)
258 return (NULL);
259
260 p = result = (char *) palloc(40);
261
262 if (bioseg->lower == bioseg->upper)
263 {
264 /*
265 * indicates that this interval was built by bioseg_in off a single point
266 */
267 sprintf(p, "%d", bioseg->lower);
268 }
269 else
270 {
271 sprintf(p, "%d..%d", bioseg->lower, bioseg->upper);
272 }
273
274 return (result);
275 }
276
277 SEG *
278 BIOSEG_PREFIX(_create)(int32 lower, int32 upper)
279 {
280 SEG *result = palloc(sizeof(SEG));
281
282 if (lower > upper) {
283 ereport(ERROR,
284 (errcode(ERRCODE_SYNTAX_ERROR),
285 errmsg("bad bioseg representation"),
286 errdetail("lower limit of range greater than upper")));
287 return NULL;
288 }
289
290 result->lower = lower;
291 result->upper = upper;
292
293 return result;
294 }
295
296
297
298 int32
299 BIOSEG_PREFIX(_center)(SEG * bioseg)
300 {
301 return ((int32) bioseg->lower + (int32) bioseg->upper) / 2;
302 }
303
304 int32
305 BIOSEG_PREFIX(_lower)(SEG * bioseg)
306 {
307 return bioseg->lower;
308 }
309
310 int32
311 BIOSEG_PREFIX(_upper)(SEG * bioseg)
312 {
313 return bioseg->upper;
314 }
315
316
317 /*****************************************************************************
318 * GiST functions
319 *****************************************************************************/
320
321 /*
322 ** The GiST Consistent method for biosegments
323 ** Should return false if for all data items x below entry,
324 ** the predicate x op query == FALSE, where op is the oper
325 ** corresponding to strategy in the pg_amop table.
326 */
327 bool
328 BIOSEG_PREFIX(_gist_consistent)(GISTENTRY *entry,
329 SEG * query,
330 StrategyNumber strategy)
331 {
332 /*
333 * if entry is not leaf, use bioseg_gist_internal_consistent, else use
334 * bioseg_gist_leaf_consistent
335 */
336 if (GIST_LEAF(entry))
337 return (BIOSEG_PREFIX(_gist_leaf_consistent)((SEG *) DatumGetPointer(entry->key), query, strategy));
338 else
339 return (BIOSEG_PREFIX(_gist_internal_consistent)((SEG *) DatumGetPointer(entry->key), query, strategy));
340 }
341
342 /*
343 ** The GiST Union method for biosegments
344 ** returns the minimal bounding bioseg that encloses all the entries in entryvec
345 */
346 SEG *
347 BIOSEG_PREFIX(_gist_union)(GistEntryVector *entryvec, int *sizep)
348 {
349 int numranges;
350 int i;
351 SEG *out = (SEG *) NULL;
352 SEG *tmp;
353
354 #ifdef GIST_DEBUG
355 fprintf(stderr, "union\n");
356 #endif
357
358 numranges = entryvec->n;
359 tmp = (SEG *) DatumGetPointer(entryvec->vector[0].key);
360 *sizep = sizeof(SEG);
361
362 for (i = 1; i < numranges; i++)
363 {
364 out = BIOSEG_PREFIX(_gist_binary_union)(tmp, (SEG *)
365 DatumGetPointer(entryvec->vector[i].key),
366 sizep);
367 tmp = out;
368 }
369
370 return (out);
371 }
372
373 /*
374 ** GiST Compress and Decompress methods for biosegments
375 ** do not do anything.
376 */
377 GISTENTRY *
378 BIOSEG_PREFIX(_gist_compress)(GISTENTRY *entry)
379 {
380 return (entry);
381 }
382
383 GISTENTRY *
384 BIOSEG_PREFIX(_gist_decompress)(GISTENTRY *entry)
385 {
386 return (entry);
387 }
388
389 /*
390 ** The GiST Penalty method for biosegments
391 ** As in the R-tree paper, we use change in area as our penalty metric
392 */
393 float *
394 BIOSEG_PREFIX(_gist_penalty)(GISTENTRY *origentry, GISTENTRY *newentry, float *result)
395 {
396 SEG *ud;
397 int32 tmp1;
398 int32 tmp2;
399
400 ud = BIOSEG_PREFIX(_union)((SEG *) DatumGetPointer(origentry->key),
401 (SEG *) DatumGetPointer(newentry->key));
402 BIOSEG_PREFIX(_rt_size)(ud, &tmp1);
403 BIOSEG_PREFIX(_rt_size)((SEG *) DatumGetPointer(origentry->key), &tmp2);
404 *result = tmp1 - tmp2;
405
406 #ifdef GIST_DEBUG
407 fprintf(stderr, "penalty\n");
408 fprintf(stderr, "\t%g\n", *result);
409 #endif
410
411 return (result);
412 }
413
414
415 /*
416 ** The GiST PickSplit method for segments
417 ** We use Guttman's poly time split algorithm
418 */
419 GIST_SPLITVEC *
420 BIOSEG_PREFIX(_gist_picksplit)(GistEntryVector *entryvec,
421 GIST_SPLITVEC *v)
422 {
423 OffsetNumber i;
424 OffsetNumber j;
425 SEG *datum_alpha;
426 SEG *datum_beta;
427 SEG *datum_l;
428 SEG *datum_r;
429 SEG *union_d;
430 SEG *union_dl;
431 SEG *union_dr;
432 SEG *inter_d;
433 bool firsttime;
434 int32 size_alpha;
435 int32 size_beta;
436 int32 size_union;
437 int32 size_inter;
438 int32 size_waste;
439 int32 waste;
440 int32 size_l;
441 int32 size_r;
442 int nbytes;
443 OffsetNumber seed_1 = 1;
444 OffsetNumber seed_2 = 2;
445 OffsetNumber *left;
446 OffsetNumber *right;
447 OffsetNumber maxoff;
448
449 #ifdef GIST_DEBUG
450 fprintf(stderr, "picksplit\n");
451 #endif
452
453 maxoff = entryvec->n - 2;
454 nbytes = (maxoff + 2) * sizeof(OffsetNumber);
455 v->spl_left = (OffsetNumber *) palloc(nbytes);
456 v->spl_right = (OffsetNumber *) palloc(nbytes);
457
458 firsttime = true;
459 waste = 0.0;
460
461 for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
462 {
463 datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[i].key);
464 for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
465 {
466 datum_beta = (SEG *) DatumGetPointer(entryvec->vector[j].key);
467
468 /* compute the wasted space by unioning these guys */
469 /* size_waste = size_union - size_inter; */
470 union_d = BIOSEG_PREFIX(_union)(datum_alpha, datum_beta);
471 BIOSEG_PREFIX(_rt_size)(union_d, &size_union);
472 inter_d = BIOSEG_PREFIX(_inter)(datum_alpha, datum_beta);
473 BIOSEG_PREFIX(_rt_size)(inter_d, &size_inter);
474 size_waste = size_union - size_inter;
475
476 /*
477 * are these a more promising split that what we've already seen?
478 */
479 if (size_waste > waste || firsttime)
480 {
481 waste = size_waste;
482 seed_1 = i;
483 seed_2 = j;
484 firsttime = false;
485 }
486 }
487 }
488
489 left = v->spl_left;
490 v->spl_nleft = 0;
491 right = v->spl_right;
492 v->spl_nright = 0;
493
494 datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[seed_1].key);
495 datum_l = BIOSEG_PREFIX(_union)(datum_alpha, datum_alpha);
496 BIOSEG_PREFIX(_rt_size)(datum_l, &size_l);
497 datum_beta = (SEG *) DatumGetPointer(entryvec->vector[seed_2].key);
498 datum_r = BIOSEG_PREFIX(_union)(datum_beta, datum_beta);
499 BIOSEG_PREFIX(_rt_size)(datum_r, &size_r);
500
501 /*
502 * Now split up the regions between the two seeds. An important property
503 * of this split algorithm is that the split vector v has the indices of
504 * items to be split in order in its left and right vectors. We exploit
505 * this property by doing a merge in the code that actually splits the
506 * page.
507 *
508 * For efficiency, we also place the new index tuple in this loop. This is
509 * handled at the very end, when we have placed all the existing tuples
510 * and i == maxoff + 1.
511 */
512
513 maxoff = OffsetNumberNext(maxoff);
514 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
515 {
516 /*
517 * If we've already decided where to place this item, just put it on
518 * the right list. Otherwise, we need to figure out which page needs
519 * the least enlargement in order to store the item.
520 */
521
522 if (i == seed_1)
523 {
524 *left++ = i;
525 v->spl_nleft++;
526 continue;
527 }
528 else if (i == seed_2)
529 {
530 *right++ = i;
531 v->spl_nright++;
532 continue;
533 }
534
535 /* okay, which page needs least enlargement? */
536 datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[i].key);
537 union_dl = BIOSEG_PREFIX(_union)(datum_l, datum_alpha);
538 union_dr = BIOSEG_PREFIX(_union)(datum_r, datum_alpha);
539 BIOSEG_PREFIX(_rt_size)(union_dl, &size_alpha);
540 BIOSEG_PREFIX(_rt_size)(union_dr, &size_beta);
541
542 /* pick which page to add it to */
543 if (size_alpha - size_l < size_beta - size_r)
544 {
545 datum_l = union_dl;
546 size_l = size_alpha;
547 *left++ = i;
548 v->spl_nleft++;
549 }
550 else
551 {
552 datum_r = union_dr;
553 size_r = size_alpha;
554 *right++ = i;
555 v->spl_nright++;
556 }
557 }
558 *left = *right = FirstOffsetNumber; /* sentinel value, see dosplit() */
559
560 v->spl_ldatum = PointerGetDatum(datum_l);
561 v->spl_rdatum = PointerGetDatum(datum_r);
562
563 return v;
564 }
565
566 /*
567 ** Equality methods
568 */
569 bool *
570 BIOSEG_PREFIX(_gist_same)(SEG * b1, SEG * b2, bool *result)
571 {
572 if (BIOSEG_PREFIX(_same)(b1, b2))
573 *result = TRUE;
574 else
575 *result = FALSE;
576
577 #ifdef GIST_DEBUG
578 fprintf(stderr, "same: %s\n", (*result ? "TRUE" : "FALSE"));
579 #endif
580
581 return (result);
582 }
583
584 /*
585 ** SUPPORT ROUTINES
586 */
587 bool
588 BIOSEG_PREFIX(_gist_leaf_consistent)(SEG * key,
589 SEG * query,
590 StrategyNumber strategy)
591 {
592 bool retval;
593
594 #ifdef GIST_QUERY_DEBUG
595 fprintf(stderr, "leaf_consistent, %d\n", strategy);
596 #endif
597
598 switch (strategy)
599 {
600 case RTLeftStrategyNumber:
601 retval = (bool) BIOSEG_PREFIX(_left)(key, query);
602 break;
603 case RTOverLeftStrategyNumber:
604 retval = (bool) BIOSEG_PREFIX(_over_left)(key, query);
605 break;
606 case RTOverlapStrategyNumber:
607 retval = (bool) BIOSEG_PREFIX(_overlap)(key, query);
608 break;
609 case RTOverRightStrategyNumber:
610 retval = (bool) BIOSEG_PREFIX(_over_right)(key, query);
611 break;
612 case RTRightStrategyNumber:
613 retval = (bool) BIOSEG_PREFIX(_right)(key, query);
614 break;
615 case RTSameStrategyNumber:
616 retval = (bool) BIOSEG_PREFIX(_same)(key, query);
617 break;
618 case RTContainsStrategyNumber:
619 case RTOldContainsStrategyNumber:
620 retval = (bool) BIOSEG_PREFIX(_contains)(key, query);
621 break;
622 case RTContainedByStrategyNumber:
623 case RTOldContainedByStrategyNumber:
624 retval = (bool) BIOSEG_PREFIX(_contained)(key, query);
625 break;
626 default:
627 retval = FALSE;
628 }
629 return (retval);
630 }
631
632 bool
633 BIOSEG_PREFIX(_gist_internal_consistent)(SEG * key,
634 SEG * query,
635 StrategyNumber strategy)
636 {
637 bool retval;
638
639 #ifdef GIST_QUERY_DEBUG
640 fprintf(stderr, "internal_consistent, %d\n", strategy);
641 #endif
642
643 switch (strategy)
644 {
645 case RTLeftStrategyNumber:
646 retval = (bool) !BIOSEG_PREFIX(_over_right)(key, query);
647 break;
648 case RTOverLeftStrategyNumber:
649 retval = (bool) !BIOSEG_PREFIX(_right)(key, query);
650 break;
651 case RTOverlapStrategyNumber:
652 retval = (bool) BIOSEG_PREFIX(_overlap)(key, query);
653 break;
654 case RTOverRightStrategyNumber:
655 retval = (bool) !BIOSEG_PREFIX(_left)(key, query);
656 break;
657 case RTRightStrategyNumber:
658 retval = (bool) !BIOSEG_PREFIX(_over_left)(key, query);
659 break;
660 case RTSameStrategyNumber:
661 case RTContainsStrategyNumber:
662 case RTOldContainsStrategyNumber:
663 retval = (bool) BIOSEG_PREFIX(_contains)(key, query);
664 break;
665 case RTContainedByStrategyNumber:
666 case RTOldContainedByStrategyNumber:
667 retval = (bool) BIOSEG_PREFIX(_overlap)(key, query);
668 break;
669 default:
670 retval = FALSE;
671 }
672 return (retval);
673 }
674
675 SEG *
676 BIOSEG_PREFIX(_gist_binary_union)(SEG * r1, SEG * r2, int *sizep)
677 {
678 SEG *retval;
679
680 retval = BIOSEG_PREFIX(_union)(r1, r2);
681 *sizep = sizeof(SEG);
682
683 return (retval);
684 }
685
686
687 bool
688 BIOSEG_PREFIX(_contains)(SEG * a, SEG * b)
689 {
690 #ifdef INTERBASE_COORDS
691 return ((a->lower <= b->lower) && (a->upper >= b->upper) &&
692 a->lower != b->upper && a->upper != b->lower);
693 #else
694 return ((a->lower <= b->lower) && (a->upper >= b->upper));
695 #endif
696 }
697
698 bool
699 BIOSEG_PREFIX(_contained)(SEG * a, SEG * b)
700 {
701 return (BIOSEG_PREFIX(_contains)(b, a));
702 }
703
704 /*****************************************************************************
705 * Operator class for R-tree indexing
706 *****************************************************************************/
707
708 bool
709 BIOSEG_PREFIX(_same)(SEG * a, SEG * b)
710 {
711 return BIOSEG_PREFIX(_cmp)(a, b) == 0;
712 }
713
714 /* bioseg_overlap -- does a overlap b?
715 */
716 bool
717 BIOSEG_PREFIX(_overlap)(SEG * a, SEG * b)
718 {
719 #ifdef INTERBASE_COORDS
720 return (
721 ((a->upper >= b->upper) && (a->lower < b->upper) &&
722 b->lower != a->upper)
723 ||
724 ((b->upper >= a->upper) && (b->lower < a->upper) &&
725 a->lower != b->upper)
726 );
727 #else
728 return
729 ((a->upper >= b->upper) && (a->lower <= b->upper))
730 ||
731 ((b->upper >= a->upper) && (b->lower <= a->upper));
732 #endif
733 }
734
735 /* bioseg_overleft -- is the right edge of (a) located at or left of the right edge of (b)?
736 */
737 bool
738 BIOSEG_PREFIX(_over_left)(SEG * a, SEG * b)
739 {
740 return (a->upper <= b->upper);
741 }
742
743 /* bioseg_left -- is (a) entirely on the left of (b)?
744 */
745 bool
746 BIOSEG_PREFIX(_left)(SEG * a, SEG * b)
747 {
748 return (a->upper < b->lower);
749 }
750
751 /* bioseg_right -- is (a) entirely on the right of (b)?
752 */
753 bool
754 BIOSEG_PREFIX(_right)(SEG * a, SEG * b)
755 {
756 return (a->lower > b->upper);
757 }
758
759 /* bioseg_overright -- is the left edge of (a) located at or right of the left edge of (b)?
760 */
761 bool
762 BIOSEG_PREFIX(_over_right)(SEG * a, SEG * b)
763 {
764 return (a->lower >= b->lower);
765 }
766
767
768 static SEG *
769 BIOSEG_PREFIX(_union)(SEG * a, SEG * b)
770 {
771 SEG *n;
772
773 n = (SEG *) palloc(sizeof(*n));
774
775 /* take max of upper endpoints */
776 if (a->upper > b->upper)
777 {
778 n->upper = a->upper;
779 }
780 else
781 {
782 n->upper = b->upper;
783 }
784
785 /* take min of lower endpoints */
786 if (a->lower < b->lower)
787 {
788 n->lower = a->lower;
789 }
790 else
791 {
792 n->lower = b->lower;
793 }
794
795 return (n);
796 }
797
798
799 static SEG *
800 BIOSEG_PREFIX(_inter)(SEG * a, SEG * b)
801 {
802 SEG *n;
803
804 n = (SEG *) palloc(sizeof(*n));
805
806 /* take min of upper endpoints */
807 if (a->upper < b->upper)
808 {
809 n->upper = a->upper;
810 }
811 else
812 {
813 n->upper = b->upper;
814 }
815
816 /* take max of lower endpoints */
817 if (a->lower > b->lower)
818 {
819 n->lower = a->lower;
820 }
821 else
822 {
823 n->lower = b->lower;
824 }
825
826 return (n);
827 }
828
829 void
830 BIOSEG_PREFIX(_rt_size)(SEG * a, int32 *size)
831 {
832 if (a == (SEG *) NULL)
833 *size = 0;
834 else
835 #ifdef INTERBASE_COORDS
836 *size = (int32) (a->upper - a->lower);
837 #else
838 *size = (int32) (a->upper - a->lower + 1);
839 #endif
840 }
841
842 int32
843 BIOSEG_PREFIX(_size)(SEG * a)
844 {
845 #ifdef INTERBASE_COORDS
846 return a->upper - a->lower;
847 #else
848 return a->upper - a->lower + 1;
849 #endif
850 }
851
852
853 /*****************************************************************************
854 * Miscellaneous operators
855 *****************************************************************************/
856 int32
857 BIOSEG_PREFIX(_cmp)(SEG * a, SEG * b)
858 {
859 if (a->lower < b->lower)
860 return -1;
861 if (a->lower > b->lower)
862 return 1;
863
864 if (a->upper < b->upper)
865 return -1;
866 if (a->upper > b->upper)
867 return 1;
868
869 return 0;
870 }
871
872 bool
873 BIOSEG_PREFIX(_lt)(SEG * a, SEG * b)
874 {
875 return BIOSEG_PREFIX(_cmp)(a, b) < 0;
876 }
877
878 bool
879 BIOSEG_PREFIX(_le)(SEG * a, SEG * b)
880 {
881 return BIOSEG_PREFIX(_cmp)(a, b) <= 0;
882 }
883
884 bool
885 BIOSEG_PREFIX(_gt)(SEG * a, SEG * b)
886 {
887 return BIOSEG_PREFIX(_cmp)(a, b) > 0;
888 }
889
890 bool
891 BIOSEG_PREFIX(_ge)(SEG * a, SEG * b)
892 {
893 return BIOSEG_PREFIX(_cmp)(a, b) >= 0;
894 }
895
896 bool
897 BIOSEG_PREFIX(_different)(SEG * a, SEG * b)
898 {
899 return BIOSEG_PREFIX(_cmp)(a, b) != 0;
900 }
901
902 bool
903 BIOSEG_PREFIX(_contains_int)(SEG * a, int *b)
904 {
905 #ifdef INTERBASE_COORDS
906 return ((a->lower < *b) && (a->upper > *b));
907 #else
908 return ((a->lower <= *b) && (a->upper >= *b));
909 #endif
910 }
911
912 /*
913 ** These are lower than those in geo_selfuncs.c - found by trail and error.
914 */
915 Datum
916 BIOSEG_PREFIX(_sel)(PG_FUNCTION_ARGS)
917 {
918 PG_RETURN_FLOAT8(2.0e-4);
919 }
920
921 Datum
922 BIOSEG_PREFIX(_joinsel)(PG_FUNCTION_ARGS)
923 {
924 PG_RETURN_FLOAT8(1.0e-5);
925 }
926
927 Datum
928 BIOSEG_PREFIX(_contsel)(PG_FUNCTION_ARGS)
929 {
930 PG_RETURN_FLOAT8(1.0e-4);
931 }
932
933 Datum
934 BIOSEG_PREFIX(_contjoinsel)(PG_FUNCTION_ARGS)
935 {
936 PG_RETURN_FLOAT8(5e-6);
937 }