From: Beyond <beyond@...>
Date: 2002-05-16T23:47:15+09:00
Subject: [ruby-dev:17122] Array#bsearch


Beyondです。

Array に、bsearch メソッドを追加する予定は、ありませんか？

拡張ライブラリは書いたことが無いのですが、sort を参考にして作ったら、簡
単に出来ました。Ruby/Bsearchと違い、ライブラリ関数を使用しています。

qsort を使う関数があるのですから、bsearch もあって良いかと思います（あっ
た方が便利）。いかがでしょう？

サンプル
===================================================================
arr = [
    [ "aaa", 1 ],
    [ "aaa", 4 ],
    [ "aaa", 9 ],
    [ "bbb", 2 ],
    [ "bbb", 4 ],
]

arr.sort! { | a, b | a[1] <=> b[1] }
p arr.bsearch( [ "", 2 ] ) { | a, b | a[1] <=> b[1] }  # => ["bbb", 2]

Index: array.c
===================================================================
$ diff -u array.c.org array.c
--- array.c.org	Tue Dec 18 17:38:51 2001
+++ array.c	Thu May 16 23:27:19 2002
@@ -1012,6 +1012,38 @@
     return ary;
 }
 
+struct bsearch_arg {
+	VALUE ary;
+	VALUE key;
+};
+
+static VALUE
+bsearch_internal( arg )
+	struct bsearch_arg*	arg;
+{
+	VALUE ary = arg->ary;
+	VALUE key = arg->key;
+	VALUE* r = bsearch( &key, RARRAY(ary)->ptr, RARRAY(ary)->len, sizeof(VALUE),
+	  rb_block_given_p()?sort_1:sort_2);
+	if( r == 0 )
+		return Qnil;
+	else
+		return *r;
+}
+
+VALUE
+rb_bsearch(ary, key)
+	VALUE ary, key;
+{
+	struct bsearch_arg	arg;
+	rb_ary_modify(ary);
+
+	FL_SET(ary, ARY_TMPLOCK);	/* prohibit modification during sort */
+	arg.ary = ary;
+	arg.key = key;
+	return rb_ensure(bsearch_internal, (VALUE)&arg, sort_unlock, ary);
+}
+
 static VALUE
 rb_ary_collect(ary)
     VALUE ary;
@@ -1714,6 +1746,7 @@
     rb_define_method(rb_cArray, "reverse!", rb_ary_reverse_bang, 0);
     rb_define_method(rb_cArray, "sort", rb_ary_sort, 0);
     rb_define_method(rb_cArray, "sort!", rb_ary_sort_bang, 0);
+    rb_define_method(rb_cArray, "bsearch", rb_bsearch, 1);
     rb_define_method(rb_cArray, "collect", rb_ary_collect, 0);
     rb_define_method(rb_cArray, "collect!", rb_ary_collect_bang, 0);
     rb_define_method(rb_cArray, "map!", rb_ary_collect_bang, 0);

---------------------
Beyond