// ----------------------------------------------------------------------------
//
// Copyright (C) Columbia University, 1994. All Rights Reserved.
// Sameer A. Nene, Shree K. Nayar, Hiroshi Murase
//
// See file LICENSE for details of software license agreement.
//
// ----------------------------------------------------------------------------
//
// binarysearch.h
//
// Author:               Sameer Nene
// Date:                 05/26/94
// Version:              1.0
// Modification History:
//   06/25/94: BinarySearch is now derived directly from Persistent rather than
//             via a SearchScheme. This was necessary because SearchScheme is
//             no longer derived from a Persistent.
//   06/26/94: Change in Interface necessary due to change in interface of
//             DataSet. Internal data storage no longer as VectAry, but a
//             DataSet.
//
// Bugs:
//
// Classes:
//   BinarySearch
//
// Notes:
//   This header includes declarations for the class BinarySearch. This method
//   is a modification of the conventional binary search by extension to
//   multiple dimensions. It gives a huge improvement in performance over
//   FullSearch and PartialSearch because of log2(n) time complexity, but uses
//   a threshold. It is crucial that the threshold be set in the range of the
//   estimated distance between a given point and a point closest to it. If the
//   threshold is too high then the performance degrades to a FullSearch. If
//   too less, it might "miss" the closest point. Note also that it uses much
//   more memory (1.5 times) than Full or Partial Search. BinarySearch is
//   derived from SearchScheme and hence obeys that protocol.
//   setSearchParameters() is used to set the threshold. The constructor
//   BinarySearch::BinarySearch() is used to construct or initialize the object
//   for(with) the supplied data. Once it is initialized, it can be immediately
//   used to do a search, or can be stored to disk for later use. A mapping
//   between the table index of the supplied data and the corresponding
//   physical quantity has also to be supplied. This ensures that the vector
//   returned by search() has the correct reverse mapping.
//   
// ----------------------------------------------------------------------------

#ifndef BINARYSEARCH_INCLUDED
#define BINARYSEARCH_INCLUDED

#ifndef REGISTRY_INCLUDED
#include "registry.h"
#endif

class ErrorScope;

class Interpolation;

#ifndef SEARCHSCHEME_INLCUDED
#include "searchscheme.h"
#endif

#ifndef VECTOR_INCLUDED
#include "vector.h"
#endif

#ifndef DATASET_INCLUDED
#include "dataset.h"
#endif

#ifndef PERSISTENTSEARCHSCHEME_INCLUDED
#include "persscheme.h"
#endif

#include <stdio.h>

class BinarySearch : public PersistentSearchScheme {

  // Private members
  
  static void *d_protocol;
  static int d_pos;
  static char *d_name_p;
  static double *d_sa_p;
  static Registrar d_registrar;
  static Vector d_pv;

  static Persistent* createFunc();
  // returns a pointer to a newly created BinarySearch

  double d_thresh;
  Vector d_n, d_rangemin, d_rangemax;
  VectAry d_data;
  int **d_bmaps_p, **d_fmaps_p;

  static int compare(const void*, const void*);
  static void sample(const Interpolation &ip, int level, int d, const Vector &f);

  int bsearchL(int col, double d) const;
  int bsearchR(int col, double d) const;

  // BinarySearch cannot be copied or assigned
  
  BinarySearch(const BinarySearch&);
  BinarySearch& operator=(const BinarySearch&);

  // Protected Members
  
protected:
  
  virtual int hasProtocol(void *protocol) const;
  // returns 1 if this object is of type(protocol) protocol OR is derived
  // from an object of type(protocol) protocol
  
  // Public members
  
public:
  
  // Construct and destroy

  BinarySearch();

  BinarySearch(const DataSet &ds, const Vector &rangemin,
	       const Vector &rangemax);
  // Construct a binary search data structure from points in ds. rangemin &
  // rangemax give min. & max. values of output parameters for every dimension.

  BinarySearch(const Interpolation &ip, const Vector &f, const Vector &n,
	       const Vector &rangemin, const Vector &rangemax);
  // Construct a binary search data structure from points in ip.
  // Dimensionality of ip is in n. rangemin & rangemax give min. & max. values
  // of output parameters for every dimension. f supplies the number of
  // samples per dimension.
  
  ~BinarySearch();

  // Accessors
  
  static BinarySearch* safeCast(Persistent*);
  // Converts Persistent pointer to a BinarySearch pointer if the object
  // pointed to by Persistent is in fact a BinarySearch
  
  Vector search(const Vector &v) const;
  // searches for v and returns result vector
  
  ErrorScope::Error put(FILE*) const;
  // puts BinarySearch into file
  
  const char *name() const;
  // returns name of class

  const VectAry& getData() const;
  // returns a reference to the underlying data
  
  // Modifiers

  void setSearchParameters(const Vector &v);
  // sets threshold for the box size. v should have only one element
  
  ErrorScope::Error get(FILE*);
  // gets BinarySearch from disk
  
};

#endif


