speed up joining of cells in bisect (follow up of #19033)

[dkrenn]

Use trees in the joining of neighboring cells in the bisection algorithm proposed in #19033.

Replying to [ticket:19033 comment:47 vdelecroix]:

Replying to [ticket:19033 comment:45 dkrenn]:

Replying to [ticket:19033 comment:41 vdelecroix]:

The following is a big waste.

if join_neighboring_cells:
     verbose('joining neighboring cells...', level=1)
     cells = result
     result = []

     while len(cells) > 0:
         joined = cells.pop(0)
         k = 0
         while k < len(cells):
             try:
                 joined.intersection(cells[k])
             except ValueError:
                 k += 1
             else:
                 joined = joined.union(cells.pop(k))
         result.append(joined)

The intervals should be stored in order (a binary tree seems the most appropriate).

This can only be simplified if we talk about real intervals, but not if we talk about complex intervals, or do I miss something here?

Indeed. For complex intervals you want a quad-tree not a binary tree.

Depends on #19033

Component: numerical

Issue created by migration from https://trac.sagemath.org/ticket/27595

[embray]

comment:2

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).