Would be nice to show how some common tasks can be achieved with appropriate structures.

The best way I can think of doing this is to keep track of the number of active iterators on the structure, and check if this is > 0 when modifying the structure (during push, remove etc). This will incur a small amount of overhead.

The other question is what to do when that number is > 0?

• throw an exception
• create a warning

It's currently possible to modify / update a collection during iteration. This leads to undefined behaviour, because the internal iterator is not aware of these modifications. There are three possible solutions here:

1. Keep a modcount, throw exception during iterator validation if modcount is different.
2. Keep an iterator count on the structure, and throw an exception during updates if > 0.
3. Leave as is, it's the user's responsibility to be sensible.

Could also just raise a warning instead of throwing an exception.

@krakjoe, curious to hear your thoughts. 💡

Currently using iterators, could iterate on the internal structures directly.

I compiled and installed the package (as described in README.md). Then I checked phpinfo() and I cannot find any details about ds (except it is enabled).

Register package on packagist for installation via composer.
It can be used for highlights in IDE in dev environment.

See #4

Python example:

a = dict()
a['a'] = 3
a['b'] = 2
a['c'] = 1

print a

{'a': 3, 'c': 1, 'b': 2}

I had this implemented very very early when php-ds was still private, where the structures would echo something similar to JSON. Values that could not be converted to strings had default fallbacks like object(stdClass)#1 and resource(type)#1.

I imagine the above equivalent would echo something like:

{'a': 3, 'b': 2, 'c': 1}

I'm not sure what it would look like, but a PriorityQueue that could be reused, without cloning, may be useful.

Primary use case that I can think of would be priority based event aggregators. Cloning works, but has a significant cost for doing so.

• each(callable): bool stops on false, returns if finished
• any([callable]): bool whether any values pass the test or are true if no test
• shuffle(): void shuffles the map
• partition([callable]) values that pass to the front, others to the back.
• pluck(mixed, mixed): Sequence|Map access each by key, creates a new sequence.
• only(keys): Map only keep certain keys
• groupBy(mixed key): Map groups values by given key.
• swap
• update(key, callable)

• Don't allow null as key
• Array hash should be the array's length, because the current hash value is O(n)
• Hashable's equals should receive the key as is, don't enforce type of class.

New (and awsome) data structures but still php, this should work 😋

<?php
class Foo {
    public $bar;
    public function __construct($bar) {
        $this->bar = $bar;
    }
}

$set = new \Ds\Set;
for ($i = 0; $i<=9; $i++) {
    $set[] = new Foo($i);
}
foreach ($set as $key => $value) {
    echo $value->bar;
}
echo PHP_EOL;
foreach ($set as $key => $value) {
    echo $value->bar;
    $set->remove($value);
}
echo PHP_EOL;
var_dump($set);

0123456789
01234
object(Ds\Set)#1 (5) {
  [0]=>
  object(class@anonymous)#7 (1) {
    ["bar"]=>
    int(5)
  }
  [1]=>
  object(class@anonymous)#8 (1) {
    ["bar"]=>
    int(6)
  }
  [2]=>
  object(class@anonymous)#9 (1) {
    ["bar"]=>
    int(7)
  }
  [3]=>
  object(class@anonymous)#10 (1) {
    ["bar"]=>
    int(8)
  }
  [4]=>
  object(class@anonymous)#11 (1) {
    ["bar"]=>
    int(9)
  }
}

All structures share the same global FCI, so if while sorting something you try to sort something else, things will break. The best way to handle this is to save the current FCI, use it, then restore it.

This reduces the number of allocations and indirection.

Instead of

typedef struct _php_ds_map_t {
    zend_object  std;
    ds_map_t    *map;
} php_ds_map_t;

use

typedef struct _php_ds_map_t {
    zend_object  std;
    ds_map_t     map;
} php_ds_map_t;

array_reverse returns a reversed copy, but you can't reverse an array in place (without doing it manually). Something as common as reversing a sequence would benefit from the option of not creating a copy of the sequence.

It appears that allocated space is not being freed resulting in large memory usage. I believe entire object graphs are staying around when stored in sets.

I've tested these classes that all seem to have the problem:

• Set
• Map
• Stack
• Queue
• Deque

Notes: Neither calling clear() on the set nor the use of gc_collect_cycles() frees any memory.

Example reproduction:

$original = memory_get_usage(true);

for ($i = 0; $i < 10000000; $i++) {
    new \Ds\Set(["A", "B"]);
}

echo memory_get_usage(true) - $original, " additional bytes allocated\n";

Output:

79691776 additional bytes allocated

Environment:

• PHP DS compiled from master
• PHP 7.0.9 64-bit
• macOS 10.11.6 / Ubuntu 14.04

Edit: 10x iteration count + output changes to showcase larger memory footprint

Wondering what sort of support (both paid and unpaid) you see yourself doing for this repository, unless PHP accepts your extension as-is (or almost as-is).

The reason is because anyone grabbing this today may be taking a risk in doing so, because the PHP implementation does not perform as well as PHP's objects or arrays so it cannot act as an exact replacement, and it may be possible this extension stops working with any major release of PHP in the future like 7.1.

Like any library, there is a risk of deprecation in a large code base and normally such a thing does not get fixed for a while as it 'still works'. The problem is that with PHP extensions the code can simply stop working when a PHP upgrade is nearly required (when PHP 7.0.x gets deprecated) if the API becomes incompatible.

each(callable): bool stops on false, returns if finished

• Polyfill
• Extension
• Tests

some([callable]): bool whether any values pass the test or are true if no test

• Polyfill
• Extension
• Tests

shuffle(): void shuffles the sequence

• Polyfill
• Extension
• Tests (should be able to use seed)

partition([callable]): void values that pass to the front, others to the back.

• Polyfill
• Extension
• Tests

pluck(mixed key): Sequence access each by key, creates a new sequence.

• Polyfill
• Extension
• Tests

groupBy(mixed key): Map groups values by given key.

• Polyfill
• Extension
• Tests

splice(int, int, iterable): Sequence implementation of array_splice

• Polyfill
• Extension
• Tests

swap(int, int): void Swaps two values by index

• Polyfill
• Extension
• Tests

each(callable): bool stops on false, returns if finished

• Polyfill
• Tests
• Extension

some([callable]): bool whether any values pass the test or are true if no test

• Polyfill
• Tests
• Extension

every([callable]): bool whether all values pass the test or are true if no test

• Polyfill
• Tests
• Extension

shuffle(): void shuffles the set

• Polyfill
• Tests
• Extension

partition([callable]): void values that pass to the front, others to the back.

• Polyfill
• Tests
• Extension

pluck(mixed key): Sequence access each by key, creates a new set.

• Polyfill
• Tests
• Extension

groupBy(mixed key): Map groups values by given key.

• Polyfill
• Tests
• Extension

swap(int, int)

• Polyfill
• Tests
• Extension

isset(index)
unset(index)

See #8

This applies to all current and future variations of find.

Would be a heap using an optional comparator function (max heap by default). PriorityQueue already uses a heap internally so we could extend that and create a dedicated implementation, potentially replacing PriorityQueue entirely.

This is so that it's possible to call the array access functions directly, even though no one should ever need to do that.

• Test calling the offset* functions as well.

I've run into a case where I have sets that contain hashable objects which themselves contain sets and hashable objects.¹ The equals function on \Ds\Hashable necessitates adding an equals() method. To do this I ensure this I xor the two sets and check that the resulting set has no elements.²

However, it appears that this freezes when:

• objects have the same hash.
• AND the objects are checked for equality by their identity using ===

I've got a test case here. The only reason I didn't PR this one is it is seemingly fragile. I tried porting it over and it didn't fail. Not sure why that is.

class PauseTest extends PHPUnit_Framework_TestCase
{
    /** @test */
    public function doesnt_freeze_when_adding_items_to_a_set()
    {
        $a = new Container([new Box(0)]);
        $b = new Container([new Box(0)]);

        new Ds\Set([$a, $b]);
    }
}

final class Container implements Ds\Hashable
{
    public $items;

    public function __construct($items) { $this->items = new Ds\Set($items); }
    public function hash() { return 0; }
    public function equals($obj) : bool { return $this->items->xor($obj->items)->count() === 0; }
}

class Box implements Ds\Hashable
{
    private $id;

    public function __construct($id) { $this->id = $id; }
    public function equals($obj) : bool { return $this === $obj; }
    public function hash() { return $this->id; }
}

1. Could we have Hashable sets built-in? That'd be awesome!
2. I realize now that this logic is flawed… oops. Hey, at least I found a bug!

We currently allow allocation via allocate(int $capacity), but we don't check for overflow or have a maximum capacity. @nikic also mentioned that we should be using the safe_* variants when multiplying sizeof by a variable capacity.

Iteration by reference is not supported, so this should take care of the following use case:

foreach ($collection as &$value) {
    // Do something with $value
}

$collection->apply(function($value) {
    // Return what value should become
});

Currently the only documentation is the PHP include files (for IDE autocompletion etc). The plan is to create a complete * DocBook* as part of an official release.

See:

• http://doc.php.net/phd/docs/
• https://www.sammyk.me/how-to-contribute-to-php-documentation

There is currently two ways to construct a structure:

Namespaced, using new

$map = new \Ds\Map();

Advantages:

• Expected
• Namespaced

Global namespace, static

$map = ds::map();

Advantages:

• Can use all structures with use ds;.
• Can be chained without enclosing parentheses, ie. no (new Map())->reverse().
• Resembles C++ syntax.

Would it be better, for the sake of consistency, to keep to either one or the other? And if so, which?

The differences between Deque and Vector might be considered small enough to consider removing Vector and Sequence, and rename Deque to Sequence.

Advantages of Deque:

• O(1) unshift and shift

Advantages of Vector:

• 1.5x growth factor yields less average memory used than Deque's 2.0x
• Slightly faster access time due to not having to translate into the buffer.

Sequence is also the only interface below Collection.

The important question is: is it clear enough when you would use one over the other?

These have been implemented for Sequence, but not the others.

Hello,

This is AWESOME! I have few questions:

1. Why did you use "\Ds" namespace, why not "\DataStructure"? It is more explanatory, I know it is related to coding style, but I can not see reason why did you use abbreviation...
2. It seams that Binary Tree, Balanced Binary Tree and maybe B+ Tree is missing... Did you planned to add these data structures as well?
3. This is most important - there is no alternative pure PHP implementation. I believe that popularity of this PHP extension depends on alternative pure PHP implementation. To explain this, here is the example: via Composer, I would include in my project pure PHP implementation of your data structures. In one point of time, in order to speed my application, I will remove pure PHP implementation and install dedicated PHP extension.

What is scary about PHP extensions that you can have a project which requires upgrade of PHP and some of the extensions are not easy to recompile for upgraded version.

Here is the example: https://github.com/AOP-PHP/AOP this was AWESOME extension, pure awesomeness... However, every library that depends on this extension is scr***ed, unusable.

There are awesome extensions out there for PHP, like this one - but do have in mind that we are scared that things can go wrong as for AOP extension. Pure PHP implementation would ensure us that there is fail safe strategy.

Thanks for your time. Hope you find these suggestions and questions useful.

This would be an immutable, array access zval buffer which would serve as the groups in operations such as groupBy. Instead of a Map<mixed, Sequence> it would be Map<mixed, Tuple>. It would be very easy to convert those tuples into sequences if you need the extra mutability and functionality.

$map->groupBy('key')->apply('sequence'); // assuming sequence is a function

$map->groupBy('key')->apply(function($key, $value) {
    return new Sequence($value);
});

API I'm thinking of is basically:

• __construct(iterable|array)
• get(int)
• toArray()
• count()
• clear() ??
• isEmpty() ??

I would like to manage releases and installation through PECL. I'm not sure what is involved exactly, but will take a look at it when the docs at #5 are completed.

@krakjoe might be a good thing to chat about.

Whilst trying to calculate a set of mutations the xor operation hangs

I expect $removalChangeSet to contain only ['member']

I'm using DS 1.0.4 extension on OSX

require 'vendor/autoload.php';

$roles             = new \Ds\Set(['guest', 'member']);
$requestedRemovals = new \Ds\Set(['member', 'nothing']);

$keepSet          = $roles->diff($requestedRemovals);
$removalChangeSet = $roles->xor($keepSet);

var_dump($removalChangeSet->toArray());

What's the best way to do this?

The main reason for this is to be able to indicate an invalid key. For example, Map::find(mixed $value): mixed $key would be ambiguous if either false or null indicates that a key could not be found. It doesn't make enough sense to have a null key, so we should just disallow it entirely and throw an exception when a null key is used.

I'm trying to separate the "internal" structures from all the zend stuff (zend_object, handlers, ce, etc), which has been smooth sailing so far. I came across a potential situation where this might not work as well as it sounds:

The case is with $vector->merge($iterable). We can take internal shortcuts when the $iterable is a php-ds structure, eg. another php_ds_vector_t. In order to access the internal buffer of that vector we have to follow this path: zval => zend_object => structure, ie. ((php_ds_vector_t*)(Z_OBJ(z)))->vector. The problem is that the current scope doesn't have knowledge of php_ds_vector_t, only ds_vector_t.

The only solution I can think of is to create separate functions, one for each shortcut, and only accept the structures, rather than a generic zval, except for the case where the Z_OBJ_CE is not a php-ds structure (array or other iterable). This would work fine, effectively moving the logic of "is this a vector? is this a deque?" out of the internal structure and into the callee's scope.

So instead of calling ds_vector_t *ds_vector_merge(ds_vector_t *vector, zval *values) I could use something like ds_vector_t *ds_vector_merge_vector(ds_vector_t *vector, ds_vector_t *values).

Is it possible to pass a void * along with a typedef to a function? That way the callee is responsible for extracting the structure, but the structure is responsible for the logic to merge it in. Would remove the need to have multiple x_merge_x, x_merge_y, x_merge_z patterns.

If i run command

 php -d extension=ds.so some_file.php

Then Ds extension works ok. But when i want add this line to php.ini:

extension=ds.so

Then php throw error:

PHP Warning:  PHP Startup: Unable to load dynamic library '/usr/lib/php/20151012/ds.so'
 - /usr/lib/php/20151012/ds.so: undefined symbol: php_json_serializable_ce in Unknown on line 0

My PHP version:
PHP 7.0.3 on Ubuntu 14.04

I don't see a use for knowing the current capacity of a structure.

Potentially an optionally weighted directed acyclic graph, implemented using a map of vectors internally for the adjacency list.

@krakjoe pointed out that the tests are failing on Windows x64:

Fatal error: Return value of Ds\Deque::filter() must implement interface Ds\Sequence, null returned in Unknown on line 0

Warning: Uncaught Exception in C:\php-sdk\src\ext\ds\vendor\php-ds\tests\tests\Sequence\filter.php:58

There's a try/catch which should be catching the exception in the closure, and ignore the fact that the function returned null.

Test case: testFilterCallbackThrowsException

public function testFilterCallbackThrowsException()
{
    $instance = $this->getInstance([1, 2, 3]);
    $filtered = null;
    try {
        $filtered = $instance->filter(function($value) {
            throw new \Exception();
        });
    } catch (\Exception $e) {
        $this->assertToArray([1, 2, 3], $instance);
        $this->assertNull($filtered);
        return;
    }
    $this->fail('Exception should have been caught');
}

Internal callback filter code: deque_filter_callback

void deque_filter_callback(Deque *deque, zval *obj, FCI_PARAMS)
{
    if (DEQUE_IS_EMPTY(deque)) {
        ZVAL_NEW_DEQUE(obj);
        return;

    } else {
        zval param;
        zval retval;

        zval *src;
        zval *ptr = ALLOC_ZVAL_BUFFER(deque->capacity);
        zval *pos = ptr;

        DEQUE_FOREACH(deque, src) {
            ZVAL_COPY_VALUE(&param, src);
            fci.param_count = 1;
            fci.params      = &param;
            fci.retval      = &retval;

            // Catch potential exceptions or other errors during comparison.
            if (zend_call_function(&fci, &fci_cache) == FAILURE) {
                efree(ptr);
                ZVAL_UNDEF(obj);
                return;
            }

            // Only push if the value is not falsey.
            if (zend_is_true(&retval)) {
                ZVAL_COPY(pos++, src);
            }
        }
        DEQUE_FOREACH_END();
        ZVAL_DEQUE(obj, deque_from_buffer(ptr, pos - ptr));
    }
}

Map

• Map::removeAll
• Map::first
• Map::last
• Map::skip(position)
• Map::merge, merges two maps together, replaces keys, returns new map.
• Map::intersection, key intersection, returns new map.
• Map::exclusive, key exclusive (symmetric difference), returns new map.
• Map::union, pairs where key is in either a or b, replaces keys, returns new map.
• Map::difference, returns new map containing keys in a but not in b.

Sequence

• Sequence::unshiftAll
• Sequence::merge

Set

• Set::removeAll
• Remove bitwise support for the sake of compatibility

• Rename intersection to intersect
• Rename difference to diff
• Rename exclusive to xor
• Rename union to merge

• Merge should accept any traversable

@krakjoe we can discuss things here. Current plan:

Files

#include "[src/public/]  ds/name.h"
#include "[src/private/] ds/common.h"
#include "[src/private/] ds/php_name.h"
#include "[src/private/] ds/ce/php_name.h"
#include "[src/private/] ds/handlers/php_name.h"
#include "[src/private/] ds/iterators/php_name.h"

Structs

• ds_name_t for the data structures
• php_ds_name_t for the objects

Macros

Internal:

• Z_{NAME}
• Z_{NAME}_P

External:

• ZVAL_{NAME}
• RETURN_{NAME}

Policies

• Prefer index access over pointer arithmetic, ie "&ptr[index]" over "ptr + index".
• Strict 80 char max line length.
• Header functions should have comments to describe their use where not obvious.
• Function order in .c should match the order in .h
• Method entries must be in alphabetical order.
• Macros should be prefixed with DS_ where appropriate.
• Internal functions should be prefixed with php_ds_
• External functions should be prefixed with ds_
• Headers should include everything they need to be included in isolation

Maybe also test these? Someone might be relying on grep. -__-

Hi,

Is there a compeling reason to make all classes final? It makes it hard to do this;

class SomeSet extends Set
{
...
}

function someFunction(SomeSet $set) {
...
} 

I know I can do composition over inheritance to create VO that use ds internally

class SomeSet
{
  private $set;

  function  __construct($values)
  {
    $this->set = new Set($values);
  }
  ... more methods exposing $this->set. 
}

I've looked into class_alias but that only works with user provided classes

We have to include the PHP json extension header in order to have Collection extend JsonSerializable. Should we include this header conditionally or specify json as a module dependency? The only reason to extend JsonSerializable is so that we can support json_encode, but a user who doesn't have the json extension enabled wouldn't be using json_encode anyway.