Double Linked List in default haxe distrib

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

Double Linked List in default haxe distrib

interaction-designer
Hi all,

Just as a linked list is a very basic datatype included in the default haxe distrib, why not also include another very basic one: the Double Linked List?

It's not that hard to create a Double Linked List, but for some newcomers to haxe such a 'feauture' would be nice. To scratch that itch I have some code for you to review. I basically tried to do it in the same style as the official Linked List is coded. I have to put some code for example for an php (and maybe others) implementation in it by using the preprocessor instructions, which isn't much work.

However I would first want to know if you like to have a Double Linked List as a default feature. And also if the code generally is ok with coding style, maybe some extra methods, some speedups i should do, etc. I like to hear and then I will do anything if Nicholas and other like it to be part of the default datastructures set.

Warm Regards, Simon

class DLList<T> {
        public var length(getLength, null):Int;
        public function new() {
                h = [null,null,null];
                clear();
        }
        public function clear() {
                h[2] = h[0] = h;
                length_ = 0;
        }
        public function isEmpty():Bool {
                return h[2] == h;
        }
        public function push(value:T) {
                var newItem:Array<Dynamic> = [h[0], value, h];
                newItem[0][2] = newItem;
                h[0] = newItem;
                length_++;
        }
        public function unshift(value:T) {
                var newItem:Array<Dynamic> = [h, value, h[2]];
                newItem[2][0] = newItem;
                h[2] = newItem;
                length_++;
        }
        public function pop() {
                if(!isEmpty()){
                        h[0][0][2] = h[0][2];
                        h[0][2][0] = h[0][0];
                        length_--;
                }
        }
        public function shift() {
                if(!isEmpty()){
                        h[2][0][2] = h[2][2];
                        h[2][2][0] = h[2][0];
                        length_--;
                }
        }
        public function iterator():DLListIterator<T> {
                return cast {
                        owner:this,
                        h : h,
                        pos:h,
                        hasNext : function() {
                                return untyped (this.pos[2] != this.h );
                        },
                        hasPrevious : function() {
                                return untyped (this.pos[0] != this.h );
                        },
                        next : function() {
                                untyped {
                                        if (this.pos[2] == this.h) return null;
                                        this.pos = this.pos[2];
                                        return this.pos[1];
                                }
                        },
                        previous : function() {
                                untyped {
                                        if (this.pos[0] == this.h) return null;
                                        this.pos = this.pos[0];
                                        return this.pos[1];
                                }
                        }
                }
        }
        private var length_:Int;
        private var h : Array<Dynamic>;
        private function getLength():Int {
                return length_;
        }
}


typedef DLListIterator<T> = {>Iterator<T>,
        var hasPrevious:Dynamic;
        var previous:Dynamic;
        var h:Array<Dynamic>;
        var pos:Array<Dynamic>;
}

 

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Double Linked List in default haxe distrib

Justin Donaldson
Simon,

Thanks for your contribution.

The HaXe libraries are indeed "batteries included" in the sense that they provide class specifications for simple container structures, all the way up to server API's.  These basic
class specifications are also usually highly tuned for each of the platforms that haXe targets.  This is done through optimized conditional compilation for each of the targets, and this can be somewhat time consuming to specify and test (you might try seeing how some of the base classes are implemented in the std library, as well as looking for other articles on optimization like http://haxe.org/com/libs/listtools/which_iterable_type_should_i_use_).  The haXe language has changed quickly, and most of the main developers have been working on those language features, rather than libraries.  However, there's several other people that have provided their own low level libraries on haxelib: http://lib.haxe.org/

Feel free to browse around haxelib, I'm sure there are double linked list implementations in a number of different libraries.  If you have some code that you think is faster, more flexible, or just prettier than what's available, please consider adding it as your own project, and making an announcement.

Best,
-Justin


On Tue, May 11, 2010 at 7:26 PM, <[hidden email]> wrote:
Hi all,

Just as a linked list is a very basic datatype included in the default haxe distrib, why not also include another very basic one: the Double Linked List?

It's not that hard to create a Double Linked List, but for some newcomers to haxe such a 'feauture' would be nice. To scratch that itch I have some code for you to review. I basically tried to do it in the same style as the official Linked List is coded. I have to put some code for example for an php (and maybe others) implementation in it by using the preprocessor instructions, which isn't much work.

However I would first want to know if you like to have a Double Linked List as a default feature. And also if the code generally is ok with coding style, maybe some extra methods, some speedups i should do, etc. I like to hear and then I will do anything if Nicholas and other like it to be part of the default datastructures set.

Warm Regards, Simon

class DLList<T> {
       public var length(getLength, null):Int;
       public function new() {
               h = [null,null,null];
               clear();
       }
       public function clear() {
               h[2] = h[0] = h;
               length_ = 0;
       }
       public function isEmpty():Bool {
               return h[2] == h;
       }
       public function push(value:T) {
               var newItem:Array<Dynamic> = [h[0], value, h];
               newItem[0][2] = newItem;
               h[0] = newItem;
               length_++;
       }
       public function unshift(value:T) {
               var newItem:Array<Dynamic> = [h, value, h[2]];
               newItem[2][0] = newItem;
               h[2] = newItem;
               length_++;
       }
       public function pop() {
               if(!isEmpty()){
                       h[0][0][2] = h[0][2];
                       h[0][2][0] = h[0][0];
                       length_--;
               }
       }
       public function shift() {
               if(!isEmpty()){
                       h[2][0][2] = h[2][2];
                       h[2][2][0] = h[2][0];
                       length_--;
               }
       }
       public function iterator():DLListIterator<T> {
               return cast {
                       owner:this,
                       h : h,
                       pos:h,
                       hasNext : function() {
                               return untyped (this.pos[2] != this.h );
                       },
                       hasPrevious : function() {
                               return untyped (this.pos[0] != this.h );
                       },
                       next : function() {
                               untyped {
                                       if (this.pos[2] == this.h) return null;
                                       this.pos = this.pos[2];
                                       return this.pos[1];
                               }
                       },
                       previous : function() {
                               untyped {
                                       if (this.pos[0] == this.h) return null;
                                       this.pos = this.pos[0];
                                       return this.pos[1];
                               }
                       }
               }
       }
       private var length_:Int;
       private var h : Array<Dynamic>;
       private function getLength():Int {
               return length_;
       }
}


typedef DLListIterator<T> = {>Iterator<T>,
       var hasPrevious:Dynamic;
       var previous:Dynamic;
       var h:Array<Dynamic>;
       var pos:Array<Dynamic>;
}



--
haXe - an open source web programming language
http://haxe.org



--
Justin Donaldson
PhD Candidate, Informatics
Indiana University
http://www.scwn.net
aim: iujjd
twitter: jjdonald

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Double Linked List in default haxe distrib

interaction-designer
Hi Justin,

What i meant to say, is that if a Single Linked List is part of the default haxe (not meaning the libs) then why not a Doubly Linked List, since they are both such basic and common data structures (it's not a red-back tree, an AVL or something)?

And second I will test it optimize it for various targets, give it more methods if that what it takes to get into the default distrib (if people would like to that is).

I am a beginner in Haxe, and I find it odd i have to look for libs for a standard datastructure like a Doubly linked list. Most of the Doubly Linked Lists in other libs I find too different (for example by using a class based iterator, instead of a type def) or too exotic (too many manipulation methods on the iterator, too few on the list itself), too much concentrated on one target (only flash) or are very much based on a - sorry - Java library (if not a bit too much). There fore I gave the code example. If it's much work to get it in de default distrib (not the libs) then I will put that effort in it. First I have to know if that is even wanted and second if people have any suggestions for what should a basic functionality doubly linked list provide in the sense of methods. If you don't think such a structure should be part of the default haxe distrib, then let me know also. I want to understand why some basic things get into the default distrib and other basic stuff doesn't, this is because start using a new langauge is a investment (and when it's very young a risky one). As I want to be able to use it for business too. And I like to provide some code, but then I have know how functionality and design decisions are made.

Simon Asselbergs



----- Oorspronkelijk bericht -----
Van: "Justin Donaldson" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Woensdag 12 mei 2010 03:05:45 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Double Linked List in default haxe distrib


Simon,

Thanks for your contribution.

The HaXe libraries are indeed "batteries included" in the sense that they provide class specifications for simple container structures, all the way up to server API's. These basic
class specifications are also usually highly tuned for each of the platforms that haXe targets. This is done through optimized conditional compilation for each of the targets, and this can be somewhat time consuming to specify and test (you might try seeing how some of the base classes are implemented in the std library, as well as looking for other articles on optimization like http://haxe.org/com/libs/listtools/which_iterable_type_should_i_use_ ). The haXe language has changed quickly, and most of the main developers have been working on those language features, rather than libraries. However, there's several other people that have provided their own low level libraries on haxelib: http://lib.haxe.org/ 

Feel free to browse around haxelib, I'm sure there are double linked list implementations in a number of different libraries. If you have some code that you think is faster, more flexible, or just prettier than what's available, please consider adding it as your own project, and making an announcement.

Best,
-Justin



On Tue, May 11, 2010 at 7:26 PM, < [hidden email] > wrote:


Hi all,

Just as a linked list is a very basic datatype included in the default haxe distrib, why not also include another very basic one: the Double Linked List?

It's not that hard to create a Double Linked List, but for some newcomers to haxe such a 'feauture' would be nice. To scratch that itch I have some code for you to review. I basically tried to do it in the same style as the official Linked List is coded. I have to put some code for example for an php (and maybe others) implementation in it by using the preprocessor instructions, which isn't much work.

However I would first want to know if you like to have a Double Linked List as a default feature. And also if the code generally is ok with coding style, maybe some extra methods, some speedups i should do, etc. I like to hear and then I will do anything if Nicholas and other like it to be part of the default datastructures set.

Warm Regards, Simon

class DLList<T> {
public var length(getLength, null):Int;
public function new() {
h = [null,null,null];
clear();
}
public function clear() {
h[2] = h[0] = h;
length_ = 0;
}
public function isEmpty():Bool {
return h[2] == h;
}
public function push(value:T) {
var newItem:Array<Dynamic> = [h[0], value, h];
newItem[0][2] = newItem;
h[0] = newItem;
length_++;
}
public function unshift(value:T) {
var newItem:Array<Dynamic> = [h, value, h[2]];
newItem[2][0] = newItem;
h[2] = newItem;
length_++;
}
public function pop() {
if(!isEmpty()){
h[0][0][2] = h[0][2];
h[0][2][0] = h[0][0];
length_--;
}
}
public function shift() {
if(!isEmpty()){
h[2][0][2] = h[2][2];
h[2][2][0] = h[2][0];
length_--;
}
}
public function iterator():DLListIterator<T> {
return cast {
owner:this,
h : h,
pos:h,
hasNext : function() {
return untyped (this.pos[2] != this.h );
},
hasPrevious : function() {
return untyped (this.pos[0] != this.h );
},
next : function() {
untyped {
if (this.pos[2] == this.h) return null;
this.pos = this.pos[2];
return this.pos[1];
}
},
previous : function() {
untyped {
if (this.pos[0] == this.h) return null;
this.pos = this.pos[0];
return this.pos[1];
}
}
}
}
private var length_:Int;
private var h : Array<Dynamic>;
private function getLength():Int {
return length_;
}
}


typedef DLListIterator<T> = {>Iterator<T>,
var hasPrevious:Dynamic;
var previous:Dynamic;
var h:Array<Dynamic>;
var pos:Array<Dynamic>;
}



--
haXe - an open source web programming language
http://haxe.org 



--
Justin Donaldson
PhD Candidate, Informatics
Indiana University
http://www.scwn.net 
aim: iujjd
twitter: jjdonald

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Double Linked List in default haxe distrib

Nicolas Cannasse
> I am a beginner in Haxe, and I find it odd i have to look for libs for a standard datastructure like a Doubly linked list.

We are trying to avoid having too much different containers for data,
since the more containers you have to more time you spend converting
data between one container and another depending on the method you are
using which require a specific container.

Some language deals with that by creating an abstract container which
actually remove all the usefulness of having several containers in the
first place.

The double linked list does not offer compelling advantages over the
single linked list in order to justify adding one more container in the
standard library.

Hope that helps,

Nicolas

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

RE: Double Linked List in default haxe distrib

Simon Krajewski
In reply to this post by interaction-designer
Hi Simon,

it's hard to draw the line between what's part of the standard distribution and what's part of the libs. If I examine my past usage of data structures, I realize that I used lots of lots of lists, but rarely double linked ones. Thus having them in the libs as opposed to the standard is justifiable for me. Why should it end with double linked lists, how about trees, hashes or other data structures? As I said, hard to draw the line.

Also, you pretty much gave another reason not to put them in the standard. Linked lists in several other libs don't match your requirements, so it's obviously a good thing they're part of the libs and not in the standard. I didn't check your code thoroughly, but I'm positive some people will find your solution not fitting their requirements. For instance, using Array<Dynamic> is painfully slow on the Flash target, so people targetting Flash won't like it.

However, I appreciate that you bring this up and put work into it. So what exactly does your double linked list do better than the ones in die libs?

Regards
Simon

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of [hidden email]
Sent: Mittwoch, 12. Mai 2010 11:52
To: The haXe compiler list
Subject: Re: [haXe] Double Linked List in default haxe distrib

Hi Justin,

What i meant to say, is that if a Single Linked List is part of the default haxe (not meaning the libs) then why not a Doubly Linked List, since they are both such basic and common data structures (it's not a red-back tree, an AVL or something)?

And second I will test it optimize it for various targets, give it more methods if that what it takes to get into the default distrib (if people would like to that is).

I am a beginner in Haxe, and I find it odd i have to look for libs for a standard datastructure like a Doubly linked list. Most of the Doubly Linked Lists in other libs I find too different (for example by using a class based iterator, instead of a type def) or too exotic (too many manipulation methods on the iterator, too few on the list itself), too much concentrated on one target (only flash) or are very much based on a - sorry - Java library (if not a bit too much). There fore I gave the code example. If it's much work to get it in de default distrib (not the libs) then I will put that effort in it. First I have to know if that is even wanted and second if people have any suggestions for what should a basic functionality doubly linked list provide in the sense of methods. If you don't think such a structure should be part of the default haxe distrib, then let me know also. I want to understand why some basic things get into the default distrib and other basic stuff doesn't, this is because start using a new langauge is a investment (and when it's very young a risky one). As I want to be able to use it for business too. And I like to provide some code, but then I have know how functionality and design decisions are made.

Simon Asselbergs



----- Oorspronkelijk bericht -----
Van: "Justin Donaldson" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Woensdag 12 mei 2010 03:05:45 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Double Linked List in default haxe distrib


Simon,

Thanks for your contribution.

The HaXe libraries are indeed "batteries included" in the sense that they provide class specifications for simple container structures, all the way up to server API's. These basic
class specifications are also usually highly tuned for each of the platforms that haXe targets. This is done through optimized conditional compilation for each of the targets, and this can be somewhat time consuming to specify and test (you might try seeing how some of the base classes are implemented in the std library, as well as looking for other articles on optimization like http://haxe.org/com/libs/listtools/which_iterable_type_should_i_use_ ). The haXe language has changed quickly, and most of the main developers have been working on those language features, rather than libraries. However, there's several other people that have provided their own low level libraries on haxelib: http://lib.haxe.org/ 

Feel free to browse around haxelib, I'm sure there are double linked list implementations in a number of different libraries. If you have some code that you think is faster, more flexible, or just prettier than what's available, please consider adding it as your own project, and making an announcement.

Best,
-Justin



On Tue, May 11, 2010 at 7:26 PM, < [hidden email] > wrote:


Hi all,

Just as a linked list is a very basic datatype included in the default haxe distrib, why not also include another very basic one: the Double Linked List?

It's not that hard to create a Double Linked List, but for some newcomers to haxe such a 'feauture' would be nice. To scratch that itch I have some code for you to review. I basically tried to do it in the same style as the official Linked List is coded. I have to put some code for example for an php (and maybe others) implementation in it by using the preprocessor instructions, which isn't much work.

However I would first want to know if you like to have a Double Linked List as a default feature. And also if the code generally is ok with coding style, maybe some extra methods, some speedups i should do, etc. I like to hear and then I will do anything if Nicholas and other like it to be part of the default datastructures set.

Warm Regards, Simon

class DLList<T> {
public var length(getLength, null):Int;
public function new() {
h = [null,null,null];
clear();
}
public function clear() {
h[2] = h[0] = h;
length_ = 0;
}
public function isEmpty():Bool {
return h[2] == h;
}
public function push(value:T) {
var newItem:Array<Dynamic> = [h[0], value, h];
newItem[0][2] = newItem;
h[0] = newItem;
length_++;
}
public function unshift(value:T) {
var newItem:Array<Dynamic> = [h, value, h[2]];
newItem[2][0] = newItem;
h[2] = newItem;
length_++;
}
public function pop() {
if(!isEmpty()){
h[0][0][2] = h[0][2];
h[0][2][0] = h[0][0];
length_--;
}
}
public function shift() {
if(!isEmpty()){
h[2][0][2] = h[2][2];
h[2][2][0] = h[2][0];
length_--;
}
}
public function iterator():DLListIterator<T> {
return cast {
owner:this,
h : h,
pos:h,
hasNext : function() {
return untyped (this.pos[2] != this.h );
},
hasPrevious : function() {
return untyped (this.pos[0] != this.h );
},
next : function() {
untyped {
if (this.pos[2] == this.h) return null;
this.pos = this.pos[2];
return this.pos[1];
}
},
previous : function() {
untyped {
if (this.pos[0] == this.h) return null;
this.pos = this.pos[0];
return this.pos[1];
}
}
}
}
private var length_:Int;
private var h : Array<Dynamic>;
private function getLength():Int {
return length_;
}
}


typedef DLListIterator<T> = {>Iterator<T>,
var hasPrevious:Dynamic;
var previous:Dynamic;
var h:Array<Dynamic>;
var pos:Array<Dynamic>;
}



--
haXe - an open source web programming language
http://haxe.org 



--
Justin Donaldson
PhD Candidate, Informatics
Indiana University
http://www.scwn.net 
aim: iujjd
twitter: jjdonald

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

RE: Double Linked List in default haxe distrib

Martijn Loots
On Wed, 12 May 2010, Simon Krajewski wrote:

> So what exactly does your double linked list do better than the ones
> in die libs?
>
I've written a few editors in the past; double linked lists are
very useful to delete stuff in the middle and just as easy to
step thru backwards as forwards.

That's about it IMHO. It's nice to have it as a building block
for these kind of projects in the haxelib. With functionality
like:

   for (node in dllist.reverse()) ...

   node = current.cut();

   current = current.previous;

   etc.

I don't see a real need for it within standard haXe neither,
because of its ease of implementation *if* necessary...

Grtz,
--
-Martijn    @..@    ( Martijn Loots       -  Hengelo  [NL] )
-          (`--')   ( martijn<@>cosix.com -  www.cosix.com )
-         ( >__< )  ----------------------------------------
-         ^^^  ^^^  (   Netwerken, Security, Open Source   )

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

RE: Double Linked List in default haxe distrib

Simon Krajewski
Hi,

my question was in which aspects his implementation of a DLL surpasses
implementations of the DLLs that can be found in the libs.

Regards
Simon

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Martijn Loots
Sent: Mittwoch, 12. Mai 2010 13:20
To: The haXe compiler list
Subject: RE: [haXe] Double Linked List in default haxe distrib

On Wed, 12 May 2010, Simon Krajewski wrote:

> So what exactly does your double linked list do better than the ones
> in die libs?
>
I've written a few editors in the past; double linked lists are
very useful to delete stuff in the middle and just as easy to
step thru backwards as forwards.

That's about it IMHO. It's nice to have it as a building block
for these kind of projects in the haxelib. With functionality
like:

   for (node in dllist.reverse()) ...

   node = current.cut();

   current = current.previous;

   etc.

I don't see a real need for it within standard haXe neither,
because of its ease of implementation *if* necessary...

Grtz,
--
-Martijn    @..@    ( Martijn Loots       -  Hengelo  [NL] )
-          (`--')   ( martijn<@>cosix.com -  www.cosix.com )
-         ( >__< )  ----------------------------------------
-         ^^^  ^^^  (   Netwerken, Security, Open Source   )

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Double Linked List in default haxe distrib

interaction-designer
In reply to this post by Simon Krajewski
Simon says: hi Simon :)

Supporting very primitive basic functionality to at least to have a lean and mean default core is important to most people I guess. So talking about what should be part of it or not is then important, there must be some reasoning and some standards for acceptance. That's why I want to know as it gives me some more idea how haxe was designed and how it can evoluate. I also want to contribute to that so i started talking about it, using as an example a Doubli Linked List with some code.

"it's hard to draw the line between what's part of the standard distribution and what's part of the libs"
To have a lean an mean, yet workable tool like haxe, it would be strange not too include very primitive basic data structures which are common and used often by a large group of people also complying to what is common sense nowadays. So ofcourse there is support for Array, etc. And using that same reasoning it is logical to have a Single Linked List and a Doubly Linked List included in the default especially since they are comparable primitive and commonly often used, right? Then why would a Doubly Linked List not be ion it?    

"Thus having them in the libs as opposed to the standard is justifiable for me. Why should it end with double linked lists, how about trees, hashes or other data structures? As I said, hard to draw the line."
  That makes a lot of sense to me. However the opposite reasoning is also possible, why wouldn't we exclude more? I think common and frequent use of very primitive functionality could be a very valid reason to have it in a default lean and mean haxe, without having to resort on haxelibs.

"Also, you pretty much gave another reason not to put them in the standard. Linked lists in several other libs don't match your requirements, so it's obviously a good thing they're part of the libs and not in the standard." I asked people to argue why Doudly Linked List should or shouldn't be part of the default install, so thanks. But I would nbuance a bit on the sentence "several other libs don't match your requirements"
  If I would think this would be just __my requirements__, I wouldn't care much for any discussion i would have it part of my own library and why i would even bother to open source it? I also say I want to code it to the requirements of the community if that community needs it. That's why I ask about requirements, that's why I try to use the same kind of style of code for the Double Linked List as the Singly Linked List which is part of the default, that's why i bring some code with me.

"using Array<Dynamic> is painfully slow on the Flash target, so people targetting Flash won't like it."
That's true and i don't like that too, but 1) But it's implemented very much the same as the default Single Linked List. 2) I said if people like the idea i will also optimize the code to the other targets other platforms and test it. I'll even provide unit test. Not hard, only a lot of work, that's why i will only do it if people would like the idea of having it. I want to contribute smart, i like words but code better so i couldn't resist to give an example of it.

Speaking of the example of code, if people would like such functionality I would start making the code also for more targets and of couse even test on it. If that is a lot of hassle, i be still glad to do it anyway. But i don't think it's a lot of hassle. It's simple code and testing is much simpler than coding, so np.

"So what exactly does your double linked list do better than the ones in die libs?"
I don't want it to be my double linked list. Again I just want to know what the reasoning is to have primitive commonly and often used fucntionality become part of the deafult haxe install without having to resort on libs. And I wan't to build they way the community, meaing also you, want. Again if it's just me I couldn't care less about open sourcing or contributing anything to it.

Regards,
Simon


----- Oorspronkelijk bericht -----
Van: "Simon Krajewski" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Woensdag 12 mei 2010 12:13:58 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: RE: [haXe] Double Linked List in default haxe distrib

Hi Simon,

it's hard to draw the line between what's part of the standard distribution and what's part of the libs. If I examine my past usage of data structures, I realize that I used lots of lots of lists, but rarely double linked ones. Thus having them in the libs as opposed to the standard is justifiable for me. Why should it end with double linked lists, how about trees, hashes or other data structures? As I said, hard to draw the line.

Also, you pretty much gave another reason not to put them in the standard. Linked lists in several other libs don't match your requirements, so it's obviously a good thing they're part of the libs and not in the standard. I didn't check your code thoroughly, but I'm positive some people will find your solution not fitting their requirements. For instance, using Array<Dynamic> is painfully slow on the Flash target, so people targetting Flash won't like it.

However, I appreciate that you bring this up and put work into it. So what exactly does your double linked list do better than the ones in die libs?

Regards
Simon

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of [hidden email]
Sent: Mittwoch, 12. Mai 2010 11:52
To: The haXe compiler list
Subject: Re: [haXe] Double Linked List in default haxe distrib

Hi Justin,

What i meant to say, is that if a Single Linked List is part of the default haxe (not meaning the libs) then why not a Doubly Linked List, since they are both such basic and common data structures (it's not a red-back tree, an AVL or something)?

And second I will test it optimize it for various targets, give it more methods if that what it takes to get into the default distrib (if people would like to that is).

I am a beginner in Haxe, and I find it odd i have to look for libs for a standard datastructure like a Doubly linked list. Most of the Doubly Linked Lists in other libs I find too different (for example by using a class based iterator, instead of a type def) or too exotic (too many manipulation methods on the iterator, too few on the list itself), too much concentrated on one target (only flash) or are very much based on a - sorry - Java library (if not a bit too much). There fore I gave the code example. If it's much work to get it in de default distrib (not the libs) then I will put that effort in it. First I have to know if that is even wanted and second if people have any suggestions for what should a basic functionality doubly linked list provide in the sense of methods. If you don't think such a structure should be part of the default haxe distrib, then let me know also. I want to understand why some basic things get into the default distrib and other basic stuff doesn't, this is because start using a new langauge is a investment (and when it's very young a risky one). As I want to be able to use it for business too. And I like to provide some code, but then I have know how functionality and design decisions are made.

Simon Asselbergs



----- Oorspronkelijk bericht -----
Van: "Justin Donaldson" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Woensdag 12 mei 2010 03:05:45 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Double Linked List in default haxe distrib


Simon,

Thanks for your contribution.

The HaXe libraries are indeed "batteries included" in the sense that they provide class specifications for simple container structures, all the way up to server API's. These basic
class specifications are also usually highly tuned for each of the platforms that haXe targets. This is done through optimized conditional compilation for each of the targets, and this can be somewhat time consuming to specify and test (you might try seeing how some of the base classes are implemented in the std library, as well as looking for other articles on optimization like http://haxe.org/com/libs/listtools/which_iterable_type_should_i_use_ ). The haXe language has changed quickly, and most of the main developers have been working on those language features, rather than libraries. However, there's several other people that have provided their own low level libraries on haxelib: http://lib.haxe.org/ 

Feel free to browse around haxelib, I'm sure there are double linked list implementations in a number of different libraries. If you have some code that you think is faster, more flexible, or just prettier than what's available, please consider adding it as your own project, and making an announcement.

Best,
-Justin



On Tue, May 11, 2010 at 7:26 PM, < [hidden email] > wrote:


Hi all,

Just as a linked list is a very basic datatype included in the default haxe distrib, why not also include another very basic one: the Double Linked List?

It's not that hard to create a Double Linked List, but for some newcomers to haxe such a 'feauture' would be nice. To scratch that itch I have some code for you to review. I basically tried to do it in the same style as the official Linked List is coded. I have to put some code for example for an php (and maybe others) implementation in it by using the preprocessor instructions, which isn't much work.

However I would first want to know if you like to have a Double Linked List as a default feature. And also if the code generally is ok with coding style, maybe some extra methods, some speedups i should do, etc. I like to hear and then I will do anything if Nicholas and other like it to be part of the default datastructures set.

Warm Regards, Simon

class DLList<T> {
public var length(getLength, null):Int;
public function new() {
h = [null,null,null];
clear();
}
public function clear() {
h[2] = h[0] = h;
length_ = 0;
}
public function isEmpty():Bool {
return h[2] == h;
}
public function push(value:T) {
var newItem:Array<Dynamic> = [h[0], value, h];
newItem[0][2] = newItem;
h[0] = newItem;
length_++;
}
public function unshift(value:T) {
var newItem:Array<Dynamic> = [h, value, h[2]];
newItem[2][0] = newItem;
h[2] = newItem;
length_++;
}
public function pop() {
if(!isEmpty()){
h[0][0][2] = h[0][2];
h[0][2][0] = h[0][0];
length_--;
}
}
public function shift() {
if(!isEmpty()){
h[2][0][2] = h[2][2];
h[2][2][0] = h[2][0];
length_--;
}
}
public function iterator():DLListIterator<T> {
return cast {
owner:this,
h : h,
pos:h,
hasNext : function() {
return untyped (this.pos[2] != this.h );
},
hasPrevious : function() {
return untyped (this.pos[0] != this.h );
},
next : function() {
untyped {
if (this.pos[2] == this.h) return null;
this.pos = this.pos[2];
return this.pos[1];
}
},
previous : function() {
untyped {
if (this.pos[0] == this.h) return null;
this.pos = this.pos[0];
return this.pos[1];
}
}
}
}
private var length_:Int;
private var h : Array<Dynamic>;
private function getLength():Int {
return length_;
}
}


typedef DLListIterator<T> = {>Iterator<T>,
var hasPrevious:Dynamic;
var previous:Dynamic;
var h:Array<Dynamic>;
var pos:Array<Dynamic>;
}



--
haXe - an open source web programming language
http://haxe.org 



--
Justin Donaldson
PhD Candidate, Informatics
Indiana University
http://www.scwn.net 
aim: iujjd
twitter: jjdonald

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Double Linked List in default haxe distrib

interaction-designer
In reply to this post by Nicolas Cannasse
Thanks Nicolas,

That was why i was asking for yet expressed much more compressed than I asked my question. Thanks!

Kindest Regards, Simon


----- Oorspronkelijk bericht -----
Van: "Nicolas Cannasse" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Woensdag 12 mei 2010 12:13:21 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Double Linked List in default haxe distrib

> I am a beginner in Haxe, and I find it odd i have to look for libs for a standard datastructure like a Doubly linked list.

We are trying to avoid having too much different containers for data,
since the more containers you have to more time you spend converting
data between one container and another depending on the method you are
using which require a specific container.

Some language deals with that by creating an abstract container which
actually remove all the usefulness of having several containers in the
first place.

The double linked list does not offer compelling advantages over the
single linked list in order to justify adding one more container in the
standard library.

Hope that helps,

Nicolas

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Double Linked List in default haxe distrib

Justin Donaldson
Here's a noteworthy new technique in iterators/list operations, called "ranges"
http://www.informit.com/articles/printerfriendly.aspx?p=1407357

At first glance, it seems to be a much more natural partitioning of interfaces for collections.  It also has the nice effect of always defining a beginning and end state (so you know both are valid).  This is a problem with arrays, but not as they are defined in most of the haXe targets.
http://www.devx.com/cplus/10MinuteSolution/36394/1954


-Justin

On Wed, May 12, 2010 at 8:49 AM, <[hidden email]> wrote:
Thanks Nicolas,

That was why i was asking for yet expressed much more compressed than I asked my question. Thanks!

Kindest Regards, Simon


----- Oorspronkelijk bericht -----
Van: "Nicolas Cannasse" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Woensdag 12 mei 2010 12:13:21 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Double Linked List in default haxe distrib

> I am a beginner in Haxe, and I find it odd i have to look for libs for a standard datastructure like a Doubly linked list.

We are trying to avoid having too much different containers for data,
since the more containers you have to more time you spend converting
data between one container and another depending on the method you are
using which require a specific container.

Some language deals with that by creating an abstract container which
actually remove all the usefulness of having several containers in the
first place.

The double linked list does not offer compelling advantages over the
single linked list in order to justify adding one more container in the
standard library.

Hope that helps,

Nicolas

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org



--
Justin Donaldson
PhD Candidate, Informatics
Indiana University
http://www.scwn.net
aim: iujjd
twitter: jjdonald

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Double Linked List in default haxe distrib

interaction-designer
In reply to this post by interaction-designer
Justin,

Thanks, for the great articles!!!

I always felt iterators should need some further evolution. Some implementations are horrible, most notable in that regard to me are the STL and Java iterator designs and implementations. So this article was a very interesting read with recognizable thoughts about iterators.

Justin and Nicholas, can you assign me some useful coding task for the default haxe library? Or some useful part which desperately needs some documentation?

Regards, Simon


----- Oorspronkelijk bericht -----
Van: "Justin Donaldson" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Donderdag 13 mei 2010 04:35:15 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Double Linked List in default haxe distrib


Here's a noteworthy new technique in iterators/list operations, called "ranges"
http://www.informit.com/articles/printerfriendly.aspx?p=1407357 

At first glance, it seems to be a much more natural partitioning of interfaces for collections. It also has the nice effect of always defining a beginning and end state (so you know both are valid). This is a problem with arrays, but not as they are defined in most of the haXe targets.
http://www.devx.com/cplus/10MinuteSolution/36394/1954 


-Justin


On Wed, May 12, 2010 at 8:49 AM, < [hidden email] > wrote:


Thanks Nicolas,

That was why i was asking for yet expressed much more compressed than I asked my question. Thanks!

Kindest Regards, Simon


----- Oorspronkelijk bericht -----
Van: "Nicolas Cannasse" < [hidden email] >

Aan: "The haXe compiler list" < [hidden email] >
Verzonden: Woensdag 12 mei 2010 12:13:21 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen

Onderwerp: Re: [haXe] Double Linked List in default haxe distrib




> I am a beginner in Haxe, and I find it odd i have to look for libs for a standard datastructure like a Doubly linked list.

We are trying to avoid having too much different containers for data,
since the more containers you have to more time you spend converting
data between one container and another depending on the method you are
using which require a specific container.

Some language deals with that by creating an abstract container which
actually remove all the usefulness of having several containers in the
first place.

The double linked list does not offer compelling advantages over the
single linked list in order to justify adding one more container in the
standard library.

Hope that helps,

Nicolas

--
haXe - an open source web programming language
http://haxe.org 

--
haXe - an open source web programming language
http://haxe.org 



--
Justin Donaldson
PhD Candidate, Informatics
Indiana University
http://www.scwn.net 
aim: iujjd
twitter: jjdonald

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Double Linked List in default haxe distrib

Tony Polinelli
I was also suprised by the SLL implementation in the std lib. Specifically that it doesnt give better performance over Array in the flash target. Also, that it doesnt allow for easy removal of items (without full iteration of the list) which are the 2 reasons that i would want to use a list over an array (especially in flash). There is haxe.FastList which uses proper linking to form the list - but apparantly cannot be used with Lambda. 
So, I think Justin (if i remember correctly) implemented sugarList? with a compile flag? 
A list which gave best performance in flash, allowed fast removal, and Lambda - would be great. I dont know the technicalities (presume there are some or it might already be done), but maybe this is a good start for a task?



On Thu, May 13, 2010 at 4:00 PM, <[hidden email]> wrote:
Justin,

Thanks, for the great articles!!!

I always felt iterators should need some further evolution. Some implementations are horrible, most notable in that regard to me are the STL and Java iterator designs and implementations. So this article was a very interesting read with recognizable thoughts about iterators.

Justin and Nicholas, can you assign me some useful coding task for the default haxe library? Or some useful part which desperately needs some documentation?

Regards, Simon


----- Oorspronkelijk bericht -----
Van: "Justin Donaldson" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Donderdag 13 mei 2010 04:35:15 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Double Linked List in default haxe distrib


Here's a noteworthy new technique in iterators/list operations, called "ranges"
http://www.informit.com/articles/printerfriendly.aspx?p=1407357

At first glance, it seems to be a much more natural partitioning of interfaces for collections. It also has the nice effect of always defining a beginning and end state (so you know both are valid). This is a problem with arrays, but not as they are defined in most of the haXe targets.
http://www.devx.com/cplus/10MinuteSolution/36394/1954


-Justin


On Wed, May 12, 2010 at 8:49 AM, < [hidden email] > wrote:


Thanks Nicolas,

That was why i was asking for yet expressed much more compressed than I asked my question. Thanks!

Kindest Regards, Simon


----- Oorspronkelijk bericht -----
Van: "Nicolas Cannasse" < [hidden email] >

Aan: "The haXe compiler list" < [hidden email] >
Verzonden: Woensdag 12 mei 2010 12:13:21 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen

Onderwerp: Re: [haXe] Double Linked List in default haxe distrib




> I am a beginner in Haxe, and I find it odd i have to look for libs for a standard datastructure like a Doubly linked list.

We are trying to avoid having too much different containers for data,
since the more containers you have to more time you spend converting
data between one container and another depending on the method you are
using which require a specific container.

Some language deals with that by creating an abstract container which
actually remove all the usefulness of having several containers in the
first place.

The double linked list does not offer compelling advantages over the
single linked list in order to justify adding one more container in the
standard library.

Hope that helps,

Nicolas

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org



--
Justin Donaldson
PhD Candidate, Informatics
Indiana University
http://www.scwn.net
aim: iujjd
twitter: jjdonald

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org



--
Tony Polinelli
http://touchmypixel.com

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Double Linked List in default haxe distrib

John Plsek
In reply to this post by interaction-designer
What I don't get is ... Why the "standard" library? It's no "better" or "worse" than an "add on" library as far as function goes. I use the format library quite a bit, for instance ... it's just as useful/fast/functional as an "add on" as it would be as a "standard" library

There's enough cruft in the standard library already ... and I'm sure that other people use about the same percentage of the standard as I do ... not necessarily the same parts though

Is there some "majicks" about some class or other being in "the standard" library that gives it some advantage over one that isn't?

Seriously - there's more genius and shear poetry in the add on libs than there is in the standard lib (no offence intended)


On 13 May 2010 16:00, <[hidden email]> wrote:
Justin,

Thanks, for the great articles!!!

I always felt iterators should need some further evolution. Some implementations are horrible, most notable in that regard to me are the STL and Java iterator designs and implementations. So this article was a very interesting read with recognizable thoughts about iterators.

Justin and Nicholas, can you assign me some useful coding task for the default haxe library? Or some useful part which desperately needs some documentation?

Regards, Simon


----- Oorspronkelijk bericht -----
Van: "Justin Donaldson" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Donderdag 13 mei 2010 04:35:15 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Double Linked List in default haxe distrib


Here's a noteworthy new technique in iterators/list operations, called "ranges"
http://www.informit.com/articles/printerfriendly.aspx?p=1407357

At first glance, it seems to be a much more natural partitioning of interfaces for collections. It also has the nice effect of always defining a beginning and end state (so you know both are valid). This is a problem with arrays, but not as they are defined in most of the haXe targets.
http://www.devx.com/cplus/10MinuteSolution/36394/1954


-Justin


On Wed, May 12, 2010 at 8:49 AM, < [hidden email] > wrote:


Thanks Nicolas,

That was why i was asking for yet expressed much more compressed than I asked my question. Thanks!

Kindest Regards, Simon


----- Oorspronkelijk bericht -----
Van: "Nicolas Cannasse" < [hidden email] >

Aan: "The haXe compiler list" < [hidden email] >
Verzonden: Woensdag 12 mei 2010 12:13:21 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen

Onderwerp: Re: [haXe] Double Linked List in default haxe distrib




> I am a beginner in Haxe, and I find it odd i have to look for libs for a standard datastructure like a Doubly linked list.

We are trying to avoid having too much different containers for data,
since the more containers you have to more time you spend converting
data between one container and another depending on the method you are
using which require a specific container.

Some language deals with that by creating an abstract container which
actually remove all the usefulness of having several containers in the
first place.

The double linked list does not offer compelling advantages over the
single linked list in order to justify adding one more container in the
standard library.

Hope that helps,

Nicolas

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org



--
Justin Donaldson
PhD Candidate, Informatics
Indiana University
http://www.scwn.net
aim: iujjd
twitter: jjdonald

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org



--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Double Linked List in default haxe distrib

Tarwin Stroh-Spijer
My understanding is that if something is implemented in the standard library then conceivably it could be optimized per-platform, as long as the signature doesn't change. Is this incorrect?


Tarwin Stroh-Spijer
_______________________

Touch My Pixel
http://www.touchmypixel.com/
phone: +61 3 8060 5321
_______________________

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Double Linked List in default haxe distrib

interaction-designer
In reply to this post by John Plsek
Dear John,

There is nothing wrong with add on libraries. However the continuity of addons i question quite a lot, it happened a lot that addons are still rough around the edges and maintainance is questionable. This is not an issue for read once deploy directly projects, but for bigger longer term projects it is a serious concern. This is not obnly a problem of haxe, it is a problem everywhere. Just take a look at osflash.org or at the updates of most of the haxelibs at their repositories, and you quickly get my point here, i am sure.

Also I like the standard lib to be lean and man, I always liked that about Flash and hated the lack of it with Java. A lot of libs out side the standard one are also good, because it means that means thing are evolving. However I also like to contribute something to the thing which has in my opinion the most ciontinuity, which is the default lib of haxe.

Warmest Regards, Simon

----- Oorspronkelijk bericht -----
Van: "John Plsek" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Donderdag 13 mei 2010 08:13:08 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Double Linked List in default haxe distrib


What I don't get is ... Why the "standard" library? It's no "better" or "worse" than an "add on" library as far as function goes. I use the format library quite a bit, for instance ... it's just as useful/fast/functional as an "add on" as it would be as a "standard" library


There's enough cruft in the standard library already ... and I'm sure that other people use about the same percentage of the standard as I do ... not necessarily the same parts though


Is there some "majicks" about some class or other being in "the standard" library that gives it some advantage over one that isn't?


Seriously - there's more genius and shear poetry in the add on libs than there is in the standard lib (no offence intended)




On 13 May 2010 16:00, < [hidden email] > wrote:


Justin,

Thanks, for the great articles!!!

I always felt iterators should need some further evolution. Some implementations are horrible, most notable in that regard to me are the STL and Java iterator designs and implementations. So this article was a very interesting read with recognizable thoughts about iterators.

Justin and Nicholas, can you assign me some useful coding task for the default haxe library? Or some useful part which desperately needs some documentation?

Regards, Simon


----- Oorspronkelijk bericht -----

Van: "Justin Donaldson" < [hidden email] >

Aan: "The haXe compiler list" < [hidden email] >
Verzonden: Donderdag 13 mei 2010 04:35:15 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen



Onderwerp: Re: [haXe] Double Linked List in default haxe distrib


Here's a noteworthy new technique in iterators/list operations, called "ranges"
http://www.informit.com/articles/printerfriendly.aspx?p=1407357 

At first glance, it seems to be a much more natural partitioning of interfaces for collections. It also has the nice effect of always defining a beginning and end state (so you know both are valid). This is a problem with arrays, but not as they are defined in most of the haXe targets.
http://www.devx.com/cplus/10MinuteSolution/36394/1954 


-Justin


On Wed, May 12, 2010 at 8:49 AM, < [hidden email] > wrote:


Thanks Nicolas,

That was why i was asking for yet expressed much more compressed than I asked my question. Thanks!

Kindest Regards, Simon


----- Oorspronkelijk bericht -----
Van: "Nicolas Cannasse" < [hidden email] >

Aan: "The haXe compiler list" < [hidden email] >
Verzonden: Woensdag 12 mei 2010 12:13:21 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen

Onderwerp: Re: [haXe] Double Linked List in default haxe distrib




> I am a beginner in Haxe, and I find it odd i have to look for libs for a standard datastructure like a Doubly linked list.

We are trying to avoid having too much different containers for data,
since the more containers you have to more time you spend converting
data between one container and another depending on the method you are
using which require a specific container.

Some language deals with that by creating an abstract container which
actually remove all the usefulness of having several containers in the
first place.

The double linked list does not offer compelling advantages over the
single linked list in order to justify adding one more container in the
standard library.

Hope that helps,

Nicolas

--
haXe - an open source web programming language
http://haxe.org 

--
haXe - an open source web programming language
http://haxe.org 



--
Justin Donaldson
PhD Candidate, Informatics
Indiana University
http://www.scwn.net 
aim: iujjd
twitter: jjdonald

--



haXe - an open source web programming language
http://haxe.org 

--
haXe - an open source web programming language
http://haxe.org 



--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Double Linked List in default haxe distrib

Justin Donaldson
A couple of points/thoughts:

  1. The standard library gets some advantages in some cases.  For instance, FastList has an optimized for loop that's impossible to implement in normal haXe code.  Nicolas is trying to implement removal of temporary stack variables in an upcoming release, and when that happens, it should have the same effective optimization for other iterators in some cases.
  2. You can already optimize a container class per-platform if you want, this was essentially the motivation behind my SugarList experiment.  Although, in my case, it made sense to switch to the alternate implementation of SugarList via an hxml flag, rather than through target based conditional compilation (mainly debugging reasons).
  3. Removal/Insertion of List items is possible, but also makes it possible to invalidate the list and cause difficult errors, especially if you have any sort of  situation where two methods share the same List.  Java has an indexed addAll method for List, but it also checks if the underlying List was modified externally during iteration : http://java.sun.com/j2se/1.4.2/docs/api/java/util/LinkedList.html
    Something like that would be possible in haXe, but I imagine extra checks would slow things down.  Also, implementing inserts based on indices has pretty poor performance.  It's O(n) per insert, which is effectively the same speed as recreating a modified version of the entire List in some cases.  The interesting alternative is C++ stl list insert methods... more on that in the link below. 
There was a pretty good thread a while back on FastLists and insert methods, and Nicolas gave some thoughts on why insert methods are missing:
http://lists.motion-twin.com/pipermail/haxe/2009-August/028414.html

That thread actually contains a lot of good information on iteration/insertion in general, and some quick hacks to get a functioning insert working for FastList (or List with the same approach) thanks to Ian Liu.  However, I still consider lists/insertion to be an open problem.

-Justin

On Thu, May 13, 2010 at 3:01 AM, <[hidden email]> wrote:
Dear John,

There is nothing wrong with add on libraries. However the continuity of addons i question quite a lot, it happened a lot that addons are still rough around the edges and maintainance is questionable. This is not an issue for read once deploy directly projects, but for bigger longer term projects it is a serious concern. This is not obnly a problem of haxe, it is a problem everywhere. Just take a look at osflash.org or at the updates of most of the haxelibs at their repositories, and you quickly get my point here, i am sure.

Also I like the standard lib to be lean and man, I always liked that about Flash and hated the lack of it with Java. A lot of libs out side the standard one are also good, because it means that means thing are evolving. However I also like to contribute something to the thing which has in my opinion the most ciontinuity, which is the default lib of haxe.

Warmest Regards, Simon

----- Oorspronkelijk bericht -----
Van: "John Plsek" <[hidden email]>
Aan: "The haXe compiler list" <[hidden email]>
Verzonden: Donderdag 13 mei 2010 08:13:08 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen
Onderwerp: Re: [haXe] Double Linked List in default haxe distrib


What I don't get is ... Why the "standard" library? It's no "better" or "worse" than an "add on" library as far as function goes. I use the format library quite a bit, for instance ... it's just as useful/fast/functional as an "add on" as it would be as a "standard" library


There's enough cruft in the standard library already ... and I'm sure that other people use about the same percentage of the standard as I do ... not necessarily the same parts though


Is there some "majicks" about some class or other being in "the standard" library that gives it some advantage over one that isn't?


Seriously - there's more genius and shear poetry in the add on libs than there is in the standard lib (no offence intended)




On 13 May 2010 16:00, < [hidden email] > wrote:


Justin,

Thanks, for the great articles!!!

I always felt iterators should need some further evolution. Some implementations are horrible, most notable in that regard to me are the STL and Java iterator designs and implementations. So this article was a very interesting read with recognizable thoughts about iterators.

Justin and Nicholas, can you assign me some useful coding task for the default haxe library? Or some useful part which desperately needs some documentation?

Regards, Simon


----- Oorspronkelijk bericht -----

Van: "Justin Donaldson" < [hidden email] >

Aan: "The haXe compiler list" < [hidden email] >
Verzonden: Donderdag 13 mei 2010 04:35:15 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen



Onderwerp: Re: [haXe] Double Linked List in default haxe distrib


Here's a noteworthy new technique in iterators/list operations, called "ranges"
http://www.informit.com/articles/printerfriendly.aspx?p=1407357

At first glance, it seems to be a much more natural partitioning of interfaces for collections. It also has the nice effect of always defining a beginning and end state (so you know both are valid). This is a problem with arrays, but not as they are defined in most of the haXe targets.
http://www.devx.com/cplus/10MinuteSolution/36394/1954


-Justin


On Wed, May 12, 2010 at 8:49 AM, < [hidden email] > wrote:


Thanks Nicolas,

That was why i was asking for yet expressed much more compressed than I asked my question. Thanks!

Kindest Regards, Simon


----- Oorspronkelijk bericht -----
Van: "Nicolas Cannasse" < [hidden email] >

Aan: "The haXe compiler list" < [hidden email] >
Verzonden: Woensdag 12 mei 2010 12:13:21 GMT +01:00 Amsterdam / Berlijn / Bern / Rome / Stockholm / Wenen

Onderwerp: Re: [haXe] Double Linked List in default haxe distrib




> I am a beginner in Haxe, and I find it odd i have to look for libs for a standard datastructure like a Doubly linked list.

We are trying to avoid having too much different containers for data,
since the more containers you have to more time you spend converting
data between one container and another depending on the method you are
using which require a specific container.

Some language deals with that by creating an abstract container which
actually remove all the usefulness of having several containers in the
first place.

The double linked list does not offer compelling advantages over the
single linked list in order to justify adding one more container in the
standard library.

Hope that helps,

Nicolas

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org



--
Justin Donaldson
PhD Candidate, Informatics
Indiana University
http://www.scwn.net
aim: iujjd
twitter: jjdonald

--



haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org



--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org



--
Justin Donaldson
PhD Candidate, Informatics
Indiana University
http://www.scwn.net
aim: iujjd
twitter: jjdonald

--
haXe - an open source web programming language
http://haxe.org