Persistent waiting room

Question

This is an exercise to implement a waiting room for an hospital with the following requirements:

• Add (and remove) a patient to the queue of the waiting room
• Move a patient up and down the queue
• Show all patients in the queue
• The queue needs to be persisted

The WaitingRoom interface:

public interface WaitingRoom {
    Patient addPatient(Patient patient);

    Optional<Patient> removePatient();

    // Move a patient by delta positions in the queue.
    // E.g. if p1 is second in the queue, the operation 
    // move(p1,1) moves p1 to the first position.
    // Delta can be negative.
    void move(Patient patient, int delta);

    List<Patient> peekPatients();

    int size();

    void clear();
}

The Patient class:

@Getter
@Setter
@NoArgsConstructor
@Entity
@ToString
public class Patient {
    @Id
    @GeneratedValue
    private Long id;
    private String name;

    public Patient(String name) {
        this.name = name;
    }
}

This is the WaitingRoomService:

@Service
public class WaitingRoomService implements WaitingRoom {

    private EditableQueue<Patient> queue;

    public WaitingRoomService(PersistentQueue<Patient> queue) {
        this.queue = queue;
    }

    @Override
    public List<Patient> getAllPatients() {
        return queue.getAll();
    }

    @Override
    public Patient addPatient(Patient patient) {
        return queue.enqueue(patient);
    }

    @Override
    public Optional<Patient> removePatient() {
        return queue.dequeue();
    }

    @Override
    public void move(Patient patient, int delta) {
        queue.move(patient, delta);
    }

    @Override
    public int size() {
        return queue.size();
    }

    @Override
    public void clear() {
        queue.clear();
    }

}

EditableQueue is an interface implemented by PersistentQueue:

@Component
public class PersistentQueue<T> implements EditableQueue<T> {

    private NodeRepository<T> nodeRepo;

    public PersistentQueue(NodeRepository<T> nodeRepo) {
        this.nodeRepo = nodeRepo;
    }

    @Override
    public List<T> getAll() {
        return nodeRepo.findByOrderByPosition()
                .stream()
                .map(node -> node.getValue())
                .collect(Collectors.toList());
    }

    @Override
    @Transactional
    public T enqueue(T element) {
        Node<T> node = new Node<>(element);
        Optional<Node<T>> lastNode = nodeRepo.findByLastTrue();
        int newPosition = 0;
        if (lastNode.isPresent()) {
            newPosition = lastNode.get().getPosition() + 1;
            lastNode.get().setLast(false);
        } else {
            node.setFirst(true);
        }
        node.setPosition(newPosition);
        node.setLast(true);
        return nodeRepo.save(node).getValue();
    }

    @Override
    @Transactional
    public Optional<T> dequeue() {
        if (size() == 0) {
            return Optional.empty();
        }
        Optional<Node<T>> first = nodeRepo.findByFirstTrue();
        Optional<Node<T>> second = nodeRepo.findByPosition(first.get().getPosition() + 1);
        if (second.isPresent()) {
            second.get().setFirst(true);
        }
        nodeRepo.deleteById(first.get().getId());
        return Optional.of(first.get().getValue());
    }

    @Override
    @Transactional
    public void move(T element, int delta) {
        Node<T> toMove = nodeRepo.findByValue(element).get();
        int newPosition = toMove.getPosition() - delta;
        int next = delta > 0 ? toMove.getPosition() - 1 : toMove.getPosition() + 1;
        int start, end = 0;
        if (delta > 0) {
            start = newPosition;
            end = next;
        } else {
            start = next;
            end = newPosition;
        }
        for (Node<T> n : nodeRepo.findAllByPositionBetween(start, end)) {
            if (delta > 0) {
                // swap head with node to move
                if (n.isFirst()) {
                    n.setFirst(false);
                    toMove.setFirst(true);
                }
                // swap tail with node to move
                if (toMove.isLast() && n.getPosition() == next) {
                    toMove.setLast(false);
                    n.setLast(true);
                }
            } else {
                if (n.isLast()) {
                    n.setLast(false);
                    toMove.setLast(true);
                }
                if (toMove.isFirst() && n.getPosition() == next) {
                    toMove.setFirst(false);
                    n.setFirst(true);
                }
            }
            n.setPosition(delta > 0 ? n.getPosition() + 1 : n.getPosition() - 1);
        }
        toMove.setPosition(newPosition);

    }

    @Override
    public int size() {
        return (int) nodeRepo.count();
    }

    @Override
    public void clear() {
        nodeRepo.deleteAll();
    }

}

NodeRepository:

interface NodeRepository<T> extends JpaRepository<Node<T>, Long> {

    List<Node<T>> findByOrderByPosition();

    Optional<Node<T>> findByPosition(int position);
    
    Optional<Node<T>> findByValue(T value);

    Optional<Node<T>> findByFirstTrue();
    
    Optional<Node<T>> findByLastTrue();
    
    List<Node<T>> findAllByPositionBetween(int start, int end);
}

A Node is an element of EditableQueue and a wrapper for Patient:

@Getter
@Setter
@NoArgsConstructor
@Entity
@ToString
public class Node<T> {
    @Id
    @GeneratedValue
    private Long id;
    @OneToOne(cascade = CascadeType.PERSIST, targetEntity = Patient.class)
    private T value;
    private int position;
    private boolean first;
    private boolean last;

    public Node(T value) {
        this.value = value;
        this.position = -1;
    }
}

Finally, the tests:

@SpringBootTest
public class WaitingRoomServiceTest {

    @Autowired
    private WaitingRoom waitingRoom;

    @BeforeEach
    public void clearRoom() {
        waitingRoom.clear();
    }

    @Test
    public void enqueueDequeueTest() {
        waitingRoom.addPatient(new Patient("Marc"));
        waitingRoom.addPatient(new Patient("Anna"));

        assertTrue(waitingRoom.size() == 2);
        assertEquals("Marc", waitingRoom.removePatient().get().getName());
        assertTrue(waitingRoom.size() == 1);
        assertEquals("Anna", waitingRoom.removePatient().get().getName());
        assertTrue(waitingRoom.size() == 0);
    }

    @Test
    public void moveTest() {
        waitingRoom.addPatient(new Patient("p1"));
        waitingRoom.addPatient(new Patient("p2"));
        Patient p3 = waitingRoom.addPatient(new Patient("p3"));
        waitingRoom.addPatient(new Patient("p4"));

        // Move p3 up by 1 position
        waitingRoom.move(p3, 1);

        assertEquals("p1", waitingRoom.removePatient().get().getName());
        assertEquals("p3", waitingRoom.removePatient().get().getName());
        assertEquals("p2", waitingRoom.removePatient().get().getName());
        assertEquals("p4", waitingRoom.removePatient().get().getName());
        assertTrue(waitingRoom.size() == 0);
    }
    
    @Test
    public void moveTest2() {
        waitingRoom.addPatient(new Patient("p1"));
        waitingRoom.addPatient(new Patient("p2"));
        Patient p3 = waitingRoom.addPatient(new Patient("p3"));
        Patient p4 = waitingRoom.addPatient(new Patient("p4"));
        waitingRoom.addPatient(new Patient("p5"));

        // Move p3 up by 2 position
        waitingRoom.move(p3, 2);
        // Move p4 down by 1 position
        waitingRoom.move(p4, -1);
        
        assertEquals("p3", waitingRoom.removePatient().get().getName());
        assertEquals("p1", waitingRoom.removePatient().get().getName());
        assertEquals("p2", waitingRoom.removePatient().get().getName());
        assertEquals("p5", waitingRoom.removePatient().get().getName());
        assertEquals("p4", waitingRoom.removePatient().get().getName());
        assertTrue(waitingRoom.size() == 0);
    }
    
    @Test
    public void moveTest3() {
        waitingRoom.addPatient(new Patient("p1"));
        Patient p2 = waitingRoom.addPatient(new Patient("p2"));

        waitingRoom.move(p2, 1);
        waitingRoom.move(p2, -1);
        
        assertEquals("p1", waitingRoom.removePatient().get().getName());
        assertEquals("p2", waitingRoom.removePatient().get().getName());
        assertTrue(waitingRoom.size() == 0);
    }
    
    @Test
    public void moveTest4() {
        waitingRoom.addPatient(new Patient("p1"));
        Patient p2 = waitingRoom.addPatient(new Patient("p2"));
        waitingRoom.addPatient(new Patient("p3"));
        waitingRoom.addPatient(new Patient("p4"));

        waitingRoom.removePatient();
        waitingRoom.move(p2, -1);
        
        assertEquals("p3", waitingRoom.removePatient().get().getName());
        assertEquals("p2", waitingRoom.removePatient().get().getName());
        assertEquals("p4", waitingRoom.removePatient().get().getName());
        assertTrue(waitingRoom.size() == 0);
    }

    @Test
    public void stressTest() {
        int n = 1000;
        
        long startTime = System.nanoTime();
        for (long i = 1; i < n; i++) {
            waitingRoom.addPatient(new Patient("p" + i));
        }
        long endTime = System.nanoTime();
        System.out.format("Enqueue %d time: %d ms%n", n, (endTime - startTime) / 1000000);
        
        startTime = System.nanoTime();
        for (long i = 1; i < n; i++) {
            waitingRoom.removePatient();
        }
        endTime = System.nanoTime();
        System.out.format("Dequeue %d time: %d ms%n", n, (endTime - startTime) / 1000000);

        assertTrue(waitingRoom.size() == 0);
    }

    @Test
    public void getAllPatientsTest() {
        waitingRoom.addPatient(new Patient("p1"));
        waitingRoom.addPatient(new Patient("p2"));
        waitingRoom.addPatient(new Patient("p3"));

        List<Patient> patients = waitingRoom.getAllPatients();

        assertEquals("p1", patients.get(0).getName());
        assertEquals("p2", patients.get(1).getName());
        assertEquals("p3", patients.get(2).getName());
    }
}

The GitHub repo is here for further details.

This is how the method move works. Every node in the queue has a position:

• n1=0: head
• n2=1
• n3=2
• n4=3
• n5=4: tail

Calling the method move(n4,2) means moving the node n4 up by 2 positions. It does it in two actions:

1. Increment by 1 the nodes n3 and n2: n1=0, n2=2, n3=3, n4=3, n5=4
2. Set the position of n4 to n4.position - delta (that is 3-2=1): n1=0, n2=2, n3=3, n4=1, n5=4

Sorting by position, the nodes are now: n1, n4, n2, n3, n5.

Every time the method move needs to update the positions of the nodes in the database, can it be improved? Or can EditableQueue be implemented more efficiently?

Any feedbacks, improvements or alternative solutions are welcome. Thanks.

Answer 1

You didn't include NodeRepo so I'm assuming you're working with JPQL.

Reduce redundancy

One of the first things I was taught in database design was to avoid redundant data. Packing the first/last status to each node is entirely redundant and can easily lead to situations where your queue has more than one head or tail. You would also need an index on both columns as that status is a main search criteria in your queries. I assume the need for those columns came from not having a dedicated entity for the Queue. It would be okay to have a Queue entity just for holding the first/last references. It would also allow you to have more than one queue in your database, but that would make the data structure a bit more complicated so let's leave that for future.

Remove unnecessary data

But regardless of the Queue entity the first/last information is however completely unnecessary, since you also have the ordinal number on each node. Because that column also needs an index, you can do the first/last query efficiently with order by and limit.

SELECT * FROM Node
ORDER BY position
LIMIT 1

The database will optimize this to an O(1) operation. Once you have that, you don't need to juggle the first/last status of each node when manipulating the queue.

Reduce unnecesary writes

I'm not sure if you even need the ordinal numbers to be a continuous set. When moving a node, you can query an ordered list of nodes where ordinal number is less than or greater than the node being moved, limited by "absolute value of delta plus one". If the returned list is smaller than the limit, then you know you're moving to first/last and don't have to touch the values of nodes in between (unless you hit over/underflow of course :)).

Optimize data structure

If moves are frequent, you can then optimize the solution to your particular use case by using increments greater than one and use the gaps so that you can move a node between two others without having to always touch the values in the surrounding nodes. For example, if ordinal values are 10, 20 and 30, moving 30 one forward only requires it's ordinal value to be set to 15. (This is, BTW, how we moved code in C64 Basic when we did refactoring).

Ensure consistency

Removing the first/last column however adds complexity to concurrency management. Since you're not getting a write lock to the current last node, you run the risk of getting two nodes with the same ordinal number when adding to the end of the queue. You can do optimistic locking by configuring the ordinal number column to be unique (well it should be unique anyway) and simply retrying a write operation if one fails due to a constraint violation. Whether his is more efficient than pessimistic locking depends on your normal use case.

Minimize data needing to be read

You've made the correct choice of separating the Node and Patient data from each other so you don't need to load all patient info when manipulating the queue. However you missed a bit: default loading type for OneToOne relation is eager so you will still be loading the patient info every time you load a node. You should change the loading type between Node and Patient to lazy.

BTW, having a parameterized Node type seems a bit unnecessary since the relation annotation binds it to Patient.class. The type parameter at least should reflect the fact that the entity must be a Patient.