Numba priority queue problems

Numba Support: How do I do ...?
1

I am trying to transform a priority queue data structure type I generated to store triangles(entity) with a certain error(float) using numba but I am running into some problems with the specification

Here is the code I have so far for the priority queue (which also allows for deletion of triangles)


import heapq
import numba as nb
from triangle import typeTriangle
from numba.experimental import jitclass

# Define a Priority Queue for Triangles

@jitclass
class PriorityQueuePlus:
    queue: nb.typeof([(0, typeTriangle)])
    _location_map : nb.typed.Dict.empty(key_type=typeTriangle, value_type=nb.types.int64)
    
    def __init__(self):
        self.queue = nb.typed.List.empty_list((0.0, typeTriangle))
       
        # Maps triangles to their locations in the heap
        self._location_map = nb.typed.Dict.empty(typeTriangle,0) 

    def push(self, triangle, error):
        heapq.heappush(self.queue, (error, triangle))
        self._location_map[triangle] = len(self.queue) - 1

    def pop(self):
        if self.queue:
            error, triangle = heapq.heappop(self.queue)
            del self._location_map[triangle]
            return error, triangle
        else:
            raise IndexError("Queue is empty")

    def delete(self, triangle):
        if triangle in self._location_map:
            location = self._location_map[triangle]
            # remove the triangle with smallest error
            error, first_triangle = self.queue.pop()
           
            if location < len(self.queue):
                # subsitute the triangle we want to delete
                # by the one we just poped (with smallest error)
                self.queue[location] = (error, first_triangle)
                self._location_map[first_triangle] = location
            del self._location_map[triangle]
            heapq.heapify(self.queue)

    def is_empty(self):
        return len(self.queue) == 0

The error I get seems to be related with how I am specifying the class members. My intention is to have:

  • queue to be a list of tuples. Each tuple being a (float, Triangle).
  • _location_map to be a simple dictionary where the key a Triangle and the value is an integer

Alas I get a very long error which I am only including the first part:

TypingError: Failed in nopython mode pipeline (step: nopython frontend)
No implementation of function Function(<function new_dict at 0x0000024996E86980>) found for signature:
 
 >>> new_dict(typeref[instance.jitclass.Triangle#249974acf50<id:int64,e01:instance.jitclass.Edge#24997360cd0<id:int64,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e12:instance.jitclass.Edge#24997360cd0<id:int64,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e20:instance.jitclass.Edge#24997360cd0<id:int64,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p2:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,vertices:ListType[instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>]>], class(int64), n_keys=int64)
 
There are 2 candidate implementations:
  - Of which 1 did not match due to:
  Overload in function 'impl_new_dict': File: numba\typed\dictobject.py: Line 653.
    With argument(s): '(typeref[instance.jitclass.Triangle#249974acf50<id:int64,e01:instance.jitclass.Edge#24997360cd0<id:int64,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e12:instance.jitclass.Edge#24997360cd0<id:int64,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e20:instance.jitclass.Edge#24997360cd0<id:int64,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p2:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,vertices:ListType[instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>]>], class(int64), n_keys=int64)':
   Rejected as the implementation raised a specific error:
     TypingError: Failed in nopython mode pipeline (step: native lowering)
   No implementation of function Function(<built-in function eq>) found for signature:
    
    >>> eq(instance.jitclass.Triangle#249974acf50<id:int64,e01:instance.jitclass.Edge#24997360cd0<id:int64,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e12:instance.jitclass.Edge#24997360cd0<id:int64,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e20:instance.jitclass.Edge#24997360cd0<id:int64,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p2:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,vertices:ListType[instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>]>, instance.jitclass.Triangle#249974acf50<id:int64,e01:instance.jitclass.Edge#24997360cd0<id:int64,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e12:instance.jitclass.Edge#24997360cd0<id:int64,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e20:instance.jitclass.Edge#24997360cd0<id:int64,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,p0:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,p2:instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>,vertices:ListType[instance.jitclass.Point3D#249951acb10<x:int64,y:int64,z:float64>]>)
    
   There are 32 candidate implementations:
      - Of which 28 did not match due to:
       [...]

My understanding (please correct me if I am wrong) is that I first need to specify the type of each member and then initiate them???

2

Hey @MLLO ,
you are on the right track.
Specify the type of each field and provide it as spec to the jitclass decorator if required.
Then initialize your objects.
Can you adjust the definitions of your container objects?
Here is an example how to define container types and how to initialize the empty containers:

import numba.types as nbt
# Definition of types
typeQueueMember = nbt.Tuple((nbt.i8, typeTriangle))
typeQueue = nbt.ListType(typeQueueMember)
typeLocation_map = nbt.DictType(typeTriangle, nbt.i8)
# Initialize empty objects
Queue = nb.typed.List.empty_list(typeQueueMember)
location_map = nb.typed.Dict.empty(typeTriangle, nbt.i8)

Here is an example for numba.typed containers from the documentation:
https://numba.readthedocs.io/en/stable/user/jitclass.html#specifying-numba-typed-containers-as-class-members-explicitly

3

Hi @Oyibo! Thanks for the tips… following your comments I wrote the following

# Specify types
typeQueueEntry = nb.types.Tuple((nb.types.i8, typeTriangle))
typeQueue = nb.types.ListType(typeQueueEntry)
typeLocMap =  nb.types.DictType(typeTriangle, nb.types.i8)

pq_spec = [('queue', typeQueue),
           ('_location_map', typeLocMap),]

@jitclass(pq_spec)
class PriorityQueuePlus:
    
    def __init__(self):
        self.queue = nb.typed.List.empty_list(typeQueueEntry)
        # Maps triangles to their locations in the heap
        self._location_map = nb.typed.Dict.empty(typeTriangle, nb.types.i8)

I was able to import the priority queue without errors (so at least I was able to pass that hurdle) but when creating a new priority queue I ran into problems again. Unfortunately, no matter how much I read the errors I am unable to figure out where and what exactly went wrong. As usual, it spits out a typing type long error message (just including the beginning and end here):

TypingError: Failed in nopython mode pipeline (step: nopython frontend)
Failed in nopython mode pipeline (step: nopython frontend)
- Resolution failure for literal arguments:
No implementation of function Function(<function typeddict_empty at 0x000002DC39794B80>) found for signature:

 >>> typeddict_empty(typeref[<class 'numba.core.types.containers.DictType'>], typeref[instance.jitclass.Triangle#2dc39cd8950<id:int64,e01:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e12:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e20:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p2:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,vertices:ListType[instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>]>], class(int64))

[...]

- Resolution failure for non-literal arguments:
None

During: resolving callee type: BoundFunction((typeref[<class 'numba.core.types.containers.DictType'>], 'empty') for typeref[<class 'numba.core.types.containers.DictType'>])
During: typing of call at c:\Python\Notebooks\active\tin\pqueue.py (23)


File "pqueue.py", line 23:
    def __init__(self):
        <source elided>
        # Maps triangles to their locations in the heap
        self._location_map = nb.typed.Dict.empty(typeTriangle, nb.types.i8) 
        ^

During: resolving callee type: jitclass.PriorityQueuePlus#2dc39dbf910<queue:ListType[Tuple(int64, instance.jitclass.Triangle#2dc39cd8950<id:int64,e01:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e12:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e20:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p2:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,vertices:ListType[instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>]>)],_location_map:DictType[instance.jitclass.Triangle#2dc39cd8950<id:int64,e01:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e12:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e20:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p2:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,vertices:ListType[instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>]>,int64]<iv=None>>
During: typing of call at <string> (3)

During: resolving callee type: jitclass.PriorityQueuePlus#2dc39dbf910<queue:ListType[Tuple(int64, instance.jitclass.Triangle#2dc39cd8950<id:int64,e01:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e12:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e20:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p2:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,vertices:ListType[instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>]>)],_location_map:DictType[instance.jitclass.Triangle#2dc39cd8950<id:int64,e01:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e12:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,e20:instance.jitclass.Edge#2dc39baec50<id:int64,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,next:OptionalType(int64),inv:int64,triangle:int64>,p0:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p1:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,p2:instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>,vertices:ListType[instance.jitclass.Point3D#2dc373b0f10<x:int64,y:int64,z:float64>]>,int64]<iv=None>>
During: typing of call at <string> (3)
4

Hey @MLLO,
You can use a custom class like Triangle as a key in a dictionary in Python, but to do so effectively, I think you have to define the __hash__ and __eq__ dunder methods in your class. Your dictionary basically does not know how to compare the keys. The __hash__ method determines the object’s hash value, and the __eq__ method defines how objects are compared for equality.
Can you use The triangle ID instead of the triangle object as key for your dictionary?

1 Like
5

Thanks @Oyibo !!!

I will investigate both alternatives you provided. Originally I did not have triangle ids but as I am adapting the code to be able to run numba, I do have that now.

I will spend some time on this. Again thanks!

6

Hi @Oyibo

I did try out creating some __hash__() and __eq__() for my triangle class as such,

    def __hash__(self):
        return hash((self.p0, self.p1, self.p2))
    
    def __eq__(self, other):
        return (self.p0 == other.p0) and (self.p1 == other.p1) and (self.p2 == other.p2)

I managed to get the queue initiated but then I ran into issues (more typing errors) when calling in my push() function. It seems that as one progresses you start getting into a deeper and deeper rabbit hole.

I am see whether my original code so that instead of accessing a triangle directly I access its identifier (as you suggested) does the trick.

7

Hi @Oyibo.

FYI, I altered the priority queue so that instead of accepting triangle objects, it takes their id (int64). Here is the alteration,

# Specify types
typeQueueEntry = nb.types.Tuple((nb.types.i8, nb.types.i8)) # (location, triangle_id)
typeQueue = nb.types.ListType(typeQueueEntry)
typeLocMap =  nb.types.DictType(nb.types.i8, nb.types.i8) # (triangle_id, location)

pq_spec = [('queue', typeQueue),
           ('_location_map', typeLocMap),]

@jitclass(pq_spec)
class PriorityQueuePlus:
    
    def __init__(self):
        self.queue = nb.typed.List.empty_list(typeQueueEntry)
        # Maps triangles to their locations in the heap
        self._location_map = nb.typed.Dict.empty(nb.types.i8, nb.types.i8)

This still bombs (showing here part of the error)

---------------------------------------------------------------------------
TypingError                               Traceback (most recent call last)
c:\Python\Notebooks\active\tin\testing.ipynb Cell 10 line 1
----> 1 q.push(t0.id, 0.5)
      2 q.push(t1.id, 0.1)
      3 q.push(t2.id, 1.5)

[...]

TypingError: Failed in nopython mode pipeline (step: nopython frontend)
- Resolution failure for literal arguments:
Failed in nopython mode pipeline (step: nopython frontend)
No implementation of function Function(<built-in function heappush>) found for signature:

 >>> heappush(ListType[UniTuple(int64 x 2)], Tuple(float64, int64))

There are 2 candidate implementations:
  - Of which 2 did not match due to:
  Overload in function 'heappush': File: numba\cpython\heapq.py: Line 150.
    With argument(s): '(ListType[UniTuple(int64 x 2)], Tuple(float64, int64))':
   Rejected as the implementation raised a specific error:
     TypingError: heap type must be the same as item type
  raised from c:\Python\Miniconda3\envs\tin\Lib\site-packages\numba\cpython\heapq.py:119

During: resolving callee type: Function(<built-in function heappush>)
During: typing of call at c:\Python\Notebooks\active\tin\pqueue.py (27)


File "pqueue.py", line 27:
    def push(self, triangle_id, error):
        heapq.heappush(self.queue, (error, triangle_id))
        ^

I think this has something to do with relying on heappush() function from heapq package that is probably not sufficiently specified for numba??? It is this trickle down effect when one relies on other bits of software… do not know if this makes sense???

8

The error you are encountering when using Numba with a jitclass and the heapq module is due to Numba’s limitations in handling some Python standard library functions, especially when working with custom types.
In this case, it seems that you are having trouble inferring the types for the heapq.heappush function.
To work around this issue, you can create a custom jitted heappush function that Numba can handle.
You can use the original source code as template.

Keep in mind, Numba excels in optimizing heavy numerical computations but may not be the best choice for object-oriented coding. Consider using Python classes and incorporating Numba-jitted functions where numerical performance is crucial.

9

Thanks @Oyibo !

Yes… I thought as much (hence when I was referring to numba not trickling down). Yes, I know that most of the optimizations offered with python are not thought with OOP in mind. Unfortunately, the type of algorithm I am working on is very geometrical and it helps ‘conceptually’ to have it as OOP. i.e. to deal with triangles, points, etc.

I will see if I can get a ‘numba’ version of heapq up and running. I had found a link to an older numba implementation by @gmarkall but I am not certain if that would work.

Thanks again.

10

(I haven’t kept up with the whole thread, but a couple of quick observations)

Some of the heapq functions are supported by Numba: Supported Python features — Numba 0+untagged.4124.gd4460fe.dirty documentation. The priority queue implementation you linked to should work with current Numba versions.

1 Like
11

Thanks @gmarkall for the heads up!

12

Thought I would share this with the community in case it is of use to anyone. This priority queue works for my particular objects but it would be easy to modify in order to deal with other objects.

'''priority queue plus'''

import heapq
import numba as nb

from numba.experimental import jitclass
from point import typePoint3D, Point3D

entry_spec = [('error', nb.types.f8),
              ('triangle_id', nb.types.i8),
              ('point', typePoint3D),]

@jitclass(entry_spec)
class Entry:
    def __init__(self, error: float, triangle_id: int, point: Point3D):
        self.error = error
        self.triangle_id = triangle_id
        self.point = point

    def __lt__(self, other):
        return self.error < other.error

typeQueueEntry = Entry.class_type.instance_type

typeQueue = nb.types.ListType(typeQueueEntry)
typeLoc = nb.types.DictType(nb.types.i8, nb.types.i8) # (triangle_id, location)

pq_spec = [('queue', typeQueue),
           ('_location_map', typeLoc)]

@jitclass(pq_spec)
class PriorityQueuePlus:
    
    def __init__(self):
        self.queue = nb.typed.List.empty_list(Entry(0.0, 0, Point3D(0,0,0.0)))
        # Maps triangles to their locations in the heap
        self._location_map = nb.typed.Dict.empty(0,0)
    
    def push(self, item: Entry) -> None:
        heapq.heappush(self.queue, item)
        self._location_map[item.triangle_id] = len(self.queue) - 1

    def pop(self) -> Entry:
        if self.queue:
            entry = heapq.heappop(self.queue)
            del self._location_map[entry.triangle_id]
            return entry
        else:
            raise IndexError("Queue is empty")

    def remove(self, triangle_id: int) -> None:
        if triangle_id in self._location_map:
            location = self._location_map[triangle_id]
            # remove the triangle with smallest error
            entry = self.queue.pop()
           
            if location < len(self.queue):
                # subsitute the triangle we want to delete
                # by the one we just poped (with smallest error)
                self.queue[location] = entry
                self._location_map[entry.triangle_id] = location
            del self._location_map[entry.triangle_id]
            heapq.heapify(self.queue)

    def is_empty(self):
        return len(self.queue) == 0

Special thanks to @Oyibo and to @gmarkall

3 Likes