[DataStructure] iterating over data structures

[azjezz]

see discussion in #53 ( https://github.com/azjezz/psl/pull/53#discussion_r500772765 )

Questions:

• should you be able to iterate over a data structure ( queue, stack .. etc)
• should values be removed from the DS when iterating over them?
• should values pushed while iterating the DS be consumed in the same loop?

[azjezz]

/cc @veewee

[veewee]

Would it make sense to make the data structures immutable?

That way the questions are answered with:

• you can iterate a data structure
• the result after iteration will be exactly the same as before (so keeps values) : Think of it as "you choose to just go through the list instead of manually dequeueing)
• pushing results in a new data structure and won't be able to consumed inside the same loop (which also kinda makes sense to me)

Not sure if it makes sense from a consumer pov though.

I've also researched some other languages: https://rosettacode.org/wiki/Priority_queue

Most use something like while(!empty)... or while (0 !== count) to iterate instead of making it an iterator. Some languages support both iterating and the while approach. I think it would be nice if you could use the functions inside the Iter\ namespace on the data structures.

[azjezz]

I like the idea of immutable data structures.

If i understand correctly:

$queue = new Queue();
$queue = $queue->enqueue('hello');
$other = $queue->enqueue('hey');

$queue->count(); // 1 ['hello']
$other->count(); // 2 ['hello', 'hey']

$queue->dequeue(); // 'hello'

$queue->count(); // 0 []
$other->count(); // 2 ['hello', 'hey']

maybe we can do the same as in Collection, and have Queue, PriorityQueue, Stack be immutable, with another variant MutableQueue, MutablePriorityQueue, and MutableStack that are mutable ( see Psl\Collection\Vector vs Psl\Collection\MutableVector) ?

[veewee]

The dequeue method in your example should also be immutable then? Meaning the while will need to reassign the parameter pointing to the new version of the queue as well (which might be a bit counterintuitive).

Having both options is nice, but also more work to create and maintain. They should behave in a similar way, meaning that the 3 questions on top need to be answered in the same way for both implementations.

If I understand the haskell priority queue well, it also works in an immutable way. (But I am an absolute noob in that language :) )

[azjezz]

Here's a real world usage of PriorityQueue ( https://github.com/nuxed/http-server/blob/develop/src/Nuxed/Http/Server/Handler/NextMiddlewareHandler.hack#L5-L26 ):

final class NextMiddlewareHandler implements Server\IHandler {
  /** @var SplPriorityQueue<Server\IMiddleware> $queue */
  private SplPriorityQueue $queue;
  private Server\IHandler $handler;

  public function __construct(SplPriorityQueue $queue, Server\IHandler $handler) {
    $this->queue = clone $queue;
    $this->handler = $handler;
  }

  public function handle(Message\IServerRequest $request): Message\IResponse 
  {
    if (0 === $this->queue->count()) {
      return await $this->handler->handle($request);
    }

    $middleware = $this->queue->dequeue();

    return $middleware->process($request, $this);
  }
}

if we switch to immutable DS, this is how the API would look like ( correct me if i'm wrong ):

final class NextMiddlewareHandler implements Server\IHandler {
  /** @var SplPriorityQueue<Server\IMiddleware> $queue */
  private SplPriorityQueue $queue;
  private Server\IHandler $handler;

  public function __construct(SplPriorityQueue $queue, Server\IHandler $handler) {
    $this->queue = clone $queue;
    $this->handler = $handler;
  }

  public function handle(Message\IServerRequest $request): Message\IResponse 
  {
    if (0 === $this->queue->count()) {
      return await $this->handler->handle($request);
    }

    [$queue, $middleware] = $this->queue->dequeue();
    $this->queue = $queue;

    return $middleware->process($request, $this);
  }
}

the return type of dequeue is now bothering me, i'm not sure if immutable would be a good idea here since most PHP software seems to be using it in a mutable context.

[veewee]

I think tupples are getting more and more known in the community. The immutable implementation is indeed more verbose. Therefore, I suggest following things:

• Rename current implementation to Mutable - making it clear that it is mutable by design and making it consistent with the collections.
• This makes room for a possible immutable version that lives besides is.
• Inside the immutable version, it makes sense to return a tupple - but the user has the choice which one to use.
• We could still discuss if an immutable version is something we want to have in here or not.

Next on the topic of iterations:

• I think making it iterable is a must-have. That way you can use the iter functions on the data structures - making it very flexible in usage.
• The values should not be removed while iteration IMO, the reason : You are converting a specific version of queue to an iterable. That way, the source data structure can still be used a second time.
• Another benefit of making it iterable: it gives the user 2 ways of using the data structures:
  • By iterating over it (easy)
  • While (items) => dequeue (harder - but gives you more control)
• Values pushed by iterating should not affect current iteration, the reasons :
  • to make mutable and immutable act in a similar way.
  • Since an iterator is considered a converted version of a specific version of the queue
  • I think that creating the queue, in a lot of cases, is done before consuming it. Maybe we can look at some existing implementations to make sure this is correct?

examples:

// Iterables
$items = map([...$queue], ($value) => 'something');
$items = filter([...$queue], ($event) => $event instanceof SomeEvent);
// ...

// Looping over them with more control:
// We could add an isEmpty - which makes sense
while ($queue->count()) {
    $value = $queue->dequeue();
}

//  More advanced -> see your NextMiddlewareHandler

For your specific use-case a mutable version might make more sense. Even though I don't fully grasp the idea behind the NextMiddleware. It does something different each time it is handled, but in a regular server middleware stack - it only goes through the handle once?

For immutable it could look like this:

public function dispatch($event)
{
    $queue = $this->queue;

    while ($queue->count()) {
        [$queue, $subscriber] = $queue->dequeue();
        $subscriber($event);
    }

    return $event;
}

Which could also be used with iterator functions to make it less verbose.

[rauanmayemir]

It would be really nice to have a fallback with an optional mapping to https://github.com/php-ds.