chise/idstree.rb

   1 # Copyright (C) 2002-2004 Kouichirou Eto, All rights reserved.
   2
   3 module CHISE
   4   class Node < Array # a branch of Tree structure
   5     def initialize(nodeleaf=nil, nodenum=nil)
   6       super() # without arg
   7       @nodeleaf = nodeleaf
   8       @nodenum = nodenum
   9       if @nodeleaf
  10         original_add(@nodeleaf)
  11       end
  12     end
  13     attr_reader :nodenum
  14
  15     alias original_add <<
  16       private :original_add
  17
  18     def <<(obj)
  19       original_add(obj)
  20       @nodenum -= 1 if @nodenum
  21     end
  22
  23     def nodes
  24       ar = []
  25       ar << self.to_s
  26       self.each {|n|
  27         ar += n.nodes if n.is_a? Node
  28       }
  29       ar
  30     end
  31   end
  32
  33   class Tree
  34     def initialize
  35       @root = Node.new
  36       @stack = [@root]
  37       @leafnum = 0
  38       @depth = 1 # the deepest stack size.  If there is no tree, depth is 1.
  39     end
  40
  41     def depth() @depth - 1; end
  42
  43     def add_node(nodeleaf=nil, nodenum=nil) # add a node
  44       new_node = Node.new(nodeleaf, nodenum)
  45       @stack.last << new_node
  46       @stack << new_node
  47       if @depth < @stack.length
  48         @depth = @stack.length
  49       end
  50       self
  51     end
  52
  53     def end_node # terminate this node.
  54       @stack.pop
  55       self
  56     end
  57
  58     def add_leaf(a) # add a leaf.
  59       @stack.last << a
  60       end_check()
  61       self
  62     end
  63
  64     def end_check
  65       n = @stack.last.nodenum
  66       if n && n == 0
  67         end_node
  68         end_check # recursive.
  69       end
  70     end
  71
  72     def check_integrity
  73       n = @stack.last.nodenum
  74       return nil if @root.length == 0 # no tree is good tree
  75       raise "unmatch leaves" if n && n != 0
  76       raise "extra nodes" if @root.first.is_a?(Node) && @root.length != 1
  77       raise "extra leaves" if @root.length != 1
  78       return nil
  79     end
  80
  81     def nodes
  82       r = @root.nodes
  83       r.shift
  84       r
  85     end
  86
  87     def sub_nodes
  88       r = nodes
  89       r.shift
  90       r
  91     end
  92
  93     def to_s()    @root.to_s    end
  94
  95     def inspect() @root.inspect end
  96   end
  97
  98   class IDS_Tree < Tree
  99     def initialize(str)
 100       @str = str
 101       super()
 102       parse
 103     end
 104
 105     def parse
 106       @str.each_character {|char|
 107         if is_idc?(char)
 108           add_node(char, idc_argument_number(char))
 109         else
 110           add_leaf(char)
 111         end
 112       }
 113     end
 114
 115     def is_idc?(obj)
 116       return true if obj.is_idc?
 117       return true if "+*".include?(obj.to_s) # only for test
 118       return false
 119     end
 120
 121     def idc_argument_number(obj)
 122       n = obj.idc_argument_number
 123       return n if 0 < n
 124       return 2 # only for test
 125     end
 126
 127     def check_integrity
 128       super
 129       raise "contains ques" if /\?/ =~ @str #?が含まれている?
 130       return nil
 131     end
 132
 133   end
 134 end