Simple Trie Data Structure

Ruby
1

Disclaimer… I’ve only used Ruby for a few days and I can say I’m impressed at how easy it is to write code in this language. I’m surprised I never tried Ruby before. I tried Python before and I didn’t like the language and kind of lumped Ruby in the same camp as Python. Ruby is no Python. Ruby is literally fun to code in.

Only a few days in Ruby and I can bang out a simple Trie like data structure.

#! /usr/bin/env ruby

require 'optional'

def nextChar(arr)

	ans = arr.shift
	
	if ans.nil?
		:empty
	else
		[ans, arr]
	end

end

def empty

	{}

end

def display(tr)

	tr.keys.each{|k| print k; display(tr[k])}

end

def add(tr, chrs)

	ans = nextChar(chrs)
	
	if ans != :empty
		if tr[ans[0]].nil?
			temp = {}
			tr[ans[0]] = temp
			add(temp, ans[1])
		else
			add(tr[ans[0]], ans[1])
		end
	end

end

def find(tr, chrs)

	ans = nextChar(chrs)
	
	if ans != :empty
		if tr[ans[0]].nil?
			None
		else
			find(tr[ans[0]], ans[1])
		end
	else
		Some[tr]
	end

end

def strings_aux(tr, acc, str="")
	if tr.empty?
		acc.push(str)
	else
		tr.each{|k, v| strings_aux(v, acc, str + k)}
	end
end

def strings(tr)

	acc = []
	
	strings_aux(tr, acc)
	
	acc

end

if __FILE__ == $0

	tr = empty
	
	[
		"G4143\n", 
		"Gerard\n", 
		"This is the first\n", 
		"This is the second\n", 
		"This is the third\n", 
		"This is the fourth\n"]
		.each{|s| add(tr, s.chars)}
	
	display(tr)

	puts 

	p tr
	
	puts 
	
	find(tr, "This is the ".chars)
		.match{
			|o|
			o.some {|t| display(t)}
			o.none {puts "Nothing found!"}
		}
		
	puts "\nBuild original strings\n\n"
	
	strings(tr).each{|e| print e}

end

Amazing!

Note: I used newline characters in the strings bc it would make it easier to display and debug.