Class: GADDAG

Inherits:
Object
  • Object
show all
Defined in:
lib/gaddag.rb,
lib/gaddag/arc.rb,
lib/gaddag/node.rb,
lib/gaddag/path.rb,
lib/gaddag/word.rb

Overview

Implementation of the GADDAG data structure

Defined Under Namespace

Classes: Arc, Node, Path, Word

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ GADDAG

Initializes a GADDAG



17
18
19
 
# File 'lib/gaddag.rb', line 17

def initialize
  @root = Node.new
end

Instance Attribute Details

#root ⇒ Object (readonly)

The root node



13
14
15
 
# File 'lib/gaddag.rb', line 13

def root
  @root
end

Instance Method Details

#add(word) ⇒ GADDAG

Adds a word to the GADDAG

Parameters:

  • word (String) —

    the word to be added

Returns:

  • (GADDAG) —

    the GADDAG instance



24
25
26
27
28
29
30
31
32
 
# File 'lib/gaddag.rb', line 24

def add(word)
  @root.create_final_path(word.chars.reverse + [Path::DELIMITER])

  Word.new(word.chars).to_delimited_paths.each do |path|
    @root.create_final_path(path.letters)
  end

  self
end

#find(substring) ⇒ Array<String>

Finds all words that contain the given substring

Parameters:

  • substring (String) —

    the substring to search for

Returns:

  • (Array<String>) —

    all matching words



37
38
39
40
41
42
43
44
45
46
 
# File 'lib/gaddag.rb', line 37

def find(substring)
  first_letter, second_letter, *last_letters = *substring.chars
  return [] unless @root.path?(last_letters.reverse)

  @root.follow_path(last_letters.reverse).final_paths.select do |path|
    path.start_with?([second_letter, first_letter])
  end.map do |path|
    Path.new(last_letters.reverse + path).to_word.to_s
  end.uniq
end