Class: Okura::WordDic::DoubleArray::Builder::DAData

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(root) ⇒ DAData

Returns a new instance of DAData.



72
73
74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/okura/word_dic.rb', line 72

def initialize root
  # offset | +0         | +1       | +2       | ...
  # data   | -data_id-1 | child(0) | child(1) | ...
  #
  # base[0] = -last free cell
  # check[0] = -first free cell
  # 1 = root node id
  @base=[0,0]
  @check=[0,0]
  @length=2
  b,node_id=construct! root
  @base[1]=b
end

Instance Attribute Details

#base ⇒ Object (readonly)

Returns the value of attribute base.



85
86
87
 
# File 'lib/okura/word_dic.rb', line 85

def base
  @base
end

#check ⇒ Object (readonly)

Returns the value of attribute check.



86
87
88
 
# File 'lib/okura/word_dic.rb', line 86

def check
  @check
end

#length ⇒ Object (readonly)

Returns the value of attribute length.



87
88
89
 
# File 'lib/okura/word_dic.rb', line 87

def length
  @length
end

Instance Method Details

#alloc!(index, parent) ⇒ Object 



109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/okura/word_dic.rb', line 109

def alloc! index,parent
  assert index>0
  assert free?(index)
  if length <= index
    expand!(index+1)
  end
  assert has_free_cell?

  prev_free=-@base[index]
  next_free=-@check[index]
  @base[next_free]=-prev_free
  @check[prev_free]=-next_free
  @base[index]=0 # dummy value
  @check[index]=parent
  assert !free?(index)
end

#assert(cond) ⇒ Object 



166
167
168
 
# File 'lib/okura/word_dic.rb', line 166

def assert cond
  raise unless cond
end

#child_index(base, c) ⇒ Object 



106
107
108
 
# File 'lib/okura/word_dic.rb', line 106

def child_index base,c
  base+c+1
end

#construct!(node, parent = 1) ⇒ Object 



89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
# File 'lib/okura/word_dic.rb', line 89

def construct! node,parent=1
  # base[parent_node_id] should == s
  # -base[s+0] : data id
  # s+1+c : child node id for char c
  # check[m] : parent node id for node m
  s=find_free_space_for node
  if node.has_data?
    alloc! s,parent
    @base[s]=-node.data_id-1
  end
  node.children.each{|c,cn| alloc! child_index(s,c),parent }
  node.children.each{|c,cn|
    idx=child_index(s,c)
    @base[idx]=construct! cn,idx
  }
  s
end

#expand!(size) ⇒ Object 



125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
 
# File 'lib/okura/word_dic.rb', line 125

def expand! size
  if size <= length
    return
  end
  (length...size).each{|i|
    if has_free_cell?
      @base[i]=@base[0]
      @check[i]=0
      @check[-@base[0]]=-i
      @base[0]=-i
    else
      @base[i]=0
      @check[i]=0
      @base[0]=-i
      @check[0]=-i
    end
  }
  @length=size
end

#find_free_space_for(node) ⇒ Object 



147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
 
# File 'lib/okura/word_dic.rb', line 147

def find_free_space_for node
  alloc_indexes=node.children.keys.map{|c|c+1}
  alloc_indexes+=[0] if node.has_data?
  return 0 if alloc_indexes.empty?
  min=alloc_indexes.min
  i=-@check[0]
  while i!=0
    assert free?(i)
    if 0 < i-min && alloc_indexes.all?{|idx|free?(idx+i-min)}
      return i-min
    end
    i=-@check[i]
  end
  # free space not found
  return [length-min,1].max
end

#free?(index) ⇒ Boolean

Returns:

  • (Boolean) 


144
145
146
 
# File 'lib/okura/word_dic.rb', line 144

def free? index
  length <= index || @check[index] <= 0
end

#has_free_cell? ⇒ Boolean

Returns:

  • (Boolean) 


163
164
165
 
# File 'lib/okura/word_dic.rb', line 163

def has_free_cell?
  @base[0]!=0
end