Simple Trie Data Structure

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.

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs