Receptive map queue

I've written a class I call ReceptiveMapQueue. Its purpose is to organize the internal structure of an AFKable RPG. It only has two public methods - dumping entries into the queue, and extracting values from the head of the queue. I won't waste time describing it in paragraph form, since it is fully documented.

The expected usage of it might be:

private final Object authToken = new Object();
private final ReceptiveMapQueue playersByTick = new ReceptiveMapQueue<>(authToken);

Later, various methods will be updating characters

playersByTick.add(currentTick + 5, currentActor);

And every tick, you'll see something like this from the game loop:

Set charactersToProcess = playersByTick.extractAllOnOrBefore(currentTick);
for(PlayerCharacter pc : charactersToProcess) {
    try(AutoLock pclock = pc.getLock().write()) {
        simulator.bringGameStateToCurrent(pc);
    } catch(Exception pokemon) {
        log("error in processing " + pc.getName() + " tick " + currentTick, pokemon);
    }
}

That's the basic usage in a nutshell. I've ran it through the basic tests of adding and extracting and it seems to pass. It does have a large memory footprint when I send it sky-high (a million entries) but I figure if I have a million registered users, I'll have the capital to tackle that problem.

That said, I'm open to all suggestions about how I can reduce its footprint, make it faster or more reliable, make it safer, or just things that I could generally be doing better. I'm especially interested in test cases that break. I think I've got most of them, but that's the funny thing about test cases: it's the ones you DON'T think about that usually break your code, right?

```
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
* The Receptive Map Queue is a structure to permit batches of entities to be

The auth token is weird. Your class can't protect itself against reflection as far as I'm aware, so all this is doing is covering up a bad design. From the documentation I can sort of see it's supposed to guarantee thread safety - I don't understand why you'd go to such lengths; there are better ways of handling thread safety. Synchronizing on a private final Object lockObject = new Object() comes to mind.

The function names are also weird.

private void clearWaitList() {
    while(!waiting.isEmpty()) {

This is not what I expected.

Here's what I expected:

private void clearWaitList() {
   waiting.clear();
}

And done.

Was this not your intention?

/*
 * Clear the waiting list - this is called once per extract, which we know is externally synchronized. We could
 * just add the various entries whenever they get added but that would require even more synchronization and
 * we don't want external threads (like servlets) to drop their commands in quickly to release locks.
 */

It's not described in the documentation. It's not described in the function name. The purpose of the class is unclear. You've managed to write so many words and explain so little.

Perhaps I'm being rude. But there's so much here to confuse your fellow programmer!

/* creating a new empty set every Map#putIfAbsent() call is a bad idea. Thus, we cache an empty map
 * and replace it when we use it. This is not thread safe. We could make it thread safe (with atomic 
 * reference) but if we really decide to thread safe THIS, we would just thread safe the entire extract
 * procedure. 
 */
private Set nextEmptySet = new HashSet<>();

This is premature optimization! You are worried about ONE new instance of HashSet?! ONE?

Have you profiled your code? Do you know that constantly creating a new object is expensive in this case? If it does, you could improve this comment by stating how much the difference exactly is.

20 minutes of trying to understand this code later (That's a lot of dev time!), I sort-of get what you're trying to do here. That's not clearWaitList, it's processAddedItems. I'm still left confused:

DummyPair p = waiting.poll();
        if( p == null) return;

This code doesn't seem to make sense. The only way you can get to the return here is if the queue is not empty, but it is empty.

K old = reverseLookup.remove(p.v);
        if(old != null) {
            map.get(old).remove(p.v);
            // leave the old set, could be others - who cares if it's empty...
            // leave keys, it will get cleaned up in time
        }

This removes the old value. The comments here didn't help my understanding at first; I understand that you mean to say "don't clean up empty value sets for keys here". I don't see how it will get cleaned up in time.

Set set = map.putIfAbsent(p.k, nextEmptySet);

This... adds the key - set mapping if it's not there. Then it returns the old value, which will be null if it added and the old value if it didn't add. Pretty clear.

if(set == null) {
            set = nextEmptySet;
            nextEmptySet = new HashSet<>();   
            keys.add(p.k);
        }

If we just had to add a set for this key, make a new cached empty set... and add the key to the priority queue. Pretty clear.

set.add(p.v);
        reverseLookup.put(p.v, p.k);

Add key -> value and value -> key mappings. Pretty clear.

...

After looking at this in a bit more detail, you could merge these two lines:

K old = reverseLookup.remove(p.v);
         reverseLookup.put(p.v, p.k);

As put will return the old "value" (which is the "old key" in this case).

I don't think I can provide any meaningful commentary regarding the purpose and usage of this class. It seems to hide several VERY BIG assumptions, and it's very likely that you'll get bitten by them somewhere down the road. If I inherited this as-is, and there were no other pressing needs, I'd try to rewrite the whole thing from scratch in a simpler way, even sacrificing performance. I would personally prefer slower code over code that I couldn't understand.

A final comment:

/*
 * A dummy class to hold keys and values for processing in the waiting queue
 */
private class DummyPair {
    final K k;
    final V v;
    DummyPair(K k, V v) {
        this.k = k;
        this.v = v;
    }

}

This really could have used key and value as variable names. It would have helped with reading.

StackExchange Code Review Q#135419, answer score: 3