перечисление по индексу/стоимости в рубине

Question

Итак, у меня есть эта коллекция большой розы? Его поддерживает дерево (RBTree), поэтому поисковые запросы бывают быстрыми, и значения сортируются.

Сказать ive получил значение X. Я могу найти Х в своем дереве во время входа в систему, прохладно. Но я хочу, чтобы значения были справа от X в дереве, пока один из них не дополнил тест. Т.е., получить все элементы, которые являются> = Х и Y <

Я мог получить индекс X, я, а затем получить значение, при I + 1, I + 2 .... до Вала (I + z) есть> Y. За исключением затрат z * logn. Если вы перечислите дерево, перечислитель внутри дерева не будет стоить logn, чтобы перейти к следующему элементу - он просто следует указателю в дереве.

Итак, есть ли способ начать перечисление с определенного индекса? Такие, что мне не нужно пропускать элементы i, прежде чем я начну перечислять диапазон, который я хочу.

Скажите, если вы считаете, что я сумасшедший.

Answer 1

Ну, если вы сами поместили элементы своей коллекции, и вы не против сортировки их перед вставкой, вы можете связать их с типом связанного списка. Просто убедитесь, что ключ для связанного элемента списка элементов для каждого элемента использует ключ элемента в качестве его ключа для сортировки дерева. Тогда поиск заставит вас найти место в связанном списке, и вы могли бы просто пройти его оттуда.

Однако, если вы не можете сделать это таким образом, ваше единственное средство - это изменить RBTree, что потребует небольшой работы на C, поскольку это родное расширение для ruby. Большинство фрагментов, которые вам нужны, уже есть dict_lookup(), чтобы дать вам узел в нужном дереве и rbtree_for_each(), чтобы показать вам, как писать итератор, учитывая начальный узел.

Вы должны были бы добавить следующий код rbtree.c в RBTree перл:

*** 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); 

Затем, если вы запустите make в исходном каталоге установленной rbtree камень, он должен переделать расширение, и вы можете использовать его как обычно:

% 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> 

Просто помните, что вы сделали это изменение, и распространять модифицированную драгоценный камень с вашими изменениями. Или, эй, отправьте их the gem creator on Rubyforge, , чтобы каждый мог их использовать.