ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/bioseg/trunk/bioseg.c
Revision: 32
Committed: Thu Aug 21 16:13:43 2008 UTC (10 years, 9 months ago) by kmr
File size: 23157 byte(s)
Log Message:
Allow negative coordinates when using bioseg0.

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@xenu.org.uk>.
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 INT_MIN
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 // when INTERBASE_COORDS is set, on machines where
211 // sizeof(long int) == sizeof(int32) this block won't be executed because
212 // strtol() will return ERANGE
213 ereport(ERROR,
214 (errcode(ERRCODE_SYNTAX_ERROR),
215 errmsg("bad bioseg representation"),
216 errdetail("integer %ld at: %s is out of range - must be >= %d",
217 long_result, *strp, MIN_LOWER)));
218 return 0;
219 }
220
221 if (long_result > INT_MAX) {
222 // on machines where sizeof(long int) == sizeof(int32) this won't happen
223 // because strtol() will return ERANGE
224 ereport(ERROR,
225 (errcode(ERRCODE_SYNTAX_ERROR),
226 errmsg("bad bioseg representation"),
227 errdetail("integer %ld at: %s is out of range - must be <= %d",
228 long_result, *strp, INT_MAX)));
229 return 0;
230 }
231
232 *strp = return_pos;
233 *result = long_result;
234
235 return 1;
236 }
237
238 int
239 get_dots(char **strp)
240 {
241 if ((*strp)[0] == '.') {
242 (*strp)++;
243 if ((*strp)[0] == '.') {
244 (*strp)++;
245 if ((*strp)[0] == '.') {
246 // allow for "10...20"
247 (*strp)++;
248 }
249 return 1;
250 } else {
251 return 0;
252 }
253 } else {
254 return 0;
255 }
256 }
257
258 char *
259 BIOSEG_PREFIX(_out)(SEG * bioseg)
260 {
261 char *result;
262 char *p;
263
264 if (bioseg == NULL)
265 return (NULL);
266
267 p = result = (char *) palloc(40);
268
269 if (bioseg->lower == bioseg->upper)
270 {
271 /*
272 * indicates that this interval was built by bioseg_in off a single point
273 */
274 sprintf(p, "%d", bioseg->lower);
275 }
276 else
277 {
278 sprintf(p, "%d..%d", bioseg->lower, bioseg->upper);
279 }
280
281 return (result);
282 }
283
284 SEG *
285 BIOSEG_PREFIX(_create)(int32 lower, int32 upper)
286 {
287 SEG *result = palloc(sizeof(SEG));
288
289 if (lower > upper) {
290 ereport(ERROR,
291 (errcode(ERRCODE_SYNTAX_ERROR),
292 errmsg("bad bioseg representation"),
293 errdetail("lower limit of range greater than upper")));
294 return NULL;
295 }
296
297 result->lower = lower;
298 result->upper = upper;
299
300 return result;
301 }
302
303
304
305 int32
306 BIOSEG_PREFIX(_center)(SEG * bioseg)
307 {
308 return ((int32) bioseg->lower + (int32) bioseg->upper) / 2;
309 }
310
311 int32
312 BIOSEG_PREFIX(_lower)(SEG * bioseg)
313 {
314 return bioseg->lower;
315 }
316
317 int32
318 BIOSEG_PREFIX(_upper)(SEG * bioseg)
319 {
320 return bioseg->upper;
321 }
322
323
324 /*****************************************************************************
325 * GiST functions
326 *****************************************************************************/
327
328 /*
329 ** The GiST Consistent method for biosegments
330 ** Should return false if for all data items x below entry,
331 ** the predicate x op query == FALSE, where op is the oper
332 ** corresponding to strategy in the pg_amop table.
333 */
334 bool
335 BIOSEG_PREFIX(_gist_consistent)(GISTENTRY *entry,
336 SEG * query,
337 StrategyNumber strategy)
338 {
339 /*
340 * if entry is not leaf, use bioseg_gist_internal_consistent, else use
341 * bioseg_gist_leaf_consistent
342 */
343 if (GIST_LEAF(entry))
344 return (BIOSEG_PREFIX(_gist_leaf_consistent)((SEG *) DatumGetPointer(entry->key), query, strategy));
345 else
346 return (BIOSEG_PREFIX(_gist_internal_consistent)((SEG *) DatumGetPointer(entry->key), query, strategy));
347 }
348
349 /*
350 ** The GiST Union method for biosegments
351 ** returns the minimal bounding bioseg that encloses all the entries in entryvec
352 */
353 SEG *
354 BIOSEG_PREFIX(_gist_union)(GistEntryVector *entryvec, int *sizep)
355 {
356 int numranges;
357 int i;
358 SEG *out = (SEG *) NULL;
359 SEG *tmp;
360
361 #ifdef GIST_DEBUG
362 fprintf(stderr, "union\n");
363 #endif
364
365 numranges = entryvec->n;
366 tmp = (SEG *) DatumGetPointer(entryvec->vector[0].key);
367 *sizep = sizeof(SEG);
368
369 for (i = 1; i < numranges; i++)
370 {
371 out = BIOSEG_PREFIX(_gist_binary_union)(tmp, (SEG *)
372 DatumGetPointer(entryvec->vector[i].key),
373 sizep);
374 tmp = out;
375 }
376
377 return (out);
378 }
379
380 /*
381 ** GiST Compress and Decompress methods for biosegments
382 ** do not do anything.
383 */
384 GISTENTRY *
385 BIOSEG_PREFIX(_gist_compress)(GISTENTRY *entry)
386 {
387 return (entry);
388 }
389
390 GISTENTRY *
391 BIOSEG_PREFIX(_gist_decompress)(GISTENTRY *entry)
392 {
393 return (entry);
394 }
395
396 /*
397 ** The GiST Penalty method for biosegments
398 ** As in the R-tree paper, we use change in area as our penalty metric
399 */
400 float *
401 BIOSEG_PREFIX(_gist_penalty)(GISTENTRY *origentry, GISTENTRY *newentry, float *result)
402 {
403 SEG *ud;
404 int32 tmp1;
405 int32 tmp2;
406
407 ud = BIOSEG_PREFIX(_union)((SEG *) DatumGetPointer(origentry->key),
408 (SEG *) DatumGetPointer(newentry->key));
409 BIOSEG_PREFIX(_rt_size)(ud, &tmp1);
410 BIOSEG_PREFIX(_rt_size)((SEG *) DatumGetPointer(origentry->key), &tmp2);
411 *result = tmp1 - tmp2;
412
413 #ifdef GIST_DEBUG
414 fprintf(stderr, "penalty\n");
415 fprintf(stderr, "\t%g\n", *result);
416 #endif
417
418 return (result);
419 }
420
421
422 /*
423 ** The GiST PickSplit method for segments
424 ** We use Guttman's poly time split algorithm
425 */
426 GIST_SPLITVEC *
427 BIOSEG_PREFIX(_gist_picksplit)(GistEntryVector *entryvec,
428 GIST_SPLITVEC *v)
429 {
430 OffsetNumber i;
431 OffsetNumber j;
432 SEG *datum_alpha;
433 SEG *datum_beta;
434 SEG *datum_l;
435 SEG *datum_r;
436 SEG *union_d;
437 SEG *union_dl;
438 SEG *union_dr;
439 SEG *inter_d;
440 bool firsttime;
441 int32 size_alpha;
442 int32 size_beta;
443 int32 size_union;
444 int32 size_inter;
445 int32 size_waste;
446 int32 waste;
447 int32 size_l;
448 int32 size_r;
449 int nbytes;
450 OffsetNumber seed_1 = 1;
451 OffsetNumber seed_2 = 2;
452 OffsetNumber *left;
453 OffsetNumber *right;
454 OffsetNumber maxoff;
455
456 #ifdef GIST_DEBUG
457 fprintf(stderr, "picksplit\n");
458 #endif
459
460 maxoff = entryvec->n - 2;
461 nbytes = (maxoff + 2) * sizeof(OffsetNumber);
462 v->spl_left = (OffsetNumber *) palloc(nbytes);
463 v->spl_right = (OffsetNumber *) palloc(nbytes);
464
465 firsttime = true;
466 waste = 0.0;
467
468 for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
469 {
470 datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[i].key);
471 for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
472 {
473 datum_beta = (SEG *) DatumGetPointer(entryvec->vector[j].key);
474
475 /* compute the wasted space by unioning these guys */
476 /* size_waste = size_union - size_inter; */
477 union_d = BIOSEG_PREFIX(_union)(datum_alpha, datum_beta);
478 BIOSEG_PREFIX(_rt_size)(union_d, &size_union);
479 inter_d = BIOSEG_PREFIX(_inter)(datum_alpha, datum_beta);
480 BIOSEG_PREFIX(_rt_size)(inter_d, &size_inter);
481 size_waste = size_union - size_inter;
482
483 /*
484 * are these a more promising split that what we've already seen?
485 */
486 if (size_waste > waste || firsttime)
487 {
488 waste = size_waste;
489 seed_1 = i;
490 seed_2 = j;
491 firsttime = false;
492 }
493 }
494 }
495
496 left = v->spl_left;
497 v->spl_nleft = 0;
498 right = v->spl_right;
499 v->spl_nright = 0;
500
501 datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[seed_1].key);
502 datum_l = BIOSEG_PREFIX(_union)(datum_alpha, datum_alpha);
503 BIOSEG_PREFIX(_rt_size)(datum_l, &size_l);
504 datum_beta = (SEG *) DatumGetPointer(entryvec->vector[seed_2].key);
505 datum_r = BIOSEG_PREFIX(_union)(datum_beta, datum_beta);
506 BIOSEG_PREFIX(_rt_size)(datum_r, &size_r);
507
508 /*
509 * Now split up the regions between the two seeds. An important property
510 * of this split algorithm is that the split vector v has the indices of
511 * items to be split in order in its left and right vectors. We exploit
512 * this property by doing a merge in the code that actually splits the
513 * page.
514 *
515 * For efficiency, we also place the new index tuple in this loop. This is
516 * handled at the very end, when we have placed all the existing tuples
517 * and i == maxoff + 1.
518 */
519
520 maxoff = OffsetNumberNext(maxoff);
521 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
522 {
523 /*
524 * If we've already decided where to place this item, just put it on
525 * the right list. Otherwise, we need to figure out which page needs
526 * the least enlargement in order to store the item.
527 */
528
529 if (i == seed_1)
530 {
531 *left++ = i;
532 v->spl_nleft++;
533 continue;
534 }
535 else if (i == seed_2)
536 {
537 *right++ = i;
538 v->spl_nright++;
539 continue;
540 }
541
542 /* okay, which page needs least enlargement? */
543 datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[i].key);
544 union_dl = BIOSEG_PREFIX(_union)(datum_l, datum_alpha);
545 union_dr = BIOSEG_PREFIX(_union)(datum_r, datum_alpha);
546 BIOSEG_PREFIX(_rt_size)(union_dl, &size_alpha);
547 BIOSEG_PREFIX(_rt_size)(union_dr, &size_beta);
548
549 /* pick which page to add it to */
550 if (size_alpha - size_l < size_beta - size_r)
551 {
552 datum_l = union_dl;
553 size_l = size_alpha;
554 *left++ = i;
555 v->spl_nleft++;
556 }
557 else
558 {
559 datum_r = union_dr;
560 size_r = size_alpha;
561 *right++ = i;
562 v->spl_nright++;
563 }
564 }
565 *left = *right = FirstOffsetNumber; /* sentinel value, see dosplit() */
566
567 v->spl_ldatum = PointerGetDatum(datum_l);
568 v->spl_rdatum = PointerGetDatum(datum_r);
569
570 return v;
571 }
572
573 /*
574 ** Equality methods
575 */
576 bool *
577 BIOSEG_PREFIX(_gist_same)(SEG * b1, SEG * b2, bool *result)
578 {
579 if (BIOSEG_PREFIX(_same)(b1, b2))
580 *result = TRUE;
581 else
582 *result = FALSE;
583
584 #ifdef GIST_DEBUG
585 fprintf(stderr, "same: %s\n", (*result ? "TRUE" : "FALSE"));
586 #endif
587
588 return (result);
589 }
590
591 /*
592 ** SUPPORT ROUTINES
593 */
594 bool
595 BIOSEG_PREFIX(_gist_leaf_consistent)(SEG * key,
596 SEG * query,
597 StrategyNumber strategy)
598 {
599 bool retval;
600
601 #ifdef GIST_QUERY_DEBUG
602 fprintf(stderr, "leaf_consistent, %d\n", strategy);
603 #endif
604
605 switch (strategy)
606 {
607 case RTLeftStrategyNumber:
608 retval = (bool) BIOSEG_PREFIX(_left)(key, query);
609 break;
610 case RTOverLeftStrategyNumber:
611 retval = (bool) BIOSEG_PREFIX(_over_left)(key, query);
612 break;
613 case RTOverlapStrategyNumber:
614 retval = (bool) BIOSEG_PREFIX(_overlap)(key, query);
615 break;
616 case RTOverRightStrategyNumber:
617 retval = (bool) BIOSEG_PREFIX(_over_right)(key, query);
618 break;
619 case RTRightStrategyNumber:
620 retval = (bool) BIOSEG_PREFIX(_right)(key, query);
621 break;
622 case RTSameStrategyNumber:
623 retval = (bool) BIOSEG_PREFIX(_same)(key, query);
624 break;
625 case RTContainsStrategyNumber:
626 case RTOldContainsStrategyNumber:
627 retval = (bool) BIOSEG_PREFIX(_contains)(key, query);
628 break;
629 case RTContainedByStrategyNumber:
630 case RTOldContainedByStrategyNumber:
631 retval = (bool) BIOSEG_PREFIX(_contained)(key, query);
632 break;
633 default:
634 retval = FALSE;
635 }
636 return (retval);
637 }
638
639 bool
640 BIOSEG_PREFIX(_gist_internal_consistent)(SEG * key,
641 SEG * query,
642 StrategyNumber strategy)
643 {
644 bool retval;
645
646 #ifdef GIST_QUERY_DEBUG
647 fprintf(stderr, "internal_consistent, %d\n", strategy);
648 #endif
649
650 switch (strategy)
651 {
652 case RTLeftStrategyNumber:
653 retval = (bool) !BIOSEG_PREFIX(_over_right)(key, query);
654 break;
655 case RTOverLeftStrategyNumber:
656 retval = (bool) !BIOSEG_PREFIX(_right)(key, query);
657 break;
658 case RTOverlapStrategyNumber:
659 retval = (bool) BIOSEG_PREFIX(_overlap)(key, query);
660 break;
661 case RTOverRightStrategyNumber:
662 retval = (bool) !BIOSEG_PREFIX(_left)(key, query);
663 break;
664 case RTRightStrategyNumber:
665 retval = (bool) !BIOSEG_PREFIX(_over_left)(key, query);
666 break;
667 case RTSameStrategyNumber:
668 case RTContainsStrategyNumber:
669 case RTOldContainsStrategyNumber:
670 retval = (bool) BIOSEG_PREFIX(_contains)(key, query);
671 break;
672 case RTContainedByStrategyNumber:
673 case RTOldContainedByStrategyNumber:
674 retval = (bool) BIOSEG_PREFIX(_overlap)(key, query);
675 break;
676 default:
677 retval = FALSE;
678 }
679 return (retval);
680 }
681
682 SEG *
683 BIOSEG_PREFIX(_gist_binary_union)(SEG * r1, SEG * r2, int *sizep)
684 {
685 SEG *retval;
686
687 retval = BIOSEG_PREFIX(_union)(r1, r2);
688 *sizep = sizeof(SEG);
689
690 return (retval);
691 }
692
693
694 bool
695 BIOSEG_PREFIX(_contains)(SEG * a, SEG * b)
696 {
697 #ifdef INTERBASE_COORDS
698 return ((a->lower <= b->lower) && (a->upper >= b->upper) &&
699 a->lower != b->upper && a->upper != b->lower);
700 #else
701 return ((a->lower <= b->lower) && (a->upper >= b->upper));
702 #endif
703 }
704
705 bool
706 BIOSEG_PREFIX(_contained)(SEG * a, SEG * b)
707 {
708 return (BIOSEG_PREFIX(_contains)(b, a));
709 }
710
711 /*****************************************************************************
712 * Operator class for R-tree indexing
713 *****************************************************************************/
714
715 bool
716 BIOSEG_PREFIX(_same)(SEG * a, SEG * b)
717 {
718 return BIOSEG_PREFIX(_cmp)(a, b) == 0;
719 }
720
721 /* bioseg_overlap -- does a overlap b?
722 */
723 bool
724 BIOSEG_PREFIX(_overlap)(SEG * a, SEG * b)
725 {
726 #ifdef INTERBASE_COORDS
727 return (
728 ((a->upper >= b->upper) && (a->lower < b->upper) &&
729 b->lower != a->upper)
730 ||
731 ((b->upper >= a->upper) && (b->lower < a->upper) &&
732 a->lower != b->upper)
733 );
734 #else
735 return
736 ((a->upper >= b->upper) && (a->lower <= b->upper))
737 ||
738 ((b->upper >= a->upper) && (b->lower <= a->upper));
739 #endif
740 }
741
742 /* bioseg_overleft -- is the right edge of (a) located at or left of the right edge of (b)?
743 */
744 bool
745 BIOSEG_PREFIX(_over_left)(SEG * a, SEG * b)
746 {
747 return (a->upper <= b->upper);
748 }
749
750 /* bioseg_left -- is (a) entirely on the left of (b)?
751 */
752 bool
753 BIOSEG_PREFIX(_left)(SEG * a, SEG * b)
754 {
755 return (a->upper < b->lower);
756 }
757
758 /* bioseg_right -- is (a) entirely on the right of (b)?
759 */
760 bool
761 BIOSEG_PREFIX(_right)(SEG * a, SEG * b)
762 {
763 return (a->lower > b->upper);
764 }
765
766 /* bioseg_overright -- is the left edge of (a) located at or right of the left edge of (b)?
767 */
768 bool
769 BIOSEG_PREFIX(_over_right)(SEG * a, SEG * b)
770 {
771 return (a->lower >= b->lower);
772 }
773
774
775 static SEG *
776 BIOSEG_PREFIX(_union)(SEG * a, SEG * b)
777 {
778 SEG *n;
779
780 n = (SEG *) palloc(sizeof(*n));
781
782 /* take max of upper endpoints */
783 if (a->upper > b->upper)
784 {
785 n->upper = a->upper;
786 }
787 else
788 {
789 n->upper = b->upper;
790 }
791
792 /* take min of lower endpoints */
793 if (a->lower < b->lower)
794 {
795 n->lower = a->lower;
796 }
797 else
798 {
799 n->lower = b->lower;
800 }
801
802 return (n);
803 }
804
805
806 static SEG *
807 BIOSEG_PREFIX(_inter)(SEG * a, SEG * b)
808 {
809 SEG *n;
810
811 n = (SEG *) palloc(sizeof(*n));
812
813 /* take min of upper endpoints */
814 if (a->upper < b->upper)
815 {
816 n->upper = a->upper;
817 }
818 else
819 {
820 n->upper = b->upper;
821 }
822
823 /* take max of lower endpoints */
824 if (a->lower > b->lower)
825 {
826 n->lower = a->lower;
827 }
828 else
829 {
830 n->lower = b->lower;
831 }
832
833 return (n);
834 }
835
836 void
837 BIOSEG_PREFIX(_rt_size)(SEG * a, int32 *size)
838 {
839 if (a == (SEG *) NULL)
840 *size = 0;
841 else
842 #ifdef INTERBASE_COORDS
843 *size = (int32) (a->upper - a->lower);
844 #else
845 *size = (int32) (a->upper - a->lower + 1);
846 #endif
847 }
848
849 int32
850 BIOSEG_PREFIX(_size)(SEG * a)
851 {
852 #ifdef INTERBASE_COORDS
853 return a->upper - a->lower;
854 #else
855 return a->upper - a->lower + 1;
856 #endif
857 }
858
859
860 /*****************************************************************************
861 * Miscellaneous operators
862 *****************************************************************************/
863 int32
864 BIOSEG_PREFIX(_cmp)(SEG * a, SEG * b)
865 {
866 if (a->lower < b->lower)
867 return -1;
868 if (a->lower > b->lower)
869 return 1;
870
871 if (a->upper < b->upper)
872 return -1;
873 if (a->upper > b->upper)
874 return 1;
875
876 return 0;
877 }
878
879 bool
880 BIOSEG_PREFIX(_lt)(SEG * a, SEG * b)
881 {
882 return BIOSEG_PREFIX(_cmp)(a, b) < 0;
883 }
884
885 bool
886 BIOSEG_PREFIX(_le)(SEG * a, SEG * b)
887 {
888 return BIOSEG_PREFIX(_cmp)(a, b) <= 0;
889 }
890
891 bool
892 BIOSEG_PREFIX(_gt)(SEG * a, SEG * b)
893 {
894 return BIOSEG_PREFIX(_cmp)(a, b) > 0;
895 }
896
897 bool
898 BIOSEG_PREFIX(_ge)(SEG * a, SEG * b)
899 {
900 return BIOSEG_PREFIX(_cmp)(a, b) >= 0;
901 }
902
903 bool
904 BIOSEG_PREFIX(_different)(SEG * a, SEG * b)
905 {
906 return BIOSEG_PREFIX(_cmp)(a, b) != 0;
907 }
908
909 bool
910 BIOSEG_PREFIX(_contains_int)(SEG * a, int *b)
911 {
912 #ifdef INTERBASE_COORDS
913 return ((a->lower < *b) && (a->upper > *b));
914 #else
915 return ((a->lower <= *b) && (a->upper >= *b));
916 #endif
917 }
918
919 /*
920 ** These are lower than those in geo_selfuncs.c - found by trail and error.
921 */
922 Datum
923 BIOSEG_PREFIX(_sel)(PG_FUNCTION_ARGS)
924 {
925 PG_RETURN_FLOAT8(2.0e-4);
926 }
927
928 Datum
929 BIOSEG_PREFIX(_joinsel)(PG_FUNCTION_ARGS)
930 {
931 PG_RETURN_FLOAT8(1.0e-5);
932 }
933
934 Datum
935 BIOSEG_PREFIX(_contsel)(PG_FUNCTION_ARGS)
936 {
937 PG_RETURN_FLOAT8(1.0e-4);
938 }
939
940 Datum
941 BIOSEG_PREFIX(_contjoinsel)(PG_FUNCTION_ARGS)
942 {
943 PG_RETURN_FLOAT8(5e-6);
944 }