質問
だから、IVEはこの大きな尻コレクションの権利を得ましたか。その木担保(RBTree)、そのルックアップが高速であり、値がソートされます。
セイIVEは、私はクールな、LOGN時間に私のツリーにXを調べることができます値Xを得ました。そのうちの一つがテストを満たすdosentまで、しかし、私は、同様にツリー内のXの右側に値を求めています。
すなわち、あるすべての要素を取得します> = Xと 私のをはXの指数を得ることができ、私は、その後、I + 1での値を取得し、I + 2 ....のval(I + z)は> Yとなるまで
それは、z * LOGNがかかり除きます。
あなたは木の上に列挙した場合、ツリーdoesntのコストLOGN内の列挙子が次の要素に進みます - それだけで、ツリー内のポインタをたどります。 だから、特定のインデックスから列挙を開始する方法はありますか?私は私が私が欲しいの範囲にわたって列挙を開始する前に、i個の要素をスキップするために持っていけないようなことを。 あなたはイムはクレイジーと思えば教えてくださいます。
解決
さて、あなたは、リンクリストの種類とそれらを包むことができます。ただ、各要素のリンクリスト項目ラッパーのためのキーは、キーと要素のキーを使用して確認してください 木ソートのために。そして、ルックアップは、リンクされたリストにあなたの場所になるだろう、とあなたはそこからそれを歩くことができます。
あなたがそのように行うことができない場合は、しかし、あなたの唯一の頼みの綱は、ルビーにネイティブ拡張であることから、Cで少し作業が必要と思われる、RBTreeを変更することです。あなたがそこにいる必要がある作品のほとんどは、すでにあなたが必要ツリー内のノードを与えることdict_lookup()
、およびrbtree_for_each()
は開始ノード与えられ、イテレータを作成する方法をお見せします。
あなたはRBTree宝石でrbtree.cするには、次のコードを追加する必要があると思います:
*** rbtree.c.orig 2009-03-27 14:14:55.000000000 -0400
--- rbtree.c 2009-03-27 14:20:21.000000000 -0400
***************
*** 528,533 ****
--- 528,574 ----
return EACH_NEXT;
}
+ static VALUE
+ rbtree_each_starting_with_body(rbtree_each_arg_t* arg)
+ {
+ VALUE self = arg->self;
+ dict_t* dict = DICT(self);
+ dnode_t* node;
+
+ ITER_LEV(self)++;
+ for (node = (dnode_t*) arg->arg;
+ node != NULL;
+ node = dict_next(dict, node)) {
+
+ if (arg->func(node, NULL) == EACH_STOP)
+ break;
+ }
+ return self;
+ }
+
+ /*
+ * call-seq:
+ * rbtree.each_starting_with(key) {|key, value| block} => rbtree
+ *
+ * Calls block once for each key in order, starting with the given key,
+ * passing the key and value as a two-element array parameters.
+ */
+ VALUE
+ rbtree_each_starting_with(VALUE self, VALUE key)
+ {
+ dnode_t* node = dict_lookup(DICT(self), TO_KEY(key));
+ rbtree_each_arg_t each_arg;
+ if (node == NULL) { return self; };
+
+ RETURN_ENUMERATOR(self, 0, NULL);
+
+ each_arg.self = self;
+ each_arg.func = each_i;
+ each_arg.arg = node;
+ return rb_ensure(rbtree_each_starting_with_body, (VALUE)&each_arg,
+ rbtree_each_ensure, self);
+ }
+
/*
* call-seq:
* rbtree.each {|key, value| block} => rbtree
***************
*** 1616,1621 ****
--- 1657,1663 ----
rb_define_method(MultiRBTree, "length", rbtree_size, 0);
rb_define_method(MultiRBTree, "each", rbtree_each, 0);
+ rb_define_method(MultiRBTree, "each_starting_with", rbtree_each_starting_with, 1);
rb_define_method(MultiRBTree, "each_value", rbtree_each_value, 0);
rb_define_method(MultiRBTree, "each_key", rbtree_each_key, 0);
rb_define_method(MultiRBTree, "each_pair", rbtree_each_pair, 0);
あなたがインストールさrbtree宝石のソースディレクトリにmake
を実行する場合は、すると、それは拡張子を作り直す必要があり、あなたは、通常のようにそれを使用することができます:
% irb
irb> require 'rubygems'
=> true
irb> require 'rbtree'
=> true
irb> x = RBTree[ 'a', 1, 'b', 2, 'c', 3, 'd', 4 ]
=> #<RBTree: {"a"=>1, "b"=>2, "c"=>3, "d"=>4}, default=nil, cmp_proc=nil>
irb> x.each { |k,v| p [k, v] }
["a", 1]
["b", 2]
["c", 3]
["d", 4]
=> #<RBTree: {"a"=>1, "b"=>2, "c"=>3, "d"=>4}, default=nil, cmp_proc=nil>
irb> x.each_starting_with('b') { |k,v| p [k, v] }
["b", 2]
["c", 3]
["d", 4]
=> #<RBTree: {"a"=>1, "b"=>2, "c"=>3, "d"=>4}, default=nil, cmp_proc=nil>
ちょうどあなたがこの変更を行い、変更内容を修正宝石を配布していることに注意してください。それとも、ちょっと、のRubyForge の上宝石の作成者に提出し、 誰もがそれらを利用できるようにします。