> > The name "deque" is used in the standard library of these languages: > > > > - C++: std::deque > > - Java: java.util.Deque (interface) > > - Python: collections.deque > > - Swift: Collections.Deque (not standard lib, apparently, but Apple > > official? Don't know Swift) > > - Rust: std::collections::VecDeque > > > > And these don't have it in the standard library: > > - Go > > - C# > > - C > > - JavaScript > > > > Anyway, it's pretty decent evidence that: > > 1. This functionality is pretty widely used across languages. > > 2. This functionality should have "deque" be in the name, or be the > > complete name. > > > > Discussion naming for "vector" I can understand, as it's less widely > > used or sometimes means something specific to numbers, but there's > > little point in discussing the name "deque." It's well established in > > programming, whether PHP programmers are aware of it or not. > > > > As I see it, the discussion should be centered around: > > 1. The API Deque provides. > > 2. The package that provides it. > > 3. Whether Deque's API is consistent with other structures in the same > > package. > > 4. Whether this should be included in php-src or left to extensions. > > > > I suggest that we try to make PHP as homogenous in each bullet as we > > can with other languages: > > 1. Name it "Deque." > > 2. Put it in the namespace "Collections" (and if included in core, > > then "ext/collections"). > > 3. Support common operations on Deque (pushing and popping items to > > both front and back, subscript operator works, iteration, size, etc) > > and add little else (don't be novel here). To me, the biggest thing > > left to discuss is a notion of a maximum size, which in my own > > experience is common for circular buffers (the implementation chosen > > for Deque) but not all languages have this. > > 4. This is less clear, but I'm in favor as long as we can provide a > > few other data structures at the same time. Obviously, this a voter > > judgement call on the yes/no. > > > > Given that I've suggested the most common options for these across > > many languages, it shouldn't be very controversial. The worst bit > > seems like picking the namespace "Collections" as this will break at > > least one package: https://github.com/danielgsims/php-collections. We > > should suggest that they vendor it anyway, as "collections" is common > > e.g. "Ramsey\Collections", "Doctrine\Common\Collections". I don't see > > a good alternative here to "Collections", as we haven't agreed on very > > much on past namespace proposals. > > > > Anyway, that's what I suggest. > > > > I generally agree with everything Levi has said here. I think that adding a > deque structure generally makes sense, and that putting it into a new > ext/collections extension under the corresponding namespace would be > appropriate. I wouldn't insist on introducing it together with other > structures (I'm a lot more sceptical about your Vector proposal), but do > think there should be at least some overarching plan here, even if we only > realize a small part of it in this version. https://wiki.php.net/rfc/deque has been updated after https://wiki.php.net/rfc/deque_straw_poll. It's now going in the namespace `Collections\`, and a new always-enabled extension `collections` is added in `php-src/ext/collections` in that RFC (for end users, that would mainly affect php.net manual organization).
I plan to start voting in a few days. Also, iteration behavior has changed to https://wiki.php.net/rfc/deque#iteration_behavior I also set up a WebAssembly demo to make it easier to look up how it currently behaves: https://tysonandre.github.io/php-rfc-demo/deque/ > A few questions for the particular API proposed here: > > 1. There would be the possibility of having an interface Deque that is > backed by a VecDeque/ArrayDeque implementation. I'm not convinced this > would actually make sense, but I wanted to throw it out there, given that > the class is final (which is without any doubt the correct decision). Would `ArrayDeque` be referring to something with a hardcoded maximum size? I can't think of a strong use case for that, and it's possible in userland by wrapping `Collections\Deque` (with composition) and checking size on add operations. > 2. How do set() / offsetSet() work with an out of range index? Is it > possible to push an element with $deque[count($deque)] = x? I would assume > that throws, but want to make sure. On a related note, why do we need both > get()/set() and offsetGet()/offsetSet()? These APIs seem redundant. They throw for out of range indexes. Offsets between 0 and count-1 are in range. offsetSet/offsetGet attempt to coerce values to integers to act as a drop-in replacement for arrays and Spl datastructures (e.g. for applications that deal with string inputs). They throw TypeError if coercion fails, OutOfBoundsException for invalid offsets. > 3. I believe it's pretty standard for Deque implementations to provide > insert() / remove() methods to insert at any position (these would be O(n)). I agree it's pretty standard and something I'd want, I was concerned about increasing the scope too much (before seeing if new collections would succeed) and making this harder to review (and with more methods added to the design, more possible objections to API decisions) > 4. The design of getIterator() here is rather unusual, and deserves some > additional justification. Normally, we let getIterator() see concurrent > modifications to the structure, though the precise behavior is unspecified. > I would also like to know how this will look like on a technical level (it > doesn't seem to be implemented yet?) This seems like something that will > require a check on every write operation, to potentially separate the > structure in some form. You have a good point - the proposed and implemented behavior have been updated. It's now iterating over the original Deque, not an eager copy. https://wiki.php.net/rfc/deque#iteration_behavior The Deque now tracks how the position of the front is moved by shift()/unshift() operations. Iterators have their own positions that are unconditionally advanced by 1 in `$iterator->next()` and the delta is the iterator offset (`$iterator->key()`). The implemented behavior can be seen at https://tysonandre.github.io/php-rfc-demo/deque/ > 5. The shift/unshift terminology is already used by our array API, but I'm > not sure it's the most intuitive choice in the context of a deque. SplQueue > has enqueue() and dequeue(). Another popular option from other languages > (which I would personally favor) is pushFront() and popFront(). enqueue() is the same as push(), dequeue is the same as shift(). It's still using the inherited unshift for adding to the front of the deque. In isolation, I'd prefer pushFront/popFront as names, but introducing more than one name for common operations seemed like it wouldn't be worth the inconvenience for the potential of introducing bugs in userland code when switching between collection objects, making the standard library harder to learn/remember, etc. Thanks, Tyson -- PHP Internals - PHP Runtime Development Mailing List To unsubscribe, visit: https://www.php.net/unsub.php
