pool.cpp

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

//--------------------------------------------------------------------
//   pool.cpp
//   --------    
//   Pool of moving points
//   Implemented: TMovingPoint, TPool 
//
//   Moving point workload generator v 1.1
//   Copyright(c) 1999-2001, Aalborg University
//

#include "pool.h"
#include <assert.h>
#include <string.h>
#include <limits.h>

int TMovingPoint::Dims = 2;

//--------------------------------------------------------
//  TMovingPoint
//

ostream& TMovingPoint::write(ostream& os)
{
   os.write(reinterpret_cast<char*>(&id),  sizeof(long));
   os.write(reinterpret_cast<char*>(xref), sizeof(float) * Dims);
   os.write(reinterpret_cast<char*>(v),    sizeof(float) * Dims);

   return os;
}

//------------------------------------------------
ostream& operator << (ostream& os, TMovingPoint& mvp)
{
   int i;
  
   os << '(';
    
   for (i = 0; i < mvp.Dims; i++)
      os << mvp.xref[i] << ',';
   for (i = 0; i < mvp.Dims;)
   {
      os << mvp.v[i++];
      if (i < mvp.Dims)
         os << ',';
   } 
   os << "), " << mvp.id;

   return os;
}

//------------------------------------------------
extern "C" 
int ComparePoints  (const void *i, const void *j)
{
   if ((*(TMovingPoint**)i)->utime < (*(TMovingPoint**)j)->utime) return -1;
   if ((*(TMovingPoint**)i)->utime > (*(TMovingPoint**)j)->utime) return  1;
   if ((*(TMovingPoint**)i)->id < (*(TMovingPoint**)j)->id) return -1;
   if ((*(TMovingPoint**)i)->id > (*(TMovingPoint**)j)->id) return  1;
   
   return 0;
}

//------------------------------------------------
//  TPool 
//  TPool "owns" TMovingPoints, i.e., it deltes them in ~TPool
//
TPool::~TPool()
{
   if (array) delete[] array; 
   if (mem)   delete[] mem;
}

//------------------------------------------------
void TPool::setLen (int n)
{
   if (array) delete[] array; 
   if (mem)   delete[] mem;

   mem   = new TMovingPoint[n];
   memset (mem, 0, sizeof (mem));  
   array = new TMovingPoint*[n];
   memset (array, 0, sizeof (array));  
   len   = n;
   num   = 0; 
}

//------------------------------------------------
TMovingPoint* TPool::operator[] (int n) const
{
   assert(n < num);
   return array[n];
}

//------------------------------------------------
TMovingPoint* TPool::Top () const
{
   assert(num);
   return *array;
}

//------------------------------------------------
TMovingPoint* TPool::AddNew ()
{
   assert (num < len);
/* 
  {
      
      len += POOL_INC;

      TMovingPoint** temp = new TMovingPoint*[len];

      for (int i = 0; i < num; i++) temp[i] = array[i];
      delete[] array;
      array = temp;
   }
*/
   array[num] = mem + num;
   return array[num++];
}

//------------------------------------------------
/*
void TPool::Delete (int n)
{
    assert (false);   // not implemented correctly
   assert(n < num && n >= 0);
//   delete array[n];
   memmove (array + n, array + n + 1, (num - n - 1) * sizeof (TMovingPoint*));
   num--;
}
*/

//------------------------------------------------
void TPool::Sort()
{
   qsort(array, num, sizeof(TMovingPoint*), ComparePoints);
}

//------------------------------------------------
void TPool::Schedule ()
{
   int           pp      = 0;    // Offset from the beginning of the heap tree level 
   int           beg_lev = 0;    // Offset in the array of the beggining of the current level
   int           len_lev = 1;    // Length of the current level 
   int           cp;
   TMovingPoint** child;
   TMovingPoint*  tmp;
   TMovingPoint** point = array;  //  Starting from the top of the heap  
   
   for (;;)
   {
      pp      *= 2;      
      beg_lev += len_lev;
      cp       = beg_lev + pp;
      if (cp + 1 < num && 
          array[cp]->utime < (*point)->utime && 
          array[cp + 1]->utime < (*point)->utime)
         if (array[cp]->utime < array[cp + 1]->utime) 
	    child = array + cp;
         else
	 {
            child = array + cp + 1;
            pp++;
         } 
      else if (cp < num && array[cp]->utime < (*point)->utime) child = array + cp;
           else if (cp + 1 < num && array[cp + 1]->utime < (*point)->utime)
	        {
                   child = array + cp + 1;
                   pp++;
                } 
                else break;  
      tmp        = *point;
      *point     = *child;
      *child     = tmp;
      point      = child; 
      len_lev   *= 2;
   }
}