diff options
Diffstat (limited to 'indexmgr/sdirindexlogic.cc')
| -rw-r--r-- | indexmgr/sdirindexlogic.cc | 333 |
1 files changed, 333 insertions, 0 deletions
diff --git a/indexmgr/sdirindexlogic.cc b/indexmgr/sdirindexlogic.cc new file mode 100644 index 0000000..e63ba22 --- /dev/null +++ b/indexmgr/sdirindexlogic.cc @@ -0,0 +1,333 @@ +/* +* This file is part of rasdaman community. +* +* Rasdaman community 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 3 of the License, or +* (at your option) any later version. +* +* Rasdaman community 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 rasdaman community. If not, see <http://www.gnu.org/licenses/>. +* +* Copyright 2003, 2004, 2005, 2006, 2007, 2008, 2009 Peter Baumann / +rasdaman GmbH. +* +* For more information please see <http://www.rasdaman.org> +* or contact Peter Baumann via <baumann@rasdaman.com>. +/ +/** + * SOURCE: dirix.cc + * + * MODULE: indexmgr + * CLASS: SDirIndexLogic + * + * COMMENTS: + * +*/ +static const char rcsiddirix[] = "@(#)dirix, SDirIndexLogic: $Id: sdirindexlogic.cc,v 1.10 2002/06/15 18:27:49 coman Exp $"; + +#include <iostream> +#include "raslib/rmdebug.hh" +#include "indexmgr/sdirindexlogic.hh" +#include "keyobject.hh" +#include "indexds.hh" + + +bool +SDirIndexLogic::insertObject(IndexDS* ixDS, const KeyObject& newKeyObject, const StorageLayout& sl) + { + RMDBGENTER(4, RMDebug::module_indexmgr, "SDirIndexLogic", "insertObject(" << newKeyObject << ")"); + r_Minterval newKeyObjectDomain = newKeyObject.getDomain(); + + int pos = binarySearch(ixDS, newKeyObjectDomain, Lowest, 0, (int)ixDS->getSize()-1); + ixDS->insertObject(newKeyObject, pos + 1); + RMDBGEXIT(4, RMDebug::module_indexmgr, "SDirIndexLogic", "insertObject(" << newKeyObject << ")"); + //should check if insertion was succesfull + return true; + } + +int +SDirIndexLogic::binarySearch( const IndexDS* ixDS, + const r_Minterval& newDomain, + OrderPoint o, + int first, + int last) + { + RMDBGENTER(4, RMDebug::module_indexmgr, "SDirIndexLogic", "binarySearch(" << newDomain << ", " << (int)o << ", " << first <<", " << last << ")"); + int retval = 0; + int middle = 0; + int compResult = 0; + + if (first > last) + retval = last; + else { + middle = (last + first) /2; + compResult = compare(newDomain, ixDS->getObjectDomain(middle), o , o); + if (compResult < 0) + retval = binarySearch(ixDS, newDomain, o, first, middle - 1); + else + if (compResult > 0) + retval = binarySearch(ixDS, newDomain, o, middle + 1, last); + else + retval = middle; + } + RMDBGEXIT(4, RMDebug::module_indexmgr, "SDirIndexLogic", "binarySearch(" << newDomain << ", " << (int)o << ", " << first <<", " << last << ") " << retval); + return retval; + } + + +int +SDirIndexLogic::binaryPointSearch( const IndexDS* ixDS, + const r_Point& pnt, + SDirIndexLogic::OrderPoint o, + int first, + int last) + { + RMDBGENTER(4, RMDebug::module_indexmgr, "SDirIndexLogic", "binaryPointSearch(" << pnt << ", " << (int)o << ", " << first << ", " << last << ")"); + int retval = 0; + int middle = 0; + int compResult = 0; + r_Minterval KeyObjectDomain; + r_Point pnt2; + + if (first > last) + retval = -1; + else + { + middle = (last + first) /2; + KeyObjectDomain = ixDS->getObjectDomain(middle); + if (KeyObjectDomain.covers(pnt) == 1) + retval = middle; + else + { + switch(o) + { + case Highest: + pnt2 = KeyObjectDomain.get_high(); + break; + case Lowest: + pnt2 = KeyObjectDomain.get_origin(); + break; + case None: + RMDBGENTER(4, RMDebug::module_indexmgr, "SDirIndexLogic", "binaryPointSearch(...) o is None"); + break; + } + + compResult = pnt.compare_with(pnt2); + RMDBGMIDDLE(4, RMDebug::module_indexmgr, "SDirIndexLogic", "binaryPointSearch compResult " << compResult); + + if (compResult > 0 && o == Highest) + retval = binaryPointSearch(ixDS, pnt, o, middle+1, last); + else + if (compResult < 0 && o == Lowest) + retval = binaryPointSearch(ixDS, pnt, o, first, middle -1); + else + { + compResult = binaryPointSearch(ixDS, pnt, o, middle +1, last); + if (compResult < 0) + retval = binaryPointSearch(ixDS, pnt, o, first, middle -1); + else + retval = compResult; + } + } + } + RMDBGEXIT(4, RMDebug::module_indexmgr, "SDirIndexLogic", "binaryPointSearch(" << pnt << ", " << (int)o << ", " << first << ", " << last << ") " << retval); + return retval; + } + + +int +SDirIndexLogic::binaryRegionSearch( const IndexDS* ixDS, + const r_Minterval& mint, + r_Area& area, + KeyObjectVector& intersectedObjects, + int first, + int last) + { + RMDBGENTER(4, RMDebug::module_indexmgr, "SDirIndexLogic", "binaryRegionSearch(" << mint << ", " << area << ", vector, " << first << ", " << last << ")"); + int retval = 0; + int middle = 0; + r_Minterval t; + int inc = 0; + int ix = 0; + r_Minterval objDomain; + int compResult = 0; + KeyObject newObj; + r_Minterval intersectedRegion; + // assumes order according to the lowest corner of the objects + if (first > last) + retval = -1; + else { + middle = (last + first) / 2; + t = ixDS->getObjectDomain(middle); + if (mint.get_high().compare_with(t.get_origin()) < 0) + {// R.hi < tile.lo no tiles after this one + retval = binaryRegionSearch(ixDS, mint, area, intersectedObjects, first, middle - 1); + } + else { + if (t.get_high().compare_with(mint.get_origin()) < 0) + { + retval = binaryRegionSearch(ixDS, mint, area, intersectedObjects, middle + 1, last); + if (area > 0) + retval = binaryRegionSearch(ixDS, mint, area, intersectedObjects, first, middle - 1); + } + else { + inc = 1; + ix = middle; + //starting to search forward, starting in the middle + while (true) + { + objDomain = ixDS->getObjectDomain(ix); + compResult = mint.get_high().compare_with(objDomain.get_origin()); + RMDBGMIDDLE(4, RMDebug::module_indexmgr, "SDirIndexLogic", "position " << ix << " last " << last << " incrementor " << inc << " object domain " << objDomain << " compare " << compResult); + // object intersects region + if (objDomain.intersects_with(mint)) + { + intersectedRegion = objDomain; + intersectedRegion.intersection_with(mint); + area = area - intersectedRegion.cell_count(); + newObj = ixDS->getObject(ix); + intersectedObjects.push_back(newObj); + RMDBGMIDDLE(4, RMDebug::module_indexmgr, "SDirIndexLogic", "added one entry, intersected region " << intersectedRegion << " area left " << area); + } + if (inc != -1 && (ix == last || compResult < 0)) + { + RMDBGMIDDLE(4, RMDebug::module_indexmgr, "SDirIndexLogic", "starting again at middle, but going backwards"); + ix = middle; + inc = -1; + } + if (ix == first && inc == -1)//not needed:||first == last + { + RMDBGMIDDLE(4, RMDebug::module_indexmgr, "SDirIndexLogic", "breaking loop, arrived at start"); + retval = ix; + break; + } + if (area <= 0)// || first == last || ix == first) + { + RMDBGMIDDLE(4, RMDebug::module_indexmgr, "SDirIndexLogic", "breaking loop, area is found"); + retval = ix; + break; + } + ix += inc; + } + } + } + } + + RMDBGEXIT(4, RMDebug::module_indexmgr, "SDirIndexLogic", "binaryRegionSearch(" << mint << ", " << area << ", vector, " << first << ", " << last << ") " << retval); + return retval; + } + + +int +SDirIndexLogic::compare(const r_Minterval& mint1, + const r_Minterval& mint2, + OrderPoint o1, + OrderPoint o2) + { + RMDBGENTER(4, RMDebug::module_indexmgr, "SDirIndexLogic", "compare(" << mint1 << ", " << mint2 << ", " << (int)o1 << ", " << (int)o2 << ")"); + r_Point point1,point2; + switch(o1) + { + case Highest: + point1 = mint1.get_high(); + break; + case Lowest: + point1 = mint1.get_origin(); + break; + case None: + RMDBGENTER(4, RMDebug::module_indexmgr, "SDirIndexLogic", "compare(...) o1 is None"); + break; + } + switch(o2) + { + case Highest: + point2 = mint2.get_high(); + break; + case Lowest: + point2 = mint2.get_origin(); + break; + case None: + RMDBGENTER(4, RMDebug::module_indexmgr, "SDirIndexLogic", "compare(...) o2 is None"); + break; + } + RMDBGEXIT(4, RMDebug::module_indexmgr, "SDirIndexLogic", "compare(" << mint1 << ", " << mint2 << ", " << (int)o1 << ", " << (int)o2 << ") " << point1.compare_with(point2)); + return point1.compare_with(point2); + } + +void +SDirIndexLogic::intersect(const IndexDS* ixDS, const r_Minterval& searchInter, KeyObjectVector& intersectedObjs, const StorageLayout& sl) + { + RMDBGENTER(4, RMDebug::module_indexmgr, "SDirIndexLogic", "intersect(" << searchInter << ")"); + r_Area area = 0; + int result = 0; + r_Minterval intersectArea(searchInter.dimension()); + r_Minterval currDom(ixDS->getCoveredDomain()); + // avoid exceptions from r_Minterval + if (!searchInter.intersects_with(currDom)) + { + RMDBGEXIT(4, RMDebug::module_indexmgr, "SDirIndexLogic", "intersect(" << searchInter << ") search interval does not intersect wit current domain " << currDom); + } + else { + // Optimization: no need to search the whole area. + // only the area which is intersected by the current domain. + intersectArea.intersection_of(searchInter, currDom); + area = intersectArea.cell_count(); + RMDBGMIDDLE(4, RMDebug::module_indexmgr, "SDirIndexLogic", "Area = " << area); + result = binaryRegionSearch(ixDS, intersectArea, area, intersectedObjs, 0, (int) ixDS->getSize() - 1); + RMDBGEXIT(4, RMDebug::module_indexmgr, "SDirIndexLogic", "intersect(" << searchInter << ") vectorsize: " << intersectedObjs.size()); + } + } + +void +SDirIndexLogic::intersectUnOpt(const IndexDS* ixDS, const r_Minterval& searchInter, KeyObjectVector& intersectedObjs) + { + RMDBGENTER(4, RMDebug::module_indexmgr, "SDirIndexLogic", "intersectUnOpt(" << searchInter << ")"); + for(int i=0; i< ixDS->getSize(); i++) + { + r_Minterval objInterval = ixDS->getObjectDomain(i); + if (searchInter.intersects_with(objInterval)) + { + KeyObject obj = ixDS->getObject(i); + intersectedObjs.push_back(obj); + } + } + RMDBGEXIT(4, RMDebug::module_indexmgr, "SDirIndexLogic", "intersectUnOpt(" << searchInter << ") vectorsize: " << intersectedObjs.size()); + } + +void +SDirIndexLogic::containPointQuery(const IndexDS* ixDS, const r_Point& searchPoint, KeyObject& result, const StorageLayout& sl) + { + RMDBGENTER(4, RMDebug::module_indexmgr, "SDirIndexLogic", "containPointQuery(" << searchPoint << ")"); + int ix = binaryPointSearch(ixDS, searchPoint, Lowest, 0, (int) ixDS->getSize() - 1); + RMDBGMIDDLE(4, RMDebug::module_indexmgr, "SDirIndexLogic", "result from binaryPointSearch ix " << ix); + + if (ix >= 0) + { + result = ixDS->getObject(ix); + RMDBGEXIT(4, RMDebug::module_indexmgr, "SDirIndexLogic", "containPointQuery(" << searchPoint << ") " << result); + } + else { + RMDBGEXIT(4, RMDebug::module_indexmgr, "SDirIndexLogic", "containPointQuery(" << searchPoint << ") nothing found "); + } + } + +void +SDirIndexLogic::getObjects(const IndexDS* ixDS, KeyObjectVector& objs, const StorageLayout& sl) + { + RMDBGONCE(4, RMDebug::module_indexmgr, "SDirIndexLogic", "getObjects()"); + ixDS->getObjects(objs); + } + +bool +SDirIndexLogic::removeObject(IndexDS* ixDS, const KeyObject& objToRemove, const StorageLayout& sl) + { + RMDBGONCE(4, RMDebug::module_indexmgr, "SDirIndexLogic", "removeObject(" << objToRemove << ")"); + return ixDS->removeObject(objToRemove); + } + |