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) 


321
322
323
 
# File 'ext/trie/trie.c', line 321

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

#initialize_copy(from) ⇒ Object

nodoc



293
294
295
296
297
298
299
300
 
# File 'ext/trie/trie.c', line 293

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

    return self;
}

#leaf? ⇒ Boolean

Returns true if there are no branches at this node.

Returns:

  • (Boolean) 


423
424
425
426
427
428
 
# File 'ext/trie/trie.c', line 423

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



309
310
311
 
# File 'ext/trie/trie.c', line 309

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) 


410
411
412
413
414
415
 
# File 'ext/trie/trie.c', line 410

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.



388
389
390
391
392
393
394
395
396
397
398
399
400
 
# File 'ext/trie/trie.c', line 388

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:



359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
 
# File 'ext/trie/trie.c', line 359

static VALUE rb_trie_node_walk(VALUE self, VALUE rchar) {
	VALUE new_node = rb_funcall(self, rb_intern("dup"), 0);

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

    if(RSTRING(rchar)->len != 1)
		return Qnil;

    Bool result = trie_state_walk(state, *RSTRING(rchar)->ptr);
    
    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 self;
    } 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:



332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
 
# File 'ext/trie/trie.c', line 332

static VALUE rb_trie_node_walk_bang(VALUE self, VALUE rchar) {
    TrieState *state;
    Data_Get_Struct(self, TrieState, state);

    if(RSTRING(rchar)->len != 1)
		return Qnil;

    Bool result = trie_state_walk(state, *RSTRING(rchar)->ptr);
    
    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;
}