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, 1 month ago) by kmr
Original Path: bioseg.c
File size: 22820 byte(s)
Log Message:
Initial bioseg checkin.

Line User Rev File contents
1 kmr 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     }