laser.core.sortedqueue
laser.core.sortedqueue
SortedQueue implementation using NumPy and Numba.
laser.core.sortedqueue.SortedQueue(capacity, values)
A sorted (priority) queue implemented using NumPy arrays and sped-up with Numba.
Using the algorithm from the Python heapq module.
init with an existing array of sorting values
push with an index into sorting values
pop returns the index of the lowest sorting value and its value
Initializes a new instance of the class with a specified capacity and reference to existing, sortable values.
This implementation is specific to LASER and the expectation of tracking 10s or 100s of millions of agents.
We expect the sortable (or priority) values to already be in a NumPy array, usually a property of a LaserFrame object.
The push() and pop() will take indices into this array and will sort on values[i].
This avoids making copies of the sort values.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
capacity
|
int
|
The maximum number of elements the queue can hold. |
required |
values
|
ndarray
|
A reference to an array of values to be accessed by the queue. |
required |
laser.core.sortedqueue.SortedQueue.__len__()
Return the number of elements in the sorted queue.
Returns:
| Name | Type | Description |
|---|---|---|
int |
int
|
The number of elements in the sorted queue. |
laser.core.sortedqueue.SortedQueue.__pop()
Removes the smallest value element from the sorted queue.
Raises:
| Type | Description |
|---|---|
IndexError
|
If the sorted queue is empty. |
Side effects
- Decreases the size of the sorted queue by one.
- Reorganizes the internal structure of the sorted queue to maintain the heap property.
laser.core.sortedqueue.SortedQueue.peeki()
Returns the index of the smallest value element in the sorted queue without removing it.
Raises:
| Type | Description |
|---|---|
IndexError
|
If the sorted queue is empty. |
Returns:
| Type | Description |
|---|---|
uint32
|
np.uint32: The index of the smallest value element. |
laser.core.sortedqueue.SortedQueue.peekiv()
Returns the index and value of the smallest value element in the sorted queue without removing it.
Returns:
| Type | Description |
|---|---|
tuple[uint32, Any]
|
tuple[np.uint32, Any]: A tuple containing the index and value of the smallest value element. |
Raises:
| Type | Description |
|---|---|
IndexError
|
If the sorted queue is empty. |
laser.core.sortedqueue.SortedQueue.peekv()
Return the smallest value from the sorted queue without removing it.
Raises:
| Type | Description |
|---|---|
IndexError
|
If the sorted queue is empty. |
Returns:
| Name | Type | Description |
|---|---|---|
Any |
Any
|
The value with the smallest value in the sorted queue. |
laser.core.sortedqueue.SortedQueue.popi()
Removes and returns the index of the smallest value element in the sorted queue.
This method first retrieves the index of the smallest value element using peeki(),
then removes the element from the queue using pop(), and finally returns the index.
Returns:
| Type | Description |
|---|---|
uint32
|
np.uint32: The index of the smallest value element in the sorted queue. |
laser.core.sortedqueue.SortedQueue.popiv()
Removes and returns the index and value of the smallest value element in the sorted queue.
This method first retrieves the index and value of the smallest value element using peekiv(),
then removes the element from the queue using pop(), and finally returns the index and value.
Returns:
| Type | Description |
|---|---|
tuple[uint32, Any]
|
tuple[np.uint32, Any]: A tuple containing the index and value of the smallest value element. |
laser.core.sortedqueue.SortedQueue.popv()
Removes and returns the value at the front of the sorted queue.
This method first retrieves the value at the front of the queue without
removing it by calling peekv(), and then removes the front element
from the queue by calling pop(). The retrieved value is then returned.
Returns:
| Name | Type | Description |
|---|---|---|
Any |
Any
|
The value at the front of the sorted queue. |
laser.core.sortedqueue.SortedQueue.push(index)
Insert an element into the sorted queue.
This method adds an element at the back of the sorted queue and then ensures the heap property is maintained by sifting the element forward to its correct position.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
index
|
int
|
The index of the element to be added to the sorted queue. |
required |
Raises:
| Type | Description |
|---|---|
IndexError
|
If the sorted queue is full. |