Class: Okura::Nodes

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

Instance Method Summary collapse

Constructor Details

#initialize(len, mat) ⇒ Nodes

Returns a new instance of Nodes.



32
33
34
35
36
 
# File 'lib/okura.rb', line 32

def initialize len,mat
  @mat=mat
  @begins=(0...len).map{[]}
  @ends=(0...len).map{[]}
end

Instance Method Details

#[](i) ⇒ Object 



37
38
39
 
# File 'lib/okura.rb', line 37

def [](i)
  @begins[i]
end

#add(i, node) ⇒ Object 



80
81
82
83
 
# File 'lib/okura.rb', line 80

def add i,node
  @begins[i].push node
  @ends[i+node.length-1].push node
end

#length ⇒ Object 



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

def length
  @begins.length
end

#mincost_path ⇒ Object

Matrix -> [Node] | nil



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/okura.rb', line 44

def mincost_path
  return [] if length==0
  # calc cost
  self[0].each{|n|
    n.total_cost=n.word.cost
    n.nearest_prev=nil
  }
  (1...length).each{|i|
    prevs=@ends[i-1]
    curs=@begins[i]
    prevs.each{|prev|
      # 途中で行き止まりのNodeはtotal_costが設定されない
      next if prev.total_cost.nil?
      curs.each{|cur|
        join_cost=@mat.cost(prev.word.right.id,cur.word.left.id)
        next if join_cost.nil?
        cost=prev.total_cost+join_cost+cur.word.cost
        if !cur.total_cost || cost < cur.total_cost
          cur.total_cost=cost
          cur.nearest_prev=prev
        end
      }
    }
  }
  # calc mincost path
  ret=[]
  cur=self[-1][0]
  until cur.nil?
    ret.push cur
    cur=cur.nearest_prev
  end
  # TODO: disconnected
  #  return nil unless ...
  # success
  return ret.reverse
end