red-black and other trees

Hi -

I am considering implementing a Centered Interval Tree
(http://en.wikipedia.org/wiki/Interval_tree) because I have to get the
set of Timespans a particular Timespan overlaps from an arbitrary set of
Timespans.


In looking around I can only find the BTree implementation on
SqueakSource, and the Left-Leaning-Red-Black-Tree linked to in the
following list posting:
http://forum.world.st/Interesting-survey-about-smalltalk-tp2261561p2263370.html


Does Pharo either not need/benefit from the various kinds of trees?

Or is it trivial to implement/adapt the BTree to behave as a Red-Black
Tree (or, in my case, the Centered Interval Tree) and as such I just
need to learn how to do that?

Thanks

Paul

The BTree package contains a class called DateTree for exactly that
purpose. Works very well with huge collections of date intervals.

Lukas

On 12 October 2011 22:13, Paul DeBruicker <[hidden email]> wrote:


--
Lukas Renggli
www.lukas-renggli.ch

I created the CenteredIntervalTree repo on Squeaksource.  The
CenteredIntervalTree is about 2x slower  to create than a DateTree but
50-500x faster to query in Pharo 1.3 on Linux. The speed difference
remains relatively constant as the tree size grows.   I only tested up
to 1,000,000 timespans.   It works with instances of class Interval and
Timespan.  Converting the Timespans to Intervals using #asSeconds makes
the creation process faster than the DateTree creation process.

I used the code below to approximate the speed differences.  You need to
have the BTree package loaded from SqueakSource to try the example below.


Paul


|timespanDatabase  dateTree centeredIntervalTree timespansOfInterest
timingResults results size iterations interval tmpResults citResults
dtResults|
size:=10.
iterations:=10.
interval:=1 to: size.
results:=Dictionary new.
timingResults := Dictionary new.
timespanDatabase:= OrderedCollection new.
interval do:[:eachMonth | interval do: [:eachDay| interval
do:[:eachHour| timespanDatabase add:(Timespan starting: (DateAndTime now
+ (eachMonth*30) days + eachDay days + eachHour hours) duration: 2
hours)]]].
timespansOfInterest :=OrderedCollection new.
timespansOfInterest add: (timespanDatabase at: 20).
interval do:[:each | timespansOfInterest add: timespanDatabase atRandom].
results at: 'timespanDatabase-size' put:timespanDatabase size.
"results at: 'timespanDatabase' put: timespanDatabase ."
timingResults at:'dateTree-creation' put:([iterations
timesRepeat:[dateTree:=DateTree new.
                        timespanDatabase do:[:eachTimespan| dateTree at: eachTimespan put:
eachTimespan]]] timeToRun).
timingResults at:'dateTree-query' put:([iterations
timesRepeat:[tmpResults:=Dictionary new.
                timespansOfInterest do: [:each | tmpResults at: each put: (dateTree
during: each)]]] timeToRun).
results at:'dateTree-results' put: tmpResults.

timingResults at:'centeredIntervalTree-creation' put:([iterations
timesRepeat:[centeredIntervalTree :=CenteredIntervalTree from:
timespanDatabase ]] timeToRun).

timingResults at:'centeredIntervalTree-query' put:([iterations
timesRepeat:[tmpResults:=Dictionary new.
                timespansOfInterest do:[:each | tmpResults at: each put:
(centeredIntervalTree intervalsThatInclude: each) asSet]]] timeToRun).
results at:'centeredIntervalTree-results' put: tmpResults.
citResults:=OrderedCollection new.
(results at: 'centeredIntervalTree-results') keysAndValuesDo: [:timespan
:col| citResults addAll:col].
dtResults:=OrderedCollection new.
(results at: 'dateTree-results') keysAndValuesDo: [:timespan :col|
dtResults addAll:col].
dtResults size = citResults size ifFalse:[self halt.].
(dtResults includesAllOf: citResults) ifFalse:[self halt].
(citResults includesAllOf: dtResults) ifFalse:[self halt].
timingResults

On 10/13/2011 03:03 AM, [hidden email] wrote: