Faster Filesystem Finding

While spelunking the filesystem, I created a simple iterator that would print out the items at each level while traversing the depths of the file system. I’ve since added a new generalization of the technique which works out even better for those cases where you don’t just want to print, but you want to perhaps gather and later process.

The key to this new algorithm is that I don’t do recursion. I could not work out how I would both do recursion and create an iterator, so I use a stack. This particular exercise has historical significance for me as it was one of the interview questions I received when I first interviewed at Microsoft oh so many years ago. At the time the question was, ‘show code for traversing the DOM in depth, without using recursion’.

FileSystemItem.itemsRecursive = function(self)
  local stack = Collections.Stack();
  local itemIter = self:items();

  local closure = function()
    while true do
      local anItem = itemIter();
      if anItem then
        if (anItem.Name ~= ".") and (anItem.Name ~= "..") then
          if anItem:isDirectory() then
            stack:push(itemIter);
            itemIter = anItem:items();
          end

          return anItem;
        end
      else
        itemIter = stack:pop();
        if not itemIter then
          return nil;
        end
      end
    end
  end

  return closure;
end

With that little mechanism in place, printing all the files in my system becomes as easy as this:

local printFileItems = function(startat, filterfunc)
  for item in startat:itemsRecursive() do
    if filterfunc then
      if filterfunc(item) then
        print(item:getFullPath());
      end
    else
      print(item:getFullPath());
    end
  end
end

printFileItems(FileSystemItem({Name=arg[1]}));

That’s all fine and good. Of course, these days, ‘data’ is not useful unless it can be consumed as html or JSON, so here’s another view of file system, doing a simple html wrapper.

local printHtml = function(pattern, filterfunc)
	local fs = FileSystemItem({Name=pattern});

io.write[[
<html>
	<head>
		<title>File Directory</title>
	</head>

	<body>
		<ul>
]]
	for item in fs:items() do
		local goone = true;
		if filterfunc then
			if not filterfunc(item) then
				goone = false;
			end
		end
		local url = item:getFullPath();

		if goone then
			io.write([[<li><a href="]]..url..[[">]]..item.Name..[[</a></li>]]);
			io.write('\n');
		end
	end

io.write[[
		</ul>
	</body>
</html>
]]
end

local nodotdot = function(item)
	return item.Name ~= "." and item.Name ~= "..";
end

printHtml("c:\\tools", nodotdot);

I’m dumping what’s in my c:\tools directory, ignoring the case of ‘.’ and ‘..’. That’s a pretty funny mixing of the Lua and html code. Of course the ‘io.write’ could just as easily be replaced with ‘response:write’, and you’d be generating dynamic content directly to the web.

At any rate, having the simple iterative, non-recursive case of file exploration available makes doing file filtering a little bit more interesting, while maintaining a fairly low resource footprint.

Advertisements


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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s