Path: utzoo!attcan!uunet!zephyr.ens.tek.com!uw-beaver!milton!dali.cs.montana.edu!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!ub!oswego!news From: dl@g.g.oswego.edu (Doug Lea) Newsgroups: comp.theory Subject: Re: data structures of Tarjan, et.al and actual applications? Message-ID: Date: 1 Oct 90 10:36:44 GMT References: <1990Sep23.193541.33486@eagle.wesleyan.edu> <2430@ns-mx.uiowa.edu> <1990Sep26.021208.29411@ux1.cso.uiuc.edu> Sender: news@oswego.Oswego.EDU (Network News) Reply-To: dl@g.oswego.edu Organization: SUNY Oswego Lines: 31 In-reply-to: gooley@aquinas.csl.uiuc.edu's message of 26 Sep 90 02:12:08 GMT > In article <2430@ns-mx.uiowa.edu> jones@pyrite.cs.uiowa.edu > (Douglas W. Jones,201H MLH,3193350740,3193382879) writes: > >From article <1990Sep23.193541.33486@eagle.wesleyan.edu>, > >by aliao@eagle.wesleyan.edu: > > > >> Has anyone else been using the data structures that Bob Tarjan, et. al > >> in any actual applications? > > > >Dave Brower of Sun Microsystems transliterated my Pascal version of splay > >trees to C some time ago, and an early version of his transliteration is > >in the Gnu C++ library. Unfortunately, that version has a bug (it won't > >delete the last item from a tree!) but I gather it's been fairly widely > >used with no complaints (because few people delete randomly in a tree, I > >guess). > > Someone got their facts mixed up. The GNU C++ Library (libg++) versions of Splay trees are not simply transliterated from either Brower's or Jones's code (although several tricks and representational details were based on their versions, which is why I credited them in the headers). In particular, this bug does not exist in libg++ Splay trees. While I'm at it, Skip List implementations of Sets and Bags will be available in libg++ within a month or so. -Doug -- Doug Lea dl@g.oswego.edu || dl@cat.syr.edu || (315)341-2688 || (315)443-1060 || Computer Science Department, SUNY Oswego, Oswego, NY 13126 || Software Engineering Lab, NY CASE Center, Syracuse Univ., Syracuse NY 13244