fifo_rank
def
The rank of a page in a FIFO queue of size k, ranging from 1 for the oldest page (next to be evicted) to k for the most recently fetched page, or 0 if absent.
Statement
def fifo_rank {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (x : α) : ℕ
- Defined in
- arXiv:2610.18767 Section 3.2
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 1
- FifoQueueA first-in first-out (FIFO) cache queue of capacity k over page type α, represented as a duplicate-free list of length k.
- Used by 5
- rank_potential_offline_fetch_boundAt an offline fetch, the increase in rank potential is at most k (Lemma 3.3(i)).
- rank_potentialThe rank potential function Φ for FIFO paging, defined as the sum of ranks of all pages currently in the online FIFO cache but absent from…
- rank_potential_zero_of_subsetIf all pages in the online FIFO cache are present in the offline cache, the rank potential Φ is zero; in particular, the initial potential…
- rank_potential_online_payment_boundFor any type α with decidable equality, any k ≥ 1, any FIFO queue q of capacity k, any offline cache cOpt of cardinality k, and any page v…
- rank_potential_offline_evict_hole_boundAt an offline fetch, if the evicted page is outside the online cache, the change in rank potential is at most 0 (Lemma 3.3(ii)).
Read back from the Lean
For a type α with decidable equality, a natural number k, a FIFO queue q : FifoQueue α k, and an element x : α, fifo_rank q x is defined as the natural number equal to q.pages.idxOf x + 1 (one plus the 0-based index of x in q.pages) if x ∈ q.pages, and 0 otherwise.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Rank of a page in the FIFO queue from 1 (oldest) to k (newest). -/ def fifo_rank {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (x : α) : ℕ := if x ∈ q.pages then q.pages.idxOf x + 1 else 0