/****************************************************************************** ---- This file is part of SECONDO. Copyright (C) 2004-2010, University in Hagen, Faculty of Mathematics and Computer Science, Database Systems for New Applications. SECONDO is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. SECONDO is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with SECONDO; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA ---- //paragraph [1] Title: [{\Large \bf] [}] //paragraph [10] Footnote: [{\footnote{] [}}] //[TOC] [\tableofcontents] [1] Declaration of UGridAlgebra September 2010, Daniel Brockmann 1 Overview UGrid-Algebra implements a UGrid index structure. The memory management is based on SmiUpdateFile. UGrid-Algebra offers the following methods: - createUGrid -> Creates a new UGrid object. - insertUpload -> Inserts a single upload into UGrid. - insertStream -> Inserts a stream of uploads into UGrid. - intersectsWindow -> Returns all history units which intersect the search window. - insideWindow -> Returns all history units inside the search window. - getTrajectory -> Returns all history units wich belongs to the stated moving object. - currentUpload -> Returns the current upload. 2 Includes and globals ******************************************************************************/ #include #include #include #include "WinUnix.h" #include "SecondoSystem.h" #include "QueryProcessor.h" #include "Algebra.h" #include "NestedList.h" #include "ListUtils.h" #include "Attribute.h" #include "DateTime.h" #include "Algebras/RTree/RTreeAlgebra.h" #include "Algebras/Rectangle/RectangleAlgebra.h" #include "Algebras/Temporal/TemporalAlgebra.h" #include "Algebras/SETI/UploadUnit.h" #include "Symbols.h" using namespace std; using namespace temporalalgebra; using namespace datetime; extern NestedList* nl; extern QueryProcessor *qp; extern AlgebraManager *am; namespace UGridAlgebra { #include "UGridAlgebra.h" /****************************************************************************** 3. Auxiliary functions 3.1 CompareFloats Returns 'true' if the two floating-point numbers are almost equal. ******************************************************************************/ bool CompareFloats(double F1 ,double F2) { if ( F1 <= (F2 + 0.001) && F1 >= (F2 - 0.001) ) { return true; } else return false; } /****************************************************************************** 3.2 ModifyArea Modifies the given area. x1/x2 and y1/y2 will be swapped if necessary. ******************************************************************************/ UGridArea ModifyArea(UGridArea AREA) { double tempX = 0; double tempY = 0; if (AREA.x1 > AREA.x2) { tempX = AREA.x2; AREA.x2 = AREA.x1; AREA.x1 = tempX; } if (AREA.y1 > AREA.y2) { tempY = AREA.y2; AREA.y2 = AREA.y1; AREA.y1 = tempY; } AREA.x1 = AREA.x1 - tol; AREA.y1 = AREA.y1 - tol; AREA.x2 = AREA.x2 + tol; AREA.y2 = AREA.y2 + tol; return AREA; } /****************************************************************************** 3.3 ComputeLine Identifies a column or a row in a grid in dependence of a given position. ******************************************************************************/ int ComputeLine(double BORDER1 ,double BORDER2, int SPLITS, double POS) { double len = abs(BORDER1-BORDER2) / SPLITS; int i = 0; while ((BORDER1 + (i*len)) <= POS) i++; return i-1; } /****************************************************************************** 3.4 ComputeIntersection Computes the intersection point of two lines (A,B), (C,D). ******************************************************************************/ bool ComputeIntersection( double Ax, double Ay, double Bx, double By, double Cx, double Cy, double Dx, double Dy, UnitPos* is ) { double distAB, cos, sin, newX, ABpos ; if ( ((Ax==Bx) && (Ay==By)) || ((Cx==Dx) && (Cy==Dy)) ) return false; if ( ((Ax==Cx) && (Ay==Cy)) || ((Bx==Cx) && (By==Cy)) || ((Ax==Dx) && (Ay==Dy)) || ((Bx==Dx) && (By==Dy)) ) return false; Bx-=Ax; By-=Ay; Cx-=Ax; Cy-=Ay; Dx-=Ax; Dy-=Ay; distAB=sqrt(Bx*Bx+By*By); cos=Bx/distAB; sin=By/distAB; newX=Cx*cos+Cy*sin; Cy =Cy*cos-Cx*sin; Cx=newX; newX=Dx*cos+Dy*sin; Dy =Dy*cos-Dx*sin; Dx=newX; if ( ((Cy<0) && (Dy<0)) || ((Cy>=0) && (Dy>=0)) ) return false; ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy); if ( (ABpos<0) || (ABpos>distAB) ) return false; is->x = Ax+ABpos*cos; is->y = Ay+ABpos*sin; return true; } /****************************************************************************** 3.5 CreateUGridBox Creates an UGridBox which constists of a page number and a 3D-rectangle. ******************************************************************************/ UGridBox* CreateUGridBox( UGridCell* CELLPTR, UGridNode* NODEPTR ) { UGridBox* ugridBox = (UGridBox*)0; if ( CELLPTR != 0 ) { double minMax[] = {CELLPTR->pos1.x-tol, CELLPTR->pos2.x+tol, CELLPTR->pos1.y-tol, CELLPTR->pos2.y+tol, CELLPTR->tiv.start.ToDouble(), CELLPTR->tiv.end.ToDouble()}; Rectangle<3> box(true, minMax); ugridBox = new UGridBox(CELLPTR->currentPage, true, box); // Reset cell CELLPTR->pos1.x = 0; CELLPTR->pos1.y = 0; CELLPTR->pos2.x = 0; CELLPTR->pos2.y = 0; CELLPTR->tiv.lc = false; CELLPTR->tiv.rc = false; CELLPTR->numEntries = 0; } else if ( NODEPTR != 0 ) { double minMax[] = {NODEPTR->pos1.x-tol, NODEPTR->pos2.x+tol, NODEPTR->pos1.y-tol, NODEPTR->pos2.y+tol, NODEPTR->tiv.start.ToDouble(), NODEPTR->tiv.end.ToDouble()}; Rectangle<3> box(true,minMax); ugridBox = new UGridBox(NODEPTR->currentPage, false, box); // Reset node NODEPTR->pos1.x = 0; NODEPTR->pos1.y = 0; NODEPTR->pos2.x = 0; NODEPTR->pos2.y = 0; NODEPTR->tiv.lc = false; NODEPTR->tiv.rc = false; } return ugridBox; } /****************************************************************************** 3.6 ModifyUGridNode Modifies the values of a UGridNode in dependence of the UgridBox. ******************************************************************************/ void ModifyUGridNode( UGridNode* NODEPTR, UGridBox* BOX ) { double x1(BOX->box.MinD(0)); double x2(BOX->box.MaxD(0)); double y1(BOX->box.MinD(1)); double y2(BOX->box.MaxD(1)); double t1(BOX->box.MinD(2)); double t2(BOX->box.MaxD(2)); Instant T1 = DateTime(0,0,instanttype); Instant T2 = DateTime(0,0,instanttype); T1.ReadFrom(t1); T2.ReadFrom(t2); if (x1 < NODEPTR->pos1.x) NODEPTR->pos1.x = x1; if (y1 < NODEPTR->pos1.y) NODEPTR->pos1.y = y1; if (x2 > NODEPTR->pos2.x) NODEPTR->pos2.x = x2; if (y2 > NODEPTR->pos2.y) NODEPTR->pos2.y = y2; if ((NODEPTR->tiv.lc == false) || (T1 < NODEPTR->tiv.start)) { NODEPTR->tiv.start = T1; NODEPTR->tiv.lc = true; } if ((NODEPTR->tiv.rc == false) || (T2 > NODEPTR->tiv.end)) { NODEPTR->tiv.end = T2; NODEPTR->tiv.rc = true; } NODEPTR->numEntries++; } /****************************************************************************** 3.7 CheckUGridNode Returns true if the UGridNode intersects the search window. ******************************************************************************/ bool CheckUGridNode( UGridArea AREA, Instant TIME1, Instant TIME2, UGridNode* NODEPTR ) { if ( AREA.x1 <= NODEPTR->pos2.x && AREA.y1 <= NODEPTR->pos2.y && AREA.x2 >= NODEPTR->pos1.x && AREA.y2 >= NODEPTR->pos1.y && TIME1 <= NODEPTR->tiv.end && TIME2 >= NODEPTR->tiv.start ) { return true; } else { return false; } } /****************************************************************************** 3.8 CheckUGridBox Returns true if the UGridBox intersects the search window. ******************************************************************************/ bool CheckUGridBox(UGridArea AREA, Instant TIME1, Instant TIME2, UGridBox BOX) { double boxPos1x(BOX.box.MinD(0)); double boxPos2x(BOX.box.MaxD(0)); double boxPos1y(BOX.box.MinD(1)); double boxPos2y(BOX.box.MaxD(1)); double boxT1(BOX.box.MinD(2)); double boxT2(BOX.box.MaxD(2)); Instant* boxTivStart = new DateTime(0,0,instanttype); Instant* boxTivEnd = new DateTime(0,0,instanttype); boxTivStart->ReadFrom(boxT1); boxTivEnd->ReadFrom(boxT2); if ( AREA.x1 <= boxPos2x && AREA.y1 <= boxPos2y && AREA.x2 >= boxPos1x && AREA.y2 >= boxPos1y && TIME1 <= *boxTivEnd && TIME2 >= *boxTivStart ) { delete boxTivStart; delete boxTivEnd; return true; } else { delete boxTivStart; delete boxTivEnd; return false; } } /****************************************************************************** 4 Implementation of class UGrid 4.1 Basic constructor ******************************************************************************/ UGrid::UGrid(UGridArea AREA, int SPLITS) : suf(0) { // Create UGrid Header header = new UGridHeader(ModifyArea(AREA), SPLITS); // Create SmiUpdateFile suf = new SmiUpdateFile(pageSize); suf->Create(); header->fileID = suf->GetFileId(); // Create header page SmiUpdatePage* headerPage; int AppendedPage = suf->AppendNewPage(headerPage); assert( AppendedPage ); header->headerPageNo = headerPage->GetPageNo(); // Create and initialize fontline pages SmiUpdatePage* flPage; db_pgno_t nextPageNo = 0; int numEntries = 0; AppendedPage = suf->AppendNewPage(flPage); assert( AppendedPage ); header->flPageNo = flPage->GetPageNo(); int PageSelected = suf->GetPage(header->flPageNo, flPage); assert( PageSelected ); size_t offset = 0; for(int i = 0; i < flBuckets; i++) { SmiUpdatePage* bucketPage; db_pgno_t bucketPageNo; // Create new bucket page AppendedPage = suf->AppendNewPage(bucketPage); assert( AppendedPage ); bucketPageNo = bucketPage->GetPageNo(); // Write bucket page number into flPage flPage->Write(&bucketPageNo, sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); // Initialize bucket page PageSelected = suf->GetPage(bucketPageNo, bucketPage); assert( PageSelected ); bucketPage->Write(&nextPageNo, sizeof(db_pgno_t), 0); bucketPage->Write(&numEntries, sizeof(int), sizeof(db_pgno_t)); suf->PutPage(bucketPageNo, true); } // Create cell pages SmiUpdatePage* cellPage; numEntries = 0; for(int i = 0; i < 8; i++) { for(int j = 0; j < 8; j++) { AppendedPage = suf->AppendNewPage(cellPage); assert( AppendedPage ); header->cellPageNo[j][i] = cellPage->GetPageNo(); // Initialize cell page int PageSelected = suf->GetPage(header->cellPageNo[j][i], cellPage); assert( PageSelected ); cellPage->Write(&numEntries, sizeof(db_pgno_t), 0); } } // Create and initialize first node page SmiUpdatePage* nodePage; AppendedPage = suf->AppendNewPage(nodePage); assert( AppendedPage ); header->nodePageNo = nodePage->GetPageNo(); PageSelected = suf->GetPage(header->nodePageNo, nodePage); assert( PageSelected ); nodePage->Write(&nextPageNo, sizeof(db_pgno_t), 0); // Create a quad-tree like structure header->rootNode = CreateUGridTree((UGridNode*)0, header->numCells, header->splits, header->splits); // Write header and tree into SmiUpdateFile UpdateHeader(); UpdateUGridTree(header->rootNode, header->numCells, header->splits, header->splits); // Initialize semaphore SetSemaphore(false); } /****************************************************************************** 4.2 Query constructor ******************************************************************************/ UGrid::UGrid(SmiFileId FILEID) : suf(0) { // Open extisting file suf = new SmiUpdateFile(pageSize); suf->Open(FILEID, pageSize); // Create header object header = new UGridHeader(); } /****************************************************************************** 4.3 Destructor ******************************************************************************/ UGrid::~UGrid() { // Destruct UGrid-tree DestructUGridTree( header->rootNode, header->numCells ); // Delete header delete header; // Clear frontline for (int i = 0; i < flBuckets; i++) { frontline[i].clear(); } // Delete file object if(suf->IsOpen()) suf->Close(); delete suf; } /****************************************************************************** 4.4 The mandatory set of algebra support functions 4.4.1 In-method ******************************************************************************/ Word UGrid::In( ListExpr typeInfo, ListExpr instance, int errorPos, ListExpr& errorInfo, bool& correct ) { correct = false; Word result = SetWord(Address(0)); // Check list length if ( nl->ListLength(instance) != 2 ) { cmsg.inFunError("A list of length two expected!"); return result; } // Check area types ListExpr areaList = nl->First(instance); if ( !(nl->ListLength(areaList) == 4 && nl->IsAtom( nl->First(areaList) ) && nl->AtomType( nl->First(areaList) ) == RealType && nl->IsAtom( nl->Second(areaList) ) && nl->AtomType( nl->Second(areaList ) ) == RealType && nl->IsAtom( nl->Third(areaList) ) && nl->AtomType( nl->Third(areaList) ) == RealType && nl->IsAtom( nl->Fourth(areaList) ) && nl->AtomType( nl->Fourth(areaList) ) == RealType )) { cmsg.inFunError("A list of four real type values is " "expected for the first argument!"); return result; } // Area values double x1 = nl->RealValue( nl->First(areaList) ); double x2 = nl->RealValue( nl->Second(areaList) ); double y1 = nl->RealValue( nl->Third(areaList) ); double y2 = nl->RealValue( nl->Fourth(areaList) ); if (( x2 == x1 ) || (y1 == y2 )) { cmsg.inFunError("x1/x2 and y1/y2 must be different!"); return result; } UGridArea area(x1,y1,x2,y2); // Check number of partitions type if ( !(nl->IsAtom( nl->Second( instance ) ) && nl->AtomType( nl->Second( instance ) ) == IntType )) { cmsg.inFunError("An integer value is expected for second argument!"); return result; } // Check number of partitions int numPartitions = nl->IntValue( nl->Second(instance) ); if (!(numPartitions == 4096 || numPartitions == 256 || numPartitions == 16 || numPartitions == 4)) { // Wrong number of partitions -> create default UGrid result.addr = new UGrid(ModifyArea(area), 4); } else { result.addr = new UGrid(ModifyArea(area), (int)sqrt(numPartitions)); } correct = true; return result; } /****************************************************************************** 4.4.2 Out-method ******************************************************************************/ ListExpr UGrid::Out(ListExpr typeInfo, Word value ) { UGrid* ugridPtr = static_cast(value.addr); // Create area list ListExpr area = nl->FourElemList( nl->RealAtom(ugridPtr->header->area.x1), nl->RealAtom(ugridPtr->header->area.x2), nl->RealAtom(ugridPtr->header->area.y1), nl->RealAtom(ugridPtr->header->area.y2)); // Create time interval list ListExpr tiv; if (ugridPtr->header->numEntries == 0) { // Time interval is undefined if no entry exist tiv = nl->TwoElemList( nl->SymbolAtom(Symbol::UNDEFINED()), nl->SymbolAtom(Symbol::UNDEFINED())); } else if (ugridPtr->header->numEntries == 1) { // End time is undefined if only one entry exist tiv = nl->TwoElemList( OutDateTime(nl->TheEmptyList(), SetWord(&ugridPtr->header->tiv.start)), nl->SymbolAtom(Symbol::UNDEFINED())); } else { // Time interval is defined if UGrid has two entries or more tiv = nl->TwoElemList( OutDateTime(nl->TheEmptyList(), SetWord(&ugridPtr->header->tiv.start)), OutDateTime(nl->TheEmptyList(), SetWord(&ugridPtr->header->tiv.end))); } // Return output list return nl->TwoElemList(area, tiv); } /****************************************************************************** 4.4.3 Create-method ******************************************************************************/ Word UGrid::Create( const ListExpr typeInfo ) { return SetWord(Address(0)); } /****************************************************************************** 4.4.4 Delete-method ******************************************************************************/ void UGrid::Delete( const ListExpr typeInfo, Word& w ) { UGrid* ugridPtr = static_cast(w.addr); delete ugridPtr; w.addr = 0; } /****************************************************************************** 4.4.5 Open-method ******************************************************************************/ bool UGrid::Open( SmiRecord& valueRecord, size_t& offset, const ListExpr typeInfo, Word& value ) { SmiFileId fileID; db_pgno_t headerPageNo; bool ok = true; ok = ok && valueRecord.Read( &fileID, sizeof(SmiFileId), offset ); offset += sizeof(SmiFileId); ok = ok && valueRecord.Read( &headerPageNo, sizeof(db_pgno_t), offset ); offset += sizeof(db_pgno_t); if(!ok){ return false; } // Create new UGrid object with existing file UGrid* ugridPtr = new UGrid(fileID); ugridPtr->header->fileID = fileID; ugridPtr->header->headerPageNo = headerPageNo; // Reader header, frontline and UGridTree information from file ugridPtr->ReadHeader(); ugridPtr->ReadFLine(); UGridHeader* hPtr = ugridPtr->header; hPtr->rootNode = ugridPtr->ReadUGridTree( (UGridNode*)0, hPtr->area, hPtr->numCells, hPtr->splits, hPtr->splits ); value.addr = ugridPtr; return ok; } /****************************************************************************** 4.4.6 Save-method ******************************************************************************/ bool UGrid::Save( SmiRecord& valueRecord, size_t& offset, const ListExpr typeInfo, Word& value ) { UGrid* ugridPtr = static_cast(value.addr); bool ok = true; SmiFileId fileID = ugridPtr->header->fileID; db_pgno_t headerPageNo = ugridPtr->header->headerPageNo; ok = ok && valueRecord.Write(&fileID, sizeof(SmiFileId), offset ); offset += sizeof(SmiFileId); ok = ok && valueRecord.Write(&headerPageNo, sizeof(db_pgno_t), offset ); offset += sizeof(db_pgno_t); return ok; } /****************************************************************************** 4.4.7 Close-method ******************************************************************************/ void UGrid::Close( const ListExpr typeInfo, Word& w ) { UGrid* ugridPtr = static_cast(w.addr); delete ugridPtr; w.addr = 0; } /****************************************************************************** 4.4.8 Clone-method ******************************************************************************/ Word UGrid::Clone( const ListExpr typeInfo, const Word& w ) { return SetWord(Address(0)); } /****************************************************************************** 4.4.9 Cast-method ******************************************************************************/ void* UGrid::Cast( void* addr) { return (0); } /****************************************************************************** 4.4.10 SizeOfObj-method ******************************************************************************/ int UGrid::SizeOfObj() { return sizeof(UGrid); } /****************************************************************************** 4.4.11 KindCheck-method ******************************************************************************/ bool UGrid::KindCheck(ListExpr type, ListExpr& errorInfo) { return (nl->IsEqual(type, UGrid::BasicType())); } /****************************************************************************** 4.4.12 Property-method ******************************************************************************/ ListExpr UGrid::Property() { return (nl->TwoElemList( nl->FiveElemList(nl->StringAtom("Signature"), nl->StringAtom("Example Type List"), nl->StringAtom("List Rep"), nl->StringAtom("Example List"), nl->StringAtom("Remarks")), nl->FiveElemList(nl->StringAtom("-> DATA"), nl->StringAtom(UGrid::BasicType()), nl->StringAtom("(( ) p)"), nl->StringAtom("((8.2 1.6 9.7 4,6) 4096)"), nl->StringAtom("x/y must be of type real, " "p of type int.")))); } /****************************************************************************** 4.5 CreateUGridTree Creates an UGridTree (quad-tree like structure) and initializes all UGridCells (leaf nodes). ******************************************************************************/ UGridNode* UGrid::CreateUGridTree( UGridNode* FATHERNODE, int SQUARES, int RIGHTCOL, int TOPROW ) { // Create and initialize UGrideNode UGridNode* node = new UGridNode(); node->fatherNode = FATHERNODE; node->numEntries = 0; node->currentPage = (db_pgno_t)0; node->pos1 = UnitPos(0,0); node->pos2 = UnitPos(0,0); node->tiv.start = DateTime(0,0,instanttype); node->tiv.end = DateTime(0,0,instanttype); node->tiv.lc = false; node->tiv.rc = false; if (SQUARES > 4) { // Create left-bottom son node->leftBottomSon = CreateUGridTree( node, (SQUARES/4), (RIGHTCOL-((int)sqrt(SQUARES)/2)), (TOPROW-((int)sqrt(SQUARES)/2))); // Create right-bottom son node->rightBottomSon = CreateUGridTree( node, (SQUARES/4), RIGHTCOL, (TOPROW-((int)sqrt(SQUARES)/2))); // Create left-top son node->leftTopSon = CreateUGridTree( node, (SQUARES/4), (RIGHTCOL-((int)sqrt(SQUARES)/2)), TOPROW ); // Create right-top son node->rightTopSon = CreateUGridTree( node, (SQUARES/4), RIGHTCOL, TOPROW ); node->leftBottomCell = (UGridCell*)0; node->rightBottomCell = (UGridCell*)0; node->leftTopCell = (UGridCell*)0; node->rightTopCell = (UGridCell*)0; } else { node->leftBottomSon = (UGridNode*)0; node->rightBottomSon = (UGridNode*)0; node->leftTopSon = (UGridNode*)0; node->leftBottomSon = (UGridNode*)0; for (int i = 0; i < 4; i++) { int col = RIGHTCOL-1; int row = TOPROW-1; if ( i == 0 ) { col = col-1; row = row-1; } // left-bottom cell if ( i == 1 ) { row = row-1; } // right-bottom cell if ( i == 2 ) { col = col-1; } // left-top cell // Create and initialize UGridCell cells[col][row] = new UGridCell(); UGridCell* cellPtr = cells[col][row]; cellPtr->fatherNode = node; cellPtr->numEntries = 0; cellPtr->currentPage = (db_pgno_t)0; cellPtr->pos1 = UnitPos(0,0); cellPtr->pos2 = UnitPos(0,0); cellPtr->tiv.start = DateTime(0,0,instanttype); cellPtr->tiv.end = DateTime(0,0,instanttype); cellPtr->tiv.lc = false; cellPtr->tiv.rc = false; if ( i == 0 ) node->leftBottomCell = cellPtr; if ( i == 1 ) node->rightBottomCell = cellPtr; if ( i == 2 ) node->leftTopCell = cellPtr; if ( i == 3 ) node->rightTopCell = cellPtr; } } return node; } /****************************************************************************** 4.6 InsertUGridBox Inserts a UGridBox into the UGridTree. ******************************************************************************/ void UGrid::InsertUGridBox( UGridNode* NODE, UGridBox* BOX ) { if ( (NODE->numEntries%60) == 0 ) { if ( NODE->currentPage == 0 ) { // Current page does not exists -> create new page SmiUpdatePage* currentPage; int AppendedPage = suf->AppendNewPage(currentPage); assert( AppendedPage ); NODE->currentPage = currentPage->GetPageNo(); // Initialize page db_pgno_t nextRootPageNo = 0; int PageSelected = suf->GetPage(NODE->currentPage, currentPage); assert( PageSelected ); currentPage->Write(&nextRootPageNo, sizeof(db_pgno_t), 0); } else { if ((NODE->leftBottomCell != 0) && (NODE->fatherNode != 0)) { SmiUpdatePage* currentPage; int PageSelected = suf->GetPage(NODE->currentPage, currentPage); assert( PageSelected ); UGridBox* box; // Current page is nearly full up // -> write the boxes of all four son cells into page size_t offset = sizeof(db_pgno_t) + (boxSize * NODE->numEntries); // Insert boxes from all four sons(cells) for (int i = 0; i < 4; i++) { // Current page of cell is not empty if (i == 0) box =CreateUGridBox(NODE->leftBottomCell, (UGridNode*)0); if (i == 1) box =CreateUGridBox(NODE->rightBottomCell,(UGridNode*)0); if (i == 2) box =CreateUGridBox(NODE->leftTopCell, (UGridNode*)0); if (i == 3) box =CreateUGridBox(NODE->rightTopCell, (UGridNode*)0); if (box != 0) { ModifyUGridNode( NODE, box ); double minD0(box->box.MinD(0)); double maxD0(box->box.MaxD(0)); double minD1(box->box.MinD(1)); double maxD1(box->box.MaxD(1)); double minD2(box->box.MinD(2)); double maxD2(box->box.MaxD(2)); currentPage->Write(&box->pageID, sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); currentPage->Write(&box->huPageID, sizeof(bool), offset); offset += sizeof(bool); currentPage->Write(&minD0, sizeof(double), offset); offset += sizeof(double); currentPage->Write(&maxD0, sizeof(double), offset); offset += sizeof(double); currentPage->Write(&minD1, sizeof(double), offset); offset += sizeof(double); currentPage->Write(&maxD1, sizeof(double), offset); offset += sizeof(double); currentPage->Write(&minD2, sizeof(double), offset); offset += sizeof(double); currentPage->Write(&maxD2, sizeof(double), offset); offset += sizeof(double); } } } if (NODE->fatherNode != 0) { // Create page box UGridBox* box = CreateUGridBox( (UGridCell*)0, NODE ); if (box != 0) { // Reset number of node entries NODE->numEntries = 0; // Put current node page back to file //suf->PutPage(NODE->currentPage, true); // Insert box from son node into father node page InsertUGridBox( NODE->fatherNode, box ); // Create new node page SmiUpdatePage* currentPage; int AppendedPage = suf->AppendNewPage(currentPage); assert( AppendedPage ); NODE->currentPage = currentPage->GetPageNo(); } } else { // Create next page for root node db_pgno_t prevPageNo = NODE->currentPage; SmiUpdatePage* prevPage; db_pgno_t nextRootPageNo; SmiUpdatePage* nextRootPage; do { int PageSelected = suf->GetPage(prevPageNo, prevPage); assert( PageSelected ); prevPage->Read(&nextRootPageNo, sizeof(db_pgno_t), 0); prevPageNo = nextRootPageNo; } while ( nextRootPageNo != 0 ); int AppendedPage = suf->AppendNewPage(nextRootPage); assert( AppendedPage ); nextRootPageNo = nextRootPage->GetPageNo(); int PageSelected = suf->GetPage(nextRootPageNo, nextRootPage); assert( PageSelected ); prevPage->Write(&nextRootPageNo, sizeof(db_pgno_t), 0); nextRootPageNo = 0; nextRootPage->Write(&nextRootPageNo, sizeof(db_pgno_t), 0); } } } SmiUpdatePage* currentPage; int PageSelected = suf->GetPage(NODE->currentPage, currentPage); assert( PageSelected ); if (NODE->fatherNode != 0) { size_t offset = sizeof(db_pgno_t) + (boxSize * NODE->numEntries); ModifyUGridNode( NODE, BOX ); // Insert new UGridBox into node page double minD0(BOX->box.MinD(0)); double maxD0(BOX->box.MaxD(0)); double minD1(BOX->box.MinD(1)); double maxD1(BOX->box.MaxD(1)); double minD2(BOX->box.MinD(2)); double maxD2(BOX->box.MaxD(2)); currentPage->Write(&BOX->pageID, sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); currentPage->Write(&BOX->huPageID, sizeof(bool), offset); offset += sizeof(bool); currentPage->Write(&minD0, sizeof(double), offset); offset += sizeof(double); currentPage->Write(&maxD0, sizeof(double), offset); offset += sizeof(double); currentPage->Write(&minD1, sizeof(double), offset); offset += sizeof(double); currentPage->Write(&maxD1, sizeof(double), offset); offset += sizeof(double); currentPage->Write(&minD2, sizeof(double), offset); offset += sizeof(double); currentPage->Write(&maxD2, sizeof(double), offset); offset += sizeof(double); } else { // Insert new UGridBox into root page db_pgno_t nextRootPageNo = NODE->currentPage; SmiUpdatePage* nextRootPage; do { int PageSelected = suf->GetPage(nextRootPageNo, nextRootPage); assert( PageSelected ); nextRootPage->Read(&nextRootPageNo, sizeof(db_pgno_t), 0); } while ( nextRootPageNo != 0 ); size_t offset = sizeof(db_pgno_t) + (boxSize * (NODE->numEntries%60)); ModifyUGridNode( NODE, BOX ); double minD0(BOX->box.MinD(0)); double maxD0(BOX->box.MaxD(0)); double minD1(BOX->box.MinD(1)); double maxD1(BOX->box.MaxD(1)); double minD2(BOX->box.MinD(2)); double maxD2(BOX->box.MaxD(2)); nextRootPage->Write(&BOX->pageID, sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); nextRootPage->Write(&BOX->huPageID, sizeof(bool), offset); offset += sizeof(bool); nextRootPage->Write(&minD0, sizeof(double), offset); offset += sizeof(double); nextRootPage->Write(&maxD0, sizeof(double), offset); offset += sizeof(double); nextRootPage->Write(&minD1, sizeof(double), offset); offset += sizeof(double); nextRootPage->Write(&maxD1, sizeof(double), offset); offset += sizeof(double); nextRootPage->Write(&minD2, sizeof(double), offset); offset += sizeof(double); nextRootPage->Write(&maxD2, sizeof(double), offset); offset += sizeof(double); } } /****************************************************************************** 4.7 DestructUGridTree Destructs the UGridTree. ******************************************************************************/ void UGrid::DestructUGridTree( UGridNode* NODE, int SQUARES ) { if (SQUARES > 4) { DestructUGridTree( NODE->leftBottomSon, (SQUARES/4)); DestructUGridTree( NODE->rightBottomSon, (SQUARES/4)); DestructUGridTree( NODE->leftTopSon, (SQUARES/4)); DestructUGridTree( NODE->rightTopSon, (SQUARES/4)); } else { delete NODE->leftBottomCell; delete NODE->rightBottomCell; delete NODE->leftTopCell; delete NODE->rightTopCell; } delete NODE; } /****************************************************************************** 4.8 ReadHeader-method Reads UGrid-header information from file. ******************************************************************************/ void UGrid::ReadHeader() { SmiUpdatePage* headerPage; int PageSelected = suf->GetPage(header->headerPageNo, headerPage); assert( PageSelected ); size_t offset = 0; headerPage->Read(&header->flPageNo, sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { headerPage->Read(&header->cellPageNo[j][i], sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); } } headerPage->Read(&header->nodePageNo, sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); headerPage->Read(&header->rootNode, sizeof(UGridNode*), offset); offset += sizeof(UGridNode*); headerPage->Read(&header->area, sizeof(UGridArea), offset); offset += sizeof(UGridArea); headerPage->Read(&header->splits, sizeof(int), offset); offset += sizeof(int); headerPage->Read(&header->numCells, sizeof(int), offset); offset += sizeof(int); headerPage->Read(&header->numEntries, sizeof(int), offset); offset += sizeof(int); headerPage->Read(&header->numFlEntries, sizeof(int), offset); offset += sizeof(int); headerPage->Read(&header->tiv, sizeof(Interval), offset); } /****************************************************************************** 4.9 ReadFLine-method Reads UGrid-front-line information from file. ******************************************************************************/ void UGrid::ReadFLine() { SmiUpdatePage* flPage; int PageSelected = suf->GetPage(header->flPageNo, flPage); assert( PageSelected ); size_t flPageOffset = 0; for (int i = 0; i < flBuckets; i++) { SmiUpdatePage* bucketPage; db_pgno_t bucketPageNo; db_pgno_t nextPageNo; int numEntries; // Select bucket page flPage->Read( &bucketPageNo, sizeof(db_pgno_t),flPageOffset); flPageOffset += sizeof(db_pgno_t); do { PageSelected = suf->GetPage(bucketPageNo, bucketPage); assert( PageSelected ); bucketPage->Read(&nextPageNo, sizeof(db_pgno_t), 0); bucketPage->Read(&numEntries, sizeof(int), sizeof(db_pgno_t)); size_t offset = sizeof(db_pgno_t) + sizeof(int); for (int j = 0; j < numEntries; j++) { UploadUnit unit; bucketPage->Read(&unit, sizeof(UploadUnit), offset); offset += sizeof(UploadUnit); frontline[unit.GetID()%flBuckets].insert(make_pair(unit.GetID(),unit)); } if ( nextPageNo != 0 ) bucketPageNo = nextPageNo; } while(nextPageNo != 0); } } /****************************************************************************** 4.10 ReadUGridTree Reads UGridTree information from file. ******************************************************************************/ UGridNode* UGrid::ReadUGridTree( UGridNode* FATHERNODE, UGridArea AREA, int SQUARES, int RIGHTCOL, int TOPROW ) { if((header->currentNodeRecord%64) == 0) { if (header->selectedNodePage == (SmiUpdatePage*)0) { // Select first node page int PageSelected = suf->GetPage(header->nodePageNo,header->selectedNodePage); assert( PageSelected ); } else { // Select next node page db_pgno_t nextPageNo; header->selectedNodePage->Read(&nextPageNo,sizeof(db_pgno_t),0); int PageSelected = suf->GetPage(nextPageNo,header->selectedNodePage); assert( PageSelected ); } header->currentNodeRecord = 0; } // Read node data from page double tivStart, tivEnd; bool tivLc, tivRc; size_t offset = sizeof(db_pgno_t)+(header->currentNodeRecord*nodeSize); header->currentNodeRecord++; UGridNode* node = new UGridNode(); node->fatherNode = FATHERNODE; header->selectedNodePage->Read(&node->numEntries, sizeof(int), offset); offset += sizeof(int); header->selectedNodePage->Read(&node->currentPage,sizeof(db_pgno_t),offset); offset += sizeof(db_pgno_t); header->selectedNodePage->Read(&node->pos1, sizeof(UnitPos), offset); offset += sizeof(UnitPos); header->selectedNodePage->Read(&node->pos2, sizeof(UnitPos), offset); offset += sizeof(UnitPos); header->selectedNodePage->Read(&tivStart, sizeof(double), offset); offset += sizeof(double); header->selectedNodePage->Read(&tivEnd, sizeof(double), offset); offset += sizeof(double); header->selectedNodePage->Read(&tivLc, sizeof(bool), offset); offset += sizeof(bool); header->selectedNodePage->Read(&tivRc, sizeof(bool), offset); offset += sizeof(bool); node->tiv.start = DateTime(0,0,instanttype); node->tiv.end = DateTime(0,0,instanttype); node->tiv.lc = tivLc; node->tiv.rc = tivRc; node->tiv.start.ReadFrom(tivStart); node->tiv.end.ReadFrom(tivEnd); if (SQUARES > 4) { node->leftBottomSon = ReadUGridTree( node, AREA, (SQUARES/4), (RIGHTCOL-((int)sqrt(SQUARES)/2)), (TOPROW-((int)sqrt(SQUARES)/2))); node->rightBottomSon = ReadUGridTree( node, AREA, (SQUARES/4), RIGHTCOL, (TOPROW-((int)sqrt(SQUARES)/2))); node->leftTopSon = ReadUGridTree( node, AREA, (SQUARES/4), (RIGHTCOL-((int)sqrt(SQUARES)/2)), TOPROW ); node->rightTopSon = ReadUGridTree( node, AREA, (SQUARES/4), RIGHTCOL, TOPROW ); node->leftBottomCell = (UGridCell*)0; node->rightBottomCell = (UGridCell*)0; node->leftTopCell = (UGridCell*)0; node->rightTopCell = (UGridCell*)0; } else { node->leftBottomSon = (UGridNode*)0; node->rightBottomSon = (UGridNode*)0; node->leftTopSon = (UGridNode*)0; node->rightTopSon = (UGridNode*)0; // Calculate x/y cell length double areaLenX = abs(AREA.x2 - AREA.x1); double areaLenY = abs(AREA.y2 - AREA.y1); double cellLenX = areaLenX / header->splits; double cellLenY = areaLenY / header->splits; for (int i = 0; i < 4; i++) { int col = RIGHTCOL-1; int row = TOPROW-1; if ( i == 0 ) { col = col-1; row = row-1; } // leftBottomCell if ( i == 1 ) { row = row-1; } // rightBottomCell if ( i == 2 ) { col = col-1; } // leftTopCell // Create new cell object cells[col][row] = new UGridCell(); UGridCell* cellPtr = cells[col][row]; // Assign node pointer cellPtr->fatherNode = node; if ( i == 0 ) node->leftBottomCell = cells[col][row]; if ( i == 1 ) node->rightBottomCell = cells[col][row]; if ( i == 2 ) node->leftTopCell = cells[col][row]; if ( i == 3 ) node->rightTopCell = cells[col][row]; // Create cell area cellPtr->area = UGridArea(0,0,0,0); cellPtr->area.x1 = AREA.x1 + (cellLenX * col); cellPtr->area.x2 = cellPtr->area.x1 + cellLenX; cellPtr->area.y1 = AREA.y1 + (cellLenY * row); cellPtr->area.y2 = cellPtr->area.y1 + cellLenY; // Read cell data from cell page db_pgno_t cellPageNo = header->cellPageNo[(col/8)][(row/8)]; SmiUpdatePage* cellPage; int PageSelected = suf->GetPage(cellPageNo, cellPage); assert( PageSelected ); offset = ((col%8)+((row%8)*8))*cellSize; cellPage->Read(&cellPtr->numEntries, sizeof(int), offset); offset += sizeof(int); cellPage->Read(&cellPtr->currentPage, sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); cellPage->Read(&cellPtr->pos1, sizeof(UnitPos), offset); offset += sizeof(UnitPos); cellPage->Read(&cellPtr->pos2, sizeof(UnitPos), offset); offset += sizeof(UnitPos); cellPage->Read(&tivStart, sizeof(double), offset); offset += sizeof(double); cellPage->Read(&tivEnd, sizeof(double), offset); offset += sizeof(double); cellPage->Read(&tivLc, sizeof(bool), offset); offset += sizeof(bool); cellPage->Read(&tivRc, sizeof(bool), offset); cellPtr->tiv.start = DateTime(0,0,instanttype); cellPtr->tiv.end = DateTime(0,0,instanttype); cellPtr->tiv.lc = tivLc; cellPtr->tiv.rc = tivRc; cellPtr->tiv.start.ReadFrom(tivStart); cellPtr->tiv.end.ReadFrom(tivEnd); } } if (SQUARES == header->numCells) { header->currentNodeRecord = 0; header->selectedNodePage = (SmiUpdatePage*)0; } return node; } /****************************************************************************** 4.11 UpdateHeader-method Writes UGrid-header information into file. ******************************************************************************/ void UGrid::UpdateHeader() { SmiUpdatePage* headerPage; int PageSelected = suf->GetPage(header->headerPageNo, headerPage); assert( PageSelected ); size_t offset = 0; headerPage->Write(&header->flPageNo, sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { headerPage->Write(&header->cellPageNo[j][i], sizeof(db_pgno_t),offset); offset += sizeof(db_pgno_t); } } headerPage->Write(&header->nodePageNo, sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); headerPage->Write(&header->rootNode, sizeof(UGridNode*), offset); offset += sizeof(UGridNode*); headerPage->Write(&header->area, sizeof(UGridArea), offset); offset += sizeof(UGridArea); headerPage->Write(&header->splits, sizeof(int), offset); offset += sizeof(int); headerPage->Write(&header->numCells, sizeof(int), offset); offset += sizeof(int); headerPage->Write(&header->numEntries, sizeof(int), offset); offset += sizeof(int); headerPage->Write(&header->numFlEntries, sizeof(int), offset); offset += sizeof(int); headerPage->Write(&header->tiv, sizeof(Interval), offset); } /****************************************************************************** 4.12 UpdateFLine-method Writes UGrid-front-line information into file. ******************************************************************************/ void UGrid::UpdateFLine() { SmiUpdatePage* flPage; int PageSelected = suf->GetPage(header->flPageNo, flPage); assert( PageSelected ); size_t flPageOffset = 0; for (int i = 0; i < flBuckets; i++) { SmiUpdatePage* bucketPage; db_pgno_t bucketPageNo; db_pgno_t nextPageNo; // Select bucket page flPage->Read( &bucketPageNo, sizeof(db_pgno_t), flPageOffset); flPageOffset += sizeof(db_pgno_t); PageSelected = suf->GetPage(bucketPageNo, bucketPage); assert( PageSelected ); int numEntries = 0; size_t bucketPageOffset = sizeof(db_pgno_t) + sizeof(int); for (map::iterator it = frontline[i].begin(); it != frontline[i].end(); it++) { numEntries++; bucketPage->Write( &numEntries, sizeof(int), sizeof(db_pgno_t) ); bucketPage->Write( &it->second, sizeof(UploadUnit), bucketPageOffset ); bucketPageOffset += sizeof(UploadUnit); if((numEntries%70) == 0) { // Page is full up bucketPageOffset = sizeof(db_pgno_t) + sizeof(int); // Get next page bucketPage->Read(&nextPageNo, sizeof(db_pgno_t), 0); if(nextPageNo == 0) { // No next page exist -> create new next page SmiUpdatePage* newPage; int AppendedPage = suf->AppendNewPage(newPage); assert( AppendedPage ); nextPageNo = newPage->GetPageNo(); bucketPage->Write(&nextPageNo, sizeof(db_pgno_t), 0); } // Select and initialize next page PageSelected = suf->GetPage(nextPageNo, bucketPage); assert( PageSelected ); nextPageNo = 0; numEntries = 0; bucketPage->Write(&nextPageNo, sizeof(db_pgno_t), 0); bucketPage->Write(&numEntries, sizeof(int), sizeof(db_pgno_t)); } } } } /****************************************************************************** 4.13 UpdateUGridTree Writes UGridTree information into file. ******************************************************************************/ void UGrid::UpdateUGridTree( UGridNode* NODE, int SQUARES, int RIGHTCOL, int TOPROW ) { if((header->currentNodeRecord%64) == 0) { if (header->selectedNodePage == (SmiUpdatePage*)0) { // Select first node page int PageSelected = suf->GetPage(header->nodePageNo, header->selectedNodePage); assert( PageSelected ); } else { // Select next node page db_pgno_t nextPageNo; header->selectedNodePage->Read(&nextPageNo,sizeof(db_pgno_t),0); if(nextPageNo == 0) { // No next page exist -> create new next page SmiUpdatePage* newPage; int AppendedPage = suf->AppendNewPage(newPage); assert( AppendedPage ); nextPageNo = newPage->GetPageNo(); // Write next page number into previous page header->selectedNodePage->Write(&nextPageNo, sizeof(db_pgno_t), 0); } int PageSelected = suf->GetPage(nextPageNo,header->selectedNodePage); assert( PageSelected ); // Initialize next page number nextPageNo = 0; header->selectedNodePage->Write(&nextPageNo, sizeof(db_pgno_t), 0); } header->currentNodeRecord = 0; } // Write node data into page size_t offset = sizeof(db_pgno_t) + (header->currentNodeRecord*nodeSize); header->currentNodeRecord++; double tivStart = NODE->tiv.start.ToDouble(); double tivEnd = NODE->tiv.end.ToDouble(); header->selectedNodePage->Write(&NODE->numEntries, sizeof(int), offset); offset += sizeof(int); header->selectedNodePage->Write(&NODE->currentPage,sizeof(db_pgno_t),offset); offset += sizeof(db_pgno_t); header->selectedNodePage->Write(&NODE->pos1, sizeof(UnitPos), offset); offset += sizeof(UnitPos); header->selectedNodePage->Write(&NODE->pos2, sizeof(UnitPos), offset); offset += sizeof(UnitPos); header->selectedNodePage->Write(&tivStart, sizeof(double), offset); offset += sizeof(double); header->selectedNodePage->Write(&tivEnd, sizeof(double), offset); offset += sizeof(double); header->selectedNodePage->Write(&NODE->tiv.lc, sizeof(bool), offset); offset += sizeof(bool); header->selectedNodePage->Write(&NODE->tiv.rc, sizeof(bool), offset); offset += sizeof(bool); if (SQUARES > 4) { UpdateUGridTree( NODE->leftBottomSon, (SQUARES/4), (RIGHTCOL-((int)sqrt(SQUARES)/2)), (TOPROW-((int)sqrt(SQUARES)/2))); UpdateUGridTree( NODE->rightBottomSon, (SQUARES/4), RIGHTCOL, (TOPROW-((int)sqrt(SQUARES)/2))); UpdateUGridTree( NODE->leftTopSon, (SQUARES/4), (RIGHTCOL-((int)sqrt(SQUARES)/2)), TOPROW ); UpdateUGridTree( NODE->rightTopSon, (SQUARES/4), RIGHTCOL, TOPROW ); } else { for (int i = 0; i < 4; i++) { int col = RIGHTCOL-1; int row = TOPROW-1; if ( i == 0 ) { col = col-1; row = row-1; } // leftBottomCell if ( i == 1 ) { row = row-1; } // rightBottomCell if ( i == 2 ) { col = col-1; } // leftTopCell // Current cell pointer UGridCell* cellPtr = cells[col][row]; // Select cell page db_pgno_t cellPageNo = header->cellPageNo[(col/8)][(row/8)]; SmiUpdatePage* cellPage; int PageSelected = suf->GetPage(cellPageNo, cellPage); assert( PageSelected ); tivStart = cellPtr->tiv.start.ToDouble(); tivEnd = cellPtr->tiv.end.ToDouble(); // Write cell data into cell page offset = ((col%8)+((row%8)*8))*cellSize; cellPage->Write(&cellPtr->numEntries, sizeof(int), offset); offset += sizeof(int); cellPage->Write(&cellPtr->currentPage, sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); cellPage->Write(&cellPtr->pos1, sizeof(UnitPos), offset); offset += sizeof(UnitPos); cellPage->Write(&cellPtr->pos2, sizeof(UnitPos), offset); offset += sizeof(UnitPos); cellPage->Write(&tivStart, sizeof(double), offset); offset += sizeof(double); cellPage->Write(&tivEnd, sizeof(double), offset); offset += sizeof(double); cellPage->Write(&cellPtr->tiv.lc, sizeof(bool), offset); offset += sizeof(bool); cellPage->Write(&cellPtr->tiv.rc, sizeof(bool), offset); offset += sizeof(bool); } } if (SQUARES == header->numCells) { header->currentNodeRecord = 0; header->selectedNodePage = (SmiUpdatePage*)0; } } /****************************************************************************** 4.14 UpdateUGrid-method Writes all UGrid data into file. ******************************************************************************/ bool UGrid::UpdateUGrid() { // Check if SmiUpdateFile is released if(GetSemaphore()) { return false; } else { // Lock SmiUpdateFile SetSemaphore(true); // Update header in SmiUpdateFile UpdateHeader(); // Update front line in SmiUpdateFile UpdateFLine(); // Update UGrid-tree UpdateUGridTree( header->rootNode, header->numCells, header->splits, header->splits ); // Release SmiUpdateFile SetSemaphore(false); return true; } } /****************************************************************************** 4.15 insertPageID-method Inserts HistoryUnit page id's into pages set. ******************************************************************************/ void UGrid::insertPageID(db_pgno_t NODEPAGEID, bool HUPAGEID) { SmiUpdatePage* selectedNodePage; int PageSelected = suf->GetPage(NODEPAGEID,selectedNodePage); assert( PageSelected ); db_pgno_t pageID; bool huPageID; size_t offset = sizeof(db_pgno_t); for (int i = 0; i < 60; i++) { selectedNodePage->Read(&pageID, sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); selectedNodePage->Read(&huPageID, sizeof(bool), offset); offset += (sizeof(bool) + (6*sizeof(double))); if (huPageID && pageID != 0) pages.insert(pageID); if (!huPageID) insertPageID(pageID, huPageID); } } /****************************************************************************** 4.16 FindHistoryPages-method Finds HistoryUnit pages in the UGridTree. ******************************************************************************/ void UGrid::FindHistoryPages(UGridArea AREA, Instant TIME1, Instant TIME2, UGridNode* NODE, int SQUARES) { if ((NODE->numEntries > 0) && CheckUGridNode(AREA,TIME1,TIME2,NODE)) { // Find UGridBoxes in node page SmiUpdatePage* selectedNodePage; int PageSelected = suf->GetPage(NODE->currentPage,selectedNodePage); assert( PageSelected ); size_t offset = sizeof(db_pgno_t); for (int i = 0; i < NODE->numEntries; i++) { if ((NODE->fatherNode == 0) && ((i%60) == 0) && (i > 0)) { // For the root node read the following pages db_pgno_t nextPageNo; selectedNodePage->Read(&nextPageNo, sizeof(db_pgno_t), 0); if (nextPageNo != 0) { PageSelected = suf->GetPage(nextPageNo, selectedNodePage); assert( PageSelected ); offset = sizeof(db_pgno_t); } } // Read UGridBox db_pgno_t pageID; bool huPageID; double minD0, maxD0, minD1, maxD1, minD2, maxD2; selectedNodePage->Read(&pageID, sizeof(db_pgno_t), offset); offset += sizeof(db_pgno_t); selectedNodePage->Read(&huPageID, sizeof(bool), offset); offset += sizeof(bool); selectedNodePage->Read(&minD0, sizeof(double), offset); offset += sizeof(double); selectedNodePage->Read(&maxD0, sizeof(double), offset); offset += sizeof(double); selectedNodePage->Read(&minD1, sizeof(double), offset); offset += sizeof(double); selectedNodePage->Read(&maxD1, sizeof(double), offset); offset += sizeof(double); selectedNodePage->Read(&minD2, sizeof(double), offset); offset += sizeof(double); selectedNodePage->Read(&maxD2, sizeof(double), offset); offset += sizeof(double); double minMax[] = {minD0-tol, maxD0+tol, minD1-tol, maxD1+tol, minD2-tol, maxD2+tol}; Rectangle<3> rect(true,minMax); UGridBox* box = new UGridBox(pageID, huPageID, rect); if (CheckUGridBox(AREA,TIME1,TIME2,*box)) { // UGridBox is in searchWindow if (huPageID) pages.insert(pageID); else insertPageID(pageID, false); } delete box; } } if (SQUARES > 4) { FindHistoryPages(AREA,TIME1,TIME2,NODE->leftBottomSon,(SQUARES/4)); FindHistoryPages(AREA,TIME1,TIME2,NODE->rightBottomSon,(SQUARES/4)); FindHistoryPages(AREA,TIME1,TIME2,NODE->leftTopSon,(SQUARES/4)); FindHistoryPages(AREA,TIME1,TIME2,NODE->rightTopSon,(SQUARES/4)); } } /****************************************************************************** 4.17 GetUpdateFile-method Returns the UGrid file id. ******************************************************************************/ SmiUpdateFile* UGrid::GetUpdateFile() { return suf; } /****************************************************************************** 4.18 GetHeader-method Returns the pointer to the UGrid header. ******************************************************************************/ UGridHeader* UGrid::GetHeader() { return header; } /****************************************************************************** 4.19 GetCell-method Returns the pointer to the stated cell. ******************************************************************************/ UGridCell* UGrid::GetCell(int COL, int ROW) { return cells[COL][ROW]; } /****************************************************************************** 4.20 GetSemaphore-method Returns the state of the semaphore. ******************************************************************************/ bool UGrid::GetSemaphore() { bool value; SmiUpdatePage* headerPage; int PageSelected = suf->GetPage(header->headerPageNo, headerPage); assert( PageSelected ); headerPage->Read(&value, sizeof(bool), sizeof(UGridHeader)); // Wait until file is released or timeout is 0 int timeout = 100000; while(value && (timeout >= 0)) { headerPage->Read(&value, sizeof(bool), sizeof(UGridHeader)); for(int i = 0; i < 10000; i++); timeout--; } return value; } /****************************************************************************** 4.21 SetSemaphore-method Sets the state of the semaphore. ******************************************************************************/ void UGrid::SetSemaphore(bool value) { SmiUpdatePage* headerPage; int PageSelected = suf->GetPage(header->headerPageNo, headerPage); assert( PageSelected ); headerPage->Write(&value, sizeof(bool), sizeof(UGridHeader)); } /****************************************************************************** 4.22 Type constructor ******************************************************************************/ TypeConstructor UGridTC( UGrid::BasicType(), // name UGrid::Property, // property function UGrid::Out, UGrid::In, // Out and In functions 0, 0, // SaveTo and RestoreFrom functions UGrid::Create, UGrid::Delete, // object creation and deletion UGrid::Open, UGrid::Save, // object open and save UGrid::Close, UGrid::Clone, // object close and clone UGrid::Cast, // cast function UGrid::SizeOfObj, // sizeof function UGrid::KindCheck ); // kind checking function /****************************************************************************** 5 createUGrid operator Creates a new UGrid object. 5.1 createUGrid - Type mapping method ******************************************************************************/ ListExpr CreateTM(ListExpr args) { if( nl->ListLength( args ) == 2 && nl->IsEqual(nl->First(args),Rectangle<2>::BasicType()) && nl->IsEqual(nl->Second(args),CcInt::BasicType()) ) { return (nl->SymbolAtom(UGrid::BasicType())); } ErrorReporter::ReportError("rect x int expected!"); return (nl->SymbolAtom( Symbol::TYPEERROR() )); } /****************************************************************************** 5.2 createUGrid - Value mapping method ******************************************************************************/ int CreateVM(Word* args, Word& result, int message, Word& local, Supplier s) { UGrid* ugridPtr = static_cast(qp->ResultStorage(s).addr); Rectangle<2>* rect = static_cast*>(args[0].addr); CcInt* partitions = static_cast(args[1].addr); // Create UGrid area double x1(rect->MinD(0)); double x2(rect->MaxD(0)); double y1(rect->MinD(1)); double y2(rect->MaxD(1)); UGridArea area(x1,y1,x2,y2); area = ModifyArea(area); // Check number of partitions int numPartitions = partitions->GetValue(); if (!(numPartitions == 4096 || numPartitions == 256 || numPartitions == 16 || numPartitions == 4 )) { // Wrong number of partitions -> create default UGrid numPartitions = 16; } // Create UGrid with the stated number of partitions ugridPtr = new UGrid(area,(int)sqrt(numPartitions)); result.setAddr( ugridPtr ); return 0; } /****************************************************************************** 5.3 createUGrid - Specification of operator ******************************************************************************/ struct CreateInfo : OperatorInfo { CreateInfo() { name = "createUGrid"; signature = "rect x int -> ugrid"; syntax = "createUGrid( _, _ )"; meaning = "UGrid construction operator. The second argument must be 4, " "16, 256 or 4096, otherwise it will be set a default value."; } }; /****************************************************************************** 6 insertUpload operator Inserts a single upload into UGrid. 6.1 ComputeHistoryUnit-method Computes a history unit and returns it to the insertHandle method. ******************************************************************************/ HistoryUnit* ComputeHistoryUnit( UGridArea AREA, int SPLITS, UnitPos POS1, UnitPos POS2, Interval TIV ) { int startCol = ComputeLine(AREA.x1, AREA.x2, SPLITS, POS1.x); int startRow = ComputeLine(AREA.y1, AREA.y2, SPLITS, POS1.y); double xLen = abs(AREA.x1-AREA.x2) / SPLITS; double yLen = abs(AREA.y1-AREA.y2) / SPLITS; double right = (startCol+1)*xLen + AREA.x1; double left = (startCol)*xLen + AREA.x1; double top = (startRow+1)*yLen + AREA.y1; double bottom = (startRow)*yLen + AREA.y1; // Compute intersection points UnitPos* isR = new UnitPos(0,0); UnitPos* isL = new UnitPos(0,0); UnitPos* isT = new UnitPos(0,0); UnitPos* isB = new UnitPos(0,0); bool intersectsRight = ComputeIntersection(right, bottom, right, top, POS1.x, POS1.y, POS2.x, POS2.y, isR); bool intersectsLeft = ComputeIntersection(left, bottom, left,top, POS1.x, POS1.y, POS2.x, POS2.y, isL); bool intersectsTop = ComputeIntersection(left, top, right, top, POS1.x, POS1.y, POS2.x, POS2.y, isT); bool intersectsBottom = ComputeIntersection(left, bottom, right, bottom, POS1.x, POS1.y, POS2.x, POS2.y, isB); // Create new end point for history unit UnitPos p(POS2.x,POS2.y); for (int i = 0; i < 4; i++) intersects[i] = false; if (intersectsRight) {p.x = isR->x; p.y = isR->y; intersects[0] = true;} if (intersectsLeft) {p.x = isL->x; p.y = isL->y; intersects[1] = true;} if (intersectsTop) {p.x = isT->x; p.y = isT->y; intersects[2] = true;} if (intersectsBottom) {p.x = isB->x; p.y = isB->y; intersects[3] = true;} delete isR; delete isL; delete isT; delete isB; HistoryUnit* hu = new HistoryUnit(0, 0, TIV.start.ToDouble(), TIV.end.ToDouble(), POS1, p); return hu; } /****************************************************************************** 6.2 InsertHandle-method Inserts an upload into the UGrid index structure. The insertUpload and the insertStream operator make use of this method. ******************************************************************************/ int InsertHandle(UGrid* UGRIDPTR, UploadUnit* UNITPTR) { SmiUpdateFile* suf = UGRIDPTR->GetUpdateFile(); UGridHeader* hPtr = UGRIDPTR->GetHeader(); // Ceck UploadUnit if (hPtr->area.x1 < hPtr->area.x2) { if (UNITPTR->GetPos().x < hPtr->area.x1+tol || UNITPTR->GetPos().x > hPtr->area.x2-tol ) return 2; } else if (UNITPTR->GetPos().x < hPtr->area.x2+tol || UNITPTR->GetPos().x > hPtr->area.x1-tol ) return 2; if (hPtr->area.y1 < hPtr->area.y2) { if (UNITPTR->GetPos().y < hPtr->area.y1+tol || UNITPTR->GetPos().y > hPtr->area.y2-tol ) return 2; } else if (UNITPTR->GetPos().y < hPtr->area.y2+tol || UNITPTR->GetPos().y > hPtr->area.y1-tol ) return 2; // Find entry in the frontline int moID = UNITPTR->GetID(); map::iterator it; it = UGRIDPTR->frontline[moID%flBuckets].find(moID); if ( it == UGRIDPTR->frontline[moID%flBuckets].end() ) { // No entry found -> Place UploadUnit in front line UGRIDPTR->frontline[moID%flBuckets].insert(make_pair(moID,*UNITPTR)); hPtr->numFlEntries++; } else { // Entry found if(!suf->IsOpen()) suf->Open(hPtr->fileID, pageSize); HistoryUnit* hu; UnitPos pos1 = it->second.GetPos(); UnitPos pos2 = UNITPTR->GetPos(); Interval huTiv; huTiv.start = it->second.GetTime(); huTiv.end = UNITPTR->GetTime(); huTiv.lc = true; huTiv.rc = true; // Check if the current upload is younger than the last upload if(huTiv.start >= huTiv.end) return 3; // Replace UploadUnit in frontline UGRIDPTR->frontline[moID%flBuckets][moID] = *UNITPTR; do { // Find cell int col =ComputeLine(hPtr->area.x1, hPtr->area.x2, hPtr->splits, pos1.x); int row =ComputeLine(hPtr->area.y1, hPtr->area.y2, hPtr->splits, pos1.y); UGridCell* cellPtr = UGRIDPTR->GetCell(col,row); SmiUpdatePage* page; if ((cellPtr->numEntries % maxHistoryUnits) == 0) { if(cellPtr->currentPage != 0) { // Insert UGridBox into UGrid-tree UGridBox* box = CreateUGridBox( cellPtr, (UGridNode*)0 ); if (box != 0) UGRIDPTR->InsertUGridBox( cellPtr->fatherNode, box ); // Put current page back to disk //suf->PutPage(cellPtr->currentPage, true); } // Create new page if no page exist or current page is full up int AppendedPage = suf->AppendNewPage(page); assert( AppendedPage ); cellPtr->currentPage = page->GetPageNo(); } int PageSelected = suf->GetPage(cellPtr->currentPage, page); assert( PageSelected ); // Create/split new history unit hu = ComputeHistoryUnit( hPtr->area, hPtr->splits, pos1, pos2, huTiv ); hu->moID = moID; hu->huID = hPtr->numEntries; // Check/modify pos1 and pos2 of cell if ((!cellPtr->tiv.lc) || (cellPtr->pos1.x > hu->pos1.x)) cellPtr->pos1.x = hu->pos1.x; if ((!cellPtr->tiv.lc) || (cellPtr->pos1.x > hu->pos2.x)) cellPtr->pos1.x = hu->pos2.x; if ((!cellPtr->tiv.lc) || (cellPtr->pos1.y > hu->pos1.y)) cellPtr->pos1.y = hu->pos1.y; if ((!cellPtr->tiv.lc) || (cellPtr->pos1.y > hu->pos2.y)) cellPtr->pos1.y = hu->pos2.y; if ((!cellPtr->tiv.rc) || (cellPtr->pos2.x < hu->pos1.x)) cellPtr->pos2.x = hu->pos1.x; if ((!cellPtr->tiv.rc) || (cellPtr->pos2.x < hu->pos2.x)) cellPtr->pos2.x = hu->pos2.x; if ((!cellPtr->tiv.rc) || (cellPtr->pos2.y < hu->pos1.y)) cellPtr->pos2.y = hu->pos1.y; if ((!cellPtr->tiv.rc) || (cellPtr->pos2.y < hu->pos2.y)) cellPtr->pos2.y = hu->pos2.y; // Check/modify UGrid time interval if ((!hPtr->tiv.lc) || (hPtr->tiv.start > huTiv.start)) { hPtr->tiv.start = huTiv.start; hPtr->tiv.lc = true; } if ((!hPtr->tiv.rc) || (hPtr->tiv.end < huTiv.end)) { hPtr->tiv.end = huTiv.end; hPtr->tiv.rc = true; } // Check/modify cell time interval if ((!cellPtr->tiv.lc) || (cellPtr->tiv.start > huTiv.start)) { cellPtr->tiv.start = huTiv.start; cellPtr->tiv.lc = true; } if ((!cellPtr->tiv.rc) || (cellPtr->tiv.end < huTiv.end)) { cellPtr->tiv.end = huTiv.end; cellPtr->tiv.rc = true; } // Initialize tiv and number of entries in page if ((cellPtr->numEntries % maxHistoryUnits) == 0) { int pageEntries = 0; page->Write(&pageEntries, sizeof(int), 0); page->Write(&huTiv,sizeof(Interval), sizeof(int)); } // Check/modify page time interval Interval pageTiv; page->Read(&pageTiv, sizeof(Interval ), sizeof(int)); if (huTiv.start < pageTiv.start) pageTiv.start = huTiv.start; if (huTiv.end > pageTiv.end) pageTiv.end = huTiv.end; // Read number of entries in page int pageEntries; page->Read( &pageEntries, sizeof(int), 0 ); // Write HistoryUnit in page size_t offset = sizeof(int) + sizeof(Interval) + + ((pageEntries)*(sizeof(HistoryUnit))); page->Write(&hu->moID, sizeof(int), offset ); offset += sizeof(int); page->Write( &hu->huID, sizeof(int), offset ); offset += sizeof(int); page->Write(&hu->tivStart, sizeof(double), offset); offset += sizeof(double); page->Write(&hu->tivEnd, sizeof(double), offset); offset += sizeof(double); page->Write( &hu->pos1, sizeof(UnitPos), offset ); offset += sizeof(UnitPos); page->Write( &hu->pos2, sizeof(UnitPos), offset ); offset += sizeof(UnitPos); // Increase number of entries in cell and page cellPtr->numEntries++; pageEntries++; page->Write(&pageEntries, sizeof(int), 0); // Compute offset for next cell if (intersects[0] == true) pos1.x = hu->pos2.x + tol; else if (intersects[1] == true) pos1.x = hu->pos2.x - tol; else pos1.x = hu->pos2.x; if (intersects[2] == true) pos1.y = hu->pos2.y + tol; else if (intersects[3] == true) pos1.y = hu->pos2.y - tol; else pos1.y = hu->pos2.y; } while ( !(CompareFloats(pos2.x, hu->pos2.x) && CompareFloats(pos2.y, hu->pos2.y)) ); } hPtr->numEntries++; if ((hPtr->numEntries % updateCycle) == 0) { // Update file if(!UGRIDPTR->UpdateUGrid()) return 1; } return 0; } /****************************************************************************** 6.3 GenerateErrorMsg-method Generates error messages. The insertUpload and the insertStream operator make use of this method. ******************************************************************************/ void GenerateErrorMsg(bool error[3]) { static MessageCenter* msg = MessageCenter::GetInstance(); if (error[0]) { NList msgList( NList("simple"),NList("Could not access update file!") ); msg->Send(nl,msgList.listExpr()); } if (error[1]) { NList msgList( NList("simple"),NList("Upload(s) is/are out of area!") ); msg->Send(nl,msgList.listExpr()); } if (error[2]) { NList msgList( NList("simple"),NList("Upload(s) is/are out of date!") ); msg->Send(nl,msgList.listExpr()); } } /****************************************************************************** 6.4 insertUpload - Type mapping method ******************************************************************************/ ListExpr InsertUploadTM(ListExpr args) { if ( nl->ListLength( args ) == 2 && nl->IsEqual(nl->First(args), UGrid::BasicType()) && nl->IsEqual(nl->Second(args), UploadUnit::BasicType())) { return (nl->SymbolAtom(CcBool::BasicType())); } return listutils::typeError("Expected ugrid x uploadunit!"); } /****************************************************************************** 6.5 insertUpload - Value mapping method ******************************************************************************/ int InsertUploadVM(Word* args, Word& result, int message, Word& local, Supplier s) { UGrid* ugridPtr = static_cast(args[0].addr); UploadUnit* unitPtr = static_cast(args[1].addr); bool error[3]; for (int i = 0; i < 3; i++) error[i] = false; // Insert UploadUnit int res = InsertHandle(ugridPtr, unitPtr); // Memorize error if (res == 1) error[0] = true; if (res == 2) error[1] = true; if (res == 3) error[2] = true; // Update file if(!ugridPtr->UpdateUGrid()) error[0] = true; // Print error messages GenerateErrorMsg(error); // Set result result = qp->ResultStorage(s); if(error[0] || error[1] || error[2]) { static_cast( result.addr )->Set(true, false); } else { static_cast( result.addr )->Set(true, true); } return 0; } /****************************************************************************** 6.6 insertUpload - Specification of operator ******************************************************************************/ struct InsertUploadInfo : OperatorInfo { InsertUploadInfo() { name = "insertUpload"; signature = "ugrid x uploadunit -> bool"; syntax = "insertUpload( _, _)"; meaning = "UGrid insert upload operator."; } }; /****************************************************************************** 7 insertStream operator Inserts a stream of uploads into UGrid. 7.1 insertStream - Type mapping method ******************************************************************************/ ListExpr InsertStreamTM(ListExpr args) { NList type(args); if ( !type.hasLength(3) ) { return listutils::typeError("Expecting three arguments."); } NList first = type.first(); if ( !first.hasLength(2) || !first.first().isSymbol(Symbol::STREAM()) || !first.second().hasLength(2) || !first.second().first().isSymbol(Tuple::BasicType()) || !IsTupleDescription( first.second().second().listExpr() )) { return listutils::typeError("Error in first argument!"); } if ( !nl->IsEqual(nl->Second(args), UGrid::BasicType()) ) { return NList::typeError( "UGrid object for second argument expected!" ); } NList third = type.third(); if ( !third.isSymbol() ) { return NList::typeError( "Attribute name for third argument expected!" ); } string attrname = type.third().str(); ListExpr attrtype = nl->Empty(); int j = FindAttribute(first.second().second().listExpr(),attrname,attrtype); if ( j != 0 ) { if ( nl->SymbolValue(attrtype) != UploadUnit::BasicType() ) { return NList::typeError("Attribute type is not of type uploadunit."); } NList resType = NList(CcBool::BasicType()); return NList( NList(Symbol::APPEND()), NList(j).enclose(), resType ).listExpr(); } else { return NList::typeError( "Attribute name '" + attrname +"' is not known!"); } } /****************************************************************************** 7.2 insertStream - Value mapping method ******************************************************************************/ int InsertStreamVM(Word* args, Word& result, int message, Word& local, Supplier s) { Word currentTupleWord(Address(0)); int attributeIndex = static_cast( args[3].addr )->GetIntval() - 1; UGrid* ugridPtr = static_cast(args[1].addr); bool error[3]; for (int i = 0; i < 3; i++) error[i] = false; qp->Open(args[0].addr); qp->Request(args[0].addr, currentTupleWord); while(qp->Received(args[0].addr)) { Tuple* currentTuple = static_cast( currentTupleWord.addr ); UploadUnit* currentAttr = static_cast(currentTuple->GetAttribute(attributeIndex)); if( currentAttr->IsDefined() ) { // Insert upload int res = InsertHandle(ugridPtr, currentAttr); // Memorize error if (res == 1) error[0] = true; if (res == 2) error[1] = true; if (res == 3) error[2] = true; } currentTuple->DeleteIfAllowed(); qp->Request(args[0].addr, currentTupleWord); } qp->Close(args[0].addr); // Update file if(!ugridPtr->UpdateUGrid()) error[0] = true; // Print error messages GenerateErrorMsg(error); // Set result result = qp->ResultStorage(s); if(error[0] || error[1] || error[2]) { static_cast( result.addr )->Set(true, false); } else { static_cast( result.addr )->Set(true, true); } return 0; } /****************************************************************************** 7.3 insertStream - Specification of operator ******************************************************************************/ struct InsertStreamInfo : OperatorInfo { InsertStreamInfo() { name = "insertStream"; signature = "((stream (tuple([a1:d1, ..., ai:uploadunit, " "..., an:dn]))) x ugrid x ai) -> bool"; syntax = "_ insertStream[ _, _ ]"; meaning = "UGrid insert upload stream operator."; } }; /****************************************************************************** 8 IntersectsWindow operator Returns all history units which intersects the search window. 8.1 FindHistoryUnits-method Finds all history units which intersect the search window. The intersectsWindow and the insideWindow operator make use of this method. ******************************************************************************/ set FindHistoryUnits( UGrid* UGRIDPTR, UGridArea AREA, Instant TIME1, Instant TIME2) { UGridHeader* hPtr = UGRIDPTR->GetHeader(); set::iterator pIt; map::iterator huIt; map historyUnits; set hits; // Check if SmiUpdateFile is released if(UGRIDPTR->GetSemaphore()) return hits;; // Lock SmiUpdateFile UGRIDPTR->SetSemaphore(true); // Check/modify search window if ((AREA.x2 < hPtr->area.x1) || (AREA.x1 > hPtr->area.x2) || (AREA.y2 < hPtr->area.y1) || (AREA.y1 > hPtr->area.y2)) return hits; // Search window does not intersect the UGrid area if (AREA.x1area.x1) AREA.x1 = hPtr->area.x1+tol; if (AREA.x2>hPtr->area.x2) AREA.x2 = hPtr->area.x2-tol; if (AREA.y1area.y1) AREA.y1 = hPtr->area.y1+tol; if (AREA.y2>hPtr->area.y2) AREA.y2 = hPtr->area.y2-tol; // Find current pages of cell candidates int left = ComputeLine(hPtr->area.x1, hPtr->area.x2, hPtr->splits, AREA.x1); int right = ComputeLine(hPtr->area.x1, hPtr->area.x2, hPtr->splits, AREA.x2); int bottom= ComputeLine(hPtr->area.y1, hPtr->area.y2, hPtr->splits, AREA.y1); int top = ComputeLine(hPtr->area.y1, hPtr->area.y2, hPtr->splits, AREA.y2); // Clear page set UGRIDPTR->pages.clear(); for (int i = bottom; i <= top; i++) { for (int j = left; j <= right; j++) { if (UGRIDPTR->GetCell(j,i)->currentPage != 0) { // Insert current page number UGRIDPTR->pages.insert(UGRIDPTR->GetCell(j,i)->currentPage); } } } // Find history pages in UGridTree UGRIDPTR->FindHistoryPages(AREA,TIME1,TIME2,UGRIDPTR->GetHeader()->rootNode, UGRIDPTR->GetHeader()->numCells); db_pgno_t pageID; SmiRecord pageRec; int moID; int huID; double tivStart; double tivEnd; UnitPos pos1; UnitPos pos2; // Find HistoryUnits in pages for (pIt = UGRIDPTR->pages.begin(); pIt != UGRIDPTR->pages.end();) { pageID = *pIt; SmiUpdatePage* page; int PageSelected = UGRIDPTR->GetUpdateFile()->GetPage(pageID, page); assert( PageSelected ); // Read number of HistoryUnits in page int numHU; page->Read( &numHU, sizeof(int), 0 ); size_t offset = sizeof(int) + sizeof(Interval); // Read HistoryUnits for (int i = 0; i < numHU; i++) { page->Read( &moID, sizeof(int), offset ); offset += sizeof(int); page->Read( &huID, sizeof(int), offset ); offset += sizeof(int); page->Read( &tivStart, sizeof(double), offset ); offset += sizeof(double); page->Read( &tivEnd, sizeof(double), offset ); offset += sizeof(double); page->Read( &pos1, sizeof(UnitPos), offset ); offset += sizeof(UnitPos); page->Read( &pos2, sizeof(UnitPos), offset ); offset += sizeof(UnitPos); // Merge HistoryUnits if necessary bool found = false; huIt = historyUnits.find(huID); if ( huIt != historyUnits.end() ) { HistoryUnit* huPtr = huIt->second; if ( CompareFloats(huPtr->pos2.x, pos1.x) && CompareFloats(huPtr->pos2.y, pos1.y) ) { huPtr->tivEnd = tivEnd; huPtr->pos2 = pos2; found = true; } if ( CompareFloats(huPtr->pos1.x, pos2.x) && CompareFloats(huPtr->pos1.y, pos2.y) ) { huPtr->tivStart = tivStart; huPtr->pos1 = pos1; found = true; } } if (!found) historyUnits.insert(make_pair( huID, new HistoryUnit( moID, huID, tivStart, tivEnd, pos1, pos2))); } // Drop page UGRIDPTR->GetUpdateFile()->PutPage(page->GetPageNo(),false); UGRIDPTR->pages.erase(pIt++); } // Check if history unit intersects window for (huIt = historyUnits.begin(); huIt != historyUnits.end();) { HistoryUnit* huPtr = huIt->second;; Instant huStart(instanttype); Instant huEnd(instanttype); huStart.ReadFrom(huPtr->tivStart); huEnd.ReadFrom(huPtr->tivEnd); if ( TIME1 <= huEnd && TIME2 >= huStart && ((AREA.x1 <= huPtr->pos1.x && AREA.y1 <= huPtr->pos1.y && AREA.x2 >= huPtr->pos1.x && AREA.y2 >= huPtr->pos1.y) || (AREA.x1 <= huPtr->pos2.x && AREA.y1 <= huPtr->pos2.y && AREA.x2 >= huPtr->pos2.x && AREA.y2 >= huPtr->pos2.y))) hits.insert(huPtr); else delete huPtr; historyUnits.erase(huIt++); } // Release SmiUpdateFile UGRIDPTR->SetSemaphore(false); return hits; } /****************************************************************************** 8.2 intersectsWindow - Type mapping method ******************************************************************************/ ListExpr IntersectsWinTM(ListExpr args) { // Check nested list if(!(nl->ListLength( args ) == 4 && nl->IsEqual(nl->First(args),UGrid::BasicType()) && nl->IsEqual(nl->Second(args),Rectangle<2>::BasicType()) && nl->IsEqual(nl->Third(args),Instant::BasicType()) && nl->IsEqual(nl->Fourth(args),Instant::BasicType()))) { ErrorReporter::ReportError("ugrid x rect x instant x instant expected!"); return (nl->SymbolAtom( Symbol::TYPEERROR() )); } // Create output list ListExpr tupleList = nl->TwoElemList( nl->TwoElemList(nl->SymbolAtom("MovObjId"), nl->SymbolAtom(CcInt::BasicType())), nl->TwoElemList(nl->SymbolAtom("HistoryUnit"), nl->SymbolAtom(UPoint::BasicType()))); ListExpr streamList = nl->TwoElemList(nl->SymbolAtom(Symbol::STREAM()), nl->TwoElemList(nl->SymbolAtom(Tuple::BasicType()), tupleList)); return streamList; } /****************************************************************************** 8.3 intersectsWindow - Value mapping method ******************************************************************************/ int IntersectsWinVM(Word* args, Word& result, int message, Word& local, Supplier s) { struct Iterator { set hits; set::iterator it; Iterator(set HITS) { hits = HITS; it = hits.begin(); } set::iterator GetIterator() {return it;} }; Iterator* iterator = static_cast(local.addr); switch( message ) { case OPEN: { UGrid* ugridPtr = static_cast(args[0].addr); Rectangle<2>* rect = static_cast*>(args[1].addr); Instant* time1 = static_cast(args[2].addr); Instant* time2 = static_cast(args[3].addr); // Change instant values if necessary if (*time1 > *time2 ) { Instant* temp = time2; time2 = time1; time1 = temp; } // Create UGrid area double x1(rect->MinD(0)); double x2(rect->MaxD(0)); double y1(rect->MinD(1)); double y2(rect->MaxD(1)); UGridArea area(x1,y1,x2,y2); area = ModifyArea(area); // Find history units which intersect the search window set hits = FindHistoryUnits(ugridPtr,area,*time1,*time2); // Initialize iterator iterator = new Iterator(hits); local.addr = iterator; return 0; } case REQUEST: { if ( (iterator != 0) && (iterator->it != iterator->hits.end()) ) { HistoryUnit* hu = *iterator->GetIterator(); CcInt* moID = new CcInt(true, hu->moID); Interval* tiv = new Interval( DateTime(0,0,instanttype), DateTime(0,0,instanttype), true, true ); tiv->start.ReadFrom(hu->tivStart); tiv->end.ReadFrom(hu->tivEnd); UPoint* upoint = new UPoint(*tiv, hu->pos1.x, hu->pos1.y, hu->pos2.x, hu->pos2.y ); TupleType* tupType = new TupleType(nl->Second(GetTupleResultType(s))); Tuple* tup = new Tuple( tupType ); tup->PutAttribute( 0, ( Attribute* ) moID ); tup->PutAttribute( 1, ( Attribute* ) upoint ); result.addr = tup; delete tiv; delete hu; iterator->hits.erase(iterator->it++); return YIELD; } else { result.addr = 0; return CANCEL; } } case CLOSE: { if (iterator != 0) { delete iterator; local.addr = 0; } return 0; } default: { return -1; } } } /****************************************************************************** 8.4 intersectsWindow - Specification of operator ******************************************************************************/ struct IntersectsWinInfo : OperatorInfo { IntersectsWinInfo() { name = "intersectsWindow"; signature = "ugrid x rect x instant x instant -> " "stream (tuple (MovObjId int)(HistoryUnit upoint))"; syntax = "intersectsWindow ( _, _, _, _ )"; meaning = "Returns all history units which" "intersect the search window."; } }; /****************************************************************************** 9 insideWindow operator Returns all history units inside the search window. 9.1 insideWindow - Type mapping method ******************************************************************************/ ListExpr InsideWinTM(ListExpr args) { // Check nested list if(!(nl->ListLength( args ) == 4 && nl->IsEqual(nl->First(args),UGrid::BasicType()) && nl->IsEqual(nl->Second(args),Rectangle<2>::BasicType()) && nl->IsEqual(nl->Third(args),Instant::BasicType()) && nl->IsEqual(nl->Fourth(args),Instant::BasicType()))) { ErrorReporter::ReportError("ugrid x rect x instant x instant expected!"); return (nl->SymbolAtom( Symbol::TYPEERROR() )); } // Create output list ListExpr tupleList = nl->TwoElemList( nl->TwoElemList(nl->SymbolAtom("MovObjId"), nl->SymbolAtom(CcInt::BasicType())), nl->TwoElemList(nl->SymbolAtom("HistoryUnit"), nl->SymbolAtom(UPoint::BasicType()))); ListExpr streamList = nl->TwoElemList(nl->SymbolAtom(Symbol::STREAM()), nl->TwoElemList(nl->SymbolAtom(Tuple::BasicType()), tupleList)); return streamList; } /****************************************************************************** 9.2 insideWindow - Value mapping method ******************************************************************************/ int InsideWinVM(Word* args, Word& result,int message,Word& local,Supplier s) { struct Iterator { set hits; set::iterator it; Iterator(set HITS) { hits = HITS; it = hits.begin(); } set::iterator GetIterator() {return it;} }; Iterator* iterator = static_cast(local.addr); switch( message ) { case OPEN: { UGrid* ugridPtr = static_cast(args[0].addr); Rectangle<2>* rect = static_cast*>(args[1].addr); Instant* time1 = static_cast(args[2].addr); Instant* time2 = static_cast(args[3].addr); // Change time values if necessary if (*time1 > *time2 ) { Instant* temp = time2; time2 = time1; time1 = temp; } // Create UGrid area double x1(rect->MinD(0)); double x2(rect->MaxD(0)); double y1(rect->MinD(1)); double y2(rect->MaxD(1)); UGridArea area(x1,y1,x2,y2); area = ModifyArea(area); // Find history units which intersects the search window set tempHits =FindHistoryUnits(ugridPtr,area,*time1,*time2); // Check if all history units are inside the window set::iterator itTempHits; set hits; for (itTempHits = tempHits.begin(); itTempHits != tempHits.end(); itTempHits++) { HistoryUnit* ugridPtr = *itTempHits; Instant huStart(instanttype); Instant huEnd(instanttype); huStart.ReadFrom(ugridPtr->tivStart); huEnd.ReadFrom(ugridPtr->tivEnd); if ( *time1 <= huStart && *time2 >= huEnd && area.x1 <= ugridPtr->pos1.x && area.x1 <= ugridPtr->pos2.x && area.x2 >= ugridPtr->pos1.x && area.x2 >= ugridPtr->pos2.x && area.y1 <= ugridPtr->pos1.y && area.y1 <= ugridPtr->pos2.y && area.y2 >= ugridPtr->pos1.y && area.y2 >= ugridPtr->pos2.y ) { hits.insert(ugridPtr); } else delete ugridPtr; } // Initialize iterator iterator = new Iterator(hits); local.addr = iterator; return 0; } case REQUEST: { if ( (iterator != 0) && (iterator->it != iterator->hits.end()) ) { HistoryUnit* hu = *iterator->GetIterator(); CcInt* moID = new CcInt(true, hu->moID); Interval* tiv = new Interval( DateTime(0,0,instanttype), DateTime(0,0,instanttype), true, true ); tiv->start.ReadFrom(hu->tivStart); tiv->end.ReadFrom(hu->tivEnd); UPoint* upoint = new UPoint(*tiv, hu->pos1.x, hu->pos1.y, hu->pos2.x, hu->pos2.y ); TupleType* tupType = new TupleType(nl->Second(GetTupleResultType(s))); Tuple* tup = new Tuple( tupType ); tup->PutAttribute( 0, ( Attribute* ) moID ); tup->PutAttribute( 1, ( Attribute* ) upoint ); iterator->it++; result.addr = tup; delete tiv; delete hu; iterator->hits.erase(iterator->it++); return YIELD; } else { result.addr = 0; return CANCEL; } } case CLOSE: { if (iterator != 0) { delete iterator; local.addr = 0; } return 0; } default: { return -1; } } } /****************************************************************************** 9.3 insideWindow - Specification of operator ******************************************************************************/ struct InsideWinInfo : OperatorInfo { InsideWinInfo() { name = "insideWindow"; signature = "ugrid x rect x instant x instant -> " "stream (tuple (MovObjId int)(HistoryUnit upoint))"; syntax = "insideWindow ( _, _, _, _ )"; meaning = "Returns all history units inside the search window."; } }; /****************************************************************************** 10 getTrajectory operator Returns all history units wich belongs to the stated moving object. 10.1 getTrajectory - Type mapping method ******************************************************************************/ ListExpr GetTrajectoryTM(ListExpr args) { if( nl->ListLength( args ) == 2 && nl->IsEqual(nl->First(args),UGrid::BasicType()) && nl->IsEqual(nl->Second(args),CcInt::BasicType())) { ListExpr tupleList = nl->TwoElemList( nl->TwoElemList(nl->SymbolAtom("MovObjId"), nl->SymbolAtom(CcInt::BasicType())), nl->TwoElemList(nl->SymbolAtom("HistoryUnit"), nl->SymbolAtom(UPoint::BasicType()))); ListExpr streamList = nl->TwoElemList(nl->SymbolAtom(Symbol::STREAM()), nl->TwoElemList(nl->SymbolAtom(Tuple::BasicType()), tupleList)); return streamList; } ErrorReporter::ReportError("ugrid x int expected!"); return (nl->SymbolAtom( Symbol::TYPEERROR() )); } /****************************************************************************** 10.2 getTrajectory - Value mapping method ******************************************************************************/ int GetTrajectoryVM( Word* args, Word& result, int message, Word& local, Supplier s ) { struct Iterator { set hits; set::iterator it; Iterator(set HITS) { hits = HITS; it = hits.begin(); } set::iterator GetIterator() {return it;} }; Iterator* iterator = static_cast(local.addr); switch( message ) { case OPEN: { UGrid* ugritPtr = static_cast(args[0].addr); CcInt* movObjId = static_cast(args[1].addr); int moID = movObjId->GetValue(); UGridArea area (ugritPtr->GetHeader()->area.x1, ugritPtr->GetHeader()->area.y1, ugritPtr->GetHeader()->area.x2, ugritPtr->GetHeader()->area.y2); // Find all history units set tempHits = FindHistoryUnits( ugritPtr, ModifyArea(area), ugritPtr->GetHeader()->tiv.start, ugritPtr->GetHeader()->tiv.end ); // Filter all history units which belongs to the stated moving object id set::iterator itTempHits; set hits; for (itTempHits = tempHits.begin(); itTempHits != tempHits.end(); itTempHits++) { HistoryUnit* ugritPtr = *itTempHits; if ( moID == ugritPtr->moID ) { hits.insert(ugritPtr); } else delete ugritPtr; } // Initialize iterator iterator = new Iterator(hits); local.addr = iterator; return 0; } case REQUEST: { if ( iterator->it != iterator->hits.end() ) { HistoryUnit* hu = *iterator->GetIterator(); CcInt* moID = new CcInt(true, hu->moID); Interval* tiv = new Interval( DateTime(0,0,instanttype), DateTime(0,0,instanttype), true, true ); tiv->start.ReadFrom(hu->tivStart); tiv->end.ReadFrom(hu->tivEnd); UPoint* upoint = new UPoint(*tiv, hu->pos1.x, hu->pos1.y, hu->pos2.x, hu->pos2.y ); TupleType* tupType = new TupleType(nl->Second(GetTupleResultType(s))); Tuple* tup = new Tuple( tupType ); tup->PutAttribute( 0, ( Attribute* ) moID ); tup->PutAttribute( 1, ( Attribute* ) upoint ); iterator->it++; result.addr = tup; delete tiv; delete hu; iterator->hits.erase(iterator->it++); return YIELD; } else { result.addr = 0; return CANCEL; } } case CLOSE: { if (iterator != 0) { delete iterator; local.addr = 0; } return 0; } default: { return -1; } } } /****************************************************************************** 10.3 getTrajectory - Specification of operator ******************************************************************************/ struct GetTrajectoryInfo : OperatorInfo { GetTrajectoryInfo() { name = "getTrajectory"; signature = "ugrid x int -> " "stream (tuple (MovObjId int)(HistoryUnit upoint))"; syntax = "getTrajectory ( _, _ )"; meaning = "Returns all history units which belongs" "to the stated moving object id."; } }; /****************************************************************************** 11 currentUpload operator Returns the current UploadUnit. 11.1 currentUpload - Type mapping method ******************************************************************************/ ListExpr CurrentUploadTM(ListExpr args) { if( nl->ListLength( args ) == 2 && nl->IsEqual(nl->First(args),UGrid::BasicType()) && nl->IsEqual(nl->Second(args),CcInt::BasicType()) ) { return nl->SymbolAtom(UploadUnit::BasicType()); } ErrorReporter::ReportError("ugrid x int expected!"); return (nl->SymbolAtom( Symbol::TYPEERROR() )); } /****************************************************************************** 11.2 currentUpload - Value mapping method ******************************************************************************/ int CurrentUploadVM(Word* args,Word& result,int message,Word& local,Supplier s) { UGrid* ugridPtr = static_cast(args[0].addr); CcInt* moID = static_cast(args[1].addr); UploadUnit* unitPtr = static_cast(qp->ResultStorage(s).addr); // Find UploadUnit in frontline int id = moID->GetValue(); map::iterator it; it = ugridPtr->frontline[id%flBuckets].find(id); if ( it == ugridPtr->frontline[id%flBuckets].end() ) { unitPtr = new UploadUnit(); unitPtr->SetDefined(false); } else { unitPtr = new UploadUnit(it->second); unitPtr->SetDefined(true); } result.setAddr( unitPtr ); return 0; } /****************************************************************************** 11.3 currentUpload - Specification of operator ******************************************************************************/ struct CurrentUploadInfo : OperatorInfo { CurrentUploadInfo() { name = "currentUpload"; signature = "ugrid x int -> uploadunit"; syntax = "currentUpload ( _, _ )"; meaning = "Returns the current UploadUnit."; } }; /****************************************************************************** 12 UGridAlgebra ******************************************************************************/ class UGridAlgebra : public Algebra { public: UGridAlgebra() : Algebra() { AddTypeConstructor(&UGridTC); AddOperator( CreateInfo(), CreateVM, CreateTM ); AddOperator( InsertUploadInfo(), InsertUploadVM, InsertUploadTM ); AddOperator( InsertStreamInfo(), InsertStreamVM, InsertStreamTM ); AddOperator( IntersectsWinInfo(), IntersectsWinVM, IntersectsWinTM ); AddOperator( InsideWinInfo(), InsideWinVM, InsideWinTM ); AddOperator( CurrentUploadInfo(), CurrentUploadVM, CurrentUploadTM ); AddOperator( GetTrajectoryInfo(), GetTrajectoryVM, GetTrajectoryTM ); } ~UGridAlgebra() {}; }; /****************************************************************************** 13 Initialization ******************************************************************************/ extern "C" Algebra* InitializeUGridAlgebra( NestedList *nlRef, QueryProcessor *qpRef, AlgebraManager* amRef ) { nl = nlRef; qp = qpRef; am = amRef; return (new UGridAlgebra()); } } // End of UGridAlgebra namespace