std/cache/lru

=encoding utf8

=head1 NAME

std/cache/lru - Pure ZuzuScript in-memory LRU cache.

=head1 SYNOPSIS

  from std/cache/lru import Cache;

  let cache := new Cache( capacity: 20 );

  let item := cache.get( "item-key", function ( item_key ) {
    # Called only on cache miss.
    return calculate_some_expensive_value( item_key );
  } );

  cache.empty();

=head1 IMPLEMENTATION SUPPORT

This module is supported by all implementations of ZuzuScript.

=head1 DESCRIPTION

This module provides a tiny in-memory least-recently-used (LRU)
cache written in pure ZuzuScript.

Keys are stored in an internal C<Dict>, and are assumed to be
strings. Values may be any ZuzuScript value.

=head1 EXPORTS

=head2 Classes

=over

=item C<< Cache({ capacity?: Number }) >>

Construct a cache with a maximum number of entries.
Returns: C<Cache>. Defaults to C<128>.

=item C<< cache.get(String item_key, Function producer) >>

Parameters: C<item_key> is a string key and C<producer> is a function
called on cache miss. Returns: value. Returns the cached value or stores
and returns C<producer(item_key)>.

=item C<< cache.peek(String item_key, fallback?) >>

Parameters: C<item_key> is a string key and C<fallback> is optional.
Returns: value. Returns the cached value without changing recency, or
C<fallback>/C<null> on a miss.

=item C<< cache.set(String item_key, value) >>

Parameters: C<item_key> is a string key and C<value> is any value.
Returns: value. Stores C<value> and marks it as recently used.

=item C<< cache.has(String item_key) >>

Parameters: C<item_key> is a string key. Returns: C<Boolean>. Returns
true if the cache currently contains C<item_key>.

=item C<< cache.size() >>

Parameters: none. Returns: C<Number>. Returns the current number of
cached entries.

=item C<< cache.capacity() >>

Parameters: none. Returns: C<Number>. Returns the configured maximum
number of entries.

=item C<< cache.empty() >>

Parameters: none. Returns: C<null>. Removes all entries from the cache.

=back

=head1 COPYRIGHT AND LICENCE

B<< std/cache/lru >> is copyright Toby Inkster.

It is free software; you may redistribute it and/or modify it under
the terms of either the Artistic License 1.0 or the GNU General Public
License version 2.

=cut


class Cache {
	let Number capacity := 128;
	let Dict _items := {};
	let Array _order := [];

	method __build__ () {
		die "Cache capacity must be greater than zero" if capacity <= 0;
	}

	method _drop_key_from_order ( String item_key ) {
		let kept := [];
		let i := 0;
		while ( i < _order.length() ) {
			let key := _order[i];
			if ( key ≢ item_key ) {
				kept.push(key);
			}
			i++;
		}
		_order := kept;
	}

	method _touch ( String item_key ) {
		self._drop_key_from_order(item_key);
		_order.push(item_key);
	}

	method _evict_if_needed () {
		while ( _order.length() > capacity ) {
			let oldest := _order.shift();
			if ( _items.exists(oldest) ) {
				_items.remove(oldest);
			}
		}
	}

	method set ( String item_key, value ) {
		_items.set( item_key, value );
		self._touch(item_key);
		self._evict_if_needed();
		return value;
	}

	method get ( String item_key, producer ) {
		if ( _items.exists(item_key) ) {
			self._touch(item_key);
			return _items.get(item_key);
		}

		die "Cache.get expects a producer Function" if not( producer instanceof Function );

		let value := producer(item_key);
		self.set( item_key, value );
		return value;
	}

	method peek ( String item_key, fallback? ) {
		if ( _items.exists(item_key) ) {
			self._touch(item_key);
			return _items.get(item_key);
		}

		return fallback;
	}

	method has ( String item_key ) {
		return _items.exists(item_key);
	}

	method size () {
		return _items.length();
	}

	method capacity () {
		return capacity;
	}

	method empty () {
		_items.clear();
		_order.clear();
		return self;
	}
}
Module
