Decima: /Users/asorokin/Documents/workspaceC/Decima/ts/sax.c Source File

00001 /*-------------------------------------------------------------------------
00002  *
00003  * sax.c
00004  *
00005  *
00006  * Author: Anatoly Sorokin <asorokin@inf.ed.ac.uk>
00007  *
00008  *   $Id: sax.c 28 2009-07-17 17:18:31Z lptolik $
00009  *
00010  *-------------------------------------------------------------------------
00011  *
00012  * Copyright 2009 Anatoly Sorokin, School of Informatics, The University of Edinburgh
00013  *
00014  * Licensed under the Apache License, Version 2.0 (the "License");
00015  * you may not use this file except in compliance with the License.
00016  * You may obtain a copy of the License at
00017  *
00018  *          http://www.apache.org/licenses/LICENSE-2.0
00019  *
00020  *  Unless required by applicable law or agreed to in writing, software
00021  *  distributed under the License is distributed on an "AS IS" BASIS,
00022  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00023  *  See the License for the specific language governing permissions and
00024  *  limitations under the License.
00025  *
00026  *-------------------------------------------------------------------------
00027  */
00028 #include "postgres.h"
00029 
00030 #include <string.h>          /* For text conversion*/
00031 #include <float.h>
00032 #include <math.h>             /* for HUGE_VAL */
00033 
00034 #include "access/gist.h"
00035 #include "access/skey.h"
00036 #include "utils/builtins.h"
00037 #include "utils/array.h"
00038 #include "utils/builtins.h"
00039 
00040 #include "tsdata.h"
00041 
00042 /*
00043 #define GIST_DEBUG
00044 #define GIST_QUERY_DEBUG
00045 */
00046 
00047 
00048 /*
00049  * Taken from the intarray contrib header
00050  */
00051 #define ARRPTR(x)  ( (double *) ARR_DATA_PTR(x) )
00052 #define ARRNELEMS(x)  ArrayGetNItems( ARR_NDIM(x), ARR_DIMS(x))
00053 
00054 extern int  sax_yyparse();
00055 extern void sax_yyerror(const char *message);
00056 extern int sax_scanner_init(const char *str);
00057 extern void sax_scanner_finish(void);
00058 
00059 bool sax_isNull ( SAX_ELEMENT *point );
00060 
00061 PG_FUNCTION_INFO_V1(sax_in);
00062 PG_FUNCTION_INFO_V1(sax_out);
00063 PG_FUNCTION_INFO_V1(sax_length);
00064 PG_FUNCTION_INFO_V1(sax_points_per_letter);
00065 PG_FUNCTION_INFO_V1(sax_range);
00066 PG_FUNCTION_INFO_V1(sax_upper);
00067 PG_FUNCTION_INFO_V1(sax_lower);
00068 PG_FUNCTION_INFO_V1(sax_string);
00069 PG_FUNCTION_INFO_V1(sax_subset);
00070 
00071 Datum  sax_in(PG_FUNCTION_ARGS);
00072 Datum  sax_out(PG_FUNCTION_ARGS);
00073 Datum  sax_length(PG_FUNCTION_ARGS);
00074 Datum  sax_points_per_letter(PG_FUNCTION_ARGS);
00075 Datum  sax_range(PG_FUNCTION_ARGS);
00076 Datum  sax_upper(PG_FUNCTION_ARGS);
00077 Datum  sax_lower(PG_FUNCTION_ARGS);
00078 
00079 Datum  sax_string(PG_FUNCTION_ARGS);
00080 
00081 SAX* i_sax_upper(SAX* sax);
00082 SAX* i_sax_lower(SAX* sax);
00083 
00084 
00085 
00086 extern int   sax_yydebug;
00087 
00088 /*****************************************************************************
00089  * Input/Output functions
00090  *
00091  *****************************************************************************/
00099 SAX* i_sax_in(char* str){
00100      SAX *result;
00101      int length;
00102      int size;
00103 
00104      sax_yydebug = 0;//1;
00105      length = sax_scanner_init(str);
00106      size = SIZE_OF_SAX(length);//offsetof(SAX, data[0]) + sizeof(SAX_ELEMENT) * length;
00107      result = palloc0(size);
00108      SET_VARSIZE(result, size);
00109      result->length = length;
00110 
00111      if (sax_yyparse((void *)result) != 0)
00112        sax_yyerror("bogus input");
00113        /* elog(NOTICE, ">>>>>>>>>>.. did I get here at all?"); */
00114 
00115      sax_scanner_finish();
00116      return result;
00117 }
00118 
00126 Datum
00127 sax_in(PG_FUNCTION_ARGS)
00128 {
00129   char *str = PG_GETARG_CSTRING(0);
00130   SAX *result=i_sax_in(str);
00131 //  int length;
00132 //  int size;
00133 //
00134 //  sax_yydebug = 0;//1;
00135 //  length = sax_scanner_init(str);
00136 //  size = SIZE_OF_SAX(length);//offsetof(SAX, data[0]) + sizeof(SAX_ELEMENT) * length;
00137 //  result = palloc0(size);
00138 //  SET_VARSIZE(result, size);
00139 //  result->length = length;
00140 //
00141 //  if (sax_yyparse((void *)result) != 0)
00142 //    sax_yyerror("bogus input");
00143 //    /* elog(NOTICE, ">>>>>>>>>>.. did I get here at all?"); */
00144 //
00145 //  sax_scanner_finish();
00146 
00147   PG_RETURN_SAX(result);
00148 }
00149 
00150 StringInfo i_sax_string(SAX* sax){
00151      StringInfo buf;
00152      int i;
00153      int ndig;
00154      unsigned char l,u;
00155 
00156      buf=makeStringInfo();
00157 
00158      if ( sax->length > 0 ) {
00159        /*
00160         * Get the number of digits to display.
00161         */
00162        ndig = DBL_DIG + extra_float_digits;
00163        if (ndig < 1)
00164          ndig = 1;
00165 
00166        if (ndig > 5)
00167          ndig = 5;
00168 
00169        for ( i = 0; i < sax->length; i++ ) {
00170          if(sax->data[i].cardinality <4){
00171             l=promoteLetter(sax->data[i].lower,0,sax->data[i].cardinality,4);
00172             u=promoteLetter(sax->data[i].upper,15,sax->data[i].cardinality,4);
00173          }else if(sax->data[i].cardinality==4){
00174             l=sax->data[i].lower;
00175             u=sax->data[i].upper;
00176          }else{
00177             l=downgradeLetter(sax->data[i].lower,sax->data[i].cardinality,4);
00178             u=downgradeLetter(sax->data[i].upper,sax->data[i].cardinality,4);
00179          }
00180          if ( sax->data[i].lower > sax->data[i].upper ) { /* testing for non-NULL values on intact sequence*/
00181       appendStringInfo(buf, "NULL");
00182 
00183          }
00184                else if ( l != u ) {
00185         appendStringInfo(buf, "|%x:%x|", l,u);
00186          }
00187          else {
00188             appendStringInfo(buf, "%x", l);
00189         }
00190        }
00191 
00192        if ( sax->points_per_letter > 0 ) {
00193          appendStringInfoChar(buf, '/');
00194          appendStringInfo(buf, "%.*g", ndig, sax->points_per_letter);
00195        }
00196      }
00197      return buf;
00198 }
00199 
00208 Datum
00209 sax_string(PG_FUNCTION_ARGS)
00210 {
00211   SAX *sax = PG_GETARG_SAX(0);
00212   int32 len,size;
00213   StringInfo str;
00214   text* result;
00215   if (sax == NULL)
00216      PG_RETURN_TEXT_P(NULL);
00217   str= i_sax_string(sax);
00218 //  fprintf(stderr, "sax_string, %d, %d, %s\n", str->len,str->maxlen,str->data);
00219   len=str->maxlen;
00220   size=VARHDRSZ + len;
00221   result = (text *) palloc(size);
00222 //  result->length = size;
00223   SET_VARSIZE(result, size);
00224   memcpy(VARDATA(result), str->data, len);
00225   PG_FREE_IF_COPY(sax, 0);
00226   pfree(str->data);
00227   pfree(str);
00228 //  PG_RETURN_CSTRING(result);
00229   PG_RETURN_TEXT_P(result);
00230 }
00231 
00232 
00240 Datum
00241 sax_out(PG_FUNCTION_ARGS)
00242 {
00243   SAX *sax = PG_GETARG_SAX(0);
00244   StringInfoData buf;
00245   int i;
00246   int ndig;
00247 
00248   if (sax == NULL)
00249     PG_RETURN_SAX(NULL);
00250 
00251   initStringInfo(&buf);
00252 
00253   if ( sax->length > 0 ) {
00254     /*
00255      * Get the number of digits to display.
00256      */
00257     ndig = DBL_DIG + extra_float_digits;
00258     if (ndig < 1)
00259       ndig = 1;
00260 
00261     if (ndig > 5)
00262       ndig = 5;
00263 
00264     for ( i = 0; i < sax->length; i++ ) {
00265       if ( i > 0 )
00266    appendStringInfo(&buf, "; ");
00267 
00268       if ( sax->data[i].lower <= sax->data[i].upper ) { /* testing for non-NULL values */
00269    appendStringInfo(&buf, "%x", sax->data[i].lower);
00270 
00271    if ( sax->data[i].lower != sax->data[i].upper ) {
00272      appendStringInfo(&buf, ":%x", sax->data[i].upper);
00273    }
00274    appendStringInfo(&buf, "|%x", sax->data[i].cardinality);
00275       }
00276       else {
00277    appendStringInfo(&buf, "NULL");
00278       }
00279     }
00280 
00281     if ( sax->points_per_letter > 0 ) {
00282       appendStringInfoChar(&buf, '/');
00283       appendStringInfo(&buf, "%.*g", ndig, sax->points_per_letter);
00284     }
00285   }
00286   PG_FREE_IF_COPY(sax, 0);
00287   PG_RETURN_CSTRING(buf.data);
00288 }
00289 
00294 Datum
00295 sax_points_per_letter(PG_FUNCTION_ARGS)
00296 {
00297   SAX   *sax = PG_GETARG_SAX(0);
00298   float4   ppl = sax->points_per_letter;
00299 
00300   PG_FREE_IF_COPY(sax, 0);
00301   PG_RETURN_FLOAT4(ppl);
00302 }
00307 Datum
00308 sax_length(PG_FUNCTION_ARGS)
00309 {
00310   SAX   *sax = PG_GETARG_SAX(0);
00311   int   length = sax->length;
00312 
00313   PG_FREE_IF_COPY(sax, 0);
00314   PG_RETURN_INT32(length);
00315 }
00316 
00317 
00322 Datum
00323 sax_range(PG_FUNCTION_ARGS)
00324 {
00325   SAX   *sax = PG_GETARG_SAX(0);
00326   SAX   *result;
00327   int   size, i;
00328   float min = HUGE;
00329   float max = -HUGE;
00330 
00331   size = SIZE_OF_SAX(1);//offsetof(SAX, data[0]) + sizeof(char) * 3;
00332   result = (SAX *) palloc0(size);
00333   SET_VARSIZE(result, size);
00334   result->length = 1;
00335 
00336   for (i = 0; i < sax->length; i++) {
00337     if (sax->data[i].lower < min )
00338       min = sax->data[i].lower;
00339     if (sax->data[i].upper > max )
00340       max = sax->data[i].upper;
00341   }
00342 
00343   result->data[0].lower = min;
00344   result->data[0].upper = max;
00345   result->data[0].cardinality = DEFAULT_CARDINALITY;
00346 
00347   PG_FREE_IF_COPY(sax, 0);
00348   PG_RETURN_SAX(result);
00349 }
00350 
00354 Datum
00355 sax_upper(PG_FUNCTION_ARGS)
00356 {
00357   SAX   *sax = PG_GETARG_SAX(0);
00358   SAX   *result;
00359   int   size, i;
00360   float min = HUGE;
00361   float max = -HUGE;
00362 
00363   result=i_sax_upper(sax);
00364 
00365   PG_FREE_IF_COPY(sax, 0);
00366   PG_RETURN_SAX(result);
00367 }
00368 
00369 /* Return a SAX consisting of point representing
00370    upper boundary of the input series */
00371 Datum
00372 sax_lower(PG_FUNCTION_ARGS)
00373 {
00374   SAX   *sax = PG_GETARG_SAX(0);
00375   SAX   *result;
00376   float min = HUGE;
00377   float max = -HUGE;
00378 
00379   result=i_sax_lower(sax);
00380 
00381   PG_FREE_IF_COPY(sax, 0);
00382   PG_RETURN_SAX(result);
00383 }
00384 
00385 
00386 SAX* i_sax_upper(SAX* sax){
00387    SAX* result;
00388      int   size, i;
00389   size = SIZE_OF_SAX(sax->length);
00390   result = (SAX *) palloc0(size);
00391   SET_VARSIZE(result, size);
00392   result->length = sax->length;
00393   result->points_per_letter=sax->points_per_letter;
00394   for (i = 0; i < sax->length; i++) {
00395      result->data[i].lower = sax->data[i].upper;
00396      result->data[i].upper = sax->data[i].upper;
00397      result->data[i].cardinality = sax->data[i].cardinality;
00398   }
00399 
00400   return result;
00401   }
00402 
00403 
00404 SAX* i_sax_lower(SAX* sax){
00405    SAX* result;
00406      int   size, i;
00407   size = SIZE_OF_SAX(sax->length);
00408   result = (SAX *) palloc0(size);
00409   SET_VARSIZE(result, size);
00410   result->length = sax->length;
00411   result->points_per_letter=sax->points_per_letter;
00412   for (i = 0; i < sax->length; i++) {
00413      result->data[i].lower = sax->data[i].lower;
00414      result->data[i].upper = sax->data[i].lower;
00415      result->data[i].cardinality = sax->data[i].cardinality;
00416   }
00417 
00418   return result;
00419   }
00420 
00424 bool sax_isNull ( SAX_ELEMENT *point ){
00425 
00426 //#ifdef SAX_DEBUG
00427 // fprintf(stderr, "\nsax_isNull\ncardinality, %d\n", point->cardinality);
00428 // fprintf(stderr, "lower, %d \n", point->lower);
00429 // fprintf(stderr, "upper, %d \n", point->upper);
00430 // fprintf(stderr, "isNull, %d\n", (point->lower > point->upper));
00431 //#endif
00432      return(point->lower > point->upper);
00433 }
00434 
00435 void i_sax_subset(SAX* sax,int32 offset,SAX* result){
00436    int i=0;
00437    int j=offset;
00438    while(j<0 && i<result->length){
00439       result->data[i].upper=0;
00440       result->data[i].lower=1;
00441       i++;
00442       j++;
00443    }
00444    while(j<sax->length && i<result->length){
00445       result->data[i].upper=sax->data[j].upper;
00446       result->data[i].lower=sax->data[j].lower;
00447       result->data[i].cardinality=sax->data[j].cardinality;
00448       i++;
00449       j++;
00450    }
00451    while(i<result->length){
00452       result->data[i].upper=0;
00453       result->data[i].lower=1;
00454       i++;
00455    }
00456 
00457 }
00458 
00459 Datum sax_subset(PG_FUNCTION_ARGS){
00460      SAX   *sax = PG_GETARG_SAX(0);
00461      int32 offset=PG_GETARG_UINT32(1);
00462      int32 length=PG_GETARG_UINT32(2);
00463 
00464      SAX   *result;
00465 
00466      int size;
00467 
00468      size = SIZE_OF_SAX(length);
00469      result = (SAX *) palloc0(size);
00470      SET_VARSIZE(result, size);
00471      result->length = length;
00472      result->points_per_letter=sax->points_per_letter;
00473 
00474      i_sax_subset(sax,offset,result);
00475 
00476      PG_FREE_IF_COPY(sax, 0);
00477      PG_RETURN_SAX(result);
00478 
00479 }
00480 /*
00481  * calculate distance between two SAX letters a and b with cardinality c.
00482  */
00483 float dist(unsigned char a,unsigned char b, unsigned char c){
00484    unsigned char i,j;
00485    unsigned char y,x;
00486    float d;
00487 #ifdef SAX_DEBUG
00488    fprintf(stderr, "\ndist, %d %d\n", a,b);
00489 #endif
00490    x=promoteLetter(a,0xff,c,8);
00491    y=promoteLetter(b,0xff,c,8);
00492 #ifdef SAX_DEBUG
00493    fprintf(stderr, "dist-1, %d %d\n", x,y);
00494 #endif
00495    if((x-y)*(x-y)<=1){
00496       return 0;
00497    }
00498    i=(x>y) ? x:y;
00499    j=(x<y) ? x:y;
00500 #ifdef SAX_DEBUG
00501    fprintf(stderr, "dist-2, %d %d\n", i,j);
00502 #endif
00503    d=bp256[i-1]-bp256[j];
00504    return d*d;
00505 }
00506 
00507 /*****************************************************************************
00508  * Cardinality manipulation functions
00509  *
00510  *****************************************************************************/
00511 
00516 unsigned char promoteLetter(unsigned char let, unsigned char ref, unsigned char oldA, unsigned char newA) {
00517    unsigned char c,mask,pref,shift,rem;
00518 // create mask for let
00519    shift=newA-oldA;
00520    mask=((1<<(oldA))-1)<<shift;
00521    c=let<<shift;
00522    pref=(ref&mask)>>shift;
00523 #ifdef SAX_DEBUG
00524    fprintf(stderr, "\ncardinality, %d  %d\n", oldA,newA);
00525    fprintf(stderr, "let, %d  %d\n", let,ref);
00526    fprintf(stderr, "calc: mask=%d  shift=%d  pref=%d c=%d\n", mask,shift,pref,c);
00527 #endif
00528 
00529    if(pref==let){
00530       // let forms a prefix of ref
00531       rem=ref&((1<<shift)-1);
00532    }else if(pref>let){
00533 // let lexicographically smaller than prefix in ref
00534       rem=((1<<shift)-1);
00535    }else{
00536       rem=0;
00537    }
00538    c|=rem;
00539    return c;
00540 }
00541 
00545 unsigned char downgradeLetter(unsigned char let, unsigned char oldA, unsigned char newA) {
00546    unsigned char c;
00547    int n;
00548    // handling of zero alphabet size
00549    if(newA==0) return 0;
00550    c=let;
00551    n=oldA-newA;
00552 // elog(NOTICE, "Original: '%d'; old alphabet '%x'; new alphabet '%x'; shift '%x'", c,oldA,newA,n);
00553    c>>=n;
00554 // elog(NOTICE, "Result: '%d'", c);
00555 #ifdef SAX_DEBUG
00556    fprintf(stderr, "\ncardinality, %d  %d\n", oldA,newA);
00557    fprintf(stderr, "let, %d \n", let);
00558    fprintf(stderr, "calc: n=%d  let=%d  (let>>n)=%d c=%d\n", n,let,(let>>n),c);
00559 #endif
00560    return c;
00561 }
00562 
00563 unsigned char changeLetterCardinality(unsigned char let, unsigned char oldA, unsigned char newA) {
00564 
00565    if (oldA == newA) {
00566       return let;
00567    } else {
00568       return downgradeLetter(let, oldA, newA);
00569    }
00570 }