scala.Collection, Seq, jcl.Collection, Buffer

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

scala.Collection, Seq, jcl.Collection, Buffer

Hanns Holger Rutz
hello,

i'm a little bit confusion by the amount of possible variants of  
using collections, like Seq, Collection, Buffer, ArrayList,  
ArrayBuffer, ...

i'm going to have two traits RTrail and WTrail, where RTrail is a  
read-only collection, WTrail extends RTrail by making it writable /  
mutable.

Which of the following two scenarios makes more sense:

1.)

trait RTrail[S <: Stake] extends Collection[S]  ...
trait WTrail[S <: Stake ] extends RTrail[S] with  
scala.collection.jcl.Collection[S]  ...

2.)

trait RTrail[S <: Stake] extends Seq[S]  ...
trait WTrail[S <: Stake ] extends RTrail[S] with Buffer[S]  ...


i think the second looks better, because i would like to have the  
apply method of Seq which is not found in scala.Collection. i seems  
that the variant:

3.)

trait RTrail[S <: Stake] extends Seq[S]  ...
trait WTrail[S <: Stake ] extends RTrail[S] with  
scala.collection.jcl.Collection[S]  ...

doesn't work because Seq and jcl.Collection are incompatible?

the chosen variant must have the best performance (speed-wise). trail  
is internally back up'ed by two sorted ArrayLists which seem to be  
faster than ArrayBuffer for random access operations.

thanks, -sciss-

Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Hanns Holger Rutz
err, well, and if i use variant two, should i use  
scala.collection.jcl.Buffer or scala.collection.mutable.Buffer?


Am 20.06.2008 um 18:31 schrieb Sciss:

> hello,
>
> i'm a little bit confusion by the amount of possible variants of  
> using collections, like Seq, Collection, Buffer, ArrayList,  
> ArrayBuffer, ...
>
> i'm going to have two traits RTrail and WTrail, where RTrail is a  
> read-only collection, WTrail extends RTrail by making it writable /  
> mutable.
>
> Which of the following two scenarios makes more sense:
>
> 1.)
>
> trait RTrail[S <: Stake] extends Collection[S]  ...
> trait WTrail[S <: Stake ] extends RTrail[S] with  
> scala.collection.jcl.Collection[S]  ...
>
> 2.)
>
> trait RTrail[S <: Stake] extends Seq[S]  ...
> trait WTrail[S <: Stake ] extends RTrail[S] with Buffer[S]  ...
>
>
> i think the second looks better, because i would like to have the  
> apply method of Seq which is not found in scala.Collection. i seems  
> that the variant:
>
> 3.)
>
> trait RTrail[S <: Stake] extends Seq[S]  ...
> trait WTrail[S <: Stake ] extends RTrail[S] with  
> scala.collection.jcl.Collection[S]  ...
>
> doesn't work because Seq and jcl.Collection are incompatible?
>
> the chosen variant must have the best performance (speed-wise).  
> trail is internally back up'ed by two sorted ArrayLists which seem  
> to be faster than ArrayBuffer for random access operations.
>
> thanks, -sciss-
>

Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Hanns Holger Rutz
no, buffer doesn't make sense because it contradicts the automatic  
sorting of added elements. so i have come up with

trait RTrail[S <: Stake] extends Collection[S] with Function1
[Int,S]  ...
trait WTrail[S <: Stake ] extends RTrail[S] with  
scala.collection.jcl.Collection[S]  ...

looks ok... ? jcl.Collection as far as i understand doesn't make  
assumptions about the ordering of the elements.


Am 20.06.2008 um 18:33 schrieb Sciss:

> err, well, and if i use variant two, should i use  
> scala.collection.jcl.Buffer or scala.collection.mutable.Buffer?
>
>
> Am 20.06.2008 um 18:31 schrieb Sciss:
>
>> hello,
>>
>> i'm a little bit confusion by the amount of possible variants of  
>> using collections, like Seq, Collection, Buffer, ArrayList,  
>> ArrayBuffer, ...
>>
>> i'm going to have two traits RTrail and WTrail, where RTrail is a  
>> read-only collection, WTrail extends RTrail by making it  
>> writable / mutable.
>>
>> Which of the following two scenarios makes more sense:
>>
>> 1.)
>>
>> trait RTrail[S <: Stake] extends Collection[S]  ...
>> trait WTrail[S <: Stake ] extends RTrail[S] with  
>> scala.collection.jcl.Collection[S]  ...
>>
>> 2.)
>>
>> trait RTrail[S <: Stake] extends Seq[S]  ...
>> trait WTrail[S <: Stake ] extends RTrail[S] with Buffer[S]  ...
>>
>>
>> i think the second looks better, because i would like to have the  
>> apply method of Seq which is not found in scala.Collection. i  
>> seems that the variant:
>>
>> 3.)
>>
>> trait RTrail[S <: Stake] extends Seq[S]  ...
>> trait WTrail[S <: Stake ] extends RTrail[S] with  
>> scala.collection.jcl.Collection[S]  ...
>>
>> doesn't work because Seq and jcl.Collection are incompatible?
>>
>> the chosen variant must have the best performance (speed-wise).  
>> trail is internally back up'ed by two sorted ArrayLists which seem  
>> to be faster than ArrayBuffer for random access operations.
>>
>> thanks, -sciss-
>>
>

Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Jorge Ortiz
You probably shouldn't be extending anything in scala.collection.jcl

What do you want your data structure to do?

On Fri, Jun 20, 2008 at 9:45 AM, Sciss <[hidden email]> wrote:

> no, buffer doesn't make sense because it contradicts the automatic sorting
> of added elements. so i have come up with
>
> trait RTrail[S <: Stake] extends Collection[S] with Function1[Int,S]  ...
> trait WTrail[S <: Stake ] extends RTrail[S] with
> scala.collection.jcl.Collection[S]  ...
>
> looks ok... ? jcl.Collection as far as i understand doesn't make assumptions
> about the ordering of the elements.
>
>
> Am 20.06.2008 um 18:33 schrieb Sciss:
>
>> err, well, and if i use variant two, should i use
>> scala.collection.jcl.Buffer or scala.collection.mutable.Buffer?
>>
>>
>> Am 20.06.2008 um 18:31 schrieb Sciss:
>>
>>> hello,
>>>
>>> i'm a little bit confusion by the amount of possible variants of using
>>> collections, like Seq, Collection, Buffer, ArrayList, ArrayBuffer, ...
>>>
>>> i'm going to have two traits RTrail and WTrail, where RTrail is a
>>> read-only collection, WTrail extends RTrail by making it writable / mutable.
>>>
>>> Which of the following two scenarios makes more sense:
>>>
>>> 1.)
>>>
>>> trait RTrail[S <: Stake] extends Collection[S]  ...
>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>> scala.collection.jcl.Collection[S]  ...
>>>
>>> 2.)
>>>
>>> trait RTrail[S <: Stake] extends Seq[S]  ...
>>> trait WTrail[S <: Stake ] extends RTrail[S] with Buffer[S]  ...
>>>
>>>
>>> i think the second looks better, because i would like to have the apply
>>> method of Seq which is not found in scala.Collection. i seems that the
>>> variant:
>>>
>>> 3.)
>>>
>>> trait RTrail[S <: Stake] extends Seq[S]  ...
>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>> scala.collection.jcl.Collection[S]  ...
>>>
>>> doesn't work because Seq and jcl.Collection are incompatible?
>>>
>>> the chosen variant must have the best performance (speed-wise). trail is
>>> internally back up'ed by two sorted ArrayLists which seem to be faster than
>>> ArrayBuffer for random access operations.
>>>
>>> thanks, -sciss-
>>>
>>
>
>
Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Hanns Holger Rutz
a trail keeps hold of a double-sorted list of stakes, where each  
stake is defined by a span which itself is defined by a start and  
stop location. the trail keeps the stakes sorted both by start and  
stop position (two internal ArrayLists) and hence has fast  
implementations for retrieving stakes for a given span. the trail can  
be thought of as a timeline, the stakes can be thought of as regions  
placed on that timeline.

at the moment it works quite nice with the writable trail extending  
jcl.Collection ; why you think that is a bad approach?

ciao, -sciss-


Am 20.06.2008 um 19:31 schrieb Jorge Ortiz:

> You probably shouldn't be extending anything in scala.collection.jcl
>
> What do you want your data structure to do?
>
> On Fri, Jun 20, 2008 at 9:45 AM, Sciss <[hidden email]> wrote:
>> no, buffer doesn't make sense because it contradicts the automatic  
>> sorting
>> of added elements. so i have come up with
>>
>> trait RTrail[S <: Stake] extends Collection[S] with Function1
>> [Int,S]  ...
>> trait WTrail[S <: Stake ] extends RTrail[S] with
>> scala.collection.jcl.Collection[S]  ...
>>
>> looks ok... ? jcl.Collection as far as i understand doesn't make  
>> assumptions
>> about the ordering of the elements.
>>
>>
>> Am 20.06.2008 um 18:33 schrieb Sciss:
>>
>>> err, well, and if i use variant two, should i use
>>> scala.collection.jcl.Buffer or scala.collection.mutable.Buffer?
>>>
>>>
>>> Am 20.06.2008 um 18:31 schrieb Sciss:
>>>
>>>> hello,
>>>>
>>>> i'm a little bit confusion by the amount of possible variants of  
>>>> using
>>>> collections, like Seq, Collection, Buffer, ArrayList,  
>>>> ArrayBuffer, ...
>>>>
>>>> i'm going to have two traits RTrail and WTrail, where RTrail is a
>>>> read-only collection, WTrail extends RTrail by making it  
>>>> writable / mutable.
>>>>
>>>> Which of the following two scenarios makes more sense:
>>>>
>>>> 1.)
>>>>
>>>> trait RTrail[S <: Stake] extends Collection[S]  ...
>>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>>> scala.collection.jcl.Collection[S]  ...
>>>>
>>>> 2.)
>>>>
>>>> trait RTrail[S <: Stake] extends Seq[S]  ...
>>>> trait WTrail[S <: Stake ] extends RTrail[S] with Buffer[S]  ...
>>>>
>>>>
>>>> i think the second looks better, because i would like to have  
>>>> the apply
>>>> method of Seq which is not found in scala.Collection. i seems  
>>>> that the
>>>> variant:
>>>>
>>>> 3.)
>>>>
>>>> trait RTrail[S <: Stake] extends Seq[S]  ...
>>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>>> scala.collection.jcl.Collection[S]  ...
>>>>
>>>> doesn't work because Seq and jcl.Collection are incompatible?
>>>>
>>>> the chosen variant must have the best performance (speed-wise).  
>>>> trail is
>>>> internally back up'ed by two sorted ArrayLists which seem to be  
>>>> faster than
>>>> ArrayBuffer for random access operations.
>>>>
>>>> thanks, -sciss-
>>>>
>>>
>>
>>

Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Jorge Ortiz
Can your spans overlap? Can there be empty spaces between the spans?

--j

On Fri, Jun 20, 2008 at 10:41 AM, Sciss <[hidden email]> wrote:

> a trail keeps hold of a double-sorted list of stakes, where each stake is
> defined by a span which itself is defined by a start and stop location. the
> trail keeps the stakes sorted both by start and stop position (two internal
> ArrayLists) and hence has fast implementations for retrieving stakes for a
> given span. the trail can be thought of as a timeline, the stakes can be
> thought of as regions placed on that timeline.
>
> at the moment it works quite nice with the writable trail extending
> jcl.Collection ; why you think that is a bad approach?
>
> ciao, -sciss-
>
>
> Am 20.06.2008 um 19:31 schrieb Jorge Ortiz:
>
>> You probably shouldn't be extending anything in scala.collection.jcl
>>
>> What do you want your data structure to do?
>>
>> On Fri, Jun 20, 2008 at 9:45 AM, Sciss <[hidden email]> wrote:
>>>
>>> no, buffer doesn't make sense because it contradicts the automatic
>>> sorting
>>> of added elements. so i have come up with
>>>
>>> trait RTrail[S <: Stake] extends Collection[S] with Function1[Int,S]  ...
>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>> scala.collection.jcl.Collection[S]  ...
>>>
>>> looks ok... ? jcl.Collection as far as i understand doesn't make
>>> assumptions
>>> about the ordering of the elements.
>>>
>>>
>>> Am 20.06.2008 um 18:33 schrieb Sciss:
>>>
>>>> err, well, and if i use variant two, should i use
>>>> scala.collection.jcl.Buffer or scala.collection.mutable.Buffer?
>>>>
>>>>
>>>> Am 20.06.2008 um 18:31 schrieb Sciss:
>>>>
>>>>> hello,
>>>>>
>>>>> i'm a little bit confusion by the amount of possible variants of using
>>>>> collections, like Seq, Collection, Buffer, ArrayList, ArrayBuffer, ...
>>>>>
>>>>> i'm going to have two traits RTrail and WTrail, where RTrail is a
>>>>> read-only collection, WTrail extends RTrail by making it writable /
>>>>> mutable.
>>>>>
>>>>> Which of the following two scenarios makes more sense:
>>>>>
>>>>> 1.)
>>>>>
>>>>> trait RTrail[S <: Stake] extends Collection[S]  ...
>>>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>>>> scala.collection.jcl.Collection[S]  ...
>>>>>
>>>>> 2.)
>>>>>
>>>>> trait RTrail[S <: Stake] extends Seq[S]  ...
>>>>> trait WTrail[S <: Stake ] extends RTrail[S] with Buffer[S]  ...
>>>>>
>>>>>
>>>>> i think the second looks better, because i would like to have the apply
>>>>> method of Seq which is not found in scala.Collection. i seems that the
>>>>> variant:
>>>>>
>>>>> 3.)
>>>>>
>>>>> trait RTrail[S <: Stake] extends Seq[S]  ...
>>>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>>>> scala.collection.jcl.Collection[S]  ...
>>>>>
>>>>> doesn't work because Seq and jcl.Collection are incompatible?
>>>>>
>>>>> the chosen variant must have the best performance (speed-wise). trail
>>>>> is
>>>>> internally back up'ed by two sorted ArrayLists which seem to be faster
>>>>> than
>>>>> ArrayBuffer for random access operations.
>>>>>
>>>>> thanks, -sciss-
>>>>>
>>>>
>>>
>>>
>
>
Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Jorge Ortiz
And by spans I mean stakes.

On Fri, Jun 20, 2008 at 10:52 AM, Jorge Ortiz <[hidden email]> wrote:

> Can your spans overlap? Can there be empty spaces between the spans?
>
> --j
>
> On Fri, Jun 20, 2008 at 10:41 AM, Sciss <[hidden email]> wrote:
>> a trail keeps hold of a double-sorted list of stakes, where each stake is
>> defined by a span which itself is defined by a start and stop location. the
>> trail keeps the stakes sorted both by start and stop position (two internal
>> ArrayLists) and hence has fast implementations for retrieving stakes for a
>> given span. the trail can be thought of as a timeline, the stakes can be
>> thought of as regions placed on that timeline.
>>
>> at the moment it works quite nice with the writable trail extending
>> jcl.Collection ; why you think that is a bad approach?
>>
>> ciao, -sciss-
>>
>>
>> Am 20.06.2008 um 19:31 schrieb Jorge Ortiz:
>>
>>> You probably shouldn't be extending anything in scala.collection.jcl
>>>
>>> What do you want your data structure to do?
>>>
>>> On Fri, Jun 20, 2008 at 9:45 AM, Sciss <[hidden email]> wrote:
>>>>
>>>> no, buffer doesn't make sense because it contradicts the automatic
>>>> sorting
>>>> of added elements. so i have come up with
>>>>
>>>> trait RTrail[S <: Stake] extends Collection[S] with Function1[Int,S]  ...
>>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>>> scala.collection.jcl.Collection[S]  ...
>>>>
>>>> looks ok... ? jcl.Collection as far as i understand doesn't make
>>>> assumptions
>>>> about the ordering of the elements.
>>>>
>>>>
>>>> Am 20.06.2008 um 18:33 schrieb Sciss:
>>>>
>>>>> err, well, and if i use variant two, should i use
>>>>> scala.collection.jcl.Buffer or scala.collection.mutable.Buffer?
>>>>>
>>>>>
>>>>> Am 20.06.2008 um 18:31 schrieb Sciss:
>>>>>
>>>>>> hello,
>>>>>>
>>>>>> i'm a little bit confusion by the amount of possible variants of using
>>>>>> collections, like Seq, Collection, Buffer, ArrayList, ArrayBuffer, ...
>>>>>>
>>>>>> i'm going to have two traits RTrail and WTrail, where RTrail is a
>>>>>> read-only collection, WTrail extends RTrail by making it writable /
>>>>>> mutable.
>>>>>>
>>>>>> Which of the following two scenarios makes more sense:
>>>>>>
>>>>>> 1.)
>>>>>>
>>>>>> trait RTrail[S <: Stake] extends Collection[S]  ...
>>>>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>>>>> scala.collection.jcl.Collection[S]  ...
>>>>>>
>>>>>> 2.)
>>>>>>
>>>>>> trait RTrail[S <: Stake] extends Seq[S]  ...
>>>>>> trait WTrail[S <: Stake ] extends RTrail[S] with Buffer[S]  ...
>>>>>>
>>>>>>
>>>>>> i think the second looks better, because i would like to have the apply
>>>>>> method of Seq which is not found in scala.Collection. i seems that the
>>>>>> variant:
>>>>>>
>>>>>> 3.)
>>>>>>
>>>>>> trait RTrail[S <: Stake] extends Seq[S]  ...
>>>>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>>>>> scala.collection.jcl.Collection[S]  ...
>>>>>>
>>>>>> doesn't work because Seq and jcl.Collection are incompatible?
>>>>>>
>>>>>> the chosen variant must have the best performance (speed-wise). trail
>>>>>> is
>>>>>> internally back up'ed by two sorted ArrayLists which seem to be faster
>>>>>> than
>>>>>> ArrayBuffer for random access operations.
>>>>>>
>>>>>> thanks, -sciss-
>>>>>>
>>>>>
>>>>
>>>>
>>
>>
>
Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Hanns Holger Rutz
In reply to this post by Jorge Ortiz
yes and yes. i am using a frame-based approach, so the start and stop  
position are given in Long (that is frames referring to some sample-
rate), and Span defines methods like overlaps, contains, touches.  
furthermore, Stake defines methods to splice itself into two parts  
and to translate it (its immutable and will returned a translated copy)

Am 20.06.2008 um 19:52 schrieb Jorge Ortiz:

> Can your spans overlap? Can there be empty spaces between the spans?
>
> --j
>
> On Fri, Jun 20, 2008 at 10:41 AM, Sciss <[hidden email]> wrote:
>> a trail keeps hold of a double-sorted list of stakes, where each  
>> stake is
>> defined by a span which itself is defined by a start and stop  
>> location. the
>> trail keeps the stakes sorted both by start and stop position (two  
>> internal
>> ArrayLists) and hence has fast implementations for retrieving  
>> stakes for a
>> given span. the trail can be thought of as a timeline, the stakes  
>> can be
>> thought of as regions placed on that timeline.
>>
>> at the moment it works quite nice with the writable trail extending
>> jcl.Collection ; why you think that is a bad approach?
>>
>> ciao, -sciss-
>>
>>
>> Am 20.06.2008 um 19:31 schrieb Jorge Ortiz:
>>
>>> You probably shouldn't be extending anything in scala.collection.jcl
>>>
>>> What do you want your data structure to do?
>>>
>>> On Fri, Jun 20, 2008 at 9:45 AM, Sciss <[hidden email]> wrote:
>>>>
>>>> no, buffer doesn't make sense because it contradicts the automatic
>>>> sorting
>>>> of added elements. so i have come up with
>>>>
>>>> trait RTrail[S <: Stake] extends Collection[S] with Function1
>>>> [Int,S]  ...
>>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>>> scala.collection.jcl.Collection[S]  ...
>>>>
>>>> looks ok... ? jcl.Collection as far as i understand doesn't make
>>>> assumptions
>>>> about the ordering of the elements.
>>>>
>>>>
>>>> Am 20.06.2008 um 18:33 schrieb Sciss:
>>>>
>>>>> err, well, and if i use variant two, should i use
>>>>> scala.collection.jcl.Buffer or scala.collection.mutable.Buffer?
>>>>>
>>>>>
>>>>> Am 20.06.2008 um 18:31 schrieb Sciss:
>>>>>
>>>>>> hello,
>>>>>>
>>>>>> i'm a little bit confusion by the amount of possible variants  
>>>>>> of using
>>>>>> collections, like Seq, Collection, Buffer, ArrayList,  
>>>>>> ArrayBuffer, ...
>>>>>>
>>>>>> i'm going to have two traits RTrail and WTrail, where RTrail is a
>>>>>> read-only collection, WTrail extends RTrail by making it  
>>>>>> writable /
>>>>>> mutable.
>>>>>>
>>>>>> Which of the following two scenarios makes more sense:
>>>>>>
>>>>>> 1.)
>>>>>>
>>>>>> trait RTrail[S <: Stake] extends Collection[S]  ...
>>>>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>>>>> scala.collection.jcl.Collection[S]  ...
>>>>>>
>>>>>> 2.)
>>>>>>
>>>>>> trait RTrail[S <: Stake] extends Seq[S]  ...
>>>>>> trait WTrail[S <: Stake ] extends RTrail[S] with Buffer[S]  ...
>>>>>>
>>>>>>
>>>>>> i think the second looks better, because i would like to have  
>>>>>> the apply
>>>>>> method of Seq which is not found in scala.Collection. i seems  
>>>>>> that the
>>>>>> variant:
>>>>>>
>>>>>> 3.)
>>>>>>
>>>>>> trait RTrail[S <: Stake] extends Seq[S]  ...
>>>>>> trait WTrail[S <: Stake ] extends RTrail[S] with
>>>>>> scala.collection.jcl.Collection[S]  ...
>>>>>>
>>>>>> doesn't work because Seq and jcl.Collection are incompatible?
>>>>>>
>>>>>> the chosen variant must have the best performance (speed-
>>>>>> wise). trail
>>>>>> is
>>>>>> internally back up'ed by two sorted ArrayLists which seem to  
>>>>>> be faster
>>>>>> than
>>>>>> ArrayBuffer for random access operations.
>>>>>>
>>>>>> thanks, -sciss-
>>>>>>
>>>>>
>>>>
>>>>
>>
>>

Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Aaron Harnly-2-2
Hi Sciss,

On Jun 20, 2008, at 2:03 PM, Sciss wrote:
>

> yes and yes. i am using a frame-based approach, so the start and  
> stop position are given in Long (that is frames referring to some  
> sample-rate), and Span defines methods like overlaps, contains,  
> touches.


On Fri, Jun 20, 2008 at 10:41 AM, Sciss <[hidden email]> wrote:
> a trail keeps hold of a double-sorted list of stakes, where each  
> stake is
> defined by a span which itself is defined by a start and stop  
> location.

Oh, do let me know if you make a reasonable implementation of this  
data structure. I wrote something a while ago, but I shudder to think  
about it now --  (a) It was mutable, (b) It was built on a binary tree  
implementation that I never got around to updating to be self-
balancing :(, (c) It relied on iterators that weren't particularly  
careful about tail-calls and thus sometimes blew the stack.

So, with all that to recommend it (!?), if you want to take a look so  
you know what not to do, I've tossed it up at the following:

The binary tree backing:
http://harnly.net/tmp/BinaryTree.scala

iterators over the binary trees:
http://harnly.net/tmp/interval_tree_iterators.scala

A simple Range type, (which I'd name Span if I had it to do over):
http://harnly.net/tmp/Range.scala

The interval trees:
http://harnly.net/tmp/IntervalTree.scala

and iterators over those:
http://harnly.net/tmp/interval_tree_iterators.scala

cheers,
aaron


Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Hanns Holger Rutz
cool, thanks a lot for your links!  the basic thing already exists  
since a while as a java class of mine, but apart from translating it  
to scala (making a generification at the same moment), i'm going to  
try out different other things (it's combined with an observer  
pattern and undo/redo functionality)

ciao, -sciss-


Am 20.06.2008 um 22:32 schrieb Aaron Harnly:

> Hi Sciss,
>
> On Jun 20, 2008, at 2:03 PM, Sciss wrote:
>>
>
>> yes and yes. i am using a frame-based approach, so the start and  
>> stop position are given in Long (that is frames referring to some  
>> sample-rate), and Span defines methods like overlaps, contains,  
>> touches.
>
>
> On Fri, Jun 20, 2008 at 10:41 AM, Sciss <[hidden email]> wrote:
>> a trail keeps hold of a double-sorted list of stakes, where each  
>> stake is
>> defined by a span which itself is defined by a start and stop  
>> location.
>
> Oh, do let me know if you make a reasonable implementation of this  
> data structure. I wrote something a while ago, but I shudder to  
> think about it now --  (a) It was mutable, (b) It was built on a  
> binary tree implementation that I never got around to updating to  
> be self-balancing :(, (c) It relied on iterators that weren't  
> particularly careful about tail-calls and thus sometimes blew the  
> stack.
>
> So, with all that to recommend it (!?), if you want to take a look  
> so you know what not to do, I've tossed it up at the following:
>
> The binary tree backing:
> http://harnly.net/tmp/BinaryTree.scala
>
> iterators over the binary trees:
> http://harnly.net/tmp/interval_tree_iterators.scala
>
> A simple Range type, (which I'd name Span if I had it to do over):
> http://harnly.net/tmp/Range.scala
>
> The interval trees:
> http://harnly.net/tmp/IntervalTree.scala
>
> and iterators over those:
> http://harnly.net/tmp/interval_tree_iterators.scala
>
> cheers,
> aaron
>
>

Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Jorge Ortiz
Hey Sciss,

Sorry for going dark on this. As Aaron pointed out, the best approach
here is to use Interval Trees. Interval Trees would give you O(log N)
insertions/deletions and O(log N) queries, as opposed to O(N)
insertions/deletions and O(log N) (I think?) queries for double-sorted
ArrayLists.

However, if you don't care about insertion/deletion inefficiencies,
then you can forego the implementation trickiness of Interval Trees.

If Scala's ArrayBuffer was too slow for you, you might want to check
out scalax's FastArrayBuffer.

--j

On Fri, Jun 20, 2008 at 1:57 PM, Sciss <[hidden email]> wrote:

> cool, thanks a lot for your links!  the basic thing already exists since a
> while as a java class of mine, but apart from translating it to scala
> (making a generification at the same moment), i'm going to try out different
> other things (it's combined with an observer pattern and undo/redo
> functionality)
>
> ciao, -sciss-
>
>
> Am 20.06.2008 um 22:32 schrieb Aaron Harnly:
>
>> Hi Sciss,
>>
>> On Jun 20, 2008, at 2:03 PM, Sciss wrote:
>>>
>>
>>> yes and yes. i am using a frame-based approach, so the start and stop
>>> position are given in Long (that is frames referring to some sample-rate),
>>> and Span defines methods like overlaps, contains, touches.
>>
>>
>> On Fri, Jun 20, 2008 at 10:41 AM, Sciss <[hidden email]> wrote:
>>>
>>> a trail keeps hold of a double-sorted list of stakes, where each stake is
>>> defined by a span which itself is defined by a start and stop location.
>>
>> Oh, do let me know if you make a reasonable implementation of this data
>> structure. I wrote something a while ago, but I shudder to think about it
>> now --  (a) It was mutable, (b) It was built on a binary tree implementation
>> that I never got around to updating to be self-balancing :(, (c) It relied
>> on iterators that weren't particularly careful about tail-calls and thus
>> sometimes blew the stack.
>>
>> So, with all that to recommend it (!?), if you want to take a look so you
>> know what not to do, I've tossed it up at the following:
>>
>> The binary tree backing:
>> http://harnly.net/tmp/BinaryTree.scala
>>
>> iterators over the binary trees:
>> http://harnly.net/tmp/interval_tree_iterators.scala
>>
>> A simple Range type, (which I'd name Span if I had it to do over):
>> http://harnly.net/tmp/Range.scala
>>
>> The interval trees:
>> http://harnly.net/tmp/IntervalTree.scala
>>
>> and iterators over those:
>> http://harnly.net/tmp/interval_tree_iterators.scala
>>
>> cheers,
>> aaron
>>
>>
>
>
Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Hanns Holger Rutz
hi jorge,

thanks for your comments. i wonder know if the interval trees are  
really better and faster. i'm using binary search in the insertion  
and deletion process, so i wonder if that still gives me O(N) speed  
due to the workings of ArrayList? like:

class Trail[S <: Stake] extends WTrail[S] {

   private val collStakesByStart = new ArrayList[S]
   private val collStakesByStop = new ArrayList[S]

    ...

   def add( stake: S ) : Boolean = {
     val span = stake.span
     val idx1 = binarySearchStart( collStakesByStart, span.start )
     collStakesByStart.add( if( idx1 < 0 ) -(idx1 + 1) else idx1,  
stake )
     val idx2 = binarySearchStop( collStakesByStop, span.stop )
     collStakesByStop.add( if( idx2 < 0 ) -(idx2 + 1) else idx2, stake )
     ...
     true
   }

   private def binarySearchStart( coll: Seq[S], value: Long ) : Int = {
     var low = 0
     var high = coll.size - 1

     while( low <= high ) {
       val mid = (low + high) >>> 1
       val midVal = coll( mid ).span.start

       if( midVal < value )
         low = mid + 1
       else if( midVal > value )
         high = mid - 1
       else
         return mid
     }
     -(low + 1)  // key not found
   }

   ...
}

so two O(logN) operations for the search plus two calls to  
ArrayList's add method. Is the latter less performative than using  
trees?

ciao, -sciss-



Am 26.06.2008 um 04:09 schrieb Jorge Ortiz:

> Hey Sciss,
>
> Sorry for going dark on this. As Aaron pointed out, the best approach
> here is to use Interval Trees. Interval Trees would give you O(log N)
> insertions/deletions and O(log N) queries, as opposed to O(N)
> insertions/deletions and O(log N) (I think?) queries for double-sorted
> ArrayLists.
>
> However, if you don't care about insertion/deletion inefficiencies,
> then you can forego the implementation trickiness of Interval Trees.
>
> If Scala's ArrayBuffer was too slow for you, you might want to check
> out scalax's FastArrayBuffer.
>
> --j
>
> On Fri, Jun 20, 2008 at 1:57 PM, Sciss <[hidden email]> wrote:
>> cool, thanks a lot for your links!  the basic thing already exists  
>> since a
>> while as a java class of mine, but apart from translating it to scala
>> (making a generification at the same moment), i'm going to try out  
>> different
>> other things (it's combined with an observer pattern and undo/redo
>> functionality)
>>
>> ciao, -sciss-
>>
>>
>> Am 20.06.2008 um 22:32 schrieb Aaron Harnly:
>>
>>> Hi Sciss,
>>>
>>> On Jun 20, 2008, at 2:03 PM, Sciss wrote:
>>>>
>>>
>>>> yes and yes. i am using a frame-based approach, so the start and  
>>>> stop
>>>> position are given in Long (that is frames referring to some  
>>>> sample-rate),
>>>> and Span defines methods like overlaps, contains, touches.
>>>
>>>
>>> On Fri, Jun 20, 2008 at 10:41 AM, Sciss <[hidden email]> wrote:
>>>>
>>>> a trail keeps hold of a double-sorted list of stakes, where each  
>>>> stake is
>>>> defined by a span which itself is defined by a start and stop  
>>>> location.
>>>
>>> Oh, do let me know if you make a reasonable implementation of  
>>> this data
>>> structure. I wrote something a while ago, but I shudder to think  
>>> about it
>>> now --  (a) It was mutable, (b) It was built on a binary tree  
>>> implementation
>>> that I never got around to updating to be self-balancing :(, (c)  
>>> It relied
>>> on iterators that weren't particularly careful about tail-calls  
>>> and thus
>>> sometimes blew the stack.
>>>
>>> So, with all that to recommend it (!?), if you want to take a  
>>> look so you
>>> know what not to do, I've tossed it up at the following:
>>>
>>> The binary tree backing:
>>> http://harnly.net/tmp/BinaryTree.scala
>>>
>>> iterators over the binary trees:
>>> http://harnly.net/tmp/interval_tree_iterators.scala
>>>
>>> A simple Range type, (which I'd name Span if I had it to do over):
>>> http://harnly.net/tmp/Range.scala
>>>
>>> The interval trees:
>>> http://harnly.net/tmp/IntervalTree.scala
>>>
>>> and iterators over those:
>>> http://harnly.net/tmp/interval_tree_iterators.scala
>>>
>>> cheers,
>>> aaron
>>>
>>>
>>
>>

Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Gábor Bakos
Sciss wrote:
>   def add( stake: S ) : Boolean = {
>     val span = stake.span
>     val idx1 = binarySearchStart( collStakesByStart, span.start )
>     collStakesByStart.add( if( idx1 < 0 ) -(idx1 + 1) else idx1, stake )
>     val idx2 = binarySearchStop( collStakesByStop, span.stop )
>     collStakesByStop.add( if( idx2 < 0 ) -(idx2 + 1) else idx2, stake )
>     ...
>     true
>   }
...
> so two O(logN) operations for the search plus two calls to ArrayList's
> add method. Is the latter less performative than using trees?
Hi Sciss,

Yes, the two calls for the ArrayList's add method makes this algoritm
O(n), because these calls are not necessarily at the end. With trees it
is possible to keep them in balance and achieve O(log(n)) complexity.
Best regards, gabor

Reply | Threaded
Open this post in threaded view
|

Re: Re: scala.Collection, Seq, jcl.Collection, Buffer

Hanns Holger Rutz
so the O(N) is because of java.util.ArrayList's

     public void add(int index, E element) {
        ...
         System.arraycopy(elementData, index, elementData, index + 1,
                          size - index);
         elementData[index] = element;
         size++;
     }

?

then, wouldn't a linked list be sufficient, or does it need to be a  
binary tree?

ciao, -sciss-



Am 26.06.2008 um 21:18 schrieb Bakos Gábor:

> Sciss wrote:
>>   def add( stake: S ) : Boolean = {
>>     val span = stake.span
>>     val idx1 = binarySearchStart( collStakesByStart, span.start )
>>     collStakesByStart.add( if( idx1 < 0 ) -(idx1 + 1) else idx1,  
>> stake )
>>     val idx2 = binarySearchStop( collStakesByStop, span.stop )
>>     collStakesByStop.add( if( idx2 < 0 ) -(idx2 + 1) else idx2,  
>> stake )
>>     ...
>>     true
>>   }
> ...
>> so two O(logN) operations for the search plus two calls to  
>> ArrayList's
>> add method. Is the latter less performative than using trees?
> Hi Sciss,
>
> Yes, the two calls for the ArrayList's add method makes this algoritm
> O(n), because these calls are not necessarily at the end. With  
> trees it
> is possible to keep them in balance and achieve O(log(n)) complexity.
> Best regards, gabor
>

Reply | Threaded
Open this post in threaded view
|

Re: Re: scala.Collection, Seq, jcl.Collection, Buffer

Hanns Holger Rutz
ah well i guess the linked list doesn't work because i'm loosing  
random access needed for the binarySearch ... ?

Am 26.06.2008 um 22:58 schrieb Sciss:

> so the O(N) is because of java.util.ArrayList's
>
>     public void add(int index, E element) {
> ...
>         System.arraycopy(elementData, index, elementData, index + 1,
>                          size - index);
>         elementData[index] = element;
>         size++;
>     }
>
> ?
>
> then, wouldn't a linked list be sufficient, or does it need to be a  
> binary tree?
>
> ciao, -sciss-
>
>
>
> Am 26.06.2008 um 21:18 schrieb Bakos Gábor:
>
>> Sciss wrote:
>>>   def add( stake: S ) : Boolean = {
>>>     val span = stake.span
>>>     val idx1 = binarySearchStart( collStakesByStart, span.start )
>>>     collStakesByStart.add( if( idx1 < 0 ) -(idx1 + 1) else idx1,  
>>> stake )
>>>     val idx2 = binarySearchStop( collStakesByStop, span.stop )
>>>     collStakesByStop.add( if( idx2 < 0 ) -(idx2 + 1) else idx2,  
>>> stake )
>>>     ...
>>>     true
>>>   }
>> ...
>>> so two O(logN) operations for the search plus two calls to  
>>> ArrayList's
>>> add method. Is the latter less performative than using trees?
>> Hi Sciss,
>>
>> Yes, the two calls for the ArrayList's add method makes this algoritm
>> O(n), because these calls are not necessarily at the end. With  
>> trees it
>> is possible to keep them in balance and achieve O(log(n)) complexity.
>> Best regards, gabor
>>
>

Reply | Threaded
Open this post in threaded view
|

Re: scala.Collection, Seq, jcl.Collection, Buffer

Gábor Bakos
Yes, that is the problem.

Sciss wrote:

> ah well i guess the linked list doesn't work because i'm loosing random
> access needed for the binarySearch ... ?
>
> Am 26.06.2008 um 22:58 schrieb Sciss:
>
>> so the O(N) is because of java.util.ArrayList's
>>
>>     public void add(int index, E element) {
>>     ...
>>         System.arraycopy(elementData, index, elementData, index + 1,
>>                          size - index);
>>         elementData[index] = element;
>>         size++;
>>     }
>>
>> ?
>>
>> then, wouldn't a linked list be sufficient, or does it need to be a
>> binary tree?
>>
>> ciao, -sciss-
>>
>>
>>
>> Am 26.06.2008 um 21:18 schrieb Bakos Gábor:
>>
>>> Sciss wrote:
>>>>   def add( stake: S ) : Boolean = {
>>>>     val span = stake.span
>>>>     val idx1 = binarySearchStart( collStakesByStart, span.start )
>>>>     collStakesByStart.add( if( idx1 < 0 ) -(idx1 + 1) else idx1,
>>>> stake )
>>>>     val idx2 = binarySearchStop( collStakesByStop, span.stop )
>>>>     collStakesByStop.add( if( idx2 < 0 ) -(idx2 + 1) else idx2, stake )
>>>>     ...
>>>>     true
>>>>   }
>>> ...
>>>> so two O(logN) operations for the search plus two calls to ArrayList's
>>>> add method. Is the latter less performative than using trees?
>>> Hi Sciss,
>>>
>>> Yes, the two calls for the ArrayList's add method makes this algoritm
>>> O(n), because these calls are not necessarily at the end. With trees it
>>> is possible to keep them in balance and achieve O(log(n)) complexity.
>>> Best regards, gabor
>>>
>>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: Re: scala.Collection, Seq, jcl.Collection, Buffer

Hanns Holger Rutz
In reply to this post by Hanns Holger Rutz
in other words, is there any existing scala class with underlying  
java.util.TreeSet ?


Am 26.06.2008 um 23:04 schrieb Sciss:

> ah well i guess the linked list doesn't work because i'm loosing  
> random access needed for the binarySearch ... ?
>
> Am 26.06.2008 um 22:58 schrieb Sciss:
>
>> so the O(N) is because of java.util.ArrayList's
>>
>>     public void add(int index, E element) {
>> ...
>>         System.arraycopy(elementData, index, elementData, index + 1,
>>                          size - index);
>>         elementData[index] = element;
>>         size++;
>>     }
>>
>> ?
>>
>> then, wouldn't a linked list be sufficient, or does it need to be  
>> a binary tree?
>>
>> ciao, -sciss-
>>
>>
>>
>> Am 26.06.2008 um 21:18 schrieb Bakos Gábor:
>>
>>> Sciss wrote:
>>>>   def add( stake: S ) : Boolean = {
>>>>     val span = stake.span
>>>>     val idx1 = binarySearchStart( collStakesByStart, span.start )
>>>>     collStakesByStart.add( if( idx1 < 0 ) -(idx1 + 1) else idx1,  
>>>> stake )
>>>>     val idx2 = binarySearchStop( collStakesByStop, span.stop )
>>>>     collStakesByStop.add( if( idx2 < 0 ) -(idx2 + 1) else idx2,  
>>>> stake )
>>>>     ...
>>>>     true
>>>>   }
>>> ...
>>>> so two O(logN) operations for the search plus two calls to  
>>>> ArrayList's
>>>> add method. Is the latter less performative than using trees?
>>> Hi Sciss,
>>>
>>> Yes, the two calls for the ArrayList's add method makes this  
>>> algoritm
>>> O(n), because these calls are not necessarily at the end. With  
>>> trees it
>>> is possible to keep them in balance and achieve O(log(n))  
>>> complexity.
>>> Best regards, gabor
>>>
>>
>

Reply | Threaded
Open this post in threaded view
|

QuadTree (was: Re: scala.Collection, Seq, jcl.Collection, Buffer)

Hanns Holger Rutz
well, i came across another design flaw: when managing huge (HUGE)  
lists of regions, to return a range (window view) is extremely  
costly, because although i can quickly (binary-search) determine the  
lower index of the by-start list and the upper index of the by-stop  
list, but i would still need to create the intersection of those two  
sublists and that's slow.

now i discovered that a quadtree is maybe what i need. has anyone  
implemented a point quadtree or k-d tree in scala?

thanks, -sciss-



Am 26.06.2008 um 23:21 schrieb Sciss:

> in other words, is there any existing scala class with underlying  
> java.util.TreeSet ?
>
>
> Am 26.06.2008 um 23:04 schrieb Sciss:
>
>> ah well i guess the linked list doesn't work because i'm loosing  
>> random access needed for the binarySearch ... ?
>>
>> Am 26.06.2008 um 22:58 schrieb Sciss:
>>
>>> so the O(N) is because of java.util.ArrayList's
>>>
>>>     public void add(int index, E element) {
>>> ...
>>>         System.arraycopy(elementData, index, elementData, index + 1,
>>>                          size - index);
>>>         elementData[index] = element;
>>>         size++;
>>>     }
>>>
>>> ?
>>>
>>> then, wouldn't a linked list be sufficient, or does it need to be  
>>> a binary tree?
>>>
>>> ciao, -sciss-
>>>
>>>
>>>
>>> Am 26.06.2008 um 21:18 schrieb Bakos Gábor:
>>>
>>>> Sciss wrote:
>>>>>   def add( stake: S ) : Boolean = {
>>>>>     val span = stake.span
>>>>>     val idx1 = binarySearchStart( collStakesByStart, span.start )
>>>>>     collStakesByStart.add( if( idx1 < 0 ) -(idx1 + 1) else  
>>>>> idx1, stake )
>>>>>     val idx2 = binarySearchStop( collStakesByStop, span.stop )
>>>>>     collStakesByStop.add( if( idx2 < 0 ) -(idx2 + 1) else idx2,  
>>>>> stake )
>>>>>     ...
>>>>>     true
>>>>>   }
>>>> ...
>>>>> so two O(logN) operations for the search plus two calls to  
>>>>> ArrayList's
>>>>> add method. Is the latter less performative than using trees?
>>>> Hi Sciss,
>>>>
>>>> Yes, the two calls for the ArrayList's add method makes this  
>>>> algoritm
>>>> O(n), because these calls are not necessarily at the end. With  
>>>> trees it
>>>> is possible to keep them in balance and achieve O(log(n))  
>>>> complexity.
>>>> Best regards, gabor
>>>>
>>>
>>
>