You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucy.apache.org by ma...@apache.org on 2009/09/24 15:05:16 UTC
svn commit: r818469 - in /lucene/lucy/trunk: core/Lucy/Test/Util/
core/Lucy/Util/ perl/lib/Lucy/ perl/lib/Lucy/Util/ perl/t/core/
Author: marvin
Date: Thu Sep 24 13:05:15 2009
New Revision: 818469
URL: http://svn.apache.org/viewvc?rev=818469&view=rev
Log:
Commit LUCY-54, adding PriorityQueue.
Added:
lucene/lucy/trunk/core/Lucy/Test/Util/TestPriorityQueue.bp (with props)
lucene/lucy/trunk/core/Lucy/Test/Util/TestPriorityQueue.c (with props)
lucene/lucy/trunk/core/Lucy/Util/PriorityQueue.bp (with props)
lucene/lucy/trunk/core/Lucy/Util/PriorityQueue.c (with props)
lucene/lucy/trunk/perl/lib/Lucy/Util/PriorityQueue.pm (with props)
lucene/lucy/trunk/perl/t/core/012-priority_queue.t (with props)
Modified:
lucene/lucy/trunk/perl/lib/Lucy/Test.pm
Added: lucene/lucy/trunk/core/Lucy/Test/Util/TestPriorityQueue.bp
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Test/Util/TestPriorityQueue.bp?rev=818469&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Test/Util/TestPriorityQueue.bp (added)
+++ lucene/lucy/trunk/core/Lucy/Test/Util/TestPriorityQueue.bp Thu Sep 24 13:05:15 2009
@@ -0,0 +1,32 @@
+parcel Lucy;
+
+class Lucy::Test::Util::NumPriorityQueue cnick NumPriQ
+ extends Lucy::Util::PriorityQueue {
+
+ inert incremented NumPriorityQueue*
+ new(u32_t max_size);
+
+ bool_t
+ Less_Than(NumPriorityQueue *self, Obj *a, Obj *b);
+}
+
+inert class Lucy::Test::Util::TestPriorityQueue cnick TestPriQ {
+ inert void
+ run_tests();
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
Propchange: lucene/lucy/trunk/core/Lucy/Test/Util/TestPriorityQueue.bp
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/lucy/trunk/core/Lucy/Test/Util/TestPriorityQueue.c
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Test/Util/TestPriorityQueue.c?rev=818469&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Test/Util/TestPriorityQueue.c (added)
+++ lucene/lucy/trunk/core/Lucy/Test/Util/TestPriorityQueue.c Thu Sep 24 13:05:15 2009
@@ -0,0 +1,168 @@
+#define C_LUCY_TESTPRIORITYQUEUE
+#include "Lucy/Util/ToolSet.h"
+
+#include "Lucy/Test.h"
+#include "Lucy/Test/Util/TestPriorityQueue.h"
+#include "Lucy/Util/PriorityQueue.h"
+
+NumPriorityQueue*
+NumPriQ_new(u32_t max_size)
+{
+ NumPriorityQueue *self
+ = (NumPriorityQueue*)VTable_Make_Obj(NUMPRIORITYQUEUE);
+ return (NumPriorityQueue*)PriQ_init((PriorityQueue*)self, max_size);
+}
+
+bool_t
+NumPriQ_less_than(NumPriorityQueue *self, Obj *a, Obj *b)
+{
+ Float64 *num_a = (Float64*)a;
+ Float64 *num_b = (Float64*)b;
+ UNUSED_VAR(self);
+ return Float64_Get_Value(num_a) < Float64_Get_Value(num_b) ? true : false;
+}
+
+static void
+S_insert_num(NumPriorityQueue *pq, i32_t value)
+{
+ NumPriQ_Insert(pq, (Obj*)Float64_new((double)value));
+}
+
+static i32_t
+S_pop_num(NumPriorityQueue *pq)
+{
+ Float64 *num = (Float64*)PriQ_Pop(pq);
+ i32_t retval;
+ if (!num) { THROW(ERR, "Queue is empty"); }
+ retval = (i32_t)Float64_Get_Value(num);
+ DECREF(num);
+ return retval;
+}
+
+static void
+test_Peek_and_Pop_All(TestBatch *batch)
+{
+ NumPriorityQueue *pq = NumPriQ_new(5);
+
+ S_insert_num(pq, 3);
+ S_insert_num(pq, 1);
+ S_insert_num(pq, 2);
+ S_insert_num(pq, 20);
+ S_insert_num(pq, 10);
+ ASSERT_INT_EQ(batch, (long)Float64_Get_Value(PriQ_Peek(pq)), 1,
+ "peek at the least item in the queue" );
+ {
+ VArray *got = PriQ_Pop_All(pq);
+ ASSERT_INT_EQ(batch, (long)Float64_Get_Value(VA_Fetch(got, 0)), 20,
+ "pop_all");
+ ASSERT_INT_EQ(batch, (long)Float64_Get_Value(VA_Fetch(got, 1)), 10,
+ "pop_all");
+ ASSERT_INT_EQ(batch, (long)Float64_Get_Value(VA_Fetch(got, 2)), 3,
+ "pop_all");
+ ASSERT_INT_EQ(batch, (long)Float64_Get_Value(VA_Fetch(got, 3)), 2,
+ "pop_all");
+ ASSERT_INT_EQ(batch, (long)Float64_Get_Value(VA_Fetch(got, 4)), 1,
+ "pop_all");
+ DECREF(got);
+ }
+
+ DECREF(pq);
+}
+
+static void
+test_Insert_and_Pop(TestBatch *batch)
+{
+ NumPriorityQueue *pq = NumPriQ_new(5);
+
+ S_insert_num(pq, 3);
+ S_insert_num(pq, 1);
+ S_insert_num(pq, 2);
+ S_insert_num(pq, 20);
+ S_insert_num(pq, 10);
+
+ ASSERT_INT_EQ(batch, S_pop_num(pq), 1, "Pop");
+ ASSERT_INT_EQ(batch, S_pop_num(pq), 2, "Pop");
+ ASSERT_INT_EQ(batch, S_pop_num(pq), 3, "Pop");
+ ASSERT_INT_EQ(batch, S_pop_num(pq), 10, "Pop");
+
+ S_insert_num(pq, 7);
+ ASSERT_INT_EQ(batch, S_pop_num(pq), 7,
+ "Insert after Pop still sorts correctly");
+
+ DECREF(pq);
+}
+
+static void
+test_discard(TestBatch *batch)
+{
+ i32_t i;
+ NumPriorityQueue *pq = NumPriQ_new(5);
+
+ for (i = 1; i <= 10; i++) { S_insert_num(pq, i); }
+ S_insert_num(pq, -3);
+ for (i = 1590; i <= 1600; i++) { S_insert_num(pq, i); }
+ S_insert_num(pq, 5);
+
+ ASSERT_INT_EQ(batch, S_pop_num(pq), 1596, "discard waste");
+ ASSERT_INT_EQ(batch, S_pop_num(pq), 1597, "discard waste");
+ ASSERT_INT_EQ(batch, S_pop_num(pq), 1598, "discard waste");
+ ASSERT_INT_EQ(batch, S_pop_num(pq), 1599, "discard waste");
+ ASSERT_INT_EQ(batch, S_pop_num(pq), 1600, "discard waste");
+
+ DECREF(pq);
+}
+
+static void
+test_random_insertion(TestBatch *batch)
+{
+ int i;
+ int shuffled[64];
+ NumPriorityQueue *pq = NumPriQ_new(64);
+
+ for (i = 0; i < 64; i++) { shuffled[i] = i; }
+ for (i = 0; i < 64; i++) {
+ int shuffle_pos = rand() % 64;
+ int temp = shuffled[shuffle_pos];
+ shuffled[shuffle_pos] = shuffled[i];
+ shuffled[i] = temp;
+ }
+ for (i = 0; i < 64; i++) { S_insert_num(pq, shuffled[i]); }
+ for (i = 0; i < 64; i++) {
+ if (S_pop_num(pq) != i) { break; }
+ }
+ ASSERT_INT_EQ(batch, i, 64, "random insertion");
+
+ DECREF(pq);
+}
+
+void
+TestPriQ_run_tests()
+{
+ TestBatch *batch = Test_new_batch("TestPriQ", 17, NULL);
+
+ PLAN(batch);
+
+ test_Peek_and_Pop_All(batch);
+ test_Insert_and_Pop(batch);
+ test_discard(batch);
+ test_random_insertion(batch);
+
+ batch->destroy(batch);
+}
+
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
Propchange: lucene/lucy/trunk/core/Lucy/Test/Util/TestPriorityQueue.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/lucy/trunk/core/Lucy/Util/PriorityQueue.bp
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Util/PriorityQueue.bp?rev=818469&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Util/PriorityQueue.bp (added)
+++ lucene/lucy/trunk/core/Lucy/Util/PriorityQueue.bp Thu Sep 24 13:05:15 2009
@@ -0,0 +1,85 @@
+parcel Lucy;
+
+/**
+ * Heap sort / priority queue.
+ *
+ * PriorityQueue implements a textbook heap sort / priority queue algorithm.
+ *
+ * Subclasses must define the abstract method Less_Than.
+ */
+
+class Lucy::Util::PriorityQueue cnick PriQ
+ extends Lucy::Object::Obj {
+ u32_t size;
+ u32_t max_size;
+
+ /* This particular priority queue variant leaves slot 0 open in order to
+ * keep the relationship between node rank and index clear in the up_heap
+ * and down_heap routines.
+ */
+ Obj **heap;
+
+ /**
+ * @param max_size Max elements the queue can hold.
+ */
+ inert PriorityQueue*
+ init(PriorityQueue *self, u32_t max_size);
+
+ /** Compare queue elements.
+ */
+ abstract bool_t
+ Less_Than(PriorityQueue *self, Obj *a, Obj *b);
+
+ /** Possibly insert an element. Add to the Queue if either...
+ * a) the queue isn't full, or
+ * b) the element belongs in the queue and should displace another.
+ */
+ bool_t
+ Insert(PriorityQueue *self, decremented Obj *element);
+
+ /** Equivalent to Insert(), except for the return value. If the Queue has
+ * room, the element is inserted and Jostle() returns NULL. If not, then
+ * the item which falls out of the bottom of the Queue is returned.
+ */
+ incremented Obj*
+ Jostle(PriorityQueue *self, decremented Obj *element);
+
+ /** Pop the *least* item off of the priority queue.
+ */
+ incremented Obj*
+ Pop(PriorityQueue *self);
+
+ /** Empty out the PriorityQueue into a sorted array.
+ */
+ incremented VArray*
+ Pop_All(PriorityQueue *self);
+
+ /** Return the least item in the queue, but don't remove it.
+ */
+ Obj*
+ Peek(PriorityQueue *self);
+
+ /** Accessor for "size" member.
+ */
+ u32_t
+ Get_Size(PriorityQueue *self);
+
+ public void
+ Destroy(PriorityQueue *self);
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
Propchange: lucene/lucy/trunk/core/Lucy/Util/PriorityQueue.bp
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/lucy/trunk/core/Lucy/Util/PriorityQueue.c
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Util/PriorityQueue.c?rev=818469&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Util/PriorityQueue.c (added)
+++ lucene/lucy/trunk/core/Lucy/Util/PriorityQueue.c Thu Sep 24 13:05:15 2009
@@ -0,0 +1,239 @@
+#define C_LUCY_PRIORITYQUEUE
+#include "Lucy/Util/ToolSet.h"
+
+#include <string.h>
+
+#include "Lucy/Util/PriorityQueue.h"
+
+/* Add an element to the heap. Throw an error if too many elements
+ * are added.
+ */
+static void
+S_put(PriorityQueue *self, Obj *element);
+
+/* Free all the elements in the heap and set size to 0.
+ */
+static void
+S_clear(PriorityQueue *self);
+
+/* Heap adjuster.
+ */
+static void
+S_up_heap(PriorityQueue *self);
+
+/* Heap adjuster. Should be called when the item at the top changes.
+ */
+static void
+S_down_heap(PriorityQueue *self);
+
+PriorityQueue*
+PriQ_init(PriorityQueue *self, u32_t max_size)
+{
+ u32_t heap_size = max_size + 1;
+
+ /* Init. */
+ self->size = 0;
+
+ /* Assign. */
+ self->max_size = max_size;
+
+ /* Allocate space for the heap, assign all slots to NULL. */
+ self->heap = (Obj**)CALLOCATE(heap_size, sizeof(Obj*));
+
+ ABSTRACT_CLASS_CHECK(self, PRIORITYQUEUE);
+ return self;
+}
+
+void
+PriQ_destroy(PriorityQueue *self)
+{
+ if (self->heap) {
+ S_clear(self);
+ FREEMEM(self->heap);
+ }
+ SUPER_DESTROY(self, PRIORITYQUEUE);
+}
+
+u32_t
+PriQ_get_size(PriorityQueue *self) { return self->size; }
+
+static void
+S_put(PriorityQueue *self, Obj *element)
+{
+ /* Increment size. */
+ if (self->size >= self->max_size) {
+ THROW(ERR, "PriorityQueue exceeded max_size: %u32 %u32", self->size,
+ self->max_size);
+ }
+ self->size++;
+
+ /* Put element into heap. */
+ self->heap[ self->size ] = element;
+
+ /* Adjust heap. */
+ S_up_heap(self);
+}
+
+bool_t
+PriQ_insert(PriorityQueue *self, Obj *element)
+{
+ Obj *least = PriQ_Jostle(self, element);
+ DECREF(least);
+ if (element == least) return false;
+ else return true;
+}
+
+Obj*
+PriQ_jostle(PriorityQueue *self, Obj *element)
+{
+ /* Absorb element if there's a vacancy. */
+ if (self->size < self->max_size) {
+ S_put(self, element);
+ return NULL;
+ }
+ /* Otherwise, compete for the slot. */
+ else if (self->size == 0) {
+ return element;
+ }
+ else {
+ Obj *scratch = PriQ_Peek(self);
+ if ( !PriQ_Less_Than(self, element, scratch) ) {
+ /* If the new element belongs in the queue, replace something. */
+ Obj *retval = self->heap[1];
+ self->heap[1] = element;
+ S_down_heap(self);
+ return retval;
+ }
+ else {
+ return element;
+ }
+ }
+}
+
+Obj*
+PriQ_pop(PriorityQueue *self)
+{
+ if (self->size > 0) {
+ /* Save the first value. */
+ Obj *result = self->heap[1];
+
+ /* Move last to first and adjust heap. */
+ self->heap[1] = self->heap[ self->size ];
+ self->heap[ self->size ] = NULL;
+ self->size--;
+ S_down_heap(self);
+
+ /* Return the value, leaving a refcount for the caller. */
+ return result;
+ }
+ else {
+ return NULL;
+ }
+}
+
+VArray*
+PriQ_pop_all(PriorityQueue *self)
+{
+ VArray *retval = VA_new(self->size);
+
+ /* Map the queue nodes onto the array in reverse order. */
+ if (self->size) {
+ u32_t i;
+ for (i = self->size; i--; ) {
+ Obj *const elem = PriQ_Pop(self);
+ VA_Store(retval, i, elem);
+ }
+ }
+
+ return retval;
+}
+
+Obj*
+PriQ_peek(PriorityQueue *self)
+{
+ if (self->size > 0) {
+ return self->heap[1];
+ }
+ else {
+ return NULL;
+ }
+}
+
+static void
+S_clear(PriorityQueue *self)
+{
+ u32_t i;
+ Obj **elem_ptr = (self->heap + 1);
+
+ /* Node 0 is held empty, to make the algo clearer. */
+ for (i = 1; i <= self->size; i++) {
+ DECREF(*elem_ptr);
+ *elem_ptr = NULL;
+ elem_ptr++;
+ }
+ self->size = 0;
+}
+
+static void
+S_up_heap(PriorityQueue *self)
+{
+ u32_t i = self->size;
+ u32_t j = i >> 1;
+ Obj *const node = self->heap[i]; /* save bottom node */
+
+ while ( j > 0
+ && PriQ_Less_Than(self, node, self->heap[j])
+ ) {
+ self->heap[i] = self->heap[j];
+ i = j;
+ j = j >> 1;
+ }
+ self->heap[i] = node;
+}
+
+static void
+S_down_heap(PriorityQueue *self)
+{
+ u32_t i = 1;
+ u32_t j = i << 1;
+ u32_t k = j + 1;
+ Obj *node = self->heap[i]; /* save top node */
+
+ /* Find smaller child. */
+ if ( k <= self->size
+ && PriQ_Less_Than(self, self->heap[k], self->heap[j])
+ ) {
+ j = k;
+ }
+
+ while ( j <= self->size
+ && PriQ_Less_Than(self, self->heap[j], node)
+ ) {
+ self->heap[i] = self->heap[j];
+ i = j;
+ j = i << 1;
+ k = j + 1;
+ if ( k <= self->size
+ && PriQ_Less_Than(self, self->heap[k], self->heap[j])
+ ) {
+ j = k;
+ }
+ }
+ self->heap[i] = node;
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
Propchange: lucene/lucy/trunk/core/Lucy/Util/PriorityQueue.c
------------------------------------------------------------------------------
svn:eol-style = native
Modified: lucene/lucy/trunk/perl/lib/Lucy/Test.pm
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/lib/Lucy/Test.pm?rev=818469&r1=818468&r2=818469&view=diff
==============================================================================
--- lucene/lucy/trunk/perl/lib/Lucy/Test.pm (original)
+++ lucene/lucy/trunk/perl/lib/Lucy/Test.pm Thu Sep 24 13:05:15 2009
@@ -37,6 +37,9 @@
else if (strEQ(package, "TestNumberUtils")) {
lucy_TestNumUtil_run_tests();
}
+ else if (strEQ(package, "TestPriorityQueue")) {
+ lucy_TestPriQ_run_tests();
+ }
else if (strEQ(package, "TestStringHelper")) {
lucy_TestStrHelp_run_tests();
}
Added: lucene/lucy/trunk/perl/lib/Lucy/Util/PriorityQueue.pm
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/lib/Lucy/Util/PriorityQueue.pm?rev=818469&view=auto
==============================================================================
--- lucene/lucy/trunk/perl/lib/Lucy/Util/PriorityQueue.pm (added)
+++ lucene/lucy/trunk/perl/lib/Lucy/Util/PriorityQueue.pm Thu Sep 24 13:05:15 2009
@@ -0,0 +1,42 @@
+use Lucy;
+
+1;
+
+__END__
+
+__BINDING__
+
+Boilerplater::Binding::Perl::Class->register(
+ parcel => "Lucy",
+ class_name => "Lucy::Util::PriorityQueue",
+ bind_methods => [
+ qw(
+ Less_Than
+ Insert
+ Pop
+ Pop_All
+ Peek
+ Get_Size
+ )
+ ],
+ bind_constructors => ["new"],
+);
+
+__COPYRIGHT__
+
+ /**
+ * Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ * implied. See the License for the specific language governing
+ * permissions and limitations under the License.
+ */
+
Propchange: lucene/lucy/trunk/perl/lib/Lucy/Util/PriorityQueue.pm
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/lucy/trunk/perl/t/core/012-priority_queue.t
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/t/core/012-priority_queue.t?rev=818469&view=auto
==============================================================================
--- lucene/lucy/trunk/perl/t/core/012-priority_queue.t (added)
+++ lucene/lucy/trunk/perl/t/core/012-priority_queue.t Thu Sep 24 13:05:15 2009
@@ -0,0 +1,6 @@
+use strict;
+use warnings;
+
+use Lucy::Test;
+Lucy::Test::run_tests("TestPriorityQueue");
+
Propchange: lucene/lucy/trunk/perl/t/core/012-priority_queue.t
------------------------------------------------------------------------------
svn:eol-style = native