la enumeración de un índice / valor en rubí

Question

Así Ive consiguió este gran culo-derecho de cobro? Su árbol con respaldo (RBTree), a fin de buscar-ups son rápidos, y los valores se ordenan.

Say ive consiguió valor X. Puedo mirar hacia arriba X en mi árbol en el tiempo logn, fresco. Pero quiero que los valores a la derecha de X en el árbol, así, hasta que uno de ellos dosent satisfacer una prueba. Es decir, conseguir todos los elementos que son> = X y

I podría obtener el índice de X, i, a continuación, obtener el valor en i + 1, i + 2 .... hasta val (i + z) es> Y. Excepto que cuesta z * log n. Si enumerar el árbol, el empadronador dentro del árbol costo doesnt log n para pasar a la siguiente elemento - que se limita a seguir un puntero en el árbol.

Entonces, ¿hay una manera de iniciar la enumeración de un índice específico? De tal manera que no tengo que pasar por alto que los elementos antes de que pueda comenzar la enumeración sobre el rango que quiero.

Dime si usted piensa im loco.

Answer 1

Bueno, si pones los elementos de su colección allí mismo, y no le importa ordenándolos antes de la inserción, se puede envolver con un tipo de lista enlazada. Sólo asegúrese de que la clave para la envoltura de la lista de elementos vinculados para cada elemento utiliza la clave del elemento como clave para el tipo de árbol. A continuación, una búsqueda le conseguiría una ubicación en la lista enlazada, y se podía caminar desde allí.

Sin embargo, si no puede hacerlo de esa manera, su único recurso es modificar RBTree, lo que requeriría un poco de trabajo en C, ya que es una extensión nativa al rubí. La mayor parte de las piezas que usted necesita están ya dict_lookup() para darle el nodo en el árbol que necesita, y rbtree_for_each() que le muestre cómo escribir un iterador, dado un nodo de inicio.

Habría que añadir el siguiente código a rbtree.c en la gema 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);

A continuación, si se ejecuta make en el directorio de origen de la gema rbtree instalado, se debe rehacer la extensión, y se puede utilizar como normal:

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

Sólo recuerde que usted ha hecho este cambio, y distribuir la gema modificado con los cambios. O, bueno, someterlos a el creador joya en Rubyforge , para que todos puedan sacar provecho de ellas.