My Project
Public Types | Public Member Functions
Bounded_queue< Element_type, Key_type > Class Template Reference

#include <bounded_queue.h>

List of all members.

Public Types

typedef void(* keymaker_function )(Sort_param *param, Key_type *to, Element_type *from)
typedef int(* compare_function )(size_t *n, Key_type **a, Key_type **b)

Public Member Functions

int init (ha_rows max_elements, bool max_at_top, compare_function compare, size_t compare_length, keymaker_function keymaker, Sort_param *sort_param, Key_type **sort_keys)
void push (Element_type *element)
Key_type ** pop ()
uint num_elements () const
bool is_initialized () const

Detailed Description

template<typename Element_type, typename Key_type>
class Bounded_queue< Element_type, Key_type >

A priority queue with a fixed, limited size.

This is a wrapper on top of QUEUE and the queue_xxx() functions. It keeps the top-N elements which are inserted.

Elements of type Element_type are pushed into the queue. For each element, we call a user-supplied keymaker_function, to generate a key of type Key_type for the element. Instances of Key_type are compared with the user-supplied compare_function.

The underlying QUEUE implementation needs one extra element for replacing the lowest/highest element when pushing into a full queue.

Member Typedef Documentation

template<typename Element_type , typename Key_type >
typedef int(* Bounded_queue< Element_type, Key_type >::compare_function)(size_t *n, Key_type **a, Key_type **b)

Function for comparing two keys.

nPointer to number of bytes to compare.
aFirst key.
bSecond key.
Return values:
-1,0,or1 depending on whether the left argument is less than, equal to, or greater than the right argument.
template<typename Element_type , typename Key_type >
typedef void(* Bounded_queue< Element_type, Key_type >::keymaker_function)(Sort_param *param, Key_type *to, Element_type *from)

Function for making sort-key from input data.

paramSort parameters.
toWhere to put the key.
fromThe input data.

Member Function Documentation

template<typename Element_type , typename Key_type >
int Bounded_queue< Element_type, Key_type >::init ( ha_rows  max_elements,
bool  max_at_top,
compare_function  compare,
size_t  compare_length,
keymaker_function  keymaker,
Sort_param sort_param,
Key_type **  sort_keys 

Initialize the queue.

max_elementsThe size of the queue.
max_at_topSet to true if you want biggest element on top. false: We keep the n largest elements. pop() will return the smallest key in the result set. true: We keep the n smallest elements. pop() will return the largest key in the result set.
compareCompare function for elements, takes 3 arguments. If NULL, we use get_ptr_compare(compare_length).
compare_lengthLength of the data (i.e. the keys) used for sorting.
keymakerFunction which generates keys for elements.
sort_paramSort parameters.
sort_keysArray of pointers to keys to sort.
Return values:
0OK, 1 Could not allocate memory.

We do *not* take ownership of any of the input pointer arguments.

template<typename Element_type , typename Key_type >
bool Bounded_queue< Element_type, Key_type >::is_initialized ( ) const [inline]

Is the queue initialized?

template<typename Element_type , typename Key_type >
uint Bounded_queue< Element_type, Key_type >::num_elements ( ) const [inline]

The number of elements in the queue.

template<typename Element_type , typename Key_type >
Key_type** Bounded_queue< Element_type, Key_type >::pop ( ) [inline]

Removes the top element from the queue.

Return values:
Pointerto the (key of the) removed element.
This function is for unit testing, where we push elements into to the queue, and test that the appropriate keys are retained. Interleaving of push() and pop() operations has not been tested.
template<typename Element_type , typename Key_type >
void Bounded_queue< Element_type, Key_type >::push ( Element_type *  element)

Pushes an element on the queue. If the queue is already full, we discard one element. Calls keymaker_function to generate a key for the element.

elementThe element to be pushed.

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines