Java TreeSet - How to efficiently insert then poll immediate neighbors?

Looking for a solution that would work on stock Java 8, no libraries.

I'm trying to implement the standard Line Segment intersection algorithm. This involves keeping track of a sorted collection (on y-coordinate) of Line Segments currently "active".

Part of the algorithm is, assuming a TreeSet actives and a new line Segment s:

• insert s into actives
• lookup the immediate neighbors of s in actives and do some math

I've implemented this as:

// left neighbor of s, as though already added
try {
    Segment sa = actives.tailSet(s).first();
	if (math(sa, s) {
        ...
    }
} catch(NoSuchElementException ignore) {}
// right neighbor versus s, as though already added
try {
    Segment sb = actives.headSet(s).last();
	if (math(sb, s) {
        ...
    }
} catch(NoSuchElementException ignore) {}	
				
// add s => actives
actives.add(s);

Aside from the aggravating try/catch in case first() or last() fails (which is a trade off against first getting the subset in a variable, THEN checking if it's empty, THEN proceeding if not), the real problem, as I understand it, is this is inefficient, namely:

tailSet(), headSet(), and add() all incur O(log(N)) work on my TreeSet actives, while the algorithm assumes I can insert once in O(log(N)), and then look up neighbors in O(1).

How can I do something similar, but incur the O(log(N)) binary lookup only once? I'm doing 3x as much work as necessary.

Perhaps try adding the element s to actives first, then calling actives.lower(s) and actives.higher(s). The TreeSet docs don't state the complexity of those methods but they look O(1) to me in the source code.

I rewrote your code a bit:

// left neighbor of s, as though already added
SortedSet<Segment> trailSet = actives.tailSet(s);
if (!trailSet.isEmpty()) {
    Segment sa = trailSet.first();
    if (math(sa, s) {
        ...
    }
}

// right neighbor versus s, as though already added
SortedSet<Segment> headSet = actives.headSet(s);
if (!headSet.isEmpty()) {
    Segment sb = headSet.last();
    if (math(sb, s) {
        ...
    }
}

// add s => actives
actives.add(s);

There is no need to catch anything (as you can check emptieness ahead of retrieving the first (or last) element). This is more performant, as it does not cause stack trace generation.

But you can even go with something better. According to https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html , you can call a method that

> Returns the greatest element in this set strictly less than the given element, or null if there is no such element.

or the smallest, strictly greater. The methods are called lower and higher.

Segment sa = actives.higher(s);
if (sa != null && math(sa, s) {
    ...
}

// right neighbor versus s, as though already added
Segment sb = actives.lower(s);
if (sb != null && math(sb, s) {
    ...
}

// add s => actives
actives.add(s);