Class: Trie

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

Overview

A key-value data structure for string keys which is efficient memory usage and fast retrieval time.

Instance Method Summary collapse

Instance Method Details

#add(key) ⇒ Object #add(key, value) ⇒ Object

Add a key, or a key and value to the Trie. If you add a key without a value it assumes true for the value.



67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'ext/trie/trie.c', line 67

static VALUE rb_trie_add(VALUE self, VALUE args) {
	Trie *trie;
    Data_Get_Struct(self, Trie, trie);

    int size = RARRAY(args)->len;
    if(size < 1 || size > 2)
		return Qnil;

    VALUE key;
    key = RARRAY(args)->ptr[0];
    TrieData value = size == 2 ? RARRAY(args)->ptr[1] : TRIE_DATA_ERROR;
    
    if(trie_store(trie, (TrieChar*)RSTRING(key)->ptr, value))
		return Qtrue;
    else
		return Qnil;
}

#children(prefix) ⇒ Array

Finds all keys in the Trie beginning with the given prefix.

Returns:

  • (Array) 


133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
 
# File 'ext/trie/trie.c', line 133

static VALUE rb_trie_children(VALUE self, VALUE prefix) {
    if(NIL_P(prefix))
		return rb_ary_new();

    Trie *trie;
    Data_Get_Struct(self, Trie, trie);

	int prefix_size = RSTRING(prefix)->len;
    TrieState *state = trie_root(trie);
    VALUE children = rb_ary_new();
	TrieChar *char_prefix = (TrieChar*)RSTRING(prefix)->ptr;
    
    const TrieChar *iterator = char_prefix;
    while(*iterator != 0) {
		if(!trie_state_is_walkable(state, *iterator))
			return children;
		trie_state_walk(state, *iterator);
		iterator++;
    }

    if(trie_state_is_terminal(state))
		rb_ary_push(children, prefix);
	
	char prefix_buffer[1024];
	memcpy(prefix_buffer, char_prefix, prefix_size);
	prefix_buffer[prefix_size] = 0;

    walk_all_paths(trie, children, state, prefix_buffer, prefix_size);

    trie_state_free(state);
    return children;
}

#children_with_values(key) ⇒ Array

Finds all keys with their respective values in the Trie beginning with the given prefix.

Returns:

  • (Array) 


209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
 
# File 'ext/trie/trie.c', line 209

static VALUE rb_trie_children_with_values(VALUE self, VALUE prefix) {
    if(NIL_P(prefix))
		return rb_ary_new();

    Trie *trie;
    Data_Get_Struct(self, Trie, trie);

	int prefix_size = RSTRING(prefix)->len;
    TrieChar *char_prefix = (TrieChar*)RSTRING(prefix)->ptr;
    
    VALUE children = rb_ary_new();

    TrieState *state = trie_root(trie);
    
    const TrieChar *iterator = char_prefix;
    while(*iterator != 0) {
		if(!trie_state_is_walkable(state, *iterator))
			return rb_ary_new();
		trie_state_walk(state, *iterator);
		iterator++;
    }

    if(trie_state_is_terminal(state)) {
		TrieState *end_state = trie_state_clone(state);
		trie_state_walk(end_state, '\0');

		VALUE tuple = rb_ary_new();
		rb_ary_push(tuple, prefix);
		TrieData trie_data = trie_state_get_data(end_state);
		rb_ary_push(tuple, (VALUE)trie_data);
		rb_ary_push(children, tuple);

		trie_state_free(end_state);
    }

	char prefix_buffer[1024];
	memcpy(prefix_buffer, char_prefix, prefix_size);
	prefix_buffer[prefix_size] = 0;

    walk_all_paths_with_values(trie, children, state, prefix_buffer, prefix_size);

    trie_state_free(state);
    return children;
}

#delete(key) ⇒ Object

Delete a key from the Trie. Returns true if it deleted a key, nil otherwise.



92
93
94
95
96
97
98
99
100
 
# File 'ext/trie/trie.c', line 92

static VALUE rb_trie_delete(VALUE self, VALUE key) {
	Trie *trie;
    Data_Get_Struct(self, Trie, trie);

    if(trie_delete(trie, (TrieChar*)RSTRING(key)->ptr))
		return Qtrue;
    else
		return Qnil;
}

#get(key) ⇒ Object

Retrieves the value for a particular key (or nil) from the Trie.



48
49
50
51
52
53
54
55
56
57
 
# File 'ext/trie/trie.c', line 48

static VALUE rb_trie_get(VALUE self, VALUE key) {
    Trie *trie;
    Data_Get_Struct(self, Trie, trie);

	TrieData data;
    if(trie_retrieve(trie, (TrieChar*)RSTRING(key)->ptr, &data))
		return (VALUE)data;
    else
		return Qnil;
}

#has_key?(key) ⇒ Boolean

Determines whether or not a key exists in the Trie. Use this if you don’t care about the value, as it is marginally faster than Trie#get.

Returns:

  • (Boolean) 


30
31
32
33
34
35
36
37
38
 
# File 'ext/trie/trie.c', line 30

static VALUE rb_trie_has_key(VALUE self, VALUE key) {
    Trie *trie;
    Data_Get_Struct(self, Trie, trie);

    if(trie_has_key(trie, (TrieChar*)RSTRING(key)->ptr))
		return Qtrue;
    else
		return Qnil;
}

#root ⇒ TrieNode

Returns a TrieNode representing the root of the Trie.

Returns:



263
264
265
266
267
268
269
270
271
272
273
274
275
 
# File 'ext/trie/trie.c', line 263

static VALUE rb_trie_root(VALUE self) {
    Trie *trie;
    Data_Get_Struct(self, Trie, trie);

    VALUE trie_node = rb_trie_node_alloc(cTrieNode);

	TrieState *state = trie_root(trie);
	RDATA(trie_node)->data = state;
    
    rb_iv_set(trie_node, "@state", Qnil);
    rb_iv_set(trie_node, "@full_state", rb_str_new2(""));
    return trie_node;
}