view release on metacpan or  search on metacpan

lib/KinoSearch1/Util/PriorityQueue.pm  view on Meta::CPAN

package KinoSearch1::Util::PriorityQueue;
use strict;
use warnings;
use KinoSearch1::Util::ToolSet;
use base qw( KinoSearch1::Util::CClass );

BEGIN {
    __PACKAGE__->init_instance_vars(
        # constructor args
        max_size => undef,
    );
}

1;

__END__

__XS__

MODULE =  KinoSearch1    PACKAGE = KinoSearch1::Util::PriorityQueue

void
new(either_sv, ...)
    SV *either_sv;
PREINIT:
    const char    *class;
    HV            *args_hash;
    U32            max_size;
    PriorityQueue *pq;
PPCODE:
    /* determine the class */
    class = sv_isobject(either_sv) 
        ? sv_reftype(either_sv, 0) 
        : SvPV_nolen(either_sv);
        
    /* process hash-style params */
    Kino1_Verify_build_args_hash(args_hash, 
        "KinoSearch1::Util::PriorityQueue::instance_vars", 1);
    max_size = (U32)SvUV( Kino1_Verify_extract_arg(args_hash, "max_size", 8) );

    /* build object */
    pq    = Kino1_PriQ_new(max_size);
    ST(0) = sv_newmortal();
    sv_setref_pv(ST(0), class, (void*)pq);
    XSRETURN(1);

=for comment

Add an element to the Queue if either...
a) the queue isn't full, or
b) the element belongs in the queue and should displace another

=cut

void
insert(pq, element)
    PriorityQueue *pq;
    SV             *element;
PPCODE:
    Kino1_PriQ_insert(pq, element);


=for comment

Pop the *least* item off of the priority queue.

=cut

SV*
pop(pq)
    PriorityQueue *pq;
CODE:
    RETVAL = Kino1_PriQ_pop(pq);
    if (RETVAL == Nullsv) {
        RETVAL = &PL_sv_undef;
    }
    else {
        RETVAL = newSVsv(RETVAL);
    }
OUTPUT: RETVAL


=for comment

Return the least item in the queue, but don't remove it.

=cut

SV*
peek(pq)
    PriorityQueue *pq;
CODE:
    RETVAL = Kino1_PriQ_peek(pq);
    if (RETVAL == Nullsv) {
        RETVAL = &PL_sv_undef;
    }
    else {
        RETVAL = newSVsv(RETVAL);
    }
OUTPUT: RETVAL



=for comment

Empty the queue into an array, with the highest priority item at index 0. 

=cut

void
pop_all(pq)
    PriorityQueue *pq;
PREINIT:
    AV* out_av;
PPCODE:
    out_av = Kino1_PriQ_pop_all(pq);
    XPUSHs( sv_2mortal(newRV_noinc( (SV*)out_av )) );


SV*
_set_or_get(pq, ...)
    PriorityQueue *pq;
ALIAS:
    get_size      = 2
    get_max_size  = 4
CODE:
{
    KINO_START_SET_OR_GET_SWITCH

    case 2:  RETVAL = newSVuv(pq->size);
             break;

    case 4:  RETVAL = newSVuv(pq->max_size);
             break;

    KINO_END_SET_OR_GET_SWITCH
}
OUTPUT: RETVAL


void
DESTROY(pq)
    PriorityQueue *pq;
PPCODE:
    Kino1_PriQ_destroy(pq);

__H__

#ifndef H_KINOSEARCH_UTIL_PRIORITY_QUEUE
#define H_KINOSEARCH_UTIL_PRIORITY_QUEUE 1

#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"
#include "KinoSearch1UtilCarp.h"
#include "KinoSearch1UtilMemManager.h"

typedef struct priorityqueuec {
    U32          size;
    U32          max_size;
    SV         **heap;
    bool       (*less_than)(SV*, SV*);
} PriorityQueue;

PriorityQueue* Kino1_PriQ_new (U32 max_size);
bool Kino1_PriQ_insert(PriorityQueue*, SV*);
SV*  Kino1_PriQ_pop(PriorityQueue*);
SV*  Kino1_PriQ_peek(PriorityQueue*);
AV*  Kino1_PriQ_pop_all(PriorityQueue*);
void Kino1_PriQ_destroy(PriorityQueue*);
bool Kino1_PriQ_default_less_than( SV*, SV* );
void Kino1_PriQ_dump(PriorityQueue*);

#endif /* include guard */


__C__

#include "KinoSearch1UtilPriorityQueue.h"

static void Kino1_PriQ_put(PriorityQueue*, SV*);
static SV*  Kino1_PriQ_top(PriorityQueue*);
static void Kino1_PriQ_adjust_top(PriorityQueue*);
static void Kino1_PriQ_clear(PriorityQueue*);
static void Kino1_PriQ_up_heap(PriorityQueue*);
static void Kino1_PriQ_down_heap(PriorityQueue*);

PriorityQueue*
Kino1_PriQ_new (U32 max_size) {
    PriorityQueue *pq;
    U32 i, heap_size;

    Kino1_New(0, pq, 1, PriorityQueue);

    pq->size = 0;
    pq->max_size = max_size;
    pq->less_than = Kino1_PriQ_default_less_than;

    /* allocate space for the heap, assign all slots to Nullsv */
    heap_size = max_size + 1;
    Kino1_New(0, pq->heap, heap_size, SV*);
    for (i = 0; i < heap_size; i++) {
        pq->heap[i] = Nullsv;
    }