2017 © Pedro Peláez
 

library medusa

Immutable and persistent collections

image

keyvanakbary/medusa

Immutable and persistent collections

  • Wednesday, May 11, 2016
  • by keyvanakbary
  • Repository
  • 7 Watchers
  • 148 Stars
  • 7 Installations
  • PHP
  • 0 Dependents
  • 0 Suggesters
  • 12 Forks
  • 0 Open issues
  • 1 Versions
  • 0 % Grown

The README.md

Medusa

Build Status, (*1)

Immutable and persistent collections for PHP., (*2)

Life would be a lot simpler if we had immutable data structures. Code would be easier to understand, easy to test and free of side-effects. Being immutable is not all, these data structures must be efficient. By making them persistent, collections reuse internal structure to minimize the number of operations needed to represent altered versions of an instance of a collection., (*3)

Installation

To install this library, run the command below and you will get the latest version, (*4)

composer require keyvanakbary/medusa

Usage

Persistent Stack

$s = Medusa\Stack\PersistentStack::createEmpty();

$s1 = $s->push(1);
$s2 = $s1->pop();
echo $s1->peek();//1
echo $s2->peek();//Runtime exception

Complexity

operation big-O
push O(1)
peek O(1)
pop O(1)
isEmpty O(1)
count O(1)

Persistent Queue

$q = Medusa\Queue\PersistentQueue::createEmpty();

$q1 = $q->enqueue(1);
$q2 = $q1->dequeue();
echo $q1->peek();//1
echo $q2->peek();//Runtime exception

Complexity

operation big-O
isEmpty O(1)
peek O(1)
enqueue O(1)
dequeue O(1) in average, O(n) in some cases
count O(1)

Persistent AVL Tree

$t = Medusa\Tree\PersistentAvlTree::createEmpty();

$t1 = $t->add(1, 'one');
$t2 = $t1->remove(1);
echo $t1->search(1)->value();//one
echo $t2->lookup(1);//Runtime exception

Complexity

operation big-O
isEmpty O(1)
value O(1)
key O(1)
add O(1)
search O(log(n))
contains O(log(n))
height O(1)
lookup O(log(n))

Persistent Red-Black Tree

$t = Medusa\Tree\PersistentRedBlackTree::createEmpty();

$t1 = $t->add(1, 'one');
$t2 = $t1->remove(1);
echo $t1->search(1)->value();//one
echo $t2->lookup(1);//Runtime exception

Complexity

operation big-O
isEmpty O(1)
value O(1)
key O(1)
add O(1)
search O(log(n))
contains O(log(n))
height O(1)
lookup O(log(n))
min O(log(n))
removeMin O(log(n))

The Versions

11/05 2016

dev-master

9999999-dev

Immutable and persistent collections

  Sources   Download

MIT

The Requires

  • php >=5.5.0

 

The Development Requires

by Keyvan Akbary

collections persistent immutable data structures