Class: TrieNode

Inherits:
Object
  • Object
show all
Defined in:
ext/trie/trie.c,
ext/trie/trie.c

Overview

Represents a single node in the Trie. It can be used as a cursor to walk around the Trie. You can grab a TrieNode for the root of the Trie by using Trie#root.

Instance Method Summary collapse

Instance Method Details

#full_state ⇒ String

Returns the full string from the root of the Trie up to this node. So if the node pointing at the “e” in “monkeys”, the full_state is “monke”.

Returns:

  • (String) 

447
448
449
 
# File 'ext/trie/trie.c', line 447

static VALUE rb_trie_node_get_full_state(VALUE self) {
    return rb_iv_get(self, "@full_state");
}

#initialize_copy(from) ⇒ Object

nodoc


416
417
418
419
420
421
422
423
424
425
426
 
# File 'ext/trie/trie.c', line 416

static VALUE rb_trie_node_initialize_copy(VALUE self, VALUE from) {
	RDATA(self)->data = trie_state_clone(RDATA(from)->data);
    
    VALUE state = rb_iv_get(from, "@state");
    rb_iv_set(self, "@state", state == Qnil ? Qnil : rb_str_dup(state));

    VALUE full_state = rb_iv_get(from, "@full_state");
    rb_iv_set(self, "@full_state", full_state == Qnil ? Qnil : rb_str_dup(full_state));

    return self;
}

#leaf? ⇒ Boolean

Returns true if there are no branches at this node.

Returns:

  • (Boolean) 

553
554
555
556
557
558
 
# File 'ext/trie/trie.c', line 553

static VALUE rb_trie_node_leaf(VALUE self) {
    TrieState *state;
    Data_Get_Struct(self, TrieState, state);
    
    return trie_state_is_leaf(state) ? Qtrue : Qnil;
}

#state ⇒ Object

Returns the letter that the TrieNode instance points to. So, if the node is pointing at the “e” in “monkeys”, the state is “e”.


435
436
437
 
# File 'ext/trie/trie.c', line 435

static VALUE rb_trie_node_get_state(VALUE self) {
    return rb_iv_get(self, "@state");
}

#terminal? ⇒ Boolean

Returns true if this node is at the end of a key. So if you have two keys in your Trie, “he” and “hello”, and you walk all the way to the end of “hello”, the “e” and the “o” will return true for terminal?.

Returns:

  • (Boolean) 

540
541
542
543
544
545
 
# File 'ext/trie/trie.c', line 540

static VALUE rb_trie_node_terminal(VALUE self) {
    TrieState *state;
    Data_Get_Struct(self, TrieState, state);
    
    return trie_state_is_terminal(state) ? Qtrue : Qnil;
}

#value ⇒ Object

Attempts to get the value at this node of the Trie. This only works if the node is a terminal (i.e. end of a key), otherwise it returns nil.


518
519
520
521
522
523
524
525
526
527
528
529
530
 
# File 'ext/trie/trie.c', line 518

static VALUE rb_trie_node_value(VALUE self) {
    TrieState *state;
	TrieState *dup;
    Data_Get_Struct(self, TrieState, state);
    
    dup = trie_state_clone(state);

    trie_state_walk(dup, 0);
    TrieData trie_data = trie_state_get_data(dup);
    trie_state_free(dup);

    return TRIE_DATA_ERROR == trie_data ? Qnil : (VALUE)trie_data;
}

#walk(letter) ⇒ TrieNode

Tries to walk down a particular branch of the Trie. It clones the node it is called on and walks with that one, leaving the original unchanged.

Returns:


487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
 
# File 'ext/trie/trie.c', line 487

static VALUE rb_trie_node_walk(VALUE self, VALUE rchar) {
	StringValue(rchar);

	VALUE new_node = rb_funcall(self, rb_intern("dup"), 0);

    TrieState *state;
    Data_Get_Struct(new_node, TrieState, state);

    if(RSTRING_LEN(rchar) != 1)
		return Qnil;

    Bool result = trie_state_walk(state, *RSTRING_PTR(rchar));
    
    if(result) {
		rb_iv_set(new_node, "@state", rchar);
		VALUE full_state = rb_iv_get(new_node, "@full_state");
		rb_str_append(full_state, rchar);
		rb_iv_set(new_node, "@full_state", full_state);
		return new_node;
    } else
		return Qnil;
}

#walk!(letter) ⇒ TrieNode

Tries to walk down a particular branch of the Trie. It modifies the node it is called on.

Returns:


458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
 
# File 'ext/trie/trie.c', line 458

static VALUE rb_trie_node_walk_bang(VALUE self, VALUE rchar) {
	StringValue(rchar);

    TrieState *state;
    Data_Get_Struct(self, TrieState, state);

    if(RSTRING_LEN(rchar) != 1)
		return Qnil;

    Bool result = trie_state_walk(state, *RSTRING_PTR(rchar));
    
    if(result) {
		rb_iv_set(self, "@state", rchar);
		VALUE full_state = rb_iv_get(self, "@full_state");
		rb_str_append(full_state, rchar);
		rb_iv_set(self, "@full_state", full_state);
		return self;
    } else
		return Qnil;
}