1 files changed, 107 insertions, 0 deletions
diff --git a/3rdparty/clucene/src/CLucene/search/HitQueue.cpp b/3rdparty/clucene/src/CLucene/search/HitQueue.cpp
new file mode 100644
index 000000000..c9aecc6b4
--- /dev/null
+++ b/3rdparty/clucene/src/CLucene/search/HitQueue.cpp
@@ -0,0 +1,107 @@
+/*------------------------------------------------------------------------------
+* 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();
+}
+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");
+}
+
+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