rtnode.cpp

一个俄国人写的内存数据库系统

// -*- Mode: C++ -*-

//         RTnode.cpp
//
// Copyright (c) 1996, Regents of the University of California
// $Header: /usr/local/devel/GiST/libGiST/RTree/RTnode.cpp,v 1.1.1.1 1996/08/06 23:47:25 jmh Exp $


#include <string.h>
#include "RT.h"

GiSTnode *
RTnode::PickSplit()
{
  int i;
  int j;
  double max = -1, tmp;
  int seed1 = -1, seed2 = -1;
  RTkey cover1, cover2, *expand1, *expand2;
  RTnode *rightnode;
  RTentry *tmpentry1, *tmpentry2;
  int rightdeletes = 0, leftdeletes = 0;
  int *rightvec, *leftvec;

  // Guttman's poly-time split algorithm
  // first, pick furthest-distance seeds
  for (i = 0; i < NumEntries(); i++)
    for (j = i+1; j < NumEntries(); j++) {
      tmpentry1 = (RTentry *)((*this)[i].Ptr());
      tmpentry2 = (RTentry *)((*this)[j].Ptr());
      tmp = ((RTkey)tmpentry1->bbox()).dist(tmpentry2->bbox());
      if (tmp > max) {
	seed1 = i;
	seed2 = j;
	max = tmp;
      }
    }
  tmpentry1 = (RTentry *)((*this)[seed1].Ptr());
  tmpentry2 = (RTentry *)((*this)[seed2].Ptr());
  cover1 = tmpentry1->bbox();
  cover2 = tmpentry2->bbox();

  // copy current node into rightnode; we'll delete from the nodes
  // as appropriate
  rightnode = (RTnode *)Copy();

  // now assign entries to the appropriate deletion vectors
  rightvec = new int[NumEntries()];
  leftvec = new int[NumEntries()];
  for (i = 0; i < NumEntries(); i++) {
    if (i == seed1) {
      rightvec[rightdeletes++] = i;
      continue;
    }
    if (i == seed2) {
      leftvec[leftdeletes++] = i;
      continue;
    }
    tmpentry1 = (RTentry *)((*this)[i].Ptr());
    expand1 = cover1.expand(tmpentry1->bbox());
    expand2 = cover2.expand(tmpentry1->bbox());
    if (expand2->area() > expand1->area()) 
      leftvec[leftdeletes++] = i;
    else
      rightvec[rightdeletes++] = i;
    delete expand1;
    delete expand2;
  }

  // given the deletion vectors, do bulk deletes
  DeleteBulk(leftvec, leftdeletes);
  rightnode->DeleteBulk(rightvec, rightdeletes);
  delete leftvec;
  delete rightvec;

  // Return the right node
  return rightnode;
}

GiSTentry * 
RTnode::Union() const
{
  RTentry *u = new RTentry;
  int first = 1;

  u->InitKey();
  for (int i=0; i<NumEntries(); i++) {
      RTentry *rte = (RTentry*) (*this)[i].Ptr();
      if (first || rte->xlower() < u->xlower())
	  u->setxlower(rte->xlower());
      if (first || rte->xupper() > u->xupper())
	  u->setxupper(rte->xupper());
      if (first || rte->ylower() < u->ylower())
	  u->setylower(rte->ylower());
      if (first || rte->yupper() > u->yupper())
	  u->setyupper(rte->yupper());
      first = 0;
  }

  return u;
}