BTreeSet sorted by dynamically generated keys

help
1

Hi, I'm trying to solve this problem from the ICPC's inaugural North America Championship: Bomas – Kattis, Kattis

A key piece of the solution is to build the tree of nested circles. To do this efficiently, one performs a line sweep: imagine a vertical line starting at some very negative x and gradually moving to the right. At any moment, we maintain the upper and lower arcs of all circles that intersect the current x coordinate, sorted by the y coordinate of this intersection. Since, for each arc, y is a function of x, this means the arcs are sorted by keys that vary with time.

Thus, I want to put my arcs into a BTreeSet with a custom comparator function that computes these keys on demand. The comparator would have read-only access to the x value, which is modified by my line sweep program. I understand that any changes in keys that affect the relative order of elements in the BTreeSet would be a logic error; fortunately, changes in relative order will never occur because the circles in question do not intersect. Nonetheless, I need to be able to perform successor and predecessor queries during the line sweep, in order to insert new arcs in the correct sorted position when the line sweep reaches the left endpoint of a new circle.

Are there any plans for BTreeSet to support custom comparators such as this, or does an alternative solution currently exist in the Rust standard library?

Thanks!

2

What if you wrap your keys?

struct PseudoKey {
    key: Key,
    context: Rc<RefCell<Context>>, // or Arc<RwLock<_>>,
}

impl PartialOrd for PseudoKey {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        let context = self.context.borrow();
        // compare them!
    }
}
2 Likes
3

Thanks! I think this would work, at the expense of storing a large number of pointers. I can use your method until BTreeSet gets a constructor that takes a comparator; that feels to me like the correct place to store the context pointer.

4

Another option right now is to go to the other extreme, and put that context in a thread-local or global variable -- assuming you don't need multiple of these dynamic sets.

5

I only need one dynamic set, though ideally I'd like a solution that easily extends to similar problems. Just to confirm, global variables would require either unsafe {} or a synchronization lock, right? And from what I can find, thread-local variables are declared and accessed like this: LocalKey in std::thread - Rust

Does my use case merit a request for the alternative BTreeSet constructor?

6

Static mutable variables are extremely hard to do right, and just using unsafe {} is the tip of the iceberg. A synchronization lock would be the best choice, or, if possible an atomic could also be used.

I do not follow exactly what you're trying to accomplish; if you want a custom comparator for your key, then newtype your key or use the existing one and implement Ord which is what the BTreeSet uses (And the BTreeMap).
If you're looking to edit the BTreeSet while comparing the item, then you're out of luck since that could break state.

7

You declare it with thread_local!, and then access through LocalKey::with.

It's an interesting use case, but I think it's probably too niche to find its way into std. Maybe it would warrant a fork into a dedicated crate, much like binary-heap-plus has done.

1 Like
8

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.