Recommendation for a CL data structures library
in [Lisp]
|
Prev: [2nd CfP] 7th European Lisp Workshop at ECOOP'10, June 21/22
Next: §§§ 2010 Cheap wholesale ED Hardy Suit, Baby Suit, Lacoste Suit ect at www.rijing-trade.com <Paypal Payment>
From: RG on 19 Mar 2010 14:48 In article <ho03jo$t38$1(a)news.eternal-september.org>, Raffael Cavallaro <raffaelcavallaro(a)pas.espam.s.il.vous.plait.mac.com> wrote: > On 2010-03-19 09:24:34 -0400, Pascal J. Bourguignon said: > > > What about > > http://darcs2.informatimago.com/lisp/common-lisp/llrbtree.lisp > > (Left Leaning Red-Black Tree). > > It even has a with-tree-iterator macro! > > Maybe you don't realize this Pascal, but even though much of your code > may be quite interesting, no one who currently works on a commercial, > published product, or who contemplates working on a commercial > published product in the future, can take the risk of using your > libraries because they are GPL licensed. > > Using them would place their employer or the commercial organization to > which they belong under the obligation of publishing all of the source > code for any released product that included your library. As a result, > most people working on commercial published software, or who > contemplate doing so in the future, simply avoid gpl libraries > altogether. Publishing code under the GPL does not preclude the copyright holder from also making the code available under a commercial license. If you want to use PJB's code in a commercial product why don't you just ask him for a price quote? rg
From: RG on 19 Mar 2010 16:14 In article <87vdcsv3zh.fsf(a)galatea.lan.informatimago.com>, pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: > "Alex Mizrahi" <udodenko(a)users.sourceforge.net> writes: > > > ??>> What do you need precisely? > > > > R> For now just an associative map that's O(logN) for inserts and lookups > > R> on ordered keys. But I figured as long as I was looking I'd fill out my > > R> collection as completely as possible in anticipation of future needs. > > > > I was looking for a sane library which implements binary tree-based > > associative container, but wasn't able to find any :(. > > There are some tree implementations, but they lack iterators and stuff > > like that. > > What about > http://darcs2.informatimago.com/lisp/common-lisp/llrbtree.lisp > (Left Leaning Red-Black Tree). I like it. Clean code. Wicked fast. > It even has a with-tree-iterator macro! This I don't like so much because: The data is collected before iterating, so you can modify the tree at will during iteration. Collecting all the data ahead of time is a very high price to pay for mutability during traversal. But this is a minor nit. llrbtree is more or less exactly what I was looking for. Thanks! rg
From: Pascal J. Bourguignon on 19 Mar 2010 15:17 RG <rNOSPAMon(a)flownet.com> writes: > In article <87vdcsv3zh.fsf(a)galatea.lan.informatimago.com>, > pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: > >> "Alex Mizrahi" <udodenko(a)users.sourceforge.net> writes: >> >> > ??>> What do you need precisely? >> > >> > R> For now just an associative map that's O(logN) for inserts and lookups >> > R> on ordered keys. But I figured as long as I was looking I'd fill out my >> > R> collection as completely as possible in anticipation of future needs. >> > >> > I was looking for a sane library which implements binary tree-based >> > associative container, but wasn't able to find any :(. >> > There are some tree implementations, but they lack iterators and stuff >> > like that. >> >> What about >> http://darcs2.informatimago.com/lisp/common-lisp/llrbtree.lisp >> (Left Leaning Red-Black Tree). > > I like it. Clean code. Wicked fast. > >> It even has a with-tree-iterator macro! > > This I don't like so much because: > > The data is collected before iterating, so you can modify the > tree at will during iteration. > > Collecting all the data ahead of time is a very high price to pay for > mutability during traversal. But this is a minor nit. llrbtree is more > or less exactly what I was looking for. I take note of the popular demand for a better with-tree-iterator :-) As soon as I have some time to work on it, I'll do. But if you're in a hurry, better do it yourself and contribute ;-). -- __Pascal Bourguignon__
From: RG on 19 Mar 2010 19:26 In article <871vfgunmw.fsf(a)galatea.lan.informatimago.com>, pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: > RG <rNOSPAMon(a)flownet.com> writes: > > > In article <87vdcsv3zh.fsf(a)galatea.lan.informatimago.com>, > > pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: > > > >> "Alex Mizrahi" <udodenko(a)users.sourceforge.net> writes: > >> > >> > ??>> What do you need precisely? > >> > > >> > R> For now just an associative map that's O(logN) for inserts and > >> > lookups > >> > R> on ordered keys. But I figured as long as I was looking I'd fill out > >> > my > >> > R> collection as completely as possible in anticipation of future needs. > >> > > >> > I was looking for a sane library which implements binary tree-based > >> > associative container, but wasn't able to find any :(. > >> > There are some tree implementations, but they lack iterators and stuff > >> > like that. > >> > >> What about > >> http://darcs2.informatimago.com/lisp/common-lisp/llrbtree.lisp > >> (Left Leaning Red-Black Tree). > > > > I like it. Clean code. Wicked fast. > > > >> It even has a with-tree-iterator macro! > > > > This I don't like so much because: > > > > The data is collected before iterating, so you can modify the > > tree at will during iteration. > > > > Collecting all the data ahead of time is a very high price to pay for > > mutability during traversal. But this is a minor nit. llrbtree is more > > or less exactly what I was looking for. > > I take note of the popular demand for a better with-tree-iterator :-) > As soon as I have some time to work on it, I'll do. But if you're in a > hurry, better do it yourself and contribute ;-). Here you go: (defun make-iterator1 (tree) (let ((node (tree-root tree)) (stack nil) (state :left)) (labels ((loop () (ecase state (:left (cond ((null (node-left node)) (setf state :right) (values t (node-key node) (node-value node))) (t (push node stack) (setf node (node-left node)) (loop)))) (:right (cond ((null (node-right node)) (setf state :up) (loop)) (t (push node stack) (setf node (node-right node)) (setf state :left) (loop)))) (:up (cond ((null stack) nil) ((eq node (node-left (car stack))) (setf node (pop stack)) (setf state :right) (values t (node-key node) (node-value node))) (t (setf node (pop stack)) (loop))))))) #'loop))) rg
From: Raffael Cavallaro on 19 Mar 2010 23:53
On 2010-03-19 14:48:25 -0400, RG said: > Publishing code under the GPL does not preclude the copyright holder > from also making the code available under a commercial license. If you > want to use PJB's code in a commercial product why don't you just ask > him for a price quote? That's certainly true, and if I wanted/needed any of his libraries for use in a commercial product, I certainly would (assuming a commercial license were within budget, etc.). However, as I'm sure you know, the library space is fairly competitive, and many of the competitors' offerings are not GPL licensed, with the predictable result that these other libraries will see wider use. warmest regards, Ralph -- Raffael Cavallaro |