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) 


384
385
386
 
# File 'ext/trie/trie.c', line 384

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

#initialize_copy(from) ⇒ Object

nodoc



353
354
355
356
357
358
359
360
361
362
363
 
# File 'ext/trie/trie.c', line 353

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) 


490
491
492
493
494
495
 
# File 'ext/trie/trie.c', line 490

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”.



372
373
374
 
# File 'ext/trie/trie.c', line 372

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) 


477
478
479
480
481
482
 
# File 'ext/trie/trie.c', line 477

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.



455
456
457
458
459
460
461
462
463
464
465
466
467
 
# File 'ext/trie/trie.c', line 455

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:



424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
 
# File 'ext/trie/trie.c', line 424

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:



395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
 
# File 'ext/trie/trie.c', line 395

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;
}