source: trunk/gsdl/src/mgpp/text/QueryResultsSort.h@ 861

/**************************************************************************
 *
 * QueryResultsSort.h -- Functions to sort query results and parallel data
 * Copyright (C) 1999  Rodger McNab
 *
 * This program 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 2 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 GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * $Id: QueryResultsSort.h 861 2000-01-18 23:24:19Z rjmcnab $
 *
 **************************************************************************/

#ifndef QUERYRESULTSSORT_H
#define QUERYRESULTSSORT_H

#include "Terms.h"


struct LTRank {
  bool operator()(const float &f1, const float &f2) const
    { return (f1 < f2); }
};

struct GTRank {
  bool operator()(const float &f1, const float &f2) const
    { return (f1 > f2); }
};



// assumes the rank vector is the same size as the document
// number vector. assumes the value to be pushed is in
// docNumHeap + heapSize - 1 and rankHeap + heapSize - 1
// topIndex can be set
template <class RandomAccessIterator, class Compare>
void PushHeap (DocNumArray::iterator docNumHeap,
           RandomAccessIterator parallelHeap,
           unsigned long heapSize,
           const Compare &comp) {
  unsigned long holeIndex = heapSize-1;
  unsigned long parent = (holeIndex - 1) / 2;
  while (holeIndex > 0 && comp (*(parallelHeap+parent),
                *(parallelHeap+holeIndex))) {
    swap (*(parallelHeap+holeIndex), *(parallelHeap+parent));
    swap (*(docNumHeap+holeIndex), *(docNumHeap+parent));
    holeIndex = parent;
    parent = (holeIndex - 1) / 2;
  }
}

// AdjustHeap is used to add a element to a heap after one
// element in the heap has been replaced with a new one
template <class RandomAccessIterator, class Compare>
void AdjustHeap (DocNumArray::iterator docNumHeap,
             RandomAccessIterator parallelHeap,
             unsigned long holeIndex,
             unsigned long heapSize,
             const Compare &comp) {
  unsigned long secondChild = 2 * holeIndex + 2;
  while (secondChild < heapSize) {
    if (comp(*(parallelHeap + secondChild),
         *(parallelHeap + (secondChild - 1))))
      secondChild--;
    swap (*(parallelHeap+holeIndex), *(parallelHeap+secondChild));
    swap (*(docNumHeap+holeIndex), *(docNumHeap+secondChild));
    holeIndex = secondChild;
    secondChild = 2 * secondChild + 2;
  }
  if (secondChild == heapSize) {
    swap (*(parallelHeap+holeIndex), *(parallelHeap+(secondChild-1)));
    swap (*(docNumHeap+holeIndex), *(docNumHeap+(secondChild-1)));
    holeIndex = secondChild - 1;
  }
  PushHeap (docNumHeap, parallelHeap, holeIndex+1, comp);
}

template <class RandomAccessIterator, class Compare>
void PopHeap (DocNumArray::iterator docNumHeap,
          RandomAccessIterator parallelHeap,
          unsigned long heapSize,
          const Compare &comp) {
  swap (*(parallelHeap), *(parallelHeap+heapSize-1));
  swap (*(docNumHeap), *(docNumHeap+heapSize-1));
  AdjustHeap (docNumHeap, parallelHeap, 0, heapSize-1, comp);
}

template <class RandomAccessIterator, class Compare>
void MakeHeap (DocNumArray::iterator docNumHeap,
           RandomAccessIterator parallelHeap,
           unsigned long size,
           const Compare &comp) {
  if (size < 2) return;
  
  unsigned long i = 0;
  for (i=1; i<=size; i++)
    PushHeap (docNumHeap, parallelHeap, i, comp);
}

 
template <class RandomAccessIterator, class Compare>
void SortHeap (DocNumArray::iterator docNumHeap,
           RandomAccessIterator parallelHeap,
           unsigned long size,
           const Compare &comp) {
  if (size < 2) return;

  unsigned long i;
  for (i=size; i>1; i--)
    PopHeap (docNumHeap, parallelHeap, i, comp);
}

// uses the heap to get the top "size" elements
template <class RandomAccessIterator, class Compare>
void SelectAddHeap (DocNumArray::iterator docNumHeap,
            RandomAccessIterator parallelHeap,
            unsigned long heapSize,
            DocNumArray::iterator docNumAdd,
            RandomAccessIterator parallelAdd,
            unsigned long addSize,
            const Compare &comp) {
  unsigned long i;
  for (i=0; i<addSize; i++) {
    if (comp(*(parallelAdd+i), *(parallelHeap))) {
      swap (*(docNumHeap), *(docNumAdd+i));
      swap (*(parallelHeap), *(parallelAdd+i));
      AdjustHeap (docNumHeap, parallelHeap, 0, heapSize, comp);
    }
  }
}

#endif