23 template <
typename SearchPo
intType,
typename DataSetType>
24 void copySearchPoints(BaseSearchSpace<SearchPointType, DataSetType>* dest,
25 const BaseSearchSpace<SearchPointType, DataSetType>* src,
26 int start,
int end,
int destStart) {
27 dest->setDataSet(src->dataSet());
28 int howmany = end - start;
30 SearchPointType* destp = &((*dest)[destStart]);
31 const SearchPointType* srcp = &((*src)[start]);
32 memcpy(destp, srcp, howmany *
sizeof(SearchPointType));
37 template <
typename SearchPo
intType,
typename DataSetType>
38 void copySearchPoints(BaseSearchSpace<SearchPointType, DataSetType>* dest,
39 const BaseSearchSpace<SearchPointType, DataSetType>* src,
41 dest->resize(end - start);
42 copySearchPoints(dest, src, start, end, 0);
45 template <
typename SearchPo
intType,
typename DataSetType>
46 void copySearchPoints(BaseSearchSpace<SearchPointType, DataSetType>* dest,
47 const BaseSearchSpace<SearchPointType, DataSetType>* src) {
48 copySearchPoints(dest, src, 0, src->size());
52 template <
typename SearchPo
intType,
typename DataSetType>
53 BaseSearchSpace<SearchPointType, DataSetType>* BaseSearchSpacePool<SearchPointType, DataSetType>::ValueIndex::getSubSpaceInto(SearchSpaceType* result,
int start,
int end)
const {
58 result->setDataSet(sspace->dataSet());
59 result->resize(end - start);
62 foreach (key, sorted.keys()) {
63 stepsSet << key.first << key.second;
65 QList<int> steps = QList<int>::fromSet(stepsSet);
68 Q_ASSERT(steps.first() == 0 && steps.last() == sspace->size());
73 for (i=0; i<steps.size(); i++) {
74 if (end < steps[i])
break;
79 copySearchPoints(result, sspace, start, end);
80 result->pointerSort();
83 SearchSpaceType* presorted = sorted[qMakePair(0, steps[i])];
85 copySearchPoints(&tmp, sspace, steps[i], end);
87 typename Vector<SearchPointType>::iterator
final = std::set_union(presorted->begin(), presorted->end(),
88 tmp.begin(), tmp.end(),
89 result->begin(), pointerOrderCompare<SearchPointType>);
90 Q_ASSERT(
final == result->end());
94 else if (end == sspace->size()) {
95 for (i=steps.size()-1; i>=0; i--) {
96 if (start > steps[i])
break;
100 if (i >= (steps.size()-1)) {
101 copySearchPoints(result, sspace, start, end);
102 result->pointerSort();
105 SearchSpaceType* presorted = sorted[qMakePair(steps[i], end)];
107 copySearchPoints(&tmp, sspace, start, steps[i]);
109 typename Vector<SearchPointType>::iterator
final = std::set_union(presorted->begin(), presorted->end(),
110 tmp.begin(), tmp.end(),
111 result->begin(), pointerOrderCompare<SearchPointType>);
112 Q_ASSERT(
final == result->end());
124 for (is=steps.size()-1; is>=0; is--)
if (steps[is] <= start)
break; is = qMax(is, 0);
125 for (ie=0; ie<steps.size(); ie++)
if (steps[ie] >= end)
break; ie = qMin(ie, steps.size()-1);
127 copySearchPoints(result, sorted[qMakePair(steps[is], steps[ie])]);
131 copySearchPoints(&tmp, sspace, steps[is], start);
133 result->setDifference(&tmp);
136 copySearchPoints(&tmp, sspace, end, steps[ie]);
138 result->setDifference(&tmp);
146 template <
typename SearchPo
intType,
typename DataSetType>
147 BaseSearchSpacePool<SearchPointType, DataSetType>::BaseSearchSpacePool(
const DataSetType* dataset) : _dataset(dataset), _originalSpace(0) {
151 template <
typename SearchPo
intType,
typename DataSetType>
152 BaseSearchSpacePool<SearchPointType, DataSetType>::~BaseSearchSpacePool() {
185 template <
typename SearchPo
intType,
typename DataSetType>
188 QStringList valueIndices = _valueIndex.keys();
189 QStringList labelIndices = _labelIndex.keys();
192 delete _originalSpace;
193 _originalSpace = SearchSpaceType::createFromDataSet(_dataset);
196 foreach (
const QString& name, valueIndices)
indexOn(name);
197 foreach (
const QString& name, labelIndices)
indexOn(name);
201 template <
typename SearchPo
intType,
typename DataSetType>
202 void BaseSearchSpacePool<SearchPointType, DataSetType>::clearIndices() {
203 delete _originalSpace;
206 foreach (
const QString& desc, _valueIndex.keys()) _valueIndex.value(desc).clear();
209 foreach (
const QString& desc, _labelIndex.keys()) _labelIndex.value(desc).clear();
214 template <
typename SearchPo
intType,
typename DataSetType>
216 SearchSpaceType* result = BaseSearchSpacePool<SearchPointType, DataSetType>::acquire();
217 copySearchPoints(result, _originalSpace);
223 template <
typename SearchPo
intType,
typename DataSetType>
225 PointLayout layout = _dataset->referenceDataSet()->layout();
226 QString fullName = layout.fullName(descriptorName);
241 throw GaiaException(
"SearchSpacePool::indexOn: internal error, invalid indexing type");
246 template <
typename SearchPo
intType>
247 const Point* refPoint(
const SearchPointType& p,
const DataSet* refDataSet);
250 inline const Point* refPoint(
const SearchPoint& p,
const DataSet* refDataSet) {
251 Q_UNUSED(refDataSet);
256 inline const Point* refPoint(
const FrozenSearchPoint& p,
const DataSet* refDataSet) {
257 return refDataSet->at(p.idx);
260 template <
typename SearchPo
intType,
typename DataSetType>
261 const Point* refPoint(
const SearchPointType& p,
const BaseSearchSpace<SearchPointType, DataSetType>& sspace);
264 inline const Point* refPoint(
const SearchPoint& p,
const SearchSpace& sspace) {
270 inline const Point* refPoint(
const FrozenSearchPoint& p,
const FrozenSearchSpace& sspace) {
271 return sspace.dataSet()->referenceDataSet()->at(p.idx);
274 template <
typename DataSetType, DescriptorType DescType>
277 SortOn(
const DataSetType* dataset,
const QString& descriptorName) {
278 _refDataSet = dataset->referenceDataSet();
280 Region region = _refDataSet->layout().descriptorLocation(descriptorName);
281 if (region.lengthType() != FixedLength) {
282 throw GaiaException(
"SearchSpacePool: you can only index on fixed-length descriptors");
285 if (region.size(DescType, FixedLength) != 1) {
286 throw GaiaException(
"SearchSpacePool: you can only index on descriptors of size 1");
289 _index = region.index();
292 template <
typename SearchPo
intType>
293 inline bool operator()(
const SearchPointType& p1,
const SearchPointType& p2);
296 template <
typename SearchPo
intType>
297 inline const Point* ref(
const SearchPointType& p) {
return refPoint(p, _refDataSet); }
298 const DataSet* _refDataSet;
303 template <>
template <>
305 return ref(p1)->frealData()[_index] < ref(p2)->frealData()[_index];
308 template <>
template <>
310 return ref(p1)->fstringData()[_index] < ref(p2)->fstringData()[_index];
313 template <>
template <>
317 return ref(p1)->fenumData()[_index] < ref(p2)->fenumData()[_index];
320 template <>
template <>
322 return ref(p1)->frealData()[_index] < ref(p2)->frealData()[_index];
325 template <>
template <>
327 return ref(p1)->fstringData()[_index] < ref(p2)->fstringData()[_index];
330 template <>
template <>
334 return ref(p1)->fenumData()[_index] < ref(p2)->fenumData()[_index];
338 template <
typename SearchPo
intType,
typename DataSetType>
343 ValueIndex completeIndex;
344 completeIndex.sspace = index;
348 static const int factor = 10;
349 const int chunkSize = (index->size() / factor) + 1;
353 SearchSpaceType* full =
new SearchSpaceType();
354 copySearchPoints(full, index);
356 completeIndex.sorted.insert(qMakePair(0, full->size()), full);
359 for (
int i=0; i<factor-1; i++) {
362 SearchSpaceType* half =
new SearchSpaceType();
363 copySearchPoints(half, index, 0, split);
365 completeIndex.sorted.insert(qMakePair(0, split), half);
367 half =
new SearchSpaceType();
368 copySearchPoints(half, index, split, index->size());
370 completeIndex.sorted.insert(qMakePair(split, (
int)index->size()), half);
378 for (
int end=2*chunkSize; end < (int)index->size(); end += chunkSize) {
379 for (
int start=chunkSize; start < end; start += chunkSize) {
380 SearchSpaceType* segment =
new SearchSpaceType();
381 copySearchPoints(segment, index, start, end);
382 segment->pointerSort();
383 completeIndex.sorted.insert(qMakePair(start, end), segment);
387 _valueIndex.insert(descriptorName, completeIndex);
390 template <
typename SearchPo
intType,
typename DataSetType>
395 LabelIndex completeIndex;
396 completeIndex.sspace = index;
400 const DataSet* rds = _dataset->referenceDataSet();
401 int idx = rds->layout().descriptorLocation(descriptorName).index();
402 typename Vector<SearchPointType>::iterator start = index->begin(), end = index->begin();
403 while (start != index->end()) {
404 const QString& value = refPoint(*start, rds)->fstringData()[idx];
405 while ((end != index->end()) && (refPoint(*end, rds)->fstringData()[idx] == value)) {
408 gaia2::sort(start, end, pointerOrderCompare<SearchPointType>);
409 completeIndex.ranges.insert(value, qMakePair((
int)(start - index->begin()), (
int)(end - index->begin())));
413 _labelIndex.insert(descriptorName, completeIndex);
416 template <
typename SearchPo
intType,
typename DataSetType>
421 LabelIndex completeIndex;
422 completeIndex.sspace = index;
426 const DataSet* rds = _dataset->referenceDataSet();
427 int idx = rds->layout().descriptorLocation(descriptorName).index();
428 typename Vector<SearchPointType>::iterator start = index->begin(), end = index->begin();
429 while (start != index->end()) {
430 Enum value = refPoint(*start, rds)->fenumData()[idx];
431 while ((end != index->end()) && (refPoint(*end, rds)->fenumData()[idx] == value)) {
434 gaia2::sort(start, end, pointerOrderCompare<SearchPointType>);
436 completeIndex.ranges.insert(svalue, qMakePair((
int)(start - index->begin()), (
int)(end - index->begin())));
440 _labelIndex.insert(descriptorName, completeIndex);
444 template <
typename SearchSpaceType>
445 inline int binarySearch(
const SearchSpaceType& sspace,
int idx, Real value,
int start,
int end) {
446 while (start < end) {
447 int middle = (start + end) / 2;
448 if (refPoint(sspace[middle], sspace)->frealData()[idx] < value) {
458 template <
typename SearchPo
intType,
typename DataSetType>
460 return _valueIndex.contains(descriptorName) || _labelIndex.contains(descriptorName);
464 template <
typename SearchPo
intType,
typename DataSetType>
465 int BaseSearchSpacePool<SearchPointType, DataSetType>::getCuttingPos(
const SearchSpaceType& sspace,
int idx,
int type,
466 Real value,
int start,
int end)
const {
469 int cuttingPos =
binarySearch(sspace, idx, value, start, end);
473 while (cuttingPos > start && refPoint(sspace[cuttingPos-1], sspace)->frealData()[idx] >= value) cuttingPos--;
477 while (cuttingPos < end && refPoint(sspace[cuttingPos], sspace)->frealData()[idx] <= value) cuttingPos++;
478 while (cuttingPos > start && refPoint(sspace[cuttingPos-1], sspace)->frealData()[idx] > value) cuttingPos--;
483 while (cuttingPos < end && refPoint(sspace[cuttingPos], sspace)->frealData()[idx] <= value) cuttingPos++;
487 while (cuttingPos > start && refPoint(sspace[cuttingPos-1], sspace)->frealData()[idx] >= value) cuttingPos--;
489 while (cuttingPos < end && refPoint(sspace[cuttingPos], sspace)->frealData()[idx] < value) cuttingPos++;
496 throw GaiaException(
"SearchSpacePool::getCuttingPos undefined for '==' and '!='");
502 template <
typename SearchPo
intType,
typename DataSetType>
503 BaseSearchSpace<SearchPointType, DataSetType>* BaseSearchSpacePool<SearchPointType, DataSetType>::getSubSpace(
const parser::Predicate* pred)
const {
506 const parser::PredValueComparison* comp =
dynamic_cast<const parser::PredValueComparison*
>(pred);
510 if (! ((dynamic_cast<const parser::ValueVariable*>(comp->_lhs) && dynamic_cast<const parser::ValueConstant*>(comp->_rhs)) ||
511 (dynamic_cast<const parser::ValueConstant*>(comp->_lhs) && dynamic_cast<const parser::ValueVariable*>(comp->_rhs)))) {
515 const parser::ValueVariable* var = 0;
516 const parser::ValueConstant* value = 0;
517 if (dynamic_cast<const parser::ValueVariable*>(comp->_lhs)) {
518 var =
dynamic_cast<const parser::ValueVariable*
>(comp->_lhs);
519 value =
dynamic_cast<const parser::ValueConstant*
>(comp->_rhs);
522 var =
dynamic_cast<const parser::ValueVariable*
>(comp->_rhs);
523 value =
dynamic_cast<const parser::ValueConstant*
>(comp->_lhs);
526 Q_ASSERT(var && value);
532 QString fullName = _dataset->referenceDataSet()->layout().fullName(var->name());
535 SearchSpaceType& fullSpace = *_valueIndex[fullName].sspace;
536 int idx = _dataset->referenceDataSet()->layout().descriptorLocation(fullName).index();
537 int start = 0, end = fullSpace.size();
539 switch (comp->_type) {
542 end = getCuttingPos(fullSpace, idx, comp->_type, (Real)value->value(), start, end);
547 start = getCuttingPos(fullSpace, idx, comp->_type, (Real)value->value(), start, end);
552 throw GaiaException(
"SearchSpacePool: cannot optimize with a != operator atm. Please fill a feature request.");
556 SearchSpaceType* result = BaseSearchSpacePool<SearchPointType, DataSetType>::acquire();
557 result->setFilter(alwaysTrue,
true);
559 _valueIndex[fullName].getSubSpaceInto(result, start, end);
564 const parser::PredValueRange* rangePred =
dynamic_cast<const parser::PredValueRange*
>(pred);
566 if (!dynamic_cast<parser::ValueVariable*>(rangePred->_var))
return 0;
568 QString fullName = _dataset->referenceDataSet()->layout().fullName(rangePred->_var->toString());
571 SearchSpaceType& fullSpace = *_valueIndex[fullName].sspace;
572 int idx = _dataset->referenceDataSet()->layout().descriptorLocation(fullName).index();
573 int start = 0, end = fullSpace.size();
576 start = getCuttingPos(fullSpace, idx, GTE, rangePred->_min, start, end);
577 end = getCuttingPos(fullSpace, idx, LTE, rangePred->_max, start, end);
580 SearchSpaceType* result = BaseSearchSpacePool<SearchPointType, DataSetType>::acquire();
581 result->setFilter(alwaysTrue,
true);
583 _valueIndex[fullName].getSubSpaceInto(result, start, end);
588 const parser::PredLabelComparison* labelPred =
dynamic_cast<const parser::PredLabelComparison*
>(pred);
592 if (! ((dynamic_cast<const parser::LabelVariable*>(labelPred->_lhs) && dynamic_cast<const parser::LabelConstant*>(labelPred->_rhs)) ||
593 (dynamic_cast<const parser::LabelConstant*>(labelPred->_lhs) && dynamic_cast<const parser::LabelVariable*>(labelPred->_rhs)))) {
597 const parser::LabelVariable* var = 0;
598 const parser::LabelConstant* value = 0;
599 if (dynamic_cast<const parser::LabelVariable*>(labelPred->_lhs)) {
600 var =
dynamic_cast<const parser::LabelVariable*
>(labelPred->_lhs);
601 value =
dynamic_cast<const parser::LabelConstant*
>(labelPred->_rhs);
604 var =
dynamic_cast<const parser::LabelVariable*
>(labelPred->_rhs);
605 value =
dynamic_cast<const parser::LabelConstant*
>(labelPred->_lhs);
608 Q_ASSERT(var && value);
614 QString fullName = _dataset->referenceDataSet()->layout().fullName(var->name());
617 const LabelIndex& index = _labelIndex.value(fullName);
619 SearchSpaceType* result = BaseSearchSpacePool<SearchPointType, DataSetType>::acquire();
620 result->setFilter(alwaysTrue,
true);
622 switch (labelPred->_type) {
624 if (!index.ranges.contains(value->value()))
return result;
625 QPair<int, int> rng = index.ranges.value(value->value());
626 copySearchPoints(result, index.sspace, rng.first, rng.second);
632 if (!index.ranges.contains(value->value())) {
633 BaseSearchSpacePool<SearchPointType, DataSetType>::release(result);
638 result->reserve(index.sspace->size());
639 for (GaiaMap<QString, QPair<int, int> >::const_iterator it = index.ranges.constBegin();
640 it != index.ranges.constEnd(); ++it) {
641 if (value->value() != it.key()) {
642 const QPair<int, int>& rng = it.value();
643 int previous = result->size();
644 result->resize(previous + (rng.second-rng.first));
645 copySearchPoints(result, index.sspace, rng.first, rng.second, previous);
649 result->pointerSort();
662 template <
typename SearchPo
intType,
typename DataSetType>
663 BaseSearchSpace<SearchPointType, DataSetType>* BaseSearchSpacePool<SearchPointType, DataSetType>::acquire() {
664 if (!_sspoolMutex) _sspoolMutex =
new QMutex();
665 QMutexLocker lock(_sspoolMutex);
667 if (_sspool.isEmpty()) {
668 G_DEBUG(GSearchSpace,
"Creating new SearchSpace because pool is empty");
669 return new SearchSpaceType();
672 G_DEBUG(GSearchSpace,
"Pool has " << _sspool.size() <<
" ready SearchSpaces, getting one from there");
673 SearchSpaceType* result = _sspool.takeLast();
676 result->invalidate();
681 template <
typename SearchPo
intType,
typename DataSetType>
682 void BaseSearchSpacePool<SearchPointType, DataSetType>::release(SearchSpaceType* sspace) {
685 if (!_sspoolMutex) _sspoolMutex =
new QMutex();
686 QMutexLocker lock(_sspoolMutex);
692 if (sspace->unfilteredSize() > 50000) {
693 sspace->cleanSearchSpace();
695 G_DEBUG(GSearchSpace,
"Returning SearchSpace to pool, now has " << _sspool.size() <<
" available ones");
698 G_DEBUG(GSearchSpace,
"SearchSpace is too small to return to pool, deleting it (pool has " << _sspool.size() <<
" available ones)");
704 static const int MAX_SIZE = 10;
706 while (_sspool.size() > MAX_SIZE) {
707 delete _sspool.takeLast();
711 template <
typename SearchPo
intType,
typename DataSetType>
714 QMutexLocker lock(_sspoolMutex);
715 while (!_sspool.isEmpty())
delete _sspool.takeLast();
722 template <
typename SearchPo
intType,
typename DataSetType>
723 SearchSpaceWrapper<SearchPointType, DataSetType>::~SearchSpaceWrapper() {
724 BaseSearchSpacePool<SearchPointType, DataSetType>::release(sspace);
SearchSpaceType * getAllPoints() const
Returns a SearchSpace containing all points.
Definition: searchspacepool.h:216
void indexOn(const QString &descriptorName)
Indexes on the given descriptorName.
Definition: searchspacepool.h:225
static Filter * parse(const QString &str)
Parses a given string and returns the newly created Filter object.
Definition: filter.cpp:181
int binarySearch(const Container< T > &v, T value)
Iterative function for binary search (more efficient than recursive one).
Definition: gaiamath.h:270
bool hasIndex(const QString &descriptorName) const
Returns whether an index exists for the given descriptorName.
Definition: searchspacepool.h:460
const PointLayout & layout() const
Returns the current layout of the point.
Definition: point.h:195
static void clear()
Clear the cache of preallocated SearchSpaces.
Definition: searchspacepool.h:713
void indexOnValue(const QString &descriptorName)
assumes descriptorName is the fully qualified name
Definition: searchspacepool.h:340
Definition: searchspacepool_impl.h:275
StringDescriptor enumToString(const QString &name, const EnumDescriptor &value) const
Converts the given Enum descriptor into its String representation.
Definition: pointlayout.cpp:190
DescriptorType
The possible types of descriptors accepted.
Definition: region.h:36
void recreate()
Recreates the SearchSpacePool and all the indices (needed for instance when the dataset it is pointin...
Definition: searchspacepool.h:187
void indexOnLabel(const QString &descriptorName)
assumes descriptorName is the fully qualified name
Definition: searchspacepool.h:392
void indexOnEnum(const QString &descriptorName)
assumes descriptorName is the fully qualified name
Definition: searchspacepool.h:418