A high-performance Java library providing Deques with Set uniqueness and Map lookups in O(1) time.

Standard Java collections require trade-offs between different capabilities:

• LinkedHashSet maintains insertion order and uniqueness but doesn't implement Deque
• ArrayDeque provides efficient deque operations but allows duplicates and arbitrary remove is O(n).
• LinkedHashMap offers ordered key-value pairs but lacks deque-style access to entries

This library bridges these gaps by providing collections that combine the ordering and uniqueness properties of hash-based collections with the full interface and performance characteristics of deques.

This library provides two families of collection types: standard deques and step-priority deques.

1. HashSetDeque<E>: A Deque<E> with unique elements providing O(1) contains/remove operations. Think of it as a LinkedHashSet with complete deque functionality.
2. HashMapDeque<K, V>: A Deque<Entry<K, V>> which behaves like a Map<K, V>, and provides O(1) key-based operations alongside complete deque functionality on entries.

These collections behave like priority deques, ordering elements by discrete priority levels. Their key feature is the ability to move an element to an adjacent priority level. Crucially, they remain fully-compliant Deques: in the absence of priority changes, they behave exactly like a standard deque, ensuring compatibility with existing algorithms.

1. StepPriorityHashSetDeque<E>: A Deque<E> similar to HashSetDeque<E> but with the step-priority enhancement, providing incrementPriority/decrementPriority operations in O(1) time.
2. StepPriorityHashMapDeque<K, V>: A Deque<Entry<K, V>> similar to HashMapDeque<K, V> but with the step-priority enhancement, providing incrementPriority/decrementPriority operations in O(1) time.

Java 21 introduced SequencedSet and SequencedMap interfaces, which LinkedHashSet and LinkedHashMap now implement. These provide useful methods like addFirst(), addLast(), getFirst(), and getLast().

The key distinction is in the primary interface contract:

• Sequenced collections are Sets/Maps first, with some ordering operations
• Hash Deque collections are Deques first, with uniqueness/lookup guarantees

HashSetDeque implements the complete java.util.Deque interface, including stack operations (push, pop) and queue operations (poll, peek) that SequencedSet does not provide. Similarly, HashMapDeque also implements the complete java.util.Deque interface, offering compatibility with abstract deque algorithms that SequencedMap does not.

Choose sequenced collections when you need a Set or Map with some ordering capabilities. Choose Hash Deque when you need full deque functionality with performance guarantees and some Set/Map functionalities.

<dependency>
    <groupId>dev.lucasmdjl</groupId>
    <artifactId>hash-deque</artifactId>
    <version>0.3.0</version>
</dependency>

implementation 'dev.lucasmdjl:hash-deque:0.3.0'

import dev.lucasmdjl.hashdeque.SetDeque;
import dev.lucasmdjl.hashdeque.HashSetDeque;

class TaskManager {
  SetDeque<String> tasks = new HashSetDeque<>();
  
  public void run() {
    // Add elements to the end
    tasks.addLast("first-task");  // returns true
    tasks.addLast("second-task"); // returns true

    // Duplicates are ignored (Set behavior)
    boolean wasAdded = tasks.offerLast("first-task"); // returns false
    System.out.println(tasks.size()); // Output: 2

    // Add to the front (Deque behavior)
    tasks.addFirst("urgent-task");

    // Fast containment checks
    if (tasks.contains("second-task")) {
      System.out.println("Task is pending");
    }

    // Iterate in insertion order
    // Output: urgent-task, first-task, second-task
    tasks.forEach(System.out::println);
  }
}

import dev.lucasmdjl.hashdeque.MapDeque;
import dev.lucasmdjl.hashdeque.HashMapDeque;

record User(int id, String name) {}

class SessionManager {
  MapDeque<Integer, User> userQueue = new HashMapDeque<>();
  
  public void run() {
    // Add users using the convenient (K, V) overload
    userQueue.addLast(101, new User(101, "Alice"));
    userQueue.addLast(102, new User(102, "Bob"));

    // Fast key-based lookups
    User user = userQueue.get(101); // O(1) lookup
    System.out.println("Found user: " + user.name());

    // Update without changing position
    userQueue.update(102, (id, oldUser) -> new User(id, "Robert"));

    // Process first user
    MapDeque.Entry<Integer, User> processed = userQueue.pollFirst();
    System.out.println(processed.getValue().name() + " processed");
  }
}

import dev.lucasmdjl.hashdeque.StepPriorityMapDeque;
import dev.lucasmdjl.hashdeque.StepPriorityHashMapDeque;

record Job(String id, String description) {}

class JobScheduler {
  // Use Integer for priority, where higher numbers mean higher priority
  StepPriorityMapDeque<String, Job, Integer> scheduler = new StepPriorityHashMapDeque<>();
  
  public void run() {
    // The addLast method is a convenient way to add with the lowest priority.
    scheduler.addLast("job-1", new Job("job-1", "Generate report"));
    scheduler.addLast("job-2", new Job("job-2", "Send emails"));
    scheduler.addLast("job-3", new Job("job-3", "Archive data"));

    // An urgent job comes in, escalate its priority
    System.out.println("Escalating job-3...");
    scheduler.incrementPriority("job-3"); // O(1) operation

    // Now escalate job-2. It also moves to the higher priority level,
    // placed after job-3 because it was escalated second.
    System.out.println("Escalating job-2...");
    scheduler.incrementPriority("job-2");

    // Process the highest priority job
    // pollFirst() removes and returns the entry with the highest priority
    var processedJob = scheduler.pollFirst();
    // Output: job-3
    System.out.println("Processing: " + processedJob.getKey()); 

    // The next highest priority job is now job-2.
    processedJob = scheduler.pollFirst();
    // Output: job-2
    System.out.println("Processing: " + processedJob.getKey());

    // ... and finally, job-1.
    processedJob = scheduler.pollFirst();
    // Output: job-1
    System.out.println("Processing: " + processedJob.getKey());
  }
}

*Amortized time

**Performs a shallow clear. To prevent memory leaks when using clearFast, use MapDeque.Entry.copyOf(entry) to detach any entry that needs to outlive its MapDeque.

For a quantitative performance comparison with the JDK 21 Sequenced Collections, see the benchmarks.

• High Performance: Amortized O(1) for all core operations
• Dual Ordering Strategies: Choose between insertion-order or dynamic priority-order.
• Uniqueness: Guarantees element uniqueness for the Set versions and key uniqueness for the Map versions.
• Predictable Order: Stable and predictable iteration order, even within the same priority level.
• Full Interface Compliance: Implementations are fully compliant with Deque, ensuring seamless integration with existing code.
• Modern Java: Requires Java 11+, null-safe design (prohibits null elements and keys/values)
• Thoroughly Tested: Over 1,000 comprehensive tests

This project is licensed under the Mozilla Public License 2.0. See the LICENSE file for details.