source: Sophya/trunk/SophyaLib/NTools/simplesort.h@ 3728

// This may look like C code, but it is really -*- C++ -*-
//
// $Id: simplesort.h,v 1.5 2001-01-12 15:47:31 ansari Exp $
//

// Un tri tout bete sur des reels. On donne un tableau de reels,
// et on recupere un index trie, et on peut faire des recherches.

#ifndef SIMPLESORT_SEEN
#define SIMPLESORT_SEEN

#include "peida.h"

// Pour la variante avec la STL, a preferer
#include <functional>
#include <algorithm>

namespace SOPHYA {  

class SimpleSort  {
public:
  SimpleSort(int nElts);
  // On donne au constructeur le nombre d'elements a trier.
  virtual ~SimpleSort();

  void      Set(int i, float value);
  // Donne la valeur de l'element i

  void      Sort();
  // Trie. A faire avant d'appeler la suite.

  float    Value(int i) const {return index[i].value;}
  // La valeur numero i une fois trie.

  int       Num(int i) const   {return index[i].num;}
  // L'ancien indice qui est le numero i une fois trie

  int       Lookup(float val);
  // L'indice - trie - le plus proche de val.
  
#if ARG_FUNC_CPP_C
private:
#endif
  typedef struct {
    int num;
    float value;
  } TRIPAIRE;

  static int Compare(const void* tp1, const void* tp2);
    
  int numElts;
  TRIPAIRE* index;
};

// ************ INLINES

inline
void SimpleSort::Set(int i, float value)   // Check range ?
{
  index[i].num = i;
  index[i].value = value;
}


// ----- Une variante avec la STL, a preferer


// On a un vecteur de donnees et un vecteur d'index, on trie les index
// en comparant les donnees.
// L'objet-fonction de type dataCompare doit comparer deux objets de type data.

// Comparateur qui agit sur l'index en comparant les donnees avec dataCompare
template <class data, class index, class dataCompare>
struct IndexComp : public std::binary_function<index,index,bool>
{
  IndexComp(data* begin_data, index* begin_index, dataCompare comp)
    : bdata(begin_data), bindex(begin_index), datacomp(comp) {}

  bool operator()(index const& i1, index const& i2)
    { return datacomp(*(bdata + (&i1 - bindex)), *(bdata + (&i2 - bindex)));}
    
  data* bdata;
  index* bindex;
  dataCompare datacomp;
};

// Fonction de tri qui trie un index en comparant des donnees avec dataComp
template <class data, class index, class dataCompare>
void TriIndex(data* begin_data, data* end_data, index* begin_index, dataCompare comp)
{
  sort(begin_index, begin_index + (end_data-begin_data),
        IndexComp<data, index, dataCompare>(begin_data, begin_index, comp));
}  

} // namespace SOPHYA

#endif // SIMPLESORT_SEEN