Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A concept for lazy collections using copy-on-write (I think)
<?php
interface Collection
{
/**
* @return static
*/
function map(callable cb): Collection;
// filter
// reduce
// any
// all
// ...
}
/**
* An iterator that yields values modified by a callback, preserving keys.
*/
class MapIterator implements IteratorAggregate
{
private $collection;
private $callback;
public function __construct(Collection $collection, callable $callback)
{
$this->collection = $collection;
$this->callback = $callback;
}
public function getIterator()
{
foreach ($this->collection as $key => $value) {
yield $key => $this->callback($value);
}
}
}
/**
* An iterator that yields no values.
*/
class EmptyIterator implements IteratorAggregate
{
public function getIterator()
{
yield from [];
}
}
/**
* A collection that is backed by an iterator which is only evaluated as needed.
*/
abstract class LazyCollection implements IteratorAggregate, Collection
{
protected $iter;
public function __construct(Iterator $iter = null)
{
$this->iter = $iter ?? (new EmptyIterator);
}
/**
* Evaluates the remaining values in the iterator.
*
* @todo What happens when we rewind the iterator?
* @todo When we clone $this, what happens to the iterator?
*/
abstract protected function evaluate(): Iterator;
/**
* Create a copy if referenced more than once, otherwise return self.
*/
protected function copyOnWrite()
{
return (internal_refcount_func($this) > 1) ? clone $this : $this;
}
/**
* Generates a new collection from this collection keys and mapped values.
*
* @return static
*/
public function map(callable $cb): Collection
{
/* External */
$MapIterator = function (Collection $c) {
foreach ($collection as $index => $value) {
yield $index => cb($value);
}
};
return new static(new MapIterator($this));
}
}
/**
* Basic list, but lazy.
*/
final class LazyList extends LazyCollection
{
/**
* Internal storage.
*/
private $data = [];
/**
* Evaluates the remaining values in the iterator.
*/
protected function evaluate(): Iterator
{
for ($iter = $this->iter; $iter->valid(); $iter->next()) {
$value = $iter->current();
/* Add to the cache. */
$this->data[] = $value;
yield $value;
}
}
/**
* Appends a single value and returns the resulting Sequence, which could
* either be this instance or a clone.
*/
public function push($value): Sequence
{
$result = $this->copyOnWrite();
$result->data[] = $value;
return $result;
}
/**
* Yield from cached data first, then from the iterator, caching as we go.
*/
public function getIterator()
{
$index = 0;
foreach ($this->data as $value) {
yield $index++ => $value;
}
/* TODO: What happens when we rewind the iterator? */
foreach ($this->evaluate() as $value) {
yield $index++ => $value;
}
}
}
/**
* Basic set of distinct values.
*/
final class LazySet extends LazyCollection
{
/**
* Internal storage.
*/
private $data = [];
/**
* Evaluates the remaining values in the iterator.
*/
protected function evaluate(): Iterator
{
for ($iter = $this->iter; $iter->valid(); $iter->next()) {
$value = $iter->current();
/* Do not include the value if already cached. */
if (isset($this->data[$value])) {
continue;
}
/* Add to the cache. */
$this->data[$value] = true;
yield $value;
}
}
/**
* Adds a value to this Set if the value is not already in this Set.
*/
public function add($value): Sequence
{
/* Do not do anything at all if the operation has no effect. */
if (isset($this->data[$value])) {
return $this;
}
/* Evaluate the remaining values in the iterator */
foreach ($this->evaluate() as $candidate) {
if ($value === $candidate) {
return $this;
}
}
/* We are about to make an update, so check if we need to copy first. */
$result = $this->copyOnWrite();
/* Add the value to the set. */
$result->data[$value] = true;
return $result;
}
/**
* Determines if this Set contains the given value.
*/
public function has($value): bool
{
if (isset($this->data[$value])) {
return true;
}
/* Evaluate the remaining values in the iterator */
foreach ($this->evaluate() as $candidate) {
if ($value === $candidate) {
return true;
}
}
return false;
}
/**
* Iterator using a sequential index of the data store's keys as values.
*/
public function getIterator()
{
$index = 0;
foreach ($this->data as $value => $_) {
yield $index++ => $value;
}
foreach ($this->evaluate() as $value) {
yield $index++ => $value;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment