/**************************************************************************
 *
 * 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.
 *
 **************************************************************************/

#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,
	       mg_u_long heapSize,
	       const Compare &comp) {
  mg_u_long holeIndex = heapSize-1;
  mg_u_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,
		     mg_u_long holeIndex,
		     mg_u_long heapSize,
		     const Compare &comp) {
  mg_u_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,
	      mg_u_long heapSize,
	      const Compare &comp) {
  swap (*(parallelHeap), *(parallelHeap+heapSize-1));
  swap (*(docNumHeap), *(docNumHeap+heapSize-1));
  AdjustHeap (docNumHeap, parallelHeap, (mg_u_long)0, heapSize-1, comp);
}

template <class RandomAccessIterator, class Compare>
void MakeHeap (DocNumArray::iterator docNumHeap,
	       RandomAccessIterator parallelHeap,
	       mg_u_long size,
	       const Compare &comp) {
  if (size < 2) return;
  
  mg_u_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,
	       mg_u_long size,
	       const Compare &comp) {
  if (size < 2) return;

  mg_u_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,
		    mg_u_long heapSize,
		    DocNumArray::iterator docNumAdd,
		    RandomAccessIterator parallelAdd,
		    mg_u_long addSize,
		    const Compare &comp) {
  mg_u_long i;
  for (i=0; i<addSize; ++i) {
    if (comp(*(parallelAdd+i), *(parallelHeap))) {
      swap (*(docNumHeap), *(docNumAdd+i));
      swap (*(parallelHeap), *(parallelAdd+i));
      AdjustHeap (docNumHeap, parallelHeap, (mg_u_long)0, heapSize, comp);
    }
  }
}

#endif