Module: Ron::GraphWalk
- Defined in:
- lib/ron/graphedge.rb
Overview
Class Method Summary collapse
-
.abortable_graphwalk(obj) ⇒ Object
——————————–.
-
.breadth_graphcopy(obj, old2new = {}) ⇒ Object
——————————–.
-
.depth_graphcopy(obj, old2new = {}) ⇒ Object
(also: graphcopy)
——————————–.
-
.depth_graphwalk(obj, container = nil, index = nil, type = GraphEdge::TopLevel, seen = , &block) ⇒ Object
——————————– depth-first walk of an object graph.
-
.graphmodify!(obj) ⇒ Object
——————————–.
-
.graphwalk(obj) {|nil, obj, nil, GraphEdge::TopLevel| ... } ⇒ Object
(also: breadth_graphwalk)
——————————– breadth-first walk of an object graph.
-
.recursive_each(arr, &block) ⇒ Object
wannabe in class ::Array.
-
.recursive_reverse_each(arr, &block) ⇒ Object
—————————.
-
.traverse(obj) ⇒ Object
——————————–.
Class Method Details
.abortable_graphwalk(obj) ⇒ Object
131 132 133 134 135 136 137 138 139 140 141 142 143 |
# File 'lib/ron/graphedge.rb', line 131 def abortable_graphwalk(obj) return unless yield nil,obj,nil,GraphEdge::TopLevel todolist=[obj] donelist=Set[] todolist.each{|o| traverse(o){|cntr,o2,i,ty| unless donelist.include? [cntr.__id__,ty,i] donelist<<[cntr.__id__,ty,i] todolist<<o2 if yield cntr,o2,i,ty end } } end |
.breadth_graphcopy(obj, old2new = {}) ⇒ Object
NOTE: breadth_graphcopy has a problem; since graphwalk is not depth-first,
if a node is replaced, the subnodes of the new node will not be walked.
Instead, the old nodes will be walked.
If this causes problems, use depth_graphcopy instead
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
# File 'lib/ron/graphedge.rb', line 46 def breadth_graphcopy(obj,old2new={}) root=nil breadth_graphwalk(obj){|cntr,o,i,ty| newo= block_given? && (yield cntr,o,i,ty,useit=[false]) if useit.first #fail unless newo old2new[o.__id__]=newo else #fail unless o newo= old2new[o.__id__] ||= (o.clone rescue o) end #IO objects really shouldn't be dup'd here if Ron::GraphEdge::TopLevel==ty root=newo else #fail unless old2new.has_key? cntr.__id__ ty.new(old2new[cntr.__id__],i,1){newo}.replace end } return root end |
.depth_graphcopy(obj, old2new = {}) ⇒ Object Also known as: graphcopy
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
# File 'lib/ron/graphedge.rb', line 69 def depth_graphcopy(obj,old2new={}) root=nil changes=[] depth_graphwalk(obj){|cntr,o,i,ty| newo=yield cntr,o,i,ty,useit=[false] if block_given? if useit.first #p [cntr.id,cntr,o,:>>,newo,newo.last.__id__] old2new[o.__id__]=o #bad, bad... shouldn't be refs to old tree in old2new else begin newo=o.clone rescue Exception newo=o else old2new[o.__id__]=newo end end #IO objects really shouldn't be dup'd here if Ron::GraphEdge::TopLevel==ty root=newo else changes.push ty,cntr.__id__,i,newo end } until changes.empty? ty,cntr_id,i,newo=*changes.slice!(-4,4) new_cntr=old2new[cntr_id] ty.new(new_cntr,i,1){newo}.replace if old2new.has_key? cntr_id end return root end |
.depth_graphwalk(obj, container = nil, index = nil, type = GraphEdge::TopLevel, seen = , &block) ⇒ Object
depth-first walk of an object graph
122 123 124 125 126 127 128 |
# File 'lib/ron/graphedge.rb', line 122 def depth_graphwalk(obj,container=nil,index=nil,type=GraphEdge::TopLevel,seen=Set[],&block) seen<<[container.__id__,type,index] traverse(obj){|cntr,o,i,ty| depth_graphwalk(o,cntr,i,ty,seen,&block) unless seen.include? [cntr.__id__,ty,i] } block[ container,obj,index,type ] end |
.graphmodify!(obj) ⇒ Object
26 27 28 29 30 31 32 33 34 35 36 37 38 |
# File 'lib/ron/graphedge.rb', line 26 def graphmodify!(obj) root=nil graphwalk(obj){|cntr,o,i,ty| newo= yield cntr,o,i,ty,useit=[false] useit.first or next if Ron::GraphEdge::TopLevel===ty root=newo else ty.new(cntr,i,1){newo}.replace end } return root end |
.graphwalk(obj) {|nil, obj, nil, GraphEdge::TopLevel| ... } ⇒ Object Also known as: breadth_graphwalk
breadth-first walk of an object graph
104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
# File 'lib/ron/graphedge.rb', line 104 def graphwalk(obj) yield nil,obj,nil,GraphEdge::TopLevel todolist=[obj] donelist=Set[] todolist.each{|o| traverse(o){|cntr,o2,i,ty| unless donelist.include? [cntr.__id__,ty,i] todolist<<o2 donelist<<[cntr.__id__,ty,i] yield cntr,o2,i,ty end } } end |
.recursive_each(arr, &block) ⇒ Object
wannabe in class ::Array
187 188 189 190 191 192 193 194 195 |
# File 'lib/ron/graphedge.rb', line 187 def recursive_each arr,&block arr.each {|item| if item.respond_to? :to_a recursive_each item.to_a, &block else block[item] end } end |
.recursive_reverse_each(arr, &block) ⇒ Object
198 199 200 201 202 203 204 205 206 |
# File 'lib/ron/graphedge.rb', line 198 def recursive_reverse_each arr,&block arr.reverse_each {|item| if item.respond_to? :to_ary recursive_reverse_each item.to_ary, &block else block[item] end } end |
.traverse(obj) ⇒ Object
145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 |
# File 'lib/ron/graphedge.rb', line 145 def traverse(obj) #some other container types should be explicitly #supported here: Set, Struct, OpenStruct, SuperStruct, Tree #maybe others i don't know? sparse array/sparse matrix? #ordered hashes? case obj when nil; #do nothing when (Set if defined? Set) obj.dup.each{|elem| yield(obj,elem, elem, GraphEdge::SetMember) } when Struct; obj.members.each{|mem| yield(obj,obj[mem],mem, GraphEdge::BracketsValue) } when Hash; obj.keys.each{|i| elem=obj[i] yield(obj,elem,i, GraphEdge::HashValue) yield(obj,i,i, GraphEdge::HashKey) } when Array; (obj.size-1).downto(0){|i| elem=obj[i] yield(obj,elem,i, GraphEdge::Array) } when Range; yield(obj,obj.first, :first, GraphEdge::ObjectMethValue) yield(obj,obj.last, :last, GraphEdge::ObjectMethValue) #when RBTree; huh when (ActiveRecord::Base if defined? ActiveRecord) obj.columns.each{|mem| yield(obj,obj[mem],mem, GraphEdge::BracketsValue) } end #traverse instance vars in any case obj.instance_variables.each{|var| yield obj, (obj.instance_variable_get var), var.to_s, GraphEdge::ObjectIvarValue } end |