sgram.cpp

此文件包含了在linux下实现tpr-tree索引的源代码

//--------------------------------------------------------------------
//      sgram.cpp
//      ---------
//      Simple command interpreter for GRTree test application
//      (should have been long ago thrown away and generated with yacc!)
//
//      TPR-tree - Index for continuously moving objects
//      July 2001 release, Aalborg University
//

#include "command.h"
#include "mor_opcodes.h"
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

enum TToken 
{ 
  tAlgorithm, tNormal, tNormalHilbert, tDual, tDualHilbert, tRatio,
  tBinary, tDualSpeed, tVelocity, tCSD, tCDS, tDSC, tSDC, tAlpha, tAuto, 
  tHorizon, tLoad, tClose, tOpen, tCreate, tDrop, tSelect, tDelete,
  tInsert, tQuit, tOutFile, tOutput, tUC, tNOW, tPage, tParam, 
  tAdvanceTime, tTime, tDebug, tStatistics, tPrint, tOn, tOff, tOut, 
  tImport, tSplit, tChooseSubtree, tProperties, tCompare, tArea, tOverlap, 
  tNoOverlap, tOld, tSoft, tSoftArea, tOverUnderFlows, tInfo, tSearch, 
  tBuffer, tNodes, tMORTree, tTPRtree, tOptTree, tRTree, tLParenthesis, 
  tRParenthesis, tComma, tAND, tPower, tOR, tEqual, tUnion, tInsCT, tInsRefT, 
  tVisualize, tTree, tNode, tPath, tLevel, tOther
};

static bool Sbinary = false;
static char OneSymbTokens[] = "&(),=^|";

static struct TScannerEntry
{
   char*   text;
   TToken  token;
} ScannerArray[] =
{
  {"&",       tAND   },
  {"(",       tLParenthesis},
  {")",       tRParenthesis},
  {",",       tComma },
  {"=",       tEqual },
  {"^",       tPower },
  {"a",       tAdvanceTime},
  {"advance", tAdvanceTime},
  {"algorithm", tAlgorithm},
  {"alpha",   tAlpha },
  {"area",    tArea  },
  {"auto",    tAuto  },
  {"bin",     tBinary}, 
  {"buffer",  tBuffer},
  {"c",       tCreate},
  {"cds",     tCDS   },
  {"choosesubtree", tChooseSubtree},
  {"close",   tClose },
  {"compare", tCompare}, 
  {"create",  tCreate},
  {"csd",     tCSD}, 
  {"d",       tDelete},
  {"debug",   tDebug },
  {"delete",  tDelete},
  {"drop",    tDrop  },
  {"dsc",     tDSC   },
  {"dual",    tDual  },
  {"dualhilbert", tDualHilbert},
  {"dualspeed", tDualSpeed},
  {"exit",    tQuit  },
  {"flows",   tOverUnderFlows},
  {"horizon", tHorizon},
  {"i",       tInsert},
  {"import",  tImport},
  {"info",    tInfo  },
  {"insct",   tInsCT},
  {"insert",  tInsert},
  {"insreft", tInsRefT},
  {"l",       tClose },
  {"level",   tLevel },
  {"load",    tLoad  },
  {"mortree", tMORTree }, 
  {"node",    tNode},
  {"nodes",   tNodes},
  {"nooverlap", tNoOverlap},
  {"normal",  tNormal},
  {"normalhilbert", tNormalHilbert},  
  {"now",     tNOW   },
  {"o",       tOpen  },
  {"off",     tOff   },
  {"old",     tOld   },
  {"on",      tOn    },
  {"open",    tOpen  },
  {"opttree", tOptTree}, 
  {"out",     tOut   },
  {"outfile", tOutFile},
  {"output",  tOutput},
  {"overlap", tOverlap},
  {"p",       tParam },
  {"page",    tPage  },
  {"param",   tParam },
  {"path",    tPath  },
  {"print",   tPrint },
  {"properties", tProperties},
  {"q",       tQuit  },
  {"quit",    tQuit  },
  {"r",       tDrop  },
  {"ratio",   tRatio },
  {"rtree",   tRTree},
  {"s",       tSelect},
  {"sdc",     tSDC   },
  {"search",  tSearch},
  {"select",  tSelect},
  {"soft",    tSoft  },
  {"softarea", tSoftArea},
  {"split",   tSplit },
  {"stat",    tStatistics},
  {"statistics", tStatistics},
  {"stats",   tStatistics},
  {"t",       tTime  },
  {"time",    tTime  },
  {"tprtree", tTPRtree},
  {"tree",    tTree  },
  {"uc",      tUC    },
  {"union",   tUnion},
  {"velocity", tVelocity},
  {"visualize", tVisualize},
  {"|",       tOR    },
};

enum TErrorCode 
{
  eMissingLParenthesis = 0,
  eMissingCoordinate,  
  eMissingComma,
  eMissingTimeStamp,
  eMissingRParenthesis,
  eMissingNumAfterComma,
  eWrongOperation,
  eWrongBinOperation,
  eIllegalSwitchToBinary,
  eMissingNumOfDimensions,
  eMissingMethodName,
  eMissingAlpha,
  eMissingWfactor,
  eMissingUW,
  eMissingParam,
  eMissingTimeValue,
  eMissingBufferSize,
  eMissingPageSize,
  eMissingExtent,
  eMissingOnOffOut,
  eWrongVisualizationObject,
  eUnknownCommand
};

static char* ErrorArray[] = 
{
  "( required. ",
  "Spatial coordinate required. ", 
  "Comma required. ",
  "Timestamp required. ",
  ") required. ",
  "Numerical value after comma required. ",
  "Wrong operation symbol. ",
  "Wrong operation code in binary mode. ",
  "Binary mode supported only in imported files. ",
  "Number of dimensions should be specified. ",
  "Method name required. Supported methods are: tprtree, rtree, r2tree. ",
  "Alpha ratio value required. ",
  "W-factor value required to support auto-adaptive horizon. ",   
  "Time horizon value pair (U, W) required. ",
  "Parameter required. ",
  "Time value required. ",
  "Buffer size value required. ",
  "Page size value required. ",
  "Extent value required. ",
  "On, Off, or Out required after flows, insert, search, or split. ",  
  "Wrong visualization object. Expected values are: tree, node, path, off. ", 
  "Unknown command. "
};

static char  buf[100];

//------------------------------------------------
static void Error(int err_num)
{
   outstr << "Parser error: " << ErrorArray[err_num] << endl;  
   exit (1);
}

//------------------------------------------------
static void SkipSpaces (char*& p)
{
   while (*p == ' ') p++;
}

//------------------------------------------------
static int IsWhiteSpace(char* p)
{
   SkipSpaces (p);
   return (!*p || *p == '#' || *p == '\n');
}

//------------------------------------------------
static char* GetFileName(char* p)
{
   char* pp;

   SkipSpaces(p);
   pp = p;
   while (*p && *p !=  ' ' && *p != '\n') p++;
   *p = '\x0';

   return pp;
}

//------------------------------------------------
static int TokenCmp (const void *a, const void *b)
{
   return strcmp (*(const char**) a, *(const char**)b);
}

#ifdef UNIX
//------------------------------------------------
static char* strlwr(char* str)
{
   char* p = str;

   for (; *p; p++) *p = (char) tolower(*p);

   return str;
}
#endif

//------------------------------------------------
static TToken Scanner (char*& p, char*& tokenString)
{
   static char    tokenBuf[50];
   char          *key;
   TScannerEntry *se;
   int            i = 0;

   SkipSpaces (p);
   if (strchr(OneSymbTokens, *p)) tokenBuf[i++] = *p++;
   else
      for (; !isspace(*p) && *p && !strchr(OneSymbTokens, *p); p++, i++) tokenBuf[i] = *p;
   tokenBuf[i] = '\x0';
   strlwr (tokenBuf);
   key = tokenBuf;
   se = (TScannerEntry*) bsearch (&key, ScannerArray,
                                  sizeof(ScannerArray)/sizeof(TScannerEntry),
                                  sizeof(TScannerEntry), TokenCmp);

   tokenString = tokenBuf;
   if (se) return se->token;
   return  tOther;
}

//------------------------------------------------
static inputstruct* GetKey (char*& p, bool search = false)
{
   int          i, d = search ? Settings.GetDims() : Settings.GetDims() * 2;
   TToken       token;
   char*        t;
   inputstruct* s = new inputstruct;

   s->oper = RTEqual;
   s->t1   = 0;
   s->t2   = TPR_TS_INF;

   token = Scanner (p, t);
   if (token != tLParenthesis) Error (eMissingLParenthesis); 

   for (i = 0; i < d; i++)
   {
      token = Scanner (p, t);
      if (token != tOther) Error (eMissingCoordinate);
      s->coordslow[i] = atof (t);
      token = Scanner (p, t);
      if ((i != d - 1 || search) && token != tComma)
	 Error (eMissingComma);
   }
   if (search)
   {
      for (i = 0; i < d; i++)         // getting end-coordinates of a query
      {
         token = Scanner (p, t);
         if (token != tOther) Error (eMissingCoordinate);
         s->coordshigh[i] = atof (t);
         token = Scanner (p, t);
         if (token != tComma) Error (eMissingComma);
      }

      token = Scanner (p, t);
      if (token != tOther) Error (eMissingTimeStamp);
      s->t1 = atof (t);
      token = Scanner (p, t);
      if (token != tComma) Error (eMissingComma);
      token = Scanner (p, t);
      if (token != tOther) Error (eMissingTimeStamp);
      s->t2 = atof (t);
      token = Scanner (p, t);
      if (token == tComma)           // getting type 3 query velocity
         for (i = Settings.GetDims(); i < Settings.GetDims()*2; i++)
         {
  	    if (token != tComma) Error (eMissingComma);
            token = Scanner (p, t);
            if (token != tOther) Error (eMissingCoordinate);
            s->coordslow[i] = s->coordshigh[i] = atof (t);
            token = Scanner (p, t);
         }
      else 
        for (i = Settings.GetDims(); i < Settings.GetDims() * 2; i++) 
           s->coordshigh[i] = s->coordslow[i] = 0;   
   } 

   if (token != tRParenthesis) Error (eMissingRParenthesis);

   if (!search)
   {
      token = Scanner(p, t);
      if (token != tComma) Error (eMissingComma);
      token = Scanner(p, t);
      if (token != tOther) Error (eMissingNumAfterComma);
      s->rid = atol (t);
   }
   else s->rid = 0;

   return s;
}

//------------------------------------------------
static inputstruct* GetPredicate (char*& p, bool search = false)
{
   TToken       token;
   char*        tstr;
   inputstruct* result;
   RToper oper;

   token = Scanner(p, tstr);
   switch(token)
   {
    case tAND   : oper = RToverlap;   break;
    case tPower : oper = RTcontains;  break;
    case tOR    : oper = RTcontained; break;
    case tEqual : oper = RTEqual;     break;
    default     : Error (eWrongOperation);
   }
   result       = GetKey(p, search);
   result->oper = oper;
   return result;
}

//---------------------------------------------------
static inputstruct* GetBinaryKey(FILE* fl)
{
   inputstruct* s = new inputstruct;

   s->oper = RTEqual;
   s->t1   = 0;
   s->t2   = TPR_TS_INF;

   fread(&s->rid, sizeof(GiSTpage), 1, fl);
   fread(s->coordslow, sizeof(RTcoord), 2 * Settings.GetDims(), fl);
   
   return s;
}

//------------------------------------------------
static void DoBinaryOp()
{
   int            i;
   char           opc;
   float          li;
   unsigned short us; 
   FILE*          fl = imports[numImports - 1];
   inputstruct*   st;
   
   fread(&opc, 1, 1, fl);
   switch(opc)
   {
    case OPC_EOF:
      fclose(fl);
      numImports--;
      Sbinary = false; 
      break; 
 
    case OPC_A  : 
      CommandAdvanceTime();
      break;

    case OPC_AX : 
      fread(&li, sizeof(float), 1, fl);
      CommandAdvanceTime(li);
      break;
    
    case OPC_TX : 
      fread(&li, sizeof(float), 1, fl);
      CommandTime(li);
      break;
 
    case OPC_I  : 
      st = GetBinaryKey (fl);
      CommandInsert(st); 
      delete st;
      break;

    case OPC_D  : 
      st = GetBinaryKey (fl);
      CommandDelete(st); 
      delete st;
      break;
  
    case OPC_S  :
    case OPC_S3 :
      st = new inputstruct;
      fread(st->coordslow, sizeof(RTcoord), Settings.GetDims(), fl);
      fread(st->coordshigh, sizeof(RTcoord), Settings.GetDims(), fl);
      fread(&st->t1, sizeof(RTtimeStamp), 1, fl);
      fread(&st->t2, sizeof(RTtimeStamp), 1, fl);
      if (opc == OPC_S3)