I need a data type for a collection of objects (stored in a given order) which supports both *O(log n)* insertion and deletion methods, as well as some way to perform a dichotomic search (where I provide the left-or-right test): namely, given a function `cmp`

, where I promise that `map(cmp, collection)`

is of the form `(false, false, false..., true, true, true...)`

, find the handle for the first object `x`

such that `cmp(x) == true`

.

In addition, I also need some way of performing sequential traversal (for swapping objects in the collection as needed to preserve the above promise).

In other words, I need this structure to behave like a `Vector`

, but with efficient insertion and deletion (at the price of *O(log n)* lookup). This is *not* a sorted container; namely, the data in the container is indeed sorted according to some weird ordering, but I do not need the container to know anything about this order (all the comparisons are performed by the external `cmp`

function at insertion/deletion time).

This should possible in theory by using a self-balancing binary tree; `DataStructures.jl`

has several such types (e.g. `BalancedTree23`

, and recent versions export `RBTree`

), but they apparently all use comparison functions between the stored values, which is what I want to avoid. Does there exist a data structure implementing this, or must I write it from scratch?

(For more context: my goal is to implement a variant of the Bentley-Ottmann algorithm. The data structure stores a set of segments, represented as pairs of indices of points, and sorted by increasing intercept along a given *x = constant* line. The comparison between those segments is *not* done by computing the intercepts, because this would need to be redone each time a new line is chosen; instead, the correct insertion point is chosen for each new segment by computing determinants. Whenever the data becomes incorrectly-sorted in the list, this is detected and they are manually swapped).