### Home Classes Methods

### In Files

- ext/r_utils.c

### Parent

Object

### Methods

- ::new
- #<<
- #adjust
- #capacity
- #clear
- #clone
- #insert
- #pop
- #size
- #top

### Files

- MIT-LICENSE
- README
- TODO
- TUTORIAL

### Class/Module Index

Quicksearch

- Ferret
- Ferret::Analysis
- Ferret::Analysis::Analyzer
- Ferret::Analysis::AsciiLetterAnalyzer
- Ferret::Analysis::AsciiLetterTokenizer
- Ferret::Analysis::AsciiLowerCaseFilter
- Ferret::Analysis::AsciiStandardAnalyzer
- Ferret::Analysis::AsciiStandardTokenizer
- Ferret::Analysis::AsciiWhiteSpaceAnalyzer
- Ferret::Analysis::AsciiWhiteSpaceTokenizer
- Ferret::Analysis::HyphenFilter
- Ferret::Analysis::LetterAnalyzer
- Ferret::Analysis::LetterTokenizer
- Ferret::Analysis::LowerCaseFilter
- Ferret::Analysis::MappingFilter
- Ferret::Analysis::PerFieldAnalyzer
- Ferret::Analysis::RegExpAnalyzer
- Ferret::Analysis::RegExpTokenizer
- Ferret::Analysis::StandardAnalyzer
- Ferret::Analysis::StandardTokenizer
- Ferret::Analysis::StemFilter
- Ferret::Analysis::StopFilter
- Ferret::Analysis::Token
- Ferret::Analysis::TokenStream
- Ferret::Analysis::WhiteSpaceAnalyzer
- Ferret::Analysis::WhiteSpaceTokenizer
- Ferret::BlankSlate
- Ferret::BoostMixin
- Ferret::Browser
- Ferret::Browser::Controller
- Ferret::Browser::Delegator
- Ferret::Browser::DocumentController
- Ferret::Browser::ErrorController
- Ferret::Browser::HelpController
- Ferret::Browser::HomeController
- Ferret::Browser::TermController
- Ferret::Browser::TermVectorController
- Ferret::Browser::ViewHelper
- Ferret::Document
- Ferret::Field
- Ferret::FieldSymbol
- Ferret::FieldSymbolMethods
- Ferret::FileNotFoundError
- Ferret::Index
- Ferret::Index::FieldInfo
- Ferret::Index::FieldInfos
- Ferret::Index::Index
- Ferret::Index::IndexReader
- Ferret::Index::IndexWriter
- Ferret::Index::LazyDoc
- Ferret::Index::LazyDoc::LazyDocData
- Ferret::Index::TermDocEnum
- Ferret::Index::TermEnum
- Ferret::Index::TermVector
- Ferret::Index::TermVector::TVOffsets
- Ferret::Index::TermVector::TVTerm
- Ferret::ParseError
- Ferret::QueryParser
- Ferret::QueryParser::QueryParseException
- Ferret::Search
- Ferret::Search::BooleanQuery
- Ferret::Search::BooleanQuery::BooleanClause
- Ferret::Search::ConstantScoreQuery
- Ferret::Search::Explanation
- Ferret::Search::Filter
- Ferret::Search::FilteredQuery
- Ferret::Search::FuzzyQuery
- Ferret::Search::Hit
- Ferret::Search::MatchAllQuery
- Ferret::Search::MultiSearcher
- Ferret::Search::MultiTermQuery
- Ferret::Search::PhraseQuery
- Ferret::Search::PrefixQuery
- Ferret::Search::Query
- Ferret::Search::QueryFilter
- Ferret::Search::RangeFilter
- Ferret::Search::RangeQuery
- Ferret::Search::Searcher
- Ferret::Search::Sort
- Ferret::Search::SortField
- Ferret::Search::Spans
- Ferret::Search::Spans::SpanFirstQuery
- Ferret::Search::Spans::SpanMultiTermQuery
- Ferret::Search::Spans::SpanNearQuery
- Ferret::Search::Spans::SpanNotQuery
- Ferret::Search::Spans::SpanOrQuery
- Ferret::Search::Spans::SpanPrefixQuery
- Ferret::Search::Spans::SpanTermQuery
- Ferret::Search::TermQuery
- Ferret::Search::TopDocs
- Ferret::Search::TypedRangeFilter
- Ferret::Search::TypedRangeQuery
- Ferret::Search::WildcardQuery
- Ferret::StateError
- Ferret::Store
- Ferret::Store::Directory
- Ferret::Store::FSDirectory
- Ferret::Store::Lock
- Ferret::Store::Lock::LockError
- Ferret::Store::RAMDirectory
- Ferret::Utils
- Ferret::Utils::BitVector
- Ferret::Utils::MultiMapper
- Ferret::Utils::PriorityQueue
- WEBrick
- WEBrick::FerretBrowserHandler
- Date
- DateTime
- FileUtils
- Float
- Integer
- String
- Symbol
- Time

No matching classes.

# Ferret::Utils::PriorityQueue

## Summary

A PriorityQueue is a very useful data structure and one that needs a fast implementation. Hence this priority queue is implemented in C. It is pretty easy to use; basically you just insert elements into the queue and pop them off.

The elements are sorted with the lowest valued elements on the top of the heap, ie the first to be popped off. Elements are ordered using the less_than '<' method. To change the order of the queue you can either reimplement the '<' method pass a block when you initialize the queue.

You can also set the capacity of the PriorityQueue. Once you hit the capacity, the lowest values elements are automatically popped of the top of the queue as more elements are added.

## Example

Here is a toy example that sorts strings by their length and has a capacity of 5;

    q = PriorityQueue.new(5) {|a, b| a.size < b.size}
    q << "x"
    q << "xxxxx"
    q << "xxx"
    q << "xxxx"
    q << "xxxxxx"
    q << "xx" # hit capacity so "x" will be popped off the top

    puts q.size     #=> 5
    word = q.pop    #=> "xx"
    q.top << "yyyy" # "xxxyyyy" will still be at the top of the queue
    q.adjust        # move "xxxyyyy" to its correct location in queue
    word = q.pop    #=> "xxxx"
    word = q.pop    #=> "xxxxx"
    word = q.pop    #=> "xxxxxx"
    word = q.pop    #=> "xxxyyyy"
    word = q.pop    #=> nil

### Public Class Methods

new(capacity = 32) → new_pq click to toggle source
new({:capacity => 32,
:less_than_proc => lambda{|a, b| a < b}) → new_pq
new({:capacity => 32}) {|a, b| a < b} → new_pq

Returns a new empty priority queue object with an optional capacity. Once the capacity is filled, the lowest valued elements will be automatically popped off the top of the queue as more elements are inserted into the queue.

    static VALUE
    frb_pq_init(int argc, VALUE *argv, VALUE self)
    {
        if (argc >= 1) {
            PriQ *pq;
            VALUE options = argv[0];
            VALUE param;
            int capa = PQ_START_CAPA;
            GET_PQ(pq, self);
            switch (TYPE(options)) {
                case T_FIXNUM:
                    capa = FIX2INT(options);
                    break;
                case T_HASH:
                    if (!NIL_P(param = rb_hash_aref(options,
                                                    ID2SYM(id_capacity)))) {
                        capa = FIX2INT(param);
                    }
                    if (!NIL_P(param = rb_hash_aref(options,
                                                    ID2SYM(id_less_than)))) {
                        pq->proc = param;
                    }
                    break;
                default:
                    rb_raise(rb_eArgError,
                             "PriorityQueue#initialize only takes a Hash or "
                             "an integer");

                    break;
            }
            if (capa < 0) {
                rb_raise(rb_eIndexError,
                         "PriorityQueue must have a capacity > 0. %d < 0",
                         capa);
            }
            pq->capa = capa;
            if (rb_block_given_p()) {
                pq->proc = rb_block_proc();
            }
            if (argc > 1) {
                rb_raise(rb_eArgError,
                         "PriorityQueue#initialize only takes one parameter");
            }
        }

        return self;
    }

### Public Instance Methods

insert(elem) → self click to toggle source
pq << elem → self

Insert an element into a queue. It will be inserted into the correct position in the queue according to its priority.

    static VALUE
    frb_pq_insert(VALUE self, VALUE elem)
    {
        PriQ *pq;
        GET_PQ(pq, self);
        if (pq->size < pq->capa) {
            pq_push(pq, elem);
        }
        else if (pq->size > 0 && frb_pq_lt(pq->proc, pq->heap[1], elem)) {
            pq->heap[1] = elem;
            pq_down(pq);
        }
        /* else ignore the element */
        return self;
    }

adjust → self click to toggle source

Sometimes you modify the top element in the priority queue so that its priority changes. When you do this you need to reorder the queue and you do this by calling the adjust method.

    static VALUE
    frb_pq_adjust(VALUE self)
    {
        PriQ *pq;
        GET_PQ(pq, self);
        pq_down(pq);
        return self;
    }

capacity → integer click to toggle source

Returns the capacity of the queue, ie. the number of elements that can be stored in a Priority queue before they start to drop off the end. The size of a PriorityQueue can never be greater than its capacity

    static VALUE
    frb_pq_capa(VALUE self)
    {
        PriQ *pq;
        GET_PQ(pq, self);
        return INT2FIX(pq->capa);
    }

clear → self click to toggle source

Clears all elements from the priority queue. The size will be reset to 0.

    static VALUE
    frb_pq_clear(VALUE self)
    {
        PriQ *pq;
        GET_PQ(pq, self);
        pq->size = 0;
        return self;
    }

clone → pq_clone click to toggle source

Returns a shallow clone of the priority queue. That is only the priority queue is cloned, its contents are not cloned.

    static VALUE
    frb_pq_clone(VALUE self)
    {
        PriQ *pq, *new_pq = ALLOC(PriQ);
        GET_PQ(pq, self);
        memcpy(new_pq, pq, sizeof(PriQ));
        new_pq->heap = ALLOC_N(VALUE, new_pq->mem_capa);
        memcpy(new_pq->heap, pq->heap, sizeof(VALUE) * (new_pq->size + 1));

        return Data_Wrap_Struct(cPriorityQueue, &frb_pq_mark, &frb_pq_free, new_pq);
    }

insert(elem) → self click to toggle source
pq << elem → self

Insert an element into a queue. It will be inserted into the correct position in the queue according to its priority.

    static VALUE
    frb_pq_insert(VALUE self, VALUE elem)
    {
        PriQ *pq;
        GET_PQ(pq, self);
        if (pq->size < pq->capa) {
            pq_push(pq, elem);
        }
        else if (pq->size > 0 && frb_pq_lt(pq->proc, pq->heap[1], elem)) {
            pq->heap[1] = elem;
            pq_down(pq);
        }
        /* else ignore the element */
        return self;
    }

pop → elem click to toggle source

Returns the top element in the queue removing it from the queue.

    static VALUE
    frb_pq_pop(VALUE self)
    {
        PriQ *pq;
        GET_PQ(pq, self);
        if (pq->size > 0) {
            VALUE result = pq->heap[1];       /* save first value */
            pq->heap[1] = pq->heap[pq->size]; /* move last to first */
            pq->heap[pq->size] = Qnil;
            pq->size--;
            pq_down(pq);                      /* adjust heap */
            return result;
        }
        else {
            return Qnil;
        }
    }

size → integer click to toggle source

Returns the size of the queue, ie. the number of elements currently stored in the queue. The size of a PriorityQueue can never be greater than its capacity

    static VALUE
    frb_pq_size(VALUE self)
    {
        PriQ *pq;
        GET_PQ(pq, self);
        return INT2FIX(pq->size);
    }

top → elem click to toggle source

Returns the top element in the queue but does not remove it from the queue.

    static VALUE
    frb_pq_top(VALUE self)
    {
        PriQ *pq;
        GET_PQ(pq, self);
        return (pq->size > 0) ? pq->heap[1] : Qnil;
    }

[Validate]

Generated with the Darkfish Rdoc Generator 2.