Godot PriorityQueue

This script written in Godot's GDScript language allows for usage of a priority queue datastructure.

License

CC0. Do with this whatever you want.

Download

Current version: 1.0.4
Mega.nz: Download

Changelog

Version 1.0.4, 2016/12/03

 - fixed orientation functionality, queue can now correctly sort highest or lowest value towards root

Version 1.0.3, 2016/11/25

 - [Documentation lost]

Version 1.0.2, 2016/11/24

 - [Documentation lost]

Version 1.0.1, 2016/11/23

 - added 'get_size()'

Version 1.0.0, 2016/11/21

 - initial release for Godot 2.1-stable-win64

Functionality

Constants

float LOG2BASEE = 0.69314718056

Precalculated value used to determine the size of the base array.

Variables

Array array 

The one-dimensional array at the base of the queue used to hold the items.

int currentSize

An integer equal to the number of items held in the array.

bool isEmpty

True when currentSize < 1.

int lastPowerOfTwo

Integer used to calculate the size of the array.

bool maintain_min

The operating mode of the queue. True when the lowest priority is sorted towards the root, False if the highest priority is sorted towards the root.

Functions

The following functions, sorted alphabetically, are present in the datastructure. The function names are prefixed by the type of the returned value, expressed in GDScript terms. If nothing is returned, the prefix is 'void'. Due to the dynamically typed nature of GDScript, the type of the returned value is not always predictable (mainly concerning floats and integers). Functions not listed here are for internal use only and should not be called by any other scripts (GDScript doesn't differentiate public from private methods).

void _init(Array array_of_items, bool set_maintain_min = true)

array_of_items: Input Array with zero or more items. An item is an Array of [0]a priority (float or int) and [1]a value, which can be any type.
set_maintain_min: Bool determining the mode of the queue. If true, sorts lowest priority towards root, if false, the highest priority.

Constructor method of the class. Use .new(arg0, arg1) to create a new queue.

bool change_priority(int arrayIdx, float new_priority)

Changes the priority of the item at arrayIdx to new_priority, after which the queue will sort itself to correctly place the specified item. Returns a bool to report successful operation.

int get_height()

Returns the number of 'tiers' with at least one element in it.

float/int get_item_priority(int arrayIdx)

Returns the priority of the item stored at arrayIdx in the base array. Very limited use, because the queue is not necessarily sorted after index 1.

Variable get_item_value(int arrayIdx)

Returns the value of the item stored at arrayIdx in the base array. Very limited use, because the queue is not necessarily sorted after index 1.

bool get_maintain_min()

Returns maintain_min.

Array get_root_item()

Returns the item at the root. Item is an Array of [0]priority and [1]value.

float/int get_root_priority()

Returns the priority of the item at the root of the queue.

Variable get_root_value()

Returns the value of the item at the root of the queue.

int get_size()

Returns number of items in the queue.

Array get_queue()

Returns an array filled with the values of items currently stored in the base array. Values are not necessarily sorted after the first item.

Variable remove(int arrayIdx)

Deletes the item at arrayIdx position in the base array. Returns the value of that item. Maintains queue order.

Array/Variable remove_root(bool return_array = false)

Removes and returns the item at the queue's root. If return_array is true, it will return the item as Array with [0]the priority and [1]the value. If return_array is false, will return value instead.