keyvanakbary / medusa

Immutable and persistent collections for PHP

Medusa

Immutable and persistent collections for PHP.

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.

Installation

To install this library, run the command below and you will get the latest version

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))

medusa's Issues

Better explain the purpose of this project

First of all, thanks for publishing this project as open source and thanks for raising the awareness of these concepts in the PHP community.

My concern is that the README right now is aimed only at experts. If you already know these concepts, the README file is perfect because of the short usage snippets and the efficiency information. But if you are new to these concepts, you are totally lost.

Maybe this is intended and you want to keep away novices from your project (that's totally fine because not all projects are aimed for any kind of developer). But if you want to spread the usage of these concepts, it would be great if you could explain better the purpose of this project:

• What is exactly the problem that this project can help you solve?
• You say that this project helps you avoid "side-effects". Could you create a small PHP snippet showing these side-effects and then the solution that provides this project?
• The same goes for "easier to test" claim. Could you please publish a simple comparison between a hard to test PHP code and the easier alternative provided by this project?

Thanks again for creating this project and for publishing it as open source.