PriorityLRUQueue

public class PriorityLRUQueue<K, Element> where K : Hashable

PriorityLRUQueue: Priority-aware LRU queue with O(1) average access and updates.

This data structure maintains separate LRU queues per priority level and evicts elements according to a two-tier policy:

  • By priority: lower priority values are evicted first

  • Within a priority: least-recently-used (LRU) elements are evicted first

Complexity

Complexity:

  • get/set/remove by key: O(1) average
  • eviction and priority promotion: O(1) average

  • Thread-safety: This type is not thread-safe on its own. Wrap usage with external synchronization (such as a semaphore) when accessed from multiple threads.

  • The maximum number of elements the queue can hold.

    Note

    Negative capacities are normalized to 0 in init(capacity:).

    Declaration

    Swift

    public let capacity: Int

  • The current number of elements in the queue.

    Declaration

    Swift

    public var count: Int { get }

  • Indicates if the queue is empty.

    Declaration

    Swift

    public var isEmpty: Bool { get }

  • Indicates if the queue is full.

    Declaration

    Swift

    public var isFull: Bool { get }

  • Initializes a new empty queue with specified capacity.

    Declaration

    Swift

    public init(capacity: Int)

    Parameters

    capacity

    Maximum elements allowed; negative values treated as zero.

  • Inserts or updates an element for the given key and priority.

    • Behavior:

      • If the key exists: updates its element and priority, and moves it to the front of its priority LRU.
      • If the queue is full: evicts from the lowest priority; within that level, evicts the LRU element.
      • If capacity == 0: returns the provided element (cannot be stored).

    Declaration

    Swift

    @discardableResult
public func setElement(_ element: Element, for key: K, with priority: Double = 0) -> Element?

    Parameters

    element

    The element to store.
    key

    The key to associate with the element.
    priority

    Eviction priority (lower priority evicted first). Default is 0.

    Return Value

    The evicted element, if any; or the input element if it could not be stored (for capacity 0 or lower priority than current minimum).

  • Retrieves the element for the given key and refreshes its LRU position.

    Declaration

    Swift

    @discardableResult
public func getElement(for key: K) -> Element?

    Parameters

    key

    The key to look up.

    Return Value

    The element if present; otherwise nil.

  • Removes the element for the given key, if present.

    Declaration

    Swift

    @discardableResult
public func removeElement(for key: K) -> Element?

    Parameters

    key

    The key to remove.

    Return Value

    The removed element, or nil if not found.

  • Removes and returns the least recently used element across all priorities.

    Declaration

    Swift

    @discardableResult
public func removeElement() -> Element?

    Return Value

    The removed element, or nil if the queue is empty.

  • Returns the key of the least recently used entry across all priorities.

    Declaration

    Swift

    public func getLeastRecentKey() -> K?

    Return Value

    The LRU key, or nil if the queue is empty.