# eviction-insertion-order

`software.visionary.cache:eviction-insertion-order:2026.10.13` · https://codeberg.org/caching/eviction-insertion-order

First-in-first-out and last-in-first-out cache eviction

<code>FirstInFirstOut</code> and <code>LastInFirstOut</code> are <code>EvictionStrategy</code>s that, when an <code>Insert</code> exceeds the capacity, remove the oldest or the newest earlier insertion, however often it was read.

## Rationale

**Why.** Some data ages by when it arrived, however often it is read.

## Key Concepts

### Insertion order

**Role.** A key's place is set by its first <code>Insert</code>. A <code>Hit</code>, a <code>Miss</code> or a repeated <code>Insert</code> leaves it there.

**Pattern.** STRATEGY, OBSERVER

## How It Works

**Guarantees.** No public parameter takes null and no public method returns it, declared with contrax's <code>@PreCondition(IsNotNull.class)</code> and <code>@PostCondition(IsNotNull.class)</code>.

**Thread safety.** An instance is not thread-safe: events must reach <code>update</code> one at a time.

## Lane

**Purpose.** Eviction where arrival order decides and reads must not change it.

**Alternative.** <code>eviction-recency</code> or <code>eviction-frequency</code> when a read should protect a key.

**When to avoid.** Workloads with popular keys: a key read constantly is still evicted in its turn.

## Usage

FirstInFirstOut, room for two: a leaves first despite its reads, then b

```java
import java.time.Instant;
import java.util.Map;
import java.util.Optional;
import java.util.function.Supplier;
import java.util.stream.Stream;
import software.visionary.cache.Cache;
import software.visionary.cache.capacity.fixed.FixedSize;
import software.visionary.cache.events.CacheEvent;
import software.visionary.cache.events.Evict;
import software.visionary.cache.eviction.insertion.order.FirstInFirstOut;
import software.visionary.cache.eviction.insertion.order.LastInFirstOut;
import software.visionary.cache.policy.CachePolicy;
import software.visionary.cache.topology.read.through.ReadThroughCacheFactory;
import software.visionary.events.Observer;

Map<String, Integer> source = Map.of("a", 1, "b", 2, "c", 3, "d", 4);
Supplier<Cache<String, Integer>> oldestLeaves = new ReadThroughCacheFactory<>(
        key -> Optional.ofNullable(source.get(key)),
        new CachePolicy<>(() -> new FixedSize<>(2), FirstInFirstOut::new, Instant::now));
Observer<CacheEvent<String, ?>> printEvictions = event -> {
    if (event instanceof Evict<String, ?> evicted) { System.out.println("evicted " + evicted.key()); }
};

var cache = oldestLeaves.get();
cache.add(printEvictions);
Stream.of("a", "b", "a", "a", "c", "d").forEach(cache::apply);

```

Output

```text
evicted a
evicted b
```

LastInFirstOut, same reads: a stays, and each new key replaces the one before it

```java
Supplier<Cache<String, Integer>> newestLeaves = new ReadThroughCacheFactory<>(
        key -> Optional.ofNullable(source.get(key)),
        new CachePolicy<>(() -> new FixedSize<>(2), LastInFirstOut::new, Instant::now));

var other = newestLeaves.get();
other.add(printEvictions);
Stream.of("a", "b", "a", "a", "c", "d").forEach(other::apply);

```

Output

```text
evicted b
evicted c
```

## Dependencies

- `software.visionary:cache:2026.10.13` at Compile
- `software.visionary.contrax:processor:2026.10.13` at Processor
- `software.visionary:junit-closure:2026.09.17` at Testing