Logo Search packages:      
Sourcecode: qt4-x11 version File versions

HitQueue.cpp

/*------------------------------------------------------------------------------
* Copyright (C) 2003-2006 Ben van Klinken and the CLucene Team
* 
* Distributable under the terms of either the Apache License (Version 2.0) or 
* the GNU Lesser General Public License, as specified in the COPYING file.
------------------------------------------------------------------------------*/
#include "CLucene/StdHeader.h"
#include "HitQueue.h"

CL_NS_DEF(search)

void HitQueue::upHeap(){
      size_t i = _size;
      ScoreDoc node = heap[i];                    // save bottom node (WAS object)
      int32_t j = ((uint32_t)i) >> 1;
      while (j > 0 && lessThan(node,heap[j])) {
            heap[i] = heap[j];                    // shift parents down
            i = j;
            j = ((uint32_t)j) >> 1;
      }
      heap[i] = node;                       // install saved node
}
void HitQueue::downHeap(){
      size_t i = 1;
      ScoreDoc node = heap[i];                    // save top node
      size_t j = i << 1;                          // find smaller child
      size_t k = j + 1;
      if (k <= _size && lessThan(heap[k], heap[j])) {
            j = k;
      }
      while (j <= _size && lessThan(heap[j],node)) {
            heap[i] = heap[j];                    // shift up child
            i = j;
            j = i << 1;
            k = j + 1;
            if (k <= _size && lessThan(heap[k], heap[j])) {
                  j = k;
            }
      }
      heap[i] = node;                       // install saved node
}

void HitQueue::adjustTop(){
      downHeap();
}
00046 size_t HitQueue::size(){
      return _size;
}

struct ScoreDoc& HitQueue::top(){
      if ( _size == 0 )
            _CLTHROWA(CL_ERR_IndexOutOfBounds, "Attempted to access empty hitqueue::top");
      return heap[1];
}

void HitQueue::put(struct ScoreDoc& element){
      if ( _size>=maxSize )
            _CLTHROWA(CL_ERR_IndexOutOfBounds,"add is out of bounds");

      _size++;    
      heap[_size] = element;        
      upHeap();
}

ScoreDoc HitQueue::pop(){
      if (_size > 0) {
            ScoreDoc result = heap[1];                  // save first value
            heap[1] = heap[_size];                // move last to first

            _size--;
            downHeap();                     // adjust heap
            return result;
      } else
            _CLTHROWA(CL_ERR_IndexOutOfBounds, "Attempted to access empty hitqueue::top");
}

00077 bool HitQueue::insert(struct ScoreDoc& element){
      if(_size < maxSize){
            put(element);
            return true;
      }else if(_size > 0 && !lessThan(element, heap[1])){
            heap[1] = element;
            adjustTop();
            return true;
      }else
            return false;
}

HitQueue::HitQueue(const int32_t maxSize){
      _size = 0;
    this->maxSize = maxSize;
      int32_t heapSize = maxSize + 1;
      heap = _CL_NEWARRAY(ScoreDoc,heapSize);
}
HitQueue::~HitQueue(){
      _CLDELETE_ARRAY(heap);
}

bool HitQueue::lessThan(struct ScoreDoc& hitA, struct ScoreDoc& hitB){
      if (hitA.score == hitB.score)
            return hitA.doc > hitB.doc; 
      else
            return hitA.score < hitB.score;
}


CL_NS_END

Generated by  Doxygen 1.6.0   Back to index