题
所以,香港专业教育学院得到这个大屁股集合吧?其树支持(RBTree),所以看起坐是快速和值进行排序。
说Ive得到了价值X.我可以看一下X在我的树在LOGN时间,冷却。但我希望这些值X的树权为好,直到其中一个dosent满足检验。
即,得到的是均元素> = X和 我能得到X的索引,i,则在I + 1,I + 2 ....直到VAL第(i + z)为> Y.获得的价值
除了成本Z * LOGN。
如果枚举树,树犯规成本LOGN内普查员进入到下一个元素 - 它只是遵循在树的指针。 因此,有一个开始从特定索引中列举的方法?使得我没有跳过i个元素之前,我可以就在枚举我想要的范围内。 告诉我,如果你想我疯了。
解决方案
好吧,如果你把你的集合中的元素在里面你自己,你不介意在插入之前对它们进行排序,你可以用链表类型包装他们。只要确保为链接列表项包装每个元素的键使用元素的键为核心 对于树排序。然后查找将让你在链表的位置,你可以只走从那里。
不过,如果你不能这样做的,你唯一的办法是修改RBTree,这需要用C一点点工作,因为它是一个原生扩展到红宝石。大多数的,你需要在那里已经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上宝石创造者, 使得每个人都可以利用它们。
不隶属于 StackOverflow