// Minimal bounded LRU cache, used by `ConsistentHash` when it is constructed
// with `cache=...`.
//
// Lookups and insertions are amortized O(1).  A doubly linked list would relink
// pointers on every hit; instead this cache appends the key to `order` again
// and remembers the newest position in `latest`.  `head` walks forward past
// superseded positions, and `compact` rewrites `order` once enough stale
// entries have piled up.

///|
struct LruCache[T] {
  max : Int
  values : Map[String, T]
  mut order : Array[String]
  mut latest : Map[String, Int]
  mut head : Int
}

///|
fn[T] LruCache::new(max : Int) -> LruCache[T] {
  { max, values: Map([]), order: [], latest: Map([]), head: 0, }
}

///|
/// Read `key` and refresh its recency.
fn[T] LruCache::get(self : LruCache[T], key : String) -> T? {
  match self.values.get(key) {
    None => None
    Some(value) => {
      self.mark_used(key)
      Some(value)
    }
  }
}

///|
/// Insert or update `key`, evicting the least recently used entry if the cache
/// grew past its bound.
fn[T] LruCache::set(self : LruCache[T], key : String, value : T) -> Unit {
  let existed = self.values.contains(key)
  self.values.set(key, value)
  self.mark_used(key)
  if !existed && self.values.length() > self.max {
    self.evict()
  }
}

///|
fn[T] LruCache::mark_used(self : LruCache[T], key : String) -> Unit {
  self.latest.set(key, self.order.length())
  self.order.push(key)
}

///|
/// Drop the oldest live entry in `order`.
fn[T] LruCache::evict(self : LruCache[T]) -> Unit {
  while self.head < self.order.length() {
    let key = self.order[self.head]
    if self.latest.get(key) == Some(self.head) {
      self.values.remove(key)
      self.latest.remove(key)
      self.head = self.head + 1
      break
    }
    self.head = self.head + 1
  }
  self.compact()
}

///|
/// Rewrite `order` with the live keys only, in recency order, once the stale
/// prefix dominates the queue.
fn[T] LruCache::compact(self : LruCache[T]) -> Unit {
  if self.head > 64 && self.head * 2 > self.order.length() {
    let live : Array[String] = []
    for i = self.head; i < self.order.length(); i = i + 1 {
      let key = self.order[i]
      if self.latest.get(key) == Some(i) {
        live.push(key)
      }
    }
    self.order = live
    self.latest = Map([])
    for i = 0; i < live.length(); i = i + 1 {
      self.latest.set(live[i], i)
    }
    self.head = 0
  }
}

///|
/// Forget every entry.
fn[T] LruCache::clear(self : LruCache[T]) -> Unit {
  self.values.clear()
  self.order.clear()
  self.latest.clear()
  self.head = 0
}