[ruby-core:39993] [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[ruby-core:39993] [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[David Graham]

Issue #2348 has been updated by David Graham.


Is there a chance RBTree can be added to the standard library for Ruby 2.0?  I've needed it to implement priority queues and key range scans, but the binary gem doesn't play well with JRuby or Rubinius.  It would help if we could count on this data structure being included with Ruby.

Thanks!
David
----------------------------------------
Feature #2348: RBTree Should be Added to the Standard Library
http://redmine.ruby-lang.org/issues/2348

Author: James Gray
Status: Assigned
Priority: Normal
Assignee: Yukihiro Matsumoto
Category: lib
Target version: 1.9.x


=begin
 The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:
 
 http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602
 
 RBTree has now been fixed to run on Ruby 1.9:
 
 http://github.com/skade/rbtree
 
 I think we should now give serious consideration to bringing it into the standard library.
=end



-- 
http://redmine.ruby-lang.org

[ruby-core:39995] [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[James Gray]

Issue #2348 has been updated by James Gray.


I still agree.  We've literally been asking for NArray and RBTree in the standard library for years.  Pretty please?  :)
----------------------------------------
Feature #2348: RBTree Should be Added to the Standard Library
http://redmine.ruby-lang.org/issues/2348

Author: James Gray
Status: Assigned
Priority: Normal
Assignee: Yukihiro Matsumoto
Category: lib
Target version: 1.9.x


=begin
 The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:
 
 http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602
 
 RBTree has now been fixed to run on Ruby 1.9:
 
 http://github.com/skade/rbtree
 
 I think we should now give serious consideration to bringing it into the standard library.
=end



-- 
http://redmine.ruby-lang.org

[ruby-core:39998] [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[B Kelly]

Issue #2348 has been updated by B Kelly.


I wholeheartedly agree about the usefulness of the data structure.

I'm hesitant to type this, because I don't want to impede RBTree's path toward first-class citizenship.

But last time I checked there appeared to be some API deficiencies that significantly limited RBTree's potential usefulness:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/28860
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/28879

Although I suppose it's possible these could be addressed at a later date?


Regards,

Bill

----------------------------------------
Feature #2348: RBTree Should be Added to the Standard Library
http://redmine.ruby-lang.org/issues/2348

Author: James Gray
Status: Assigned
Priority: Normal
Assignee: Yukihiro Matsumoto
Category: lib
Target version: 1.9.x


=begin
 The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:
 
 http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602
 
 RBTree has now been fixed to run on Ruby 1.9:
 
 http://github.com/skade/rbtree
 
 I think we should now give serious consideration to bringing it into the standard library.
=end



-- 
http://redmine.ruby-lang.org

[ruby-core:40000] Re: [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[Haase, Konstantin]

SortedSet could then depend on it properly instead of the voodoo code that ships with Ruby atm.

Konstantin

On Oct 6, 2011, at 13:22 , B Kelly wrote:

> 
> Issue #2348 has been updated by B Kelly.
> 
> 
> I wholeheartedly agree about the usefulness of the data structure.
> 
> I'm hesitant to type this, because I don't want to impede RBTree's path toward first-class citizenship.
> 
> But last time I checked there appeared to be some API deficiencies that significantly limited RBTree's potential usefulness:
> 
> http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/28860
> http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/28879
> 
> Although I suppose it's possible these could be addressed at a later date?
> 
> 
> Regards,
> 
> Bill
> 
> ----------------------------------------
> Feature #2348: RBTree Should be Added to the Standard Library
> http://redmine.ruby-lang.org/issues/2348
> 
> Author: James Gray
> Status: Assigned
> Priority: Normal
> Assignee: Yukihiro Matsumoto
> Category: lib
> Target version: 1.9.x
> 
> 
> =begin
> The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:
> 
> http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602
> 
> RBTree has now been fixed to run on Ruby 1.9:
> 
> http://github.com/skade/rbtree
> 
> I think we should now give serious consideration to bringing it into the standard library.
> =end
> 
> 
> 
> -- 
> http://redmine.ruby-lang.org
> 

[ruby-core:40004] Re: [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[SASADA Koichi]

(2011/10/07 1:50), David Graham wrote:
> Is there a chance RBTree can be added to the standard library for Ruby 2.0?  I've needed it to implement priority queues and key range scans, but the binary gem doesn't play well with JRuby or Rubinius.  It would help if we could count on this data structure being included with Ruby.

Gem is not enough?

-- 
// SASADA Koichi at atdot dot net

[ruby-core:40008] Re: [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[James Gray]

On Thu, Oct 6, 2011 at 6:34 PM, SASADA Koichi <ko1@atdot.net> wrote:
> (2011/10/07 1:50), David Graham wrote:
>> Is there a chance RBTree can be added to the standard library for Ruby 2.0?  I've needed it to implement priority queues and key range scans, but the binary gem doesn't play well with JRuby or Rubinius.  It would help if we could count on this data structure being included with Ruby.
>
> Gem is not enough?

I guess I just feel I would use RBTree and NArray a lot more than some
things we have in the standard library.  It's about the same
usefulness as Set, in my opinion.  Maybe even a little more.

James Edward Gray II

[ruby-core:40009] Re: [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[SASADA Koichi]

(2011/10/07 9:46), James Gray wrote:
> On Thu, Oct 6, 2011 at 6:34 PM, SASADA Koichi <ko1@atdot.net> wrote:
>> (2011/10/07 1:50), David Graham wrote:
>>> Is there a chance RBTree can be added to the standard library for Ruby 2.0?  I've needed it to implement priority queues and key range scans, but the binary gem doesn't play well with JRuby or Rubinius.  It would help if we could count on this data structure being included with Ruby.
>>
>> Gem is not enough?
> 
> I guess I just feel I would use RBTree and NArray a lot more than some
> things we have in the standard library.  It's about the same
> usefulness as Set, in my opinion.  Maybe even a little more.

Some people think most of standard libraries should be in gem.  I think
you need to persuade them.

-- 
// SASADA Koichi at atdot dot net

[ruby-core:40010] Re: [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[James Gray]

On Thu, Oct 6, 2011 at 8:07 PM, SASADA Koichi <ko1@atdot.net> wrote:
> Some people think most of standard libraries should be in gem.  I think
> you need to persuade them.

I sympathize, but we are still adding new libraries as of Ruby 1.9.3
and people have literally been wanting these two for years.  I'm not
clear on why some libraries make it but these don't.

James Edward Gray II

[ruby-core:40011] Re: [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[Gary Wright]

On Oct 6, 2011, at 9:07 PM, SASADA Koichi wrote:
> Some people think most of standard libraries should be in gem.  I think
> you need to persuade them.

I think the intent is for RBTree to be included with the Ruby distribution via the standard library or via 'standard gems'.  That is to say, the inclusion of RBTree into the standard Ruby 'distribution' is orthogonal to whether the standard distribution packages the standard library as gems or not.

Gary Wright

[ruby-core:40012] Re: [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[Kenta Murata]

(2011.10.07 01:50 ), David Graham wrote:
> Is there a chance RBTree can be added to the standard library for Ruby 2.0?

I agree with you if the library name is changed.
The name of RBTree is too specific to its internal algorithm.
If we adopt RBTree, we must change the name of the library after
more better algorithms would be discovered.

--
Kenta Murata <muraken@gmail.com>
1D69 ADDE 081C 9CC2 2E54 98C1 CEFE 8AFB 6081 B062

[ruby-core:40020] Re: [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[Clifford Heath]

On 07/10/2011, at 1:16 PM, Kenta Murata wrote:
> (2011.10.07 01:50 ), David Graham wrote:
>> Is there a chance RBTree can be added to the standard library for Ruby 2.0?
> I agree with you if the library name is changed.
> The name of RBTree is too specific to its internal algorithm.
> If we adopt RBTree, we must change the name of the library after
> more better algorithms would be discovered.

I agree. Hash is not named after the hashing algorithm that's being used,
and Array is not named after its structure either.

For sorted structures, I've previously used the name Sequence. I think
this name would be suitable.

I also wish that Ruby had this container type available as a standard.

Clifford Heath.

[ruby-core:40028] Re: [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[James Gray]

On Fri, Oct 7, 2011 at 1:20 AM, Clifford Heath <clifford.heath@gmail.com> wrote:
> On 07/10/2011, at 1:16 PM, Kenta Murata wrote:
>> (2011.10.07 01:50 ), David Graham wrote:
>>> Is there a chance RBTree can be added to the standard library for Ruby 2.0?
>> I agree with you if the library name is changed.
>> The name of RBTree is too specific to its internal algorithm.
>> If we adopt RBTree, we must change the name of the library after
>> more better algorithms would be discovered.
>
> I agree. Hash is not named after the hashing algorithm that's being used,
> and Array is not named after its structure either.
>
> For sorted structures, I've previously used the name Sequence. I think
> this name would be suitable.
>
> I also wish that Ruby had this container type available as a standard.

I think Tree would be a fine name and closer to Hash.

James Edward Gray II

[ruby-core:40035] Re: [Ruby 1.9 - Feature #2348] RBTree Should be Added to the Standard Library

[Clifford Heath]

On 08/10/2011, at 1:10 AM, James Gray wrote:
> On Fri, Oct 7, 2011 at 1:20 AM, Clifford Heath <clifford.heath@gmail.com> wrote:
>> On 07/10/2011, at 1:16 PM, Kenta Murata wrote:
>>> (2011.10.07 01:50 ), David Graham wrote:
>>>> Is there a chance RBTree can be added to the standard library for Ruby 2.0?
>>> I agree with you if the library name is changed.
>>> The name of RBTree is too specific to its internal algorithm.
>>> If we adopt RBTree, we must change the name of the library after
>>> more better algorithms would be discovered.
>> 
>> I agree. Hash is not named after the hashing algorithm that's being used,
>> and Array is not named after its structure either.
>> 
>> For sorted structures, I've previously used the name Sequence. I think
>> this name would be suitable.
>> 
>> I also wish that Ruby had this container type available as a standard.
> 
> I think Tree would be a fine name and closer to Hash.

Is there any part of the API which allows a user to know it's a Tree?
If so, why?

If it's not externally visible in the API, it should not appear in the name.

My 2c.

Clifford Heath.

[ruby-core:45118] [ruby-trunk - Feature #2348] RBTree Should be Added to the Standard Library

[jvoorhis (Jeremy Voorhis)]

Issue #2348 has been updated by jvoorhis (Jeremy Voorhis).


I think that Ruby developers would definitely benefit from having a range of well-implemented data structures within reach. I don't understand why the implementation-revealing name is an issue when our most common options are already named Array [contiguous chunk of memory] and Hash[-table]. Renaming this library's classes to something SortedMap and SortedMultiMap seems incongruous.
----------------------------------------
Feature #2348: RBTree Should be Added to the Standard Library
https://bugs.ruby-lang.org/issues/2348#change-26692

Author: JEG2 (James Gray)
Status: Assigned
Priority: Normal
Assignee: matz (Yukihiro Matsumoto)
Category: lib
Target version: 2.0.0


=begin
 The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:
 
 http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602
 
 RBTree has now been fixed to run on Ruby 1.9:
 
 http://github.com/skade/rbtree
 
 I think we should now give serious consideration to bringing it into the standard library.
=end



-- 
http://bugs.ruby-lang.org/

[ruby-core:48329] [ruby-trunk - Feature #2348] RBTree Should be Added to the Standard Library

[ko1 (Koichi Sasada)]

Issue #2348 has been updated by ko1 (Koichi Sasada).


ping. status?

----------------------------------------
Feature #2348: RBTree Should be Added to the Standard Library
https://bugs.ruby-lang.org/issues/2348#change-31634

Author: JEG2 (James Gray)
Status: Assigned
Priority: Normal
Assignee: matz (Yukihiro Matsumoto)
Category: lib
Target version: 2.0.0


=begin
 The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:
 
 http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602
 
 RBTree has now been fixed to run on Ruby 1.9:
 
 http://github.com/skade/rbtree
 
 I think we should now give serious consideration to bringing it into the standard library.
=end



-- 
http://bugs.ruby-lang.org/

[ruby-core:48404] [ruby-trunk - Feature #2348] RBTree Should be Added to the Standard Library

[matz (Yukihiro Matsumoto)]

Issue #2348 has been updated by matz (Yukihiro Matsumoto).

Target version changed from 2.0.0 to next minor

I am not positive about adding a new library to the distribution while we are discussion moving toward gems.
I am not refusuig, however, so I label this "next minor".

Matz.
----------------------------------------
Feature #2348: RBTree Should be Added to the Standard Library
https://bugs.ruby-lang.org/issues/2348#change-31718

Author: JEG2 (James Gray)
Status: Assigned
Priority: Normal
Assignee: matz (Yukihiro Matsumoto)
Category: lib
Target version: next minor


=begin
 The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:
 
 http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602
 
 RBTree has now been fixed to run on Ruby 1.9:
 
 http://github.com/skade/rbtree
 
 I think we should now give serious consideration to bringing it into the standard library.
=end



-- 
http://bugs.ruby-lang.org/

[ruby-core:59933] [ruby-trunk - Feature #2348] RBTree Should be Added to the Standard Library

[e]

Issue #2348 has been updated by Zachary Scott.


Theres a discussion going on about possibly removing dependency on RBTree, or SortedSet all together.

Please see #9121

----------------------------------------
Feature #2348: RBTree Should be Added to the Standard Library
https://bugs.ruby-lang.org/issues/2348#change-44473

* Author: James Gray
* Status: Assigned
* Priority: Normal
* Assignee: Yukihiro Matsumoto
* Category: lib
* Target version: next minor
----------------------------------------
=begin
 The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:
 
 http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602
 
 RBTree has now been fixed to run on Ruby 1.9:
 
 http://github.com/skade/rbtree
 
 I think we should now give serious consideration to bringing it into the standard library.
=end




-- 
http://bugs.ruby-lang.org/

[ruby-core:64575] [ruby-trunk - Feature #2348] RBTree Should be Added to the Standard Library

[shibata.hiroshi]

Issue #2348 has been updated by Hiroshi SHIBATA.

Related to Bug #9121: [PATCH] Remove rbtree implementation of SortedSet due to performance regression added

----------------------------------------
Feature #2348: RBTree Should be Added to the Standard Library
https://bugs.ruby-lang.org/issues/2348#change-48501

* Author: James Gray
* Status: Assigned
* Priority: Normal
* Assignee: Yukihiro Matsumoto
* Category: lib
* Target version: next minor
----------------------------------------
=begin
 The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:
 
 http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602
 
 RBTree has now been fixed to run on Ruby 1.9:
 
 http://github.com/skade/rbtree
 
 I think we should now give serious consideration to bringing it into the standard library.
=end




-- 
https://bugs.ruby-lang.org/

[ruby-core:83489] [Ruby trunk Feature#2348] RBTree Should be Added to the Standard Library

[mame]

Issue #2348 has been updated by mame (Yusuke Endoh).


Three points:

* If RBTree gem is bundled, we will do so by using the (recently-established) framework of bundled gems.
* The current framework of bundled gems does not support extension library (maybe).  We need to improve the framework first.
* After that, we must decide if RBTree gem should be bundled or not. 

----------------------------------------
Feature #2348: RBTree Should be Added to the Standard Library
https://bugs.ruby-lang.org/issues/2348#change-67500

* Author: JEG2 (James Gray)
* Status: Assigned
* Priority: Normal
* Assignee: matz (Yukihiro Matsumoto)
* Target version: next minor
----------------------------------------
=begin
 The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:
 
 http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602
 
 RBTree has now been fixed to run on Ruby 1.9:
 
 http://github.com/skade/rbtree
 
 I think we should now give serious consideration to bringing it into the standard library.
=end




-- 
https://bugs.ruby-lang.org/

[ruby-core:83516] [Ruby trunk Feature#2348] RBTree Should be Added to the Standard Library

[knu]

Issue #2348 has been updated by knu (Akinori MUSHA).


Honestly, I have no idea if this library is or can become popular.

SortedSet was originally meant to be an example implementation to show what it is like to implement a subclass of Set with an alternative data structure or an additional algorithm, because I designed Set with consideration so that it is easily extensible unlike stock container classes like Hash and Array.  Actually I wrote two examples: SortedSet and RestrictedSet, and the latter was kept in the document as I was unsure if it was practically useful.

So, it was not my point to promote rbtree as standard library, but just to show Hash is not the only possible backend for Set.

----------------------------------------
Feature #2348: RBTree Should be Added to the Standard Library
https://bugs.ruby-lang.org/issues/2348#change-67533

* Author: JEG2 (James Gray)
* Status: Assigned
* Priority: Normal
* Assignee: matz (Yukihiro Matsumoto)
* Target version: next minor
----------------------------------------
=begin
 The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:
 
 http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602
 
 RBTree has now been fixed to run on Ruby 1.9:
 
 http://github.com/skade/rbtree
 
 I think we should now give serious consideration to bringing it into the standard library.
=end




-- 
https://bugs.ruby-lang.org/

[ruby-core:83951] [Ruby trunk Feature#2348][Rejected] RBTree Should be Added to the Standard Library

[matz]

Issue #2348 has been updated by matz (Yukihiro Matsumoto).

Status changed from Assigned to Rejected

Unlike the past, it's not smart to add the standard library. Use gem.

Matz.


----------------------------------------
Feature #2348: RBTree Should be Added to the Standard Library
https://bugs.ruby-lang.org/issues/2348#change-68015

* Author: JEG2 (James Gray)
* Status: Rejected
* Priority: Normal
* Assignee: matz (Yukihiro Matsumoto)
* Target version: next minor
----------------------------------------
=begin
 The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:
 
 http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602
 
 RBTree has now been fixed to run on Ruby 1.9:
 
 http://github.com/skade/rbtree
 
 I think we should now give serious consideration to bringing it into the standard library.
=end




-- 
https://bugs.ruby-lang.org/