0x0c: These shoes are made for walking

Wanna go for a stroll? It is getting winter again, at least in this part of the world so strolling outside might be a bit, err, cold. Instead I suggest you just walk some ruby objects this time instead?

Walking – in this context – means visiting an object and all connected subobjects, and visiting them only once. So to walk an object you would just get the object, collect all subobjects (read: instance variables), and any other connected object you know about: for Arrays these are the array elements, for hashes all keys and values. And then we use some piece of storage that remembers which object we already went to, to visit each one only once, and at the same time to prevent endless loops (which would otherwise be easy with objects that store “both ends of a link”, i.e.

class Node
  attr :parent, :children
  def initialize(parent, children=[])
    self.parent = parent
    self.children = children.each { |c| c.parent = self }

Well, anyways, here is the code.

What is this good for?

Again you can do a number of different things, some even remotely interesting :) Say you want to determine the ‘mtime’ (in Unix lingo this is the time of the last modification) of an object, and say you have mtime_base methods on all supporting classes, that return the base modification time for that object only:

class Object
  def mtime_base; nil; end # dummy implementation for nonsupporting objects

class ActiveRecord::Base
  def mtime_base; self.updated_at rescue nil; end

then this could be your code

class Object
  def mtime
    epoch = Time.at(0)
    m = epoch
    walk { |obj| m = [ obj.mtime_base || epoch, m ].max }
    return m  

Now writing this I realize that walk could behave more inject-y, may be like this:

def Object.walk(val=nil, &block)
  walk_object(Set.new) do |obj| val = yield val, obj; end

Then this last piece of code would simplify to

  def mtime
    epoch = Time.at(0)
    walk(epoch) { |m, obj| [ obj.mtime_base || epoch, m ].max }

And, yes, building a temporary array for each object is bad, performancewise. But this exercise is left to the reader.


One response to “0x0c: These shoes are made for walking

  1. Pingback: 0×0d - 10+1 things I hate about rails « 1rad

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s