anonymous rb-trees?

[TedWalther]

You create an array with (array ...) but it mostly acts like a list.



I've often wanted anonymous rb-trees.



Often, I'd like to have a list of "objects", but want to access the data in them with the same syntax as with rb trees.  It is nice that we now have anonymous objects;  can we have anonymous rb-trees?



Also, I'm still trying to wrap my head around the way that contexts and rb-trees are crumpled together.  They seem like unique and independant contexts.



Lutz, would it be possible to separate them out?  When I use rb trees, I don't usually need the other stuff that a context implies.  Not saying there is any overhead speedwise. It is just grappling with it in my head.



A lot of times I deal with data where I need to stash it in rows, and there is a lot of self-similarity, but there is also odd data that pops in which I also want to stuff into the data structure and save.



How about (rbtree ...) ?



This would fit in with the default functor; right now there is no way to access the "default functor" other than with (define), but with an rbtree, the default function could be used without generating a context.

Ted

[Lutz]

- regarding arrays

Most of the functions used to access and modify lists can also be used on arrays. This lets you start out with a list, and if you have performance problems on random access in large lists, you can re-create them as arrays without the need for any other code change.



- regarding rb-trees

A quick overview how contexts/namespaces - implemented with rb-trees - are used in newLISP:



(1) Program modules modularize code into lexically isolated units. Symbols inside the tree hold different functions and data. The default functor can be used as an abbreviated function name or is not used at all.



(2) Hash trees for fast associative key <-> value access. The default functor must contain nil, which causes it to work like a hash function. Symbols in the tree are the keys containing values.



(3) They are used as OO classes in FOOP (Functional Object Oriented Programming). The default functor contains the constructor and all other symbols old methods or serve as class variables.



All three usages are implemented with the same context rb-trees.  Rb-trees cannot be anonymous in newLISP, they are part of the main symbol tree and must be attached to a symbol. If you need anonymous objects with inside key <-> value access, use association lists.



There is no overhead associated with all of these. The difference between the three use cases is only semantic and what you do (or not do) with the default functor (the functor with the same names as the context name). There is only the symbol by which it is called, and that is all. You can have millions of trees, don't worry about overhead, it exists only in your head, probably because we call the tree a "namespace". But this "space" is only as big as its contents.

[TedWalther]

Lutz, thanks for the overview.  I am interested in anonymous rbtree objects so that ORO can be applied to them, as they are created and destroyed rapidly.  That would free me from having to do the book-keeping.



Ted

[itistoday]

I've posted various techniques for creating pseudo-anonymous objects in newLISP (i.e. see my sig). You can do the same with rb-trees. Just create a function that creates contexts with a prefix + incrementing number (i.e. like 'gensym').

[TedWalther]

Thanks itistoday.  Are these objects garbage collected with ORO?

[itistoday]

Thanks itistoday.  Are these objects garbage collected with ORO?

They must be manually managed via reference counting (like in objective-c), see the link for details.

[schilling.klaus]

Is it possible to use the foreign function interface and an external c library that implements balaned trees, such as glib or GNU AVL?

[Lutz]

I am pretty sure it is possible to import GNU AVL or similar and probably you can do it using either of the two import APIs in newLISP: the simple and the extended API.



But may be, it is redundant for your application, because newLISP itself uses RB trees internally for symbol trees and exposes them four use in applications as explained earlier in this thread and here:



http://www.newlisp.org/downloads/newlisp_manual.html#hash">http://www.newlisp.org/downloads/newlis ... .html#hash">http://www.newlisp.org/downloads/newlisp_manual.html#hash

[schilling.klaus]

Do the internally implemented trees allow for supplying a user-defined comparison function, making it possible to implement a balanced binary tree sort?

[Lutz]

They don't allow for a user-defined comparison function. The built-in comparison is done alphabetically and (symbols <context>) returns all symbols in alphabetical order and (dotree ...) iterates alphabetically too.



So for anything else you would have to import functions from an external library. Hopefully that external library lets you register callbacks to specify a newLISP written comparison function.

[schilling.klaus]

GNU AVL takes a function pointer for the comparison function, data are void*.

[Lutz]

Sounds good. There is example code for callbacks here:



http://www.newlisp.org/downloads/OpenGL/opengl-demo-lsp.txt">http://www.newlisp.org/downloads/OpenGL ... mo-lsp.txt">http://www.newlisp.org/downloads/OpenGL/opengl-demo-lsp.txt

http://www.newlisp.org/downloads/OpenGL/opengl-demo-ffi-lsp.txt">http://www.newlisp.org/downloads/OpenGL ... fi-lsp.txt">http://www.newlisp.org/downloads/OpenGL/opengl-demo-ffi-lsp.txt



and in the source distribution:



newlisp-10.4.5/qa-specific-tests/qa-ffi

newlisp-10.4.5/qa-specific-tests/qa-libffi



Note that the 'import' and 'callback' functions both have simple and extended syntactic forms. The simple form doesn't specify data types the extended does. If newLISP's sign-on line contains the term "libffi" you are running a version of newLISP capable of the extended API.



All binary distributions (OSX, Windows, UBUNTU Linux) are capable of this extended, typed 'import' and 'callback' interface. The required libffi library is installed standard on OSX and Windows and on most Linux distributions.



The major part of library imports can be solved via the simple API, but the extended does better diagnosis and error messages.