This is a queue for tracking works completion status and order.

WorkCompletionQueue

package org.code.museum;

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;

import java.util.List;
import java.util.Map;
import java.util.SortedMap;

public class WorkCompletionQueue {
    private SortedMap<Long, Boolean> set;

    public WorkCompletionQueue() {
        set = Maps.newTreeMap();
    }

    public WorkCompletionQueue(SortedMap<Long, Boolean> set) {
        this.set = set;
    }

    public boolean isEmpty() {
        return set.isEmpty();
    }

    public void push(long index, boolean isFinished) {
        set.put(index, isFinished);
    }

    public void pushUncompletedWork(long key) {
        push(key, false);
    }

    public void pushCompletedWork(long key) {
        push(key, true);
    }

    public boolean contains(long key) {
        return set.containsKey(key);
    }

    public int size() {
        return set.size();
    }

    public void markCompleted(long key) {
        set.put(key, true);
    }

    public List<Long> popCompleted() {
        final List<Long> completed = Lists.newArrayList();

        for (Map.Entry<Long, Boolean> entry : set.entrySet()) {
            if (!entry.getValue()) {
                return completed;
            }
            Long key = entry.getKey();
            completed.add(key);
            set.remove(key);
        }
        return completed;
    }
}

WorkCompletionQueueTest

package org.code.museum;

import com.google.common.collect.Lists;
import com.google.common.collect.Sets;
import org.junit.Test;

import java.util.*;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import static org.mockito.Mockito.*;

public class WorkCompletionQueueTest {
    private WorkCompletionQueue tester;
    private SortedMap mockedSortedMap;

    @org.junit.Before
    public void setUp() throws Exception {
        mockedSortedMap = mock(SortedMap.class);
        tester = new WorkCompletionQueue(mockedSortedMap);
    }

    @Test
    public void testCreation() throws Exception {
        WorkCompletionQueue queue = new WorkCompletionQueue();
        assertTrue(queue.isEmpty());
    }

    @Test
    public void testIsEmpty() throws Exception {
        tester.isEmpty();
        verify(mockedSortedMap).isEmpty();
    }

    @Test
    public void testContains() throws Exception {
        tester.contains(0L);
        verify(mockedSortedMap).containsKey(0L);
    }

    @Test
    public void testSize() throws Exception {
        tester.size();
        verify(mockedSortedMap).size();
    }

    @Test
    public void testPushUncompletedWork() throws Exception {
        tester.pushUncompletedWork(0);
        verify(mockedSortedMap).put(0L, false);
    }

    @Test
    public void testPushCompletedWork() throws Exception {
        tester.pushCompletedWork(0L);
        verify(mockedSortedMap).put(0L, true);
    }

    @Test
    public void testMarkCompleted() throws Exception {
        tester.markCompleted(0L);
        verify(mockedSortedMap).put(0L, true);
    }

    @Test
     public void testPopCompleted() throws Exception {
        Map.Entry mockedEntries = mock(Map.Entry.class);
        when(mockedEntries.getKey()).thenReturn(0L).thenReturn(1L).thenReturn(2L).thenReturn(4L);
        when(mockedEntries.getValue()).thenReturn(true).thenReturn(true).thenReturn(true).thenReturn(false);
        Set mockedSet = mock(Set.class);
        when(mockedSet.iterator()).thenReturn(Lists.newArrayList(mockedEntries,
                mockedEntries, mockedEntries, mockedEntries).iterator());
        when(mockedSortedMap.entrySet()).thenReturn(mockedSet);
        List<Long> readyItems = tester.popCompleted();
        assertEquals(Arrays.asList(0L, 1L, 2L), readyItems);
        verify(mockedEntries,times(3)).getKey();
        verify(mockedEntries, times(4)).getValue();
        readyItems.stream().forEach((item) -> {
            verify(mockedSortedMap).remove(item);
        });
    }

    @Test
    public void testPopCompletedWhenNoReadies() throws Exception {
        Map.Entry mockedEntries = mock(Map.Entry.class);
        when(mockedEntries.getKey()).thenReturn(0L).thenReturn(1L).thenReturn(2L).thenReturn(4L);
        when(mockedEntries.getValue()).thenReturn(false).thenReturn(true).thenReturn(false).thenReturn(true);
        Set mockedSet = mock(Set.class);
        when(mockedSet.iterator()).thenReturn(Lists.newArrayList(mockedEntries,
                mockedEntries, mockedEntries, mockedEntries).iterator());
        when(mockedSortedMap.entrySet()).thenReturn(mockedSet);
        List<Long> readyItems = tester.popCompleted();
        assertEquals(Collections.emptyList(), readyItems);
        verify(mockedEntries,times(0)).getKey();
        verify(mockedEntries, times(1)).getValue();
    }

    @Test
    public void testPopCompletedItemsWhenQueueIsEmpty() throws Exception {
        when(mockedSortedMap.entrySet()).thenReturn(Sets.newHashSet());
        List<Long> readyItems = tester.popCompleted();
        assertEquals(Collections.emptyList(), readyItems);
    }
}