searchspace.h

/* 
 * Copyright (C) 2006-2013  Music Technology Group - Universitat Pompeu Fabra
 *
 * This file is part of Gaia
 * 
 * Gaia is free software: you can redistribute it and/or modify it under 
 * the terms of the GNU Affero General Public License as published by the Free 
 * Software Foundation (FSF), either version 3 of the License, or (at your 
 * option) any later version.
 * 
 * This program 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 Affero GNU General Public License
 * version 3 along with this program.  If not, see http://www.gnu.org/licenses/
 */

#ifndef GAIA_SEARCHSPACE_H
#define GAIA_SEARCHSPACE_H

#include <vector>
#include "dataset.h"
#include "frozendataset.h"
#include "parser/filter.h"


namespace gaia2 {


typedef QPair<QString, Real> Result;
typedef QList<Result> SearchResults;

yaml::Node toYaml(const SearchResults& results);

// fwd-declaration
class DistanceFunction;
class FrozenDistance;

#define Vector std::vector


class SearchPoint {
public:
  float dist;
  const Point* ptr;
  const Point* ref;

  // should never use the default constructor, it is defined because std::vector::resize() needs it
  SearchPoint() {}
  SearchPoint(const Point* pptr, const Point* rref) : ptr(pptr), ref(rref) {}
  bool operator<(const SearchPoint& x) const { return dist < x.dist; }
};


class FrozenSearchPoint {
public:
  float dist;
  int idx;

  // should never use the default constructor, it is defined because std::vector::resize() needs it
  FrozenSearchPoint() {}
  FrozenSearchPoint(int iidx) : idx(iidx) {}
  bool operator<(const FrozenSearchPoint& x) const { return dist < x.dist; }
};


template <typename SearchPointType, typename DataSetType>
class BaseSearchSpace : public Vector<SearchPointType> {

 public:
  BaseSearchSpace(const Filter* filter = 0, bool ownsFilter = false);

  BaseSearchSpace(const BaseSearchSpace<SearchPointType, DataSetType>& other);

  ~BaseSearchSpace();

  void copyPointsFrom(const BaseSearchSpace<SearchPointType, DataSetType>& other);

  int size() const;

  int unfilteredSize() const;

  void clear();

  SearchResults get(int n, int offset = 0);

  void limit(int n);

  void thresholdLimit(float maxDist);

  const Filter* filter() { return _filter; }
  void setFilter(const Filter* filter, bool ownsFilter = false);

  void invalidate() { _sortedUpTo = _filteredUpTo = 0; }

  void filterAll();

  void pointerSort();

  void addPoints(const DataSetType* dataset, const QList<QString>& ids);

  void removePoints(const QList<QString>& ids);

  void setIntersection(const BaseSearchSpace<SearchPointType, DataSetType>* other);

  void setUnion(const BaseSearchSpace<SearchPointType, DataSetType>* other);

  void setDifference(const BaseSearchSpace<SearchPointType, DataSetType>* other);

  QString pointName(const SearchPointType& p) const;
  const Point* refPoint(const SearchPointType& p) const;

  bool validPoint(const SearchPointType& p) const {
    return _filter->isTrue(refPoint(p));
  }

  static BaseSearchSpace<SearchPointType, DataSetType>* createFromDataSet(const DataSetType* dataset);

  static BaseSearchSpace<SearchPointType, DataSetType>* createFromPoints(const DataSetType* dataset,
                                                                         const QList<QString>& pointNames);

  template <typename PointType, typename DistanceType>
  void computeDistance(const PointType& query, const DistanceType* dist);

  //void computeDistance(const FrozenPoint& query, const FrozenDistance* dist);


  void setDataSet(const DataSetType* dataset) { _dataset = dataset; }
  const DataSetType* dataSet() const { return _dataset; }

  void filterAndSort(int n = 1000);

  void cleanSearchSpace();

 protected:
  const DataSetType* _dataset;
  const Filter* _filter;
  bool _ownsFilter;
  int _sortedUpTo, _filteredUpTo;

    // FIXME: use the typenames from the search space, not any ones like here
  template <typename SearchPointType2, typename DataSetType2>
  friend class BaseQueryOptimizer;

  int validUpTo() const { return qMin(_sortedUpTo, _filteredUpTo); }

  void sortAll();

};



typedef BaseSearchSpace<SearchPoint, DataSet> SearchSpace;

template <>
inline const Point* SearchSpace::refPoint(const SearchPoint& p) const {
  return p.ref;
}

template <>
inline QString SearchSpace::pointName(const SearchPoint& p) const {
  return p.ptr->name();
}

typedef BaseSearchSpace<FrozenSearchPoint, FrozenDataSet> FrozenSearchSpace;

template <>
inline const Point* FrozenSearchSpace::refPoint(const FrozenSearchPoint& p) const {
  return _dataset->referenceDataSet()->at(p.idx);
}

template <>
inline QString FrozenSearchSpace::pointName(const FrozenSearchPoint& p) const {
  return _dataset->pointName(p.idx);
}



template <typename SearchPointType, typename DataSetType>
class SearchSpaceWrapper : public QSharedData {
 public:
  BaseSearchSpace<SearchPointType, DataSetType>* sspace;

  SearchSpaceWrapper(BaseSearchSpace<SearchPointType, DataSetType>* s) : sspace(s) {}
  ~SearchSpaceWrapper(); // defined after SearchSpacePool is defined, at the end of SearchSpacePool_impl.h
};


template <typename SearchPointType, typename DataSetType>
class BaseResultSet {

 public:
  BaseResultSet();
  BaseResultSet(BaseSearchSpace<SearchPointType, DataSetType>* sspace);

  SearchResults get(int n, int offset = 0);

  int size() const { return _d->sspace->size(); }

  BaseResultSet limit(int n) { _d->sspace->limit(n); return *this; }

  BaseResultSet thresholdLimit(float maxDist) { _d->sspace->thresholdLimit(maxDist); return *this; }

#ifndef SWIG
  void addPoints(const DataSetType* dataset, const QList<QString>& ids);
  void removePoints(const QList<QString>& ids);
#endif

  BaseSearchSpace<SearchPointType, DataSetType>* searchSpace() { return _d->sspace; }

 protected:
  QExplicitlySharedDataPointer<SearchSpaceWrapper<SearchPointType, DataSetType> > _d;
};



// as SearchSpace* is a template, we have to import its definition here
#include "searchspace_impl.h"



typedef BaseResultSet<SearchPoint, DataSet> ResultSet;

// Useful typedefs, because sometimes we might want to create such a beast from
// scratch, in which case the name ResultSet is a bit misleading
typedef ResultSet InputSpace;

} // namespace gaia2


#endif // GAIA_SEARCHSPACE_H