enumerazione da un indice / valore in rubino

Question

Così Ive ha ottenuto questo big-ass collezione giusto? Il suo albero-backed (RBTree), in modo da guardare-up sono veloci, ed i valori sono ordinati.

Di 'Ive ha ottenuto il valore X. posso osservare in su X nel mio albero in tempo logn, fresco. Ma voglio che i valori a destra del X nell'albero così, fino a quando uno di loro mancava era soddisfare un test. Per esempio, ottenere tutti gli elementi che sono> = X e

I potrebbe ottenere l'indice di X, i, quindi ottenere il valore i + 1, i + 2 .... fino val (i + z) è> Y. Solo che costa z * logn. Se si enumera sopra l'albero, l'enumeratore all'interno dell'albero costo doesnt logn per passare al successivo elemento - si segue solo un puntatore nella struttura.

Quindi, c'è un modo per iniziare l'enumerazione da un indice specifico? Tale che non devo saltare i elementi prima di poter iniziare l'enumerazione su tutta la gamma che voglio.

Dimmi se si pensa im pazza.

Answer 1

Bene, se si mette gli elementi della vostra collezione in là te stesso, e non vi occupate di loro l'ordinamento prima dell'inserimento, si potrebbe avvolgerli con un tipo di lista collegata. Solo assicurarsi che la chiave per il wrapper voce di lista concatenata per ogni elemento utilizza la chiave dell'elemento come la sua chiave per l'albero sorta. Poi una ricerca si otterrebbe una posizione nella lista collegata, e si può solo a piedi da lì.

Tuttavia, se non si può fare in questo modo, l'unica soluzione è quella di modificare RBTree, che richiederebbe un po 'di lavoro in C, in quanto si tratta di un'estensione nativa al rubino. La maggior parte dei pezzi che ti servono ci sono già dict_lookup() per darvi il nodo dell'albero è necessario, e rbtree_for_each() per mostrare come scrivere un iteratore, dato un nodo di partenza.

Dovresti aggiungere il seguente codice al rbtree.c nella gemma 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);

Poi, se si esegue make nella directory dei sorgenti della gemma rbtree installato, dovrebbe rifare l'estensione, e si può usare come normale:

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

Basta ricordare che hai fatto questo cambiamento, e distribuire la gemma modificato con le modifiche. Oppure, hey, sottoporli a il creatore gioiello Rubyforge , in modo che tutti possano approfittare di loro.