Comments (7)
/cc @veewee
from psl.
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.
from psl.
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
) ?
from psl.
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 :) )
from psl.
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.
from psl.
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.
from psl.
It would be really nice to have a fallback with an optional mapping to https://github.com/php-ds.
from psl.
Related Issues (20)
- [Type] add `nonnull` type
- [Type] add `string_range` and `int_range` types.
- Undeprecate `positive_int` HOT 2
- base64 url safe encoding HOT 1
- Return value of `Psl\Str\trim()` must be of the type string, null returned HOT 6
- `CoercionException::withValue()` called but not throwed. Is this dead code? HOT 1
- Improve error messages for shape and vec -like types
- Improve Dict\merge HOT 1
- Make PSL PHPStan compliant
- Add an `option()` type to `Psl\Type` to coerce to a `Psl\Option\Option` HOT 3
- Split this package is multiple sub-packages HOT 2
- [Bug] Vec\range handles ints which don't roundtrip through floats wrong
- intersection + shapes unexpected behaviour (possible bug?) HOT 4
- Type\implements_interface HOT 3
- Corece an `array` out of an `stdClass`? HOT 3
- [RFC] Change `ResultInterface<T>` to `ResultInterface<T, E>` HOT 5
- chore: rename all enum cases to use PascalCase
- Improvement converted json type HOT 5
- Is nonnull helpful in any way? HOT 1
- PHPStan extension unable to report optional positive-int
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from psl.