gen.cpp

来自「此文件包含了在linux下实现tpr-tree索引的源代码」· C++ 代码 · 共 669 行 · 第 1/2 页

//------------------------------------------------
static void Comp2DVector (float* vect, double dx, double dy, double value)
{
   if (fabs(dx) > fabs(dy))    // To avoid overflow in division
   {
       vect[0] = (float) (sign (dx) * (value / sqrt(dy*dy/(dx*dx) + 1)));
       vect[1] = (float) (sign (dy) * fabs(vect[0] * dy / dx));
   }
   else 
   {
       vect[1] = (float) (sign (dy) * (value / sqrt(dx*dx/(dy*dy) + 1)));
       vect[0] = (float) (sign (dx) * fabs(vect[1] * dx / dy));
   }
}

//------------------------------------------------
void TGenerator::GenerateRandomV (TMovingPoint* point)
{
   double v, a, az;

#ifdef RT_EXPIRATION
   v = speeds[0] + randomf(speeds[numObjTypes - 1] - speeds[0]);
#else
   v = randomf(speeds[numObjTypes - 1]);
#endif

   switch(TMovingPoint::Dims)
   {
   case 1 :
      point->v[0] = (float) (randombool() ? v : -v);
      break;

   case 2 :
      a = randomf (2 * M_PI);         // angle from x axis
      point->v[0] = (float) (v * cos(a));
      point->v[1] = (float) (v * sin(a));                      
      break;
     
   default:  // 3D
      az = -M_PI_2 + randomf(M_PI);   // angle from x,y plane 
      a  = randomf (2 * M_PI);            // angle from x axis
      point->v[0] = (float) (v * cos(az) * cos(a));
      point->v[1] = (float) (v * cos(az) * sin(a));                      
      point->v[2] = (float) (v * sin(az));      
   }
}

//------------------------------------------------
void TGenerator::GenerateLoad ()
{
   int           i, j, fr;
   float         back;
   bool          noups = !updateInterval;
   
   TMovingPoint* point;

   cout << "Progress : 0%";

   // Generate hubs
   if (hubs == 2)
   {
      cities[0].x = (float) randomf(0.1 * spaceX);
      cities[1].x = (float) (spaceX - randomf(0.1 * spaceX));
      if (randombool()) swap (cities[0].x, cities[1].x);
      if (TMovingPoint::Dims > 1)
      {
         cities[0].y = (float) randomf(0.1 * spaceY);
         cities[1].y = (float) (spaceY - randomf(0.1 * spaceY));
         if (randombool()) swap (cities[0].y, cities[1].y);
      }
   }
   else
   for (i = 0; i < hubs; i++)
   {
      cities[i].x = (float) randomf(spaceX);
      cities[i].y = TMovingPoint::Dims > 1 ? (float) randomf(spaceY) : 0; 
   }
   
   // Generate intial point positions
   
   if(noups) updateInterval = 30;    // just to generate initial data
   for (maxID = 0; maxID < points; maxID++)
   {
      if (!(maxID % 100))
      {
         cout << "\rProgress : " << maxID * 100 / points << "%"; 
         cout.flush();
      }
      
      point = pool->AddNew();
      point->id      = maxID;
      point->inindex = 0;

      if (!hubs)    // uniform data
      {
         for (j = 0; j < TMovingPoint::Dims; j++)
            point->xref[j] = (float) (j == 0 ? randomf(spaceX) : 
                                               (j == 1 ? randomf(spaceY) : randomf(spaceZ)));
         GenerateRandomV (point);
         // To compute when the next update should take place we
         // pretend that we are somewhere in between the two
         // updates. First, we compute the length of the interval,
         // then we position ourselves at a random point inside this
         // interval.
         back = (float) randomf (updateInterval * 2);  // length of the interval    
         point->utime = tref + (float) randomf (back);
      } 
      else
      {
         point->type   = (char)           random(numObjTypes);
         point->hubto  = (unsigned short) random(hubs);
         point->imprec = 0;
         point->utime  = tref;
         point->phase  = -1; 
         back = 0; 
         UpdatePoint (point->utime, false, true);        
         fr = random (point->updates);         
         for (j = 1; j < fr; j++) UpdatePoint (point->utime, false, true);
         if (fr)
         {
            back = point->utime - tref;
            UpdatePoint(point->utime, false, true);
         }
         point->utime -= back;
         point->start  = tref - back;
      }

      if (load != 2)
      { 
         OutLoadPoint (*point); 
         point->inindex = 1;
      }
   }
   pool->Sort();
   cout << "\rProgress : 100%" << endl;   
   if(noups) updateInterval = 0; 
}
     
//------------------------------------------------
void TGenerator::UpdatePoint(float CT, bool newobj, bool init)
{
   int           i, half;
   double        dx, dy;
   double        t;        // time it takes to travel the leg
   double        at;       // time it takes to accelerate (deccelerate)
   double        s;        // the whole length of the leg
   double        st;       // traveled so far in the leg
   double        tt;       // time elapsed since departure from the previous hub
   double        speed;    // current speed
   double        vmin;     // minimum speed
   double        v, a; // cruising speed and acceleration 
   TMovingPoint* point = init ? (*pool)[pool->getNum() - 1] : pool->Top();

   if (!init && point->inindex) OutDelete(sqlf, *point);     // deleting the old information

   if (!hubs)   // uniform data
   {
       for (i = 0; i < TMovingPoint::Dims; i++)
       {  
          point->xref[i] += point->v[i] * (CT - tref);       // current possition
          if (point->xref[i] < 0) point->xref[i] = 0;
          s = i == 0 ? spaceX : (i == 1 ? spaceY : spaceZ);  // upper limit
          if (point->xref[i] > s) point->xref[i] = s;
       }
       GenerateRandomV (point);
       point->utime += (float) randomf (updateInterval * 2);
   } 
   else
   {
      v    = speeds[point->type];
      vmin = v / GEN_MINSP;
      half = (point->updates - 1) / 2;
      if (point->phase != -1)
      {  // Spare memory and recompute everything each time        
         dx = (cities[point->hubto].x - cities[point->hubfrom].x);
         dy = (cities[point->hubto].y - cities[point->hubfrom].y);
         s  = sqrt(dx*dx + dy*dy);
         at = 2 * s / GEN_ACCPART / (v + vmin);
         t  = 2 * at + s * (GEN_ACCPART - 2) / GEN_ACCPART / v; 
         tt = (CT - point->start);
         a = (v + vmin) * (v - vmin) * GEN_ACCPART / 2 / s;  // 1D and 2D
      }

      // compute st (distance traveled from hubfrom) and speed
      //
      if (point->phase != -1 && point->phase < half)
      {
         st    = vmin * tt + a * tt * tt / 2;
         speed = vmin + a * tt;
         point->utime += (float) (point->phase ==  half - 1 ? 
                                  (s * (GEN_ACCPART - 2) / GEN_ACCPART / v) : 
                                  at / ((point->updates - 1) / 2));
         point->phase++;   
      }
      else   // ph_decel or ph_void
      {
         if (point->phase != -1 && point->phase < point->updates - 1) 
         {
            st     = s - (vmin * (t - tt) + a * (t - tt) * (t - tt) / 2);
            speed  = vmin + a * (t - tt);
            point->phase++;
         }
         else    // starting a new leg
         { 
            double tb;        // time budget           

            point->hubfrom = point->hubto;
            do 
            {
               point->hubto = (unsigned short) random(hubs);
            } while (cities[point->hubfrom] == cities[point->hubto]);

            dx = (cities[point->hubto].x - cities[point->hubfrom].x);
            dy = (cities[point->hubto].y - cities[point->hubfrom].y);
            s  = sqrt(dx*dx + dy*dy);
            at = 2 * s / GEN_ACCPART / (v + vmin);
            t  = 2 * at + s * (GEN_ACCPART - 2) / GEN_ACCPART / v; 
        
            point->start = CT;
            tb = t + point->imprec;
            if (tb < 0) 
            {
 	            point->start -= tb;   // delay to compensate for too frequent past updates
               tb = 0;            
            }
            point->updates = (int) floor (tb / updateInterval);
            if (point->updates < 3) point->updates = 3;
            else if (!(point->updates % 2)) point->updates++;
            point->imprec = tb - point->updates * updateInterval;
            st           = 0; 
            speed        = vmin;      
            point->utime = point->start;
            point->phase = 0;    
         }     
         point->utime += (float) (at / ((point->updates - 1) / 2));
      }

      // compute velocity and current position vectors based on hubfrom, st, and speed
      //
      switch (TMovingPoint::Dims)
      {
      case 1 :
         point->v[0]    = (float) (speed * sign(dx)); 
         point->xref[0] = cities[point->hubfrom].x + (float) (st * sign(dx));
         break;

      case 2 :
         Comp2DVector (point->v, dx, dy, speed);
         Comp2DVector (point->xref, dx, dy, st);
         point->xref[0] += cities[point->hubfrom].x;
         point->xref[1] += cities[point->hubfrom].y;
         break;

      default: // 3D
     	   cout << "3D simulation is not currently supported. Aborting." << endl;
         exit(1);
      } 
   }
   if (!init)
   {
      // computing xref with respect to tref
      //
      for (int i = 0; i < TMovingPoint::Dims; i++)  
         point->xref[i] += (tref - CT) * point->v[i];
   
      OutInsert(sqlf, *point);

      if (newobj)
      {
         point->id      = maxID++;
         point->inindex = 0;
      }
      else point->inindex = 1;

      // schedule the next update
      pool->Schedule();
   }
}

//------------------------------------------------
void TGenerator::GenerateQueries(float CT)
{
   int    i,j;
   double coin;
   double qarea;
   double maxqarea = 2 * qSize * spaceX;
   float  delta;
   float  beg[3];
   float  end[3]; 
   float  tbeg, tend; 
  
   if (TMovingPoint::Dims > 1) maxqarea *= spaceY;
   if (TMovingPoint::Dims > 2) maxqarea *= spaceZ;

   for (i = 0; i < qQuantity; i++)
   {
      qarea = randomf(maxqarea);
      delta = (float) pow (qarea, 1.0 / TMovingPoint::Dims);
      coin  = rnd();
      if (coin < qType1 + qType2)
      { 
         beg[0] = (float) randomf(spaceX - delta);
         if (TMovingPoint::Dims > 1) beg[1] = (float) randomf(spaceY - delta);
         if (TMovingPoint::Dims > 2) beg[2] = (float) randomf(spaceZ - delta);
         for (j = 0; j < TMovingPoint::Dims; j++) end[j] = beg[j] + delta;
      } 
      if (coin < qType1) tbeg = tend = CT + (float) randomf(qWindow);
      else 
      {
         double deltat;         

         deltat = (float) randomf (qTSize);
         if (deltat > qWindow) deltat = qWindow;
         tbeg = CT + (float) randomf(qWindow - deltat);
         tend = tbeg + deltat;
      }
      if (coin >= qType1 + qType2)
      {
         int pn = random (pool->getNum());
         
         for (j = 0; j < TMovingPoint::Dims; j++) 
    	   {
            beg[j] = (*pool)[pn]->xref[j] + (tbeg - tref) * 
                     (*pool)[pn]->v[j] - delta / 2;
            end[j] = beg[j] + delta;
         }
         OutSelect (sqlf, beg, end, tbeg, tend, (*pool)[pn]->v);
      } 
      else 
         OutSelect (sqlf, beg, end, tbeg, tend, NULL);
   }
}