Class: MiniKraken::Core::Blackboard

Inherits:
Object
  • Object
show all
Defined in:
lib/mini_kraken/core/blackboard.rb

Overview

A data structure that keeps the progress of a MiniKraken search.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Blackboard

Constructor.



45
46
47
48
49
50
51
 
# File 'lib/mini_kraken/core/blackboard.rb', line 45

def initialize
  @i_name2moves = {}
  @vars2cv = {}
  # @bookmarks = []
  @next_serial_num = 0
  @move_queue = []
end

Instance Attribute Details

#bookmarks ⇒ Array<Integer> (readonly)

A stack of indices of bookmarks. The indices corresponds to the positions of the bookmarks on the move_queue. The events that involve bookmarks are:

  • enter_scope (when executing fresh expression)

  • leave_scope (when all solutions for given scope found)

  • add_bk_point (when a backtrack point must be added)

  • remove_bk_point (when a backtrack point must be retracted)

  • next_alternative (when a new solution is searched)

  • fail! (when the current solution fails)

Returns:

  • (Array<Integer>) 


30
31
32
 
# File 'lib/mini_kraken/core/blackboard.rb', line 30

def bookmarks
  @bookmarks
end

#i_name2moves ⇒ Hash{String=>Array<Integer>} (readonly)

This Hash answers to the question: given an i_name, what are its related moves (associations, fusions) ?

Returns:

  • (Hash{String=>Array<Integer>}) —

    LIFO queue



14
15
16
 
# File 'lib/mini_kraken/core/blackboard.rb', line 14

def i_name2moves
  @i_name2moves
end

#move_queue ⇒ Array<Association, Bookmark, Fusion> (readonly)

A queue of entries that embodies the progress towards a solution.

Returns:



39
40
41
 
# File 'lib/mini_kraken/core/blackboard.rb', line 39

def move_queue
  @move_queue
end

#next_serial_num ⇒ Integer (readonly)

Serial numbers are assigned sequentially to bookmark objects. This attribute holds the next available serial number.

Returns:

  • (Integer) —

    Next serial number to assign



35
36
37
 
# File 'lib/mini_kraken/core/blackboard.rb', line 35

def next_serial_num
  @next_serial_num
end

#resultant ⇒ Symbol (readonly)

Returns One of: :“#s” (success), :“#u” (failure).

Returns:

  • (Symbol) —

    One of: :“#s” (success), :“#u” (failure)



42
43
44
 
# File 'lib/mini_kraken/core/blackboard.rb', line 42

def resultant
  @resultant
end

#vars2cv ⇒ Hash{String => String} (readonly)

A mapping from fused variable’s i_name to a combining variable i_name

Returns:

  • (Hash{String => String}) 


18
19
20
 
# File 'lib/mini_kraken/core/blackboard.rb', line 18

def vars2cv
  @vars2cv
end

Instance Method Details

#associations_for(iName, shared = false) ⇒ Array<Association>

Retrieve the associations for the given internal name. If requested, add the association(s) shared through the fusion with another variable.

Parameters:

  • iName (String) —

    Internal name of variable

  • shared (Boolean) (defaults to: false)

Returns:



98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
# File 'lib/mini_kraken/core/blackboard.rb', line 98

def associations_for(iName, shared = false)
  assocs_idx = nil
  if shared && fused?(iName)
    assocs_idx = i_name2moves[vars2cv[iName]]
    if assocs_idx && move_queue[assocs_idx.first].kind_of?(Fusion)
        assocs_idx = assocs_idx.dup
        assocs_idx.shift
    end
  else
    indices = i_name2moves[iName]
    assocs_idx = indices.dup if indices
  end

  if assocs_idx
    assocs_idx.map { |i| move_queue[i] }
  else
    []
  end
end

#empty? ⇒ Boolean

Returns iff there is no entry in the association queue

Returns:

  • (Boolean) 


55
56
57
 
# File 'lib/mini_kraken/core/blackboard.rb', line 55

def empty?
  move_queue.empty?
end

#enqueue_association(anAssociation) ⇒ Association

Push the given association onto the move queue

Parameters:

Returns:



121
122
123
124
125
126
127
128
 
# File 'lib/mini_kraken/core/blackboard.rb', line 121

def enqueue_association(anAssociation)
  unless anAssociation.kind_of?(Association)
    raise StandardError, "Unsupported item class #{anAssociation.class}"
  end

  enqueue_move(anAssociation)
  anAssociation
end

#enqueue_fusion(aFusion) ⇒ Fusion

Push the given fusion object onto the move queue

Parameters:

Returns:



133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/mini_kraken/core/blackboard.rb', line 133

def enqueue_fusion(aFusion)
  aFusion.elements.each do |fused_i_nm|
    vars2cv[fused_i_nm] = aFusion.i_name
  end
  enqueue_move(aFusion)

  # If there is any existing association for the fused variables...
  # Add them to the associations of the combining variables
  bound = aFusion.elements.select { |i_nm| i_name2moves.include? i_nm }
  unless bound.empty?
    bound.each do |i_nm|
      to_copy = i_name2moves[i_nm]
      to_copy.each do |i|
        as = move_queue[i]
        new_as = AssociationCopy.new(aFusion.i_name, as)
        enqueue_association(new_as)
      end
    end
  end

  aFusion
end

#enter_scope ⇒ Integer

React to event ‘enter_scope’ by putting a scope bookmark on move queue.

Returns:

  • (Integer) —

    serial number of created bookmark



205
206
207
 
# File 'lib/mini_kraken/core/blackboard.rb', line 205

def enter_scope
  add_bookmark(:scope)
end

#failed! ⇒ Object

Notification of failure of last executed goal. All moves up to most recent backtrack point are dropped.



158
159
160
161
162
163
164
165
166
 
# File 'lib/mini_kraken/core/blackboard.rb', line 158

def failed!
  @resultant = :"#u"

  # Remove all items until most recent backtrack point.
  until move_queue.empty? ||
        (last_move.kind_of?(Bookmark) && last_move.kind == :bt_point)
    dequeue_item
  end
end

#failure? ⇒ Boolean

Does the latest result represent a failure?

Returns:

  • (Boolean) —

    true if failure, false otherwise



61
62
63
 
# File 'lib/mini_kraken/core/blackboard.rb', line 61

def failure?
  resultant != :"#s"
end

#fused?(iName) ⇒ Boolean

Indicate whether the variable is fused with another one

Parameters:

  • iName (String) —

    Internal name of a logical variable

Returns:

  • (Boolean) 


80
81
82
 
# File 'lib/mini_kraken/core/blackboard.rb', line 80

def fused?(iName)
  vars2cv.include? iName
end

#last_move ⇒ Association, ...

Return the most recent move.

Returns:



73
74
75
 
# File 'lib/mini_kraken/core/blackboard.rb', line 73

def last_move
  move_queue.last
end

#leave_scope ⇒ Array<Association, Bookmark, Fusion>

Remove all items until most recent scope bookmark found.

Returns:



211
212
213
214
215
216
217
218
219
220
221
222
 
# File 'lib/mini_kraken/core/blackboard.rb', line 211

def leave_scope
  removed = []

  # Remove all items until most recent scope bookmark.
  until move_queue.empty? ||
        (last_move.kind_of?(Bookmark) && last_move.kind == :scope)
   removed << dequeue_item
  end
  dequeue_item unless move_queue.empty? # Remove the bookmark (if any)

  removed
end

#next_alternative ⇒ Array<Association, Bookmark, Fusion>

Remove all items until most recent backtrack bookmark found. The boobmark is not remove from the queue

Returns:



182
183
184
185
186
187
188
189
190
191
192
 
# File 'lib/mini_kraken/core/blackboard.rb', line 182

def next_alternative
  removed = []

  # Remove all items until most recent scope bookmark.
  until move_queue.empty? ||
        (last_move.kind_of?(Bookmark) && last_move.kind == :bt_point)
   removed << dequeue_item
  end

  removed
end

#place_bt_point ⇒ Integer

Place a backtrack point as a bookmark on move queue.

Returns:

  • (Integer) —

    serial number of created bookmark



175
176
177
 
# File 'lib/mini_kraken/core/blackboard.rb', line 175

def place_bt_point
  add_bookmark(:bt_point)
end

#relevant_i_name(iName) ⇒ String

If the variable is fused, then return the internal name of the combining variable, otherwise return the input value as is.

Parameters:

  • iName (String) —

    Internal name of a logical variable

Returns:

  • (String) —

    Internal name of variable or combining variable.



88
89
90
 
# File 'lib/mini_kraken/core/blackboard.rb', line 88

def relevant_i_name(iName)
  fused?(iName) ? vars2cv[iName] : iName
end

#retract_bt_point ⇒ Array<Association, Bookmark, Fusion>

Remove all items until most recent backtrack bookmark found.

Returns:



196
197
198
199
200
201
 
# File 'lib/mini_kraken/core/blackboard.rb', line 196

def retract_bt_point
  removed = next_alternative
  dequeue_item unless move_queue.empty? # Remove the bookmark (if any)

  removed
end

#succeeded! ⇒ Object

Notify success of last executed goal



169
170
171
 
# File 'lib/mini_kraken/core/blackboard.rb', line 169

def succeeded!
  @resultant = :"#s"
end

#success? ⇒ Boolean

Does the latest result represent a success?

Returns:

  • (Boolean) —

    true if success, false otherwise



67
68
69
 
# File 'lib/mini_kraken/core/blackboard.rb', line 67

def success?
  resultant == :"#s"
end