Class: GADDAG::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/gaddag/node.rb

Overview

Represents a node in the GADDAG data structure

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Node

Initializes a GADDAG node



15
16
17
 
# File 'lib/gaddag/node.rb', line 15

def initialize
  @outgoing_arcs = {}
end

Instance Attribute Details

#outgoing_arcs ⇒ Object (readonly)

A mapping of letters to arcs



8
9
10
 
# File 'lib/gaddag/node.rb', line 8

def outgoing_arcs
  @outgoing_arcs
end

Instance Method Details

#arc?(letter) ⇒ Boolean

Checks whether an outgoing arc for the given letter exists

Parameters:

  • letter (String) —

    the letter to check for

Returns:

  • (Boolean) —

    whether the outgoing arc exists



32
33
34
 
# File 'lib/gaddag/node.rb', line 32

def arc?(letter)
  @outgoing_arcs.key?(letter.to_sym)
end

#create_arc(letter, destination = Node.new) ⇒ Arc

Creates an outgoing arc for a letter to a destination node arc is followed

Parameters:

  • letter (String) —

    the letter to be added to the path when this

  • destination (Node) (defaults to: Node.new) —

    the node to which this arc should point

Returns:

  • (Arc) —

    the newly created arc or an existing arc if one already exists for this letter



25
26
27
 
# File 'lib/gaddag/node.rb', line 25

def create_arc(letter, destination = Node.new)
  @outgoing_arcs[letter.to_sym] ||= Arc.new(destination)
end

#create_final_arc(letter, final_letter, destination = Node.new) ⇒ Object

Creates a final outgoing arc for a letter to a destination node. Effectively this will add a final letter to the outgoing arc, indicating that a valid word can be formed with it.

See Also:



40
41
42
 
# File 'lib/gaddag/node.rb', line 40

def create_final_arc(letter, final_letter, destination = Node.new)
  create_arc(letter, destination).tap { |arc| arc.add_final_letter(final_letter) }
end

#create_final_path(letters, destinations = []) ⇒ Object

Creates a path for a list of letters and optional destination nodes, ommiting the last node, and marking the last letter as final

See Also:



66
67
68
69
70
71
72
73
 
# File 'lib/gaddag/node.rb', line 66

def create_final_path(letters, destinations = [])
  *initial_letters, second_last_letter, last_letter = *letters
  second_last_node = create_path(initial_letters, destinations)

  (destinations[initial_letters.length] || Node.new).tap do |final_destination|
    second_last_node.create_final_arc(second_last_letter, last_letter, final_destination)
  end
end

#create_path(letters, destinations = []) ⇒ Node

Creates a path for a list of letters and optional destination nodes

Parameters:

  • letters (Array<String>) —

    the letters for which the path should be build

  • destinations (Array<Node>) (defaults to: []) —

    the destination nodes which the path should visit

Returns:

  • (Node) —

    the lastly created destination ode



48
49
50
51
52
 
# File 'lib/gaddag/node.rb', line 48

def create_path(letters, destinations = [])
  letters.zip(destinations).inject(self) do |node, (letter, destination)|
    node.create_arc(letter, destination || Node.new).destination
  end
end

#final_path?(letters) ⇒ Boolean

Checks whether a final path exists for the given list of letters

Parameters:

  • letters (Array<String>) —

    the letter path to check for

Returns:

  • (Boolean) —

    whether the final path exists



78
79
80
81
82
83
84
 
# File 'lib/gaddag/node.rb', line 78

def final_path?(letters)
  *initial_letters, second_last_letter, last_letter = *letters

  path?(initial_letters) && follow_path(initial_letters).final_paths.any? do |path|
    path == Path.new([second_last_letter, last_letter])
  end
end

#final_paths ⇒ Array<Path>

Returns all paths from this node that are final. The set of final paths are all paths for which the last arc includes a final letter. For each final letter a seperate path is created.

Returns:

  • (Array<Path>) —

    a list of final paths



108
109
110
111
112
 
# File 'lib/gaddag/node.rb', line 108

def final_paths
  @outgoing_arcs.reduce([]) do |paths, (letter_sym, arc)|
    paths += arc.final_paths.map { |path| Path.new([letter_sym.to_s] + path) }
  end
end

#follow_arc(letter) ⇒ Node

Follows a single outgoing arc for a given letter

Parameters:

  • letter (String) —

    the letter that should be followed

Returns:

  • (Node) —

    the destination node that the arc for this letter leads to

Raises:

  • (KeyError) —

    if no outgoing arc exists for the given letter



90
91
92
 
# File 'lib/gaddag/node.rb', line 90

def follow_arc(letter)
  @outgoing_arcs.fetch(letter.to_sym).destination
end

#follow_path(letters) ⇒ Node

Recursively follows a list of letters

Parameters:

  • letters (Array<String>) —

    the letters to be followed

Returns:

  • (Node) —

    the destination node that the path of letters leads to

Raises:

  • (KeyError) —

    if an outgoing arc does not exist for a given letter at the corresponding node



99
100
101
102
 
# File 'lib/gaddag/node.rb', line 99

def follow_path(letters)
  return self if letters.empty?
  follow_arc(letters[0]).follow_path(letters[1..-1])
end

#path?(letters) ⇒ Boolean

Checks whether a path exists for the given list of letters

Parameters:

  • letters (Array<String>) —

    the letter path to check for

Returns:

  • (Boolean) —

    whether the path exists



57
58
59
60
61
 
# File 'lib/gaddag/node.rb', line 57

def path?(letters)
  return true if letters.empty?
  return false unless arc?(letters.first)
  follow_arc(letters.first).path?(letters[1..-1])
end