« first day (431 days earlier)      last day (4522 days later) » 

8:02 PM
and back to compile error :( my C is really bad
 
yeah, that can be a problem
 
@ircmaxell It is interesting. It is also one of my top 3 complaints about PHP, not having return types.
 
yeah
agree
not on my top 3, but on the list
 
8:17 PM
I would have appreciated scalar type hints more though ;) But I understand that there are issues with that
 
Yeah, I tell you what I want: generic castability, not just to strings
 
8:40 PM
I'm such a doofus. Pro tip: Syntax highlighting on github pages only works if you include the <?php tags
 
dah
 
^^
 
405 not allowed
 
@ircmaxell Really?
 
8:42 PM
@LeviMorrison on form submission
 
@ircmaxell Yeah, they don't DO anything.
 
well, then add an on-submit handler that throws an alert box saying "Stop Clicking Me"
github.com/morrisonlevi/PHP-Datastructures/blob/master/lib/… <-- What about head() and tail() instead of peek() and peekTail()?
 
@ircmaxell Possibly. I don't like nouns as methods. Admittedly, peekTail() sounds purely awful.
 
yeah, that's my only point
 
@LeviMorrison Or purely sexy
 
8:46 PM
@CharlesSprayberry If it can be construed as an innuendo, then it needs a name change. :)
 
tail() is a verb. tail that car!
head() too. head over here.
 
@LeviMorrison Then it should definitely be changed because all I got from that is innuendo
 
Bug here: github.com/morrisonlevi/PHP-Datastructures/blob/master/lib/… if you have elements 0, 1, 2 set, and you set 3 explicitly you get an exception. You should also check if $offset === $this->count (in which case set, and increase $this->count)
 
since they are effectively getters you can name them getFirst() and getLast()
 
@ircmaxell If you set something that doesn't exist it SHOULD throw an exception. In my opinion.
 
8:48 PM
@LeviMorrison how can it exist if you don't set it?
 
@ircmaxell $list[] = '3';
 
right now, you'd have to do $foo[] = 0; $foo[0] = $realValue
 
@ircmaxell You can do $foo[] = $realValue;
 
IMHO the indexed set and the addition should behave the same, as long as the index is either within the currently set range, or at most one above it (at which point it would be identical to appending)
 
@Gordon That's an idea we could use, perhaps.
 
8:50 PM
@LeviMorrison or getTop and getBottom if its a stack
 
github.com/morrisonlevi/PHP-Datastructures/blob/master/lib/… <-- You didn't update the $this->count member here as well. So you can wind up with a discontiguous list...
 
@ircmaxell I honestly think it could be a source of bugs to set the next one.
@ircmaxell Good catch.
@ircmaxell We'll have to talk about it more.
 
@LeviMorrison Could? Sure. But I think it's rather odd that these two have different behaviors: $obj = new ArrayList; $obj[] = 1; and $obj = new ArrayList; $obj[0] = 1;...
 
I thought you couldn't implement Traversable
 
@KevinPeno Not directly, no.
 
8:52 PM
But you are in Collection
is this not meant to be PHP based?
Sorry. I'm coming in late :P
 
@KevinPeno You can still implement Traversable in PHP by implementing Iterator or IteratorAggregate. Traversable itself can only be implemented in C.
 
@KevinPeno The interface does, which means the implementing class must implement something that extends it (either Iterator, IteratorAggregate, RecursiveIterator, etc)
github.com/morrisonlevi/PHP-Datastructures/blob/master/lib/… <-- I think that needs more thought, as SplDoublyLinkedList does not right now expose a DLL. Ex: there's no way to insert a value at an arbitrary point in the list. That's important to expose in a new lib I think...
 
right. I guess my point was I thought you couldn't implement/extend it in PHP land at all (except for type checking)
but I'd never tried
 
@KevinPeno You can on interfaces (which is exactly what it does)
 
@ircmaxell good to know :)
 
8:55 PM
@ircmaxell I agree. Any ideas?
 
Well, I've always implemented DLL with a value object. So basically:
 
@KevinPeno You can implement Traversable in PHP by implementing Iterator or IteratorAggregate. Traversable itself can only be implemented in C.
 
@LeviMorrison yes. I understand that part. I didn't understand that you could use it in interfaces. Now I do.
 
struct list {
    listElement top;
    listElement bottom;
}
struct listElement {
    mixed value;
    listElement prev;
    listElement next;
}
Now, without exposing that structure, I'm not sure how to insert in the middle. Unless you internally keep track of iteration as well... At which point you'd have an insertBefore() method and an insertAfter() method, which would insert before/after the current node in iteration...
 
@ircmaxell I meant on the API, not implementation :)
@ircmaxell $dll->insertAfter($item, 4);
 
8:58 PM
@LeviMorrison that's what I'm saying. Without exposing the implementation details, it's not really trivial... Unless...
what's 4?
or what's item?
 
@ircmaxell $dll->insertAfter($toBeInserted, $indexToInsertAfter); If the latter is null, we could have it insert after the value that the iterator is on.
How's that sound?
 
@LeviMorrison That kind of defeats the point of the abstraction though. Since the indexes will change on insert, so...
 
@ircmaxell I don't see it as a problem, honestly. LinkedList implements ArrayAccess, so you can access things in the middle. So even if you don't have an index for insertAfter, the indices will still change.
If this was C++, I'd design it differently. This is PHP. It's not C++. It's not even C by usage. Thoughts?
 
Accessing things in the middle isn't the problem. It's accessing things by index that's weird, since DLL (and SLL for that matter) don't have index, but order. And that order can change at any time...
@LeviMorrison Well, how would you design it in that case?
 
@ircmaxell For one, iterators would be external :)
 
9:04 PM
@LeviMorrison You can do that with Aggregate...
 
@ircmaxell I can't. Maybe once we implement it in C.
 
@LeviMorrison huh? How can't you do that?
 
@ircmaxell I've never tried to define my own IteratorAggregate, is what I mean.
 
Well, can't and haven't are two different things
 
@ircmaxell read it.
 
9:06 PM
thoughts...?
 
@ircmaxell Do you suggest that we make all of our structures externally iterable?
 
@LeviMorrison Only where it makes sense...
if state isn't important to the data structure (like queue or stack), then yes. If it is (such as DLL, where you need to be able to alter the structure in the iteration), perhaps not
 
@ircmaxell I don't see the trouble with using insertAfter($item, $index), honestly. You can just call insertAfter($item) to insert it after the current iterator position.
 
@LeviMorrison it just feels off. I'm not sure why...
actually, because $a[4] = 1; $a->insertBefore(2, 4); dump($a[4]); produces 2 instead of the obvious 1 (or what seems obvious)
 
@ircmaxell Java doesn't even let you insert in the middle. Not with an API call.
 
9:15 PM
@LeviMorrison Then it's not a true DLL
a DLL can iterate in both directions, and you can splice in values at any point in the chain...
that's why it's useful in things like hash tables
you have an array as the hash table, but then the value is a DLL that's sorted. So you need to insert in an arbitrary location to update that DLL when adding a new value...
 
Even if you don't allow inserting after an index, it might be confusing still.
$a[4]=1;
$a->insertBefore(2);//iterator is at 0;
$a[4]; // who knows?
 
true. Either way isn't nice...
which is another reason accessing by index isn't a great idea
 
@ircmaxell But that doesn't mean it isn't useful.
 
eih, maybe, maybe not
 
@ircmaxell dunno. imo they are still way too lax but its getting better.
 
9:21 PM
yeah, that's the important thing
 
I like function insertAfter($value, $index=null); If it's null, we just add it after the current iterator position. That way if you are only iterating around, you never see the index. But if you need index positions, it's still there.
 
@LeviMorrison Practically, perhaps. But in terms of design, I really don't care for it...
 
@ircmaxell Then the only way to fix it would be to not implement ArrayAccess.
 
which may be an option...
 
@ircmaxell It would be the first thing requested, no doubt. :)
 
9:22 PM
Well, that's why I'm torn
do we want to go for Purity, or Practicality? It is a root data structure. I'm torn...
 
@ircmaxell If we do it the way I suggest, we have both styles. The confusing part is when we mix the way we use the list . . .
 
Well, what I can see is this:
perhaps we implement a series of Pure data structures. Then we add a wrapper as needed to add those convinence functions. So you can use the core if you want (for purity and limited exposure), but then also use the extended version if you need. Then again, eih
@Gordon: thoughts?
 
You guy's talking about LinkedList in that github?
 
Well, not so much that one, but a DoublyLinkedList implementation in general
 
and whether or not it can have indexes?
 
9:26 PM
one of my issues with the one that's currently in SPL, is based on the API, it's just an array with shortcuts to top and bottom
@KevinPeno more general than that, but in a sense, yes
 
@ircmaxell I'd like to weight in, but if I'm not looking general enough perhaps you can help me understand?
 
@KevinPeno Definitely weigh in...
 
@KevinPeno The question we are trying to answer is: "What should we define a LinkedList to be in our library?"
 
What's the use cases you are basing that question off of?
 
Using a LinkedList as an Array (index accessible) and a linked-structure with the ability to insert / remove in the middle.
 
9:34 PM
either way, I think the ability to insert / remove in the middle is pretty crutial in the scheme of a DLL
hrm...
 
@LeviMorrison ?
 
@LeviMorrison Huh ? ->add(17, x)
 
@NikiC I missed it I guess >.< They don't let you insert before, though, do they?
 
9:37 PM
@LeviMorrison :)
 
in the context of a linked list (which I don't believe can have indexes) I'd make insertAfter and insertBefore accept the node to put after/before as the first argument
 
@NikiC I'd say so.
 
weird. So Java allows you to specify by position, and C# requires you pass in a node element
 
@KevinPeno At the moment we don't want to expose nodes to the user.
 
You could, in theory, allow ArrayAccess on the list, but it should be expected that the order is undefined and fluctuating
 
9:38 PM
@KevinPeno Well, its order is defined. index 4 is the 4th item in the list.
 
@LeviMorrison thinking out loud question: why not?
 
@ircmaxell We can go that route if we want to. It's not nearly as simple.
 
@LeviMorrison what are you talking about? I put the node there AND I can get it via iteration
@LeviMorrison No..that's the current order.
A linked* has no order except the links
In fact, I don't think you should ever reorder a linked*
 
@KevinPeno And when you access it by index, it's based on the current order. That's how it is in any Linked API I've seen that allows indexing.
 
@LeviMorrison It makes some things harder. But some things much easier...
 
9:40 PM
@ircmaxell Such as?
@ircmaxell Also, it allows the user to muck up the nodes.
 
@LeviMorrison Inserting for one
@LeviMorrison in what sense?
 
@LeviMorrison And why can't they?
it's their nodes in their list..
 
@KevinPeno Well, no. The api should not be corruptable...
 
@ircmaxell They can break the links of the node. This is PHP, we can't give them a const node.
 
imo there is no indexing a Linked*
 
9:42 PM
@KevinPeno which is where I'm feeling uneasy
 
@LeviMorrison um, how can they do that?
here's a scenario...
I have LinkedList( one => two => three => four => one)
=> is the links
 
$node = $list->insertBefore($item, $someNode);
$node->next = null;

It's officially broken.
 
@LeviMorrison next would not be public
 
@LeviMorrison who said to allow next?
anyway...
 
@ircmaxell Doh, I forgot about that. I was thinking C structs >.<
 
9:44 PM
:-D
 
Eh, we could expose the nodes.
 
given the above I use LinkedList->insertBefore( two, three)
or even LinkedList->insertBefore( two, five )
Now I have LinkedList( one => two => five => three => four => one)
 
sorry, I currently don't get what you mean by "expose the nodes"?
 
@KevinPeno I think I'm misunderstanding your API. Do you mean function insertBefore($nodeToInsertBefore, $valueToInsert)?
 
for insertAfter(item) you wouldn't need to expose the internal nodes, or would you?
 
9:46 PM
@LeviMorrison assume they are nodes for now
 
I define it as function insertBefore($valueToInsert, $nodeToInsertBefore); The order of arguments is different.
I read it as insert X before Y, so the parameters should be in that order.
 
@LeviMorrison I like the other way around ^^
 
@NikiC So does Java. But their method is add. The order isn't implied.
 
@LeviMorrison then insertAfter would be different. Either way you order the args, they should be consistent
 
ah, now I get the node problem (i didn't think of duplicate values in the list)
 
9:48 PM
yup
 
@KevinPeno My insertAfter is defined the same way. :)
 
either way, I don't think Node should ever be null
 
@NikiC @KevinPeno @ircmaxell @Gordon All in favor of exposing the nodes, message 'Aye'.
 
first tell us how exactly you would do that
 
eih
 
9:51 PM
I couldn't imagine a clean impl off the top of my head
 
you'd return the node from the methods instead of the value
 
that doesn't sound clean at all ;) or at least very unusabe ^^
 
so you'd do $value = $list->pop()->value(); instead of $value = $list->pop();
 
Whenever you add a value, the node is returned instead of void.
 
crap the second page of the second part of the php extension tut is lost in nirvana
 
9:57 PM
@ircmaxell I have an idea for the LinkedList API. Give me a moment.
 
@ircmaxell thinking about it, providing access to the nodes might make sense. would one also be able to do ->setNext() like calls on them?
 
@NikiC I vote no.
 
@NikiC Yes
 
hi all
 
@ircmaxell How much automatism would there be? Would ->setNext() also ->setPrev on the passed element or would it allow to create "broken" (for some definitions of the word) lists?
 
10:02 PM
Well, here's the node I've got so far...
 
@NikiC Giving access to prev and null will allow for the users to break things. Of that I'm quite confident.
 
class LinkedListNode {
    protected $prev = null;
    protected $next = null;
    protected $value = null;
    protected $list = null;

    public function __construct($value, LinkedList $list) {
        $this->value = $value;
        $this->list = $list;
    }

    public static function create($value, LinkedList $list) {
        if (is_object($value) && $value instanceof self) {
            if ($list !== $value->list) {
                throw new Exception('Crossing Lists!!!');
            }
            return $value;
 
It looks fine. I'd rather have the LinkedList create the LinkedListNode and not have it publicly available which LinkedList the node belongs to.
Although, I don't know if that would work out how I envision it in my head. At least not a PHP version.
 
@LeviMorrison Well, it needs to be public
 
@ircmaxell Why?
 
10:06 PM
because inorder for insertAfter to be on node, setLast must be public on the linked list. And if it is, you need some way to ensure that the node you're setting to the last one is part of the same list
 
I'd rather have the LinkedList manage everything.
 
@LeviMorrison then you'd have to move insertBefore / insertAfter to LinkedList, which means that you'd need to keep track of iteration
 
@ircmaxell I'd rather do that, honestly.
 
LinkedList should only care that it is LinkedListNode
not create anything
I don't see why there's a static create function either. Can you explain @ircmaxell?
 
@KevinPeno Well, so that you can do $list->push(1);...
 
10:09 PM
@ircmaxell And I didn't yet get the point about the public list
 
otherwise you'd need to do $list->push(new LinkedListNode(1, $list))
give me a sec
 
nah
just have the constructor accept list as optional and allow setList in the interface for LinkedListNode
what you have there is effectively doing the push for you, imo
 
so you are pushing 2 times
 
Obviously you can't make this in a PHP implementation, but here is what I vote for:
class LinkedListNode {
friend class LinkedList;

protected $value;
protected $next;
protected $prev;

protected $list;

private __construct($value, LinkedList $list);

public getValue();
public setValue($value);
public getNext();
public getPrev();

}
 
10:11 PM
private construct?
@KevinPeno It's so that you can pass in either a value, or a value object.
 
@ircmaxell You can't make a node, only a LinkedList can.
 
A, C++, where a friend can touch your privates
 
@ircmaxell Sounds wrong, but it is useful in situations like this. I think, at least.
 
lol
Well, it would be in the PHP implementation once it got written down to C
 
Hi all
 
10:15 PM
@NikiC Hey.
 
how are we all this evening?
 
@KevinPeno The only problem is that then you can intermix 2 lists by appending them together
 
What word would you give to something that is small, powerful, flexible but can also be dictated to?
 
@ircmaxell how so?
 
@NikiC Remember you suggested some time ago, how could I work with forms from Twig templates. You suggested, that I should pass a form object and call it method there to draw needed element with specified params.
 
10:16 PM
@KevinPeno $list1->push($elementFromList2)
 
@ircmaxell but a node can only be in one list at a time
 
@Eugene vaguely ;)
 
@KevinPeno A node can, but what it points to may not
 
@Daveo I hope that it isn't a framework ^^
 
remember, the node keeps a track of previous and next items
 
10:17 PM
@NikiC Well, I found out why TokenParser is better in this case. The form result will not be cached and TokenParser result will be.
 
No Niki not a framework
 
so unless you recursivly check/modify, there is still a chance
 
In fact something unique that I can't quite put a name to it..
 
@ircmaxell True i suppose.
 
@Eugene cached in what way?
 
10:18 PM
You could always throw the exception when the list changes
 
@Daveo Call it UNI :)
 
Additionally, look at DomNode::appendChild. Specifically: Raised if newnode was created from a different document than the one that created this node.
 
So I'm looking for a word that fits it.. either something cool/popular.
 
hrm, not a trivial problem...
 
@ircmaxell well yeah. If you did pop(DifferentListNode) it shoudl indeed exception
 
10:19 PM
LLs are bad :(
 
@KevinPeno Since when does pop take a parameter?
 
@NikiC but they are powerful
 
@LeviMorrison Sorry I meant push
 
@ircmaxell On a side node, if you let LinkedList create the nodes you can't extend the nodes anymore. I don't know whether or not this is good
 
@ircmaxell You could traverse the node being added as well, but I wouldn't. I would just do it on iteration
 
10:19 PM
This is exactly why I wanted the simple API where we don't expose things.
 
@NikiC that's why I'm questioning it
I'd rather people created the objects themselves
 
@LeviMorrison But it turns out that there is no such thing ;)
 
@LeviMorrison And not exposing things stops some really powerful usecases
 
Otherwise you end up with setIterator type methods that take a string because of PHP's limitations on passing types directly
 
@NikiC I think the API I mentioned earlier is. It's not quite as powerful, but the sheer fact you don't have deal with nodes might be worth it in a language like PHP.
 
10:21 PM
@NikiC I guess as rendered form element. Since logically method from form object will render it every time as a new element and TokenParser is caching it if cache enabled. I'm not sure did I understand everything correctly. Have to test it. Only read about it. But sounds true.
 
@Eugene Well, it's "caching" the PHP code to generate it ;)
 
@KevinPeno So then we cut it down and hide the node class (keep it a struct in C).
 
@ircmaxell If the goal is to seal LinkedListNode, then that is fine I guess.
 
hrm
sadly, I feel that we're getting to the PHP implementation of DLL with the addition of the ability to insert nodes in the middle
 
@ircmaxell Honest question: how often do you randomly insert nodes into the middle? Personally, I usually do insert stuff when I'm iterating.
So the API I mentioned earlier would work very nicely for me. If randomly inserting nodes is a significant use case, we may have no choice but to expose the nodes.
 
10:30 PM
@NikiC Well, I'll test it out and tell you later about the diff. Night now.
 
@Eugene night
 
@LeviMorrison often enough where I think it would be limiting to not provide it...
the more I think about it, inserting by index may be the best we can do...
 
@ircmaxell I mean, this is PHP. Recreating the Spl is one of my ways of trying to dispell its toy language nature, but even still that doesn't mean I should allow the full-blown power of C. You know?
 
@LeviMorrison Should Stack, Queue, and Deque extend either Stack or Queue?
 
@KevinPeno no
 
10:36 PM
@KevinPeno That's a no :)
 
@ircmaxell why not?
 
@KevinPeno Because they don't by nature. They are SO close that you want to add some more inheritance, but you can't without it being ugly.
Let me make a little table for you.
 
@LeviMorrison nvm, I see.
 
Niether a stack nor a queue can add to the front. A Deque can.
 
Why do we have a deque anyways?
I thought it was decided that we don't need one?
 
10:46 PM
@NikiC A LinkedList is a Deque and more.
Btw, here's a prettier version of the same table: viper-7.com/VZXL36
 
@LeviMorrison Oh, I missed that deque is only an interface ^^
 
@LeviMorrison Your table, and comment, still makes me feel like they have to do with implementation rather than interface, but ok.
 
And probably the best version of the table: viper-7.com/ysUwgK
Except I screwed up the data
 
:D
 
It's fine. I get your point
 
but I still see the difference as implementation, not interface
 
They are all SO close but aren't quite the same. Stack and Queue COULD share the same API, but Deque cannot.
A deque has more operations than Stack and Queue. Stack and Queue have the same operations, but they act differently.
 
@LeviMorrison What structures will imeplement deque?
 
@NikiC LinkedList
 
Doesn't make sense to me to have an interface for a sole class
 
10:52 PM
@LeviMorrison you realize that it is perfectly possible, and acceptable, to have a Stacked LinkedList that is not Deque
 
Operations:
Stack
-add
-remove
-peek
Queue
-add
-remove
-peek
@KevinPeno What is a Stack LinkedList? An array implementation of LinkedList?
 
@LeviMorrison absolutely.
 
Tek
@ircmaxell Ping. Had a small question for you if you don't mind.
 
@KevinPeno Reread it. I modified it.
 
@LeviMorrison If it cannot be a Stack or a Queue then it cannot be a Deque either.
Since the only difference is implementation.
 
10:58 PM
@KevinPeno I still don't know what the heck a Stack LinkedList is. Is it a Stack that is created using a LinkedList?
 
I wasn't totally serious about the stack linked list
@LeviMorrison i suppose in theory it would be more related to iteration on the` LinkedList` than how they are attached
 
@KevinPeno I don't know wtf you are talking about, man.
Am I the only confused one here? @ircmaxell? @NikiC?
 
@LeviMorrison the only difference between Stack Queue and Deque is implementation.
 
@KevinPeno Wrong. Let me explain why.
A Stack can add to one end and remove from one end.
A Queue can add to one end and remove from one end.
A Deque can add to two ends and remove from two ends.

A Stack and Queue can share the same API and have different implementations. No problem there. But a Deque is different. It does not share the same API.
 
I'm sorry I didn't mean to insinuate that they had the same API. I'm pointing out that these are not interfaces
In all they are completely different in both contract (api) and implementation
 
11:06 PM
@KevinPeno It still doesn't matter. A Deque can be a Queue or a Stack or niether, while a Stack is not a Deque nor a Queue, and a Queue is not a Stack nor a Deque.
 
@LeviMorrison But why do we need deque in the end?
 
@NikiC Those methods could just live on inside of LinkedList and not have the interface for Deque. That certainly is possible.
@NikiC But someone could build a Deque that is not a LinkedList. So I moved it.
 
@LeviMorrison Unless we provide a Deque, I would be against providing that interface
 
@NikiC That's fine. But it's no big deal to kill it, but it is a bit harder to add back in :)
 
@LeviMorrison not really ;) git revert commit-ref ^^
 
11:11 PM
@KevinPeno I guess the easiest way to define Stack, Queue and Deque is like this:
Stack: LIFO
Queue: FIFO
Deque: undefined
 
Sorry, meeting
DeQue is just a DLL that is not allowed to be written to the center of...
 
@ircmaxell So, do we want it or not?
 
eih, perhaps
 
^^
 
can't think, ionvolved in something else atm
 
11:21 PM
May I say that this whole thing turned out more complicated than expected? :P
 
@NikiC That sounds like it could be applied to everything ever.
 
@NikiC Even still, the current Spl structures are really bad. I bet there was NO collaboration.
 
@NikiC It was always going to be complicated
 
@ircmaxell It didn't sound so ^^
I naively assumed that the C implementation will be the most complicated part of it
 
11:42 PM
@NikiC It still might be. How hard was hello_world()?
 
@LeviMorrison It gets easier
Last thing I did today was manipulate the active symbol table
I'll look into defining classes tomorrow I think
night now
 

« first day (431 days earlier)      last day (4522 days later) »