перечисление из индекса / значения в ruby - PullRequest
Новая
       9

перечисление из индекса / значения в ruby

2 голосов
/ 27 марта 2009

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

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

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

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

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

1 Ответ

3 голосов
/ 27 марта 2009

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

Однако, если вы не можете сделать это таким образом, ваш единственный выход - изменить 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>

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

...