Converted Menus to a Tree structure to allow submenus.

* Bundle the rubytree gem
* Patched RubyTree's TreeNode to add some additional methods.
* Converted the menu rendering to walk the Tree of MenuItems to render
  each item
* Added a menu option for :parent_menu to make this menu a child of the parent
* Added a bunch of tests
* Made MenuItem a subclass of Tree::TreeNode in order to use it's methods
  directly
* Changed the exceptions in MenuItem#new to be ArgumentErrors instead of the
  generic RuntimeError

  #4250

git-svn-id: svn+ssh://rubyforge.org/var/svn/redmine/trunk@3090 e93f8b46-1217-0410-a6f0-8f06a7374b81

20 files changed, 4599 insertions, 38 deletions

diff --git a/config/environment.rb b/config/environment.rb
index e6d42592f..1df06f5a0 100644
--- a/config/environment.rb
+++ b/config/environment.rb
@@ -50,6 +50,8 @@ Rails::Initializer.run do |config|
   # It will automatically turn deliveries on
   config.action_mailer.perform_deliveries = false
 
+  config.gem 'rubytree', :lib => 'tree'
+  
   # Load any local configuration that is kept out of source control
   # (e.g. gems, patches).
   if File.exists?(File.join(File.dirname(__FILE__), 'additional_environment.rb'))
diff --git a/lib/redmine/menu_manager.rb b/lib/redmine/menu_manager.rb
index d6688ffe2..debcdd143 100644
--- a/lib/redmine/menu_manager.rb
+++ b/lib/redmine/menu_manager.rb
@@ -15,6 +15,84 @@
 # along with this program; if not, write to the Free Software
 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 
+require 'tree' # gem install rubytree
+
+# Monkey patch the TreeNode to add on a few more methods :nodoc:
+module TreeNodePatch
+  def self.included(base)
+    base.class_eval do
+      attr_reader :last_items_count
+      
+      alias :old_initilize :initialize
+      def initialize(name, content = nil)
+        old_initilize(name, content)
+        @last_items_count = 0
+        extend(InstanceMethods)
+      end
+    end
+  end
+  
+  module InstanceMethods
+    # Adds the specified child node to the receiver node.  The child node's
+    # parent is set to be the receiver.  The child is added as the first child in
+    # the current list of children for the receiver node.
+    def prepend(child)
+      raise "Child already added" if @childrenHash.has_key?(child.name)
+
+      @childrenHash[child.name]  = child
+      @children = [child] + @children
+      child.parent = self
+      return child
+
+    end
+
+    # Adds the specified child node to the receiver node.  The child node's
+    # parent is set to be the receiver.  The child is added at the position
+    # into the current list of children for the receiver node.
+    def add_at(child, position)
+      raise "Child already added" if @childrenHash.has_key?(child.name)
+
+      @childrenHash[child.name]  = child
+      @children = @children.insert(position, child)
+      child.parent = self
+      return child
+
+    end
+
+    def add_last(child)
+      raise "Child already added" if @childrenHash.has_key?(child.name)
+
+      @childrenHash[child.name]  = child
+      @children <<  child
+      @last_items_count += 1
+      child.parent = self
+      return child
+
+    end
+
+    # Adds the specified child node to the receiver node.  The child node's
+    # parent is set to be the receiver.  The child is added as the last child in
+    # the current list of children for the receiver node.
+    def add(child)
+      raise "Child already added" if @childrenHash.has_key?(child.name)
+
+      @childrenHash[child.name]  = child
+      position = @children.size - @last_items_count
+      @children.insert(position, child)
+      child.parent = self
+      return child
+
+    end
+
+    # Will return the position (zero-based) of the current child in
+    # it's parent
+    def position
+      self.parent.children.index(self)
+    end
+  end
+end
+Tree::TreeNode.send(:include, TreeNodePatch)
+
 module Redmine
   module MenuManager
     module MenuController
@@ -79,35 +157,80 @@ module Redmine
       
       def render_menu(menu, project=nil)
         links = []
-        menu_items_for(menu, project) do |item, caption, url, selected|
-          links << content_tag('li', 
-            link_to(h(caption), url, item.html_options(:selected => selected)))
+        menu_items_for(menu, project) do |node|
+          links << render_menu_node(node, project)
         end
         links.empty? ? nil : content_tag('ul', links.join("\n"))
       end
 
+      def render_menu_node(node, project=nil)
+        caption, url, selected = extract_node_details(node, project)
+        if node.hasChildren?
+          html = []
+          html << '<li>'
+          html << render_single_menu_node(node, caption, url, selected) # parent
+          html << '  <ul>'
+          node.children.each do |child|
+            html << render_menu_node(child, project)
+          end
+          html << '  </ul>'
+          html << '</li>'
+          return html.join("\n")
+        else
+          return content_tag('li',
+                               render_single_menu_node(node, caption, url, selected))
+        end
+      end
+
+      def render_single_menu_node(item, caption, url, selected)
+        link_to(h(caption), url, item.html_options(:selected => selected))
+      end
+      
       def menu_items_for(menu, project=nil)
         items = []
-        Redmine::MenuManager.allowed_items(menu, User.current, project).each do |item|
-          unless item.condition && !item.condition.call(project)
-            url = case item.url
-            when Hash
-              project.nil? ? item.url : {item.param => project}.merge(item.url)
-            when Symbol
-              send(item.url)
-            else
-              item.url
-            end
-            caption = item.caption(project)
+        Redmine::MenuManager.items(menu).root.children.each do |node|
+          if allowed_node?(node, User.current, project)
             if block_given?
-              yield item, caption, url, (current_menu_item == item.name)
+              yield node
             else
-              items << [item, caption, url, (current_menu_item == item.name)]
+              items << node  # TODO: not used?
             end
           end
         end
         return block_given? ? nil : items
       end
+
+      def extract_node_details(node, project=nil)
+        item = node
+        url = case item.url
+        when Hash
+          project.nil? ? item.url : {item.param => project}.merge(item.url)
+        when Symbol
+          send(item.url)
+        else
+          item.url
+        end
+        caption = item.caption(project)
+        return [caption, url, (current_menu_item == item.name)]
+      end
+
+      # Checks if a user is allowed to access the menu item by:
+      #
+      # * Checking the conditions of the item
+      # * Checking the url target (project only)
+      def allowed_node?(node, user, project)
+        if node.condition && !node.condition.call(project)
+          # Condition that doesn't pass
+          return false
+        end
+
+        if project
+          return user && user.allowed_to?(node.url, project)
+        else
+          # outside a project, all menu items allowed
+          return true
+        end
+      end
     end
     
     class << self
@@ -122,17 +245,13 @@ module Redmine
       end
       
       def items(menu_name)
-        @items[menu_name.to_sym] || []
-      end
-      
-      def allowed_items(menu_name, user, project)
-        project ? items(menu_name).select {|item| user && user.allowed_to?(item.url, project)} : items(menu_name)
+        @items[menu_name.to_sym] || Tree::TreeNode.new(:root, {})
       end
     end
     
     class Mapper
       def initialize(menu, items)
-        items[menu] ||= []
+        items[menu] ||= Tree::TreeNode.new(:root, {})
         @menu = menu
         @menu_items = items[menu]
       end
@@ -151,36 +270,78 @@ module Redmine
       # * html_options: a hash of html options that are passed to link_to
       def push(name, url, options={})
         options = options.dup
-        
+
+        if options[:parent_menu]
+          subtree = self.find(options[:parent_menu])
+          if subtree
+            target_root = subtree
+          else
+            target_root = @menu_items.root
+          end
+
+        else
+          target_root = @menu_items.root
+        end
+
         # menu item position
-        if before = options.delete(:before)
-          position = @menu_items.collect(&:name).index(before)
+        if first = options.delete(:first)
+          target_root.prepend(MenuItem.new(name, url, options))
+        elsif before = options.delete(:before)
+
+          if exists?(before)
+            target_root.add_at(MenuItem.new(name, url, options), position_of(before))
+          else
+            target_root.add(MenuItem.new(name, url, options))
+          end
+
         elsif after = options.delete(:after)
-          position = @menu_items.collect(&:name).index(after)
-          position += 1 unless position.nil?
+
+          if exists?(after)
+            target_root.add_at(MenuItem.new(name, url, options), position_of(after) + 1)
+          else
+            target_root.add(MenuItem.new(name, url, options))
+          end
+          
         elsif options.delete(:last)
-          position = @menu_items.size
-          @@last_items_count[@menu] += 1
+          target_root.add_last(MenuItem.new(name, url, options))
+        else
+          target_root.add(MenuItem.new(name, url, options))
         end
-        # default position
-        position ||= @menu_items.size - @@last_items_count[@menu]
-        
-        @menu_items.insert(position, MenuItem.new(name, url, options))
       end
       
       # Removes a menu item
       def delete(name)
-        @menu_items.delete_if {|i| i.name == name}
+        if found = self.find(name)
+          @menu_items.remove!(found)
+        end
+      end
+
+      # Checks if a menu item exists
+      def exists?(name)
+        @menu_items.any? {|node| node.name == name}
+      end
+
+      def find(name)
+        @menu_items.find {|node| node.name == name}
+      end
+
+      def position_of(name)
+        @menu_items.each do |node|
+          if node.name == name
+            return node.position
+          end
+        end
       end
     end
     
-    class MenuItem
+    class MenuItem < Tree::TreeNode
       include Redmine::I18n
-      attr_reader :name, :url, :param, :condition
+      attr_reader :name, :url, :param, :condition, :parent_menu
       
       def initialize(name, url, options)
-        raise "Invalid option :if for menu item '#{name}'" if options[:if] && !options[:if].respond_to?(:call)
-        raise "Invalid option :html for menu item '#{name}'" if options[:html] && !options[:html].is_a?(Hash)
+        raise ArgumentError, "Invalid option :if for menu item '#{name}'" if options[:if] && !options[:if].respond_to?(:call)
+        raise ArgumentError, "Invalid option :html for menu item '#{name}'" if options[:html] && !options[:html].is_a?(Hash)
+        raise ArgumentError, "Cannot set the :parent_menu to be the same as this item" if options[:parent_menu] == name.to_sym
         @name = name
         @url = url
         @condition = options[:if]
@@ -189,6 +350,8 @@ module Redmine
         @html_options = options[:html] || {}
         # Adds a unique class to each menu item based on its name
         @html_options[:class] = [@html_options[:class], @name.to_s.dasherize].compact.join(' ')
+        @parent_menu = options[:parent_menu]
+        super @name.to_sym
       end
       
       def caption(project=nil)
diff --git a/test/unit/lib/redmine/menu_manager/mapper_test.rb b/test/unit/lib/redmine/menu_manager/mapper_test.rb
new file mode 100644
index 000000000..304ece697
--- /dev/null
+++ b/test/unit/lib/redmine/menu_manager/mapper_test.rb
@@ -0,0 +1,166 @@
+# Redmine - project management software
+# Copyright (C) 2006-2009  Jean-Philippe Lang
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+# 
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+
+require File.dirname(__FILE__) + '/../../../../test_helper'
+
+class Redmine::MenuManager::MapperTest < Test::Unit::TestCase
+  context "Mapper#initialize" do
+    should "be tested"
+  end
+
+  def test_push_onto_root
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    menu_mapper.push :test_overview, { :controller => 'projects', :action => 'show'}, {}
+
+    menu_mapper.exists?(:test_overview)
+  end
+
+  def test_push_onto_parent
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    menu_mapper.push :test_overview, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_child, { :controller => 'projects', :action => 'show'}, {:parent_menu => :test_overview}
+
+    assert menu_mapper.exists?(:test_child)
+    assert_equal :test_child, menu_mapper.find(:test_child).name
+  end
+
+  def test_push_onto_grandparent
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    menu_mapper.push :test_overview, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_child, { :controller => 'projects', :action => 'show'}, {:parent_menu => :test_overview}
+    menu_mapper.push :test_grandchild, { :controller => 'projects', :action => 'show'}, {:parent_menu => :test_child}
+
+    assert menu_mapper.exists?(:test_grandchild)
+    grandchild = menu_mapper.find(:test_grandchild)
+    assert_equal :test_grandchild, grandchild.name
+    assert_equal :test_child, grandchild.parent_menu
+  end
+
+  def test_push_first
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    menu_mapper.push :test_second, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_third, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_fourth, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_fifth, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_first, { :controller => 'projects', :action => 'show'}, {:first => true}
+
+    root = menu_mapper.find(:root)
+    assert_equal 5, root.children.size
+    {0 => :test_first, 1 => :test_second, 2 => :test_third, 3 => :test_fourth, 4 => :test_fifth}.each do |position, name|
+      assert_not_nil root.children[position]
+      assert_equal name, root.children[position].name
+    end
+  
+  end
+  
+  def test_push_before
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    menu_mapper.push :test_first, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_second, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_fourth, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_fifth, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_third, { :controller => 'projects', :action => 'show'}, {:before => :test_fourth}
+
+    root = menu_mapper.find(:root)
+    assert_equal 5, root.children.size
+    {0 => :test_first, 1 => :test_second, 2 => :test_third, 3 => :test_fourth, 4 => :test_fifth}.each do |position, name|
+      assert_not_nil root.children[position]
+      assert_equal name, root.children[position].name
+    end
+  
+  end
+
+  def test_push_after
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    menu_mapper.push :test_first, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_second, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_third, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_fifth, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_fourth, { :controller => 'projects', :action => 'show'}, {:after => :test_third}
+
+    
+    root = menu_mapper.find(:root)
+    assert_equal 5, root.children.size
+    {0 => :test_first, 1 => :test_second, 2 => :test_third, 3 => :test_fourth, 4 => :test_fifth}.each do |position, name|
+      assert_not_nil root.children[position]
+      assert_equal name, root.children[position].name
+    end
+  
+  end
+
+  def test_push_last
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    menu_mapper.push :test_first, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_second, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_third, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_fifth, { :controller => 'projects', :action => 'show'}, {:last => true}
+    menu_mapper.push :test_fourth, { :controller => 'projects', :action => 'show'}, {}
+
+    root = menu_mapper.find(:root)
+    assert_equal 5, root.children.size
+    {0 => :test_first, 1 => :test_second, 2 => :test_third, 3 => :test_fourth, 4 => :test_fifth}.each do |position, name|
+      assert_not_nil root.children[position]
+      assert_equal name, root.children[position].name
+    end
+  
+  end
+  
+  def test_exists_for_child_node
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    menu_mapper.push :test_overview, { :controller => 'projects', :action => 'show'}, {}
+    menu_mapper.push :test_child, { :controller => 'projects', :action => 'show'}, {:parent_menu => :test_overview }
+
+    assert menu_mapper.exists?(:test_child)
+  end
+
+  def test_exists_for_invalid_node
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    menu_mapper.push :test_overview, { :controller => 'projects', :action => 'show'}, {}
+
+    assert !menu_mapper.exists?(:nothing)
+  end
+
+  def test_find
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    menu_mapper.push :test_overview, { :controller => 'projects', :action => 'show'}, {}
+
+    item = menu_mapper.find(:test_overview)
+    assert_equal :test_overview, item.name
+    assert_equal({:controller => 'projects', :action => 'show'}, item.url)
+  end
+
+  def test_find_missing
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    menu_mapper.push :test_overview, { :controller => 'projects', :action => 'show'}, {}
+
+    item = menu_mapper.find(:nothing)
+    assert_equal nil, item
+  end
+
+  def test_delete
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    menu_mapper.push :test_overview, { :controller => 'projects', :action => 'show'}, {}
+    assert_not_nil menu_mapper.delete(:test_overview)
+
+    assert_nil menu_mapper.find(:test_overview)
+  end
+
+  def test_delete_missing
+    menu_mapper = Redmine::MenuManager::Mapper.new(:test_menu, {})
+    assert_nil menu_mapper.delete(:test_missing)
+  end
+end
diff --git a/test/unit/lib/redmine/menu_manager/menu_helper_test.rb b/test/unit/lib/redmine/menu_manager/menu_helper_test.rb
new file mode 100644
index 000000000..6f259f425
--- /dev/null
+++ b/test/unit/lib/redmine/menu_manager/menu_helper_test.rb
@@ -0,0 +1,161 @@
+# Redmine - project management software
+# Copyright (C) 2006-2009  Jean-Philippe Lang
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+# 
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+
+require File.dirname(__FILE__) + '/../../../../test_helper'
+
+
+
+class Redmine::MenuManager::MenuHelperTest < HelperTestCase
+  include Redmine::MenuManager::MenuHelper
+  include ActionController::Assertions::SelectorAssertions
+  fixtures :users, :members, :projects, :enabled_modules
+
+  # Used by assert_select
+  def html_document
+    HTML::Document.new(@response.body)
+  end
+  
+  def setup
+    super
+    @response = ActionController::TestResponse.new
+    # Stub the current menu item in the controller
+    def @controller.current_menu_item
+      :index
+    end
+  end
+  
+
+  context "MenuManager#current_menu_item" do
+    should "be tested"
+  end
+
+  context "MenuManager#render_main_menu" do
+    should "be tested"
+  end
+
+  context "MenuManager#render_menu" do
+    should "be tested"
+  end
+
+  context "MenuManager#menu_item_and_children" do
+    should "be tested"
+  end
+
+  context "MenuManager#extract_node_details" do
+    should "be tested"
+  end
+
+  def test_render_single_menu_node
+    node = Redmine::MenuManager::MenuItem.new(:testing, '/test', { })
+    @response.body = render_single_menu_node(node, 'This is a test', node.url, false)
+
+    assert_select("a.testing", "This is a test")
+  end
+
+  def test_render_menu_node
+    single_node = Redmine::MenuManager::MenuItem.new(:single_node, '/test', { })
+    @response.body = render_menu_node(single_node, nil)
+
+    assert_select("li") do
+      assert_select("a.single-node", "Single node")
+    end
+  end
+  
+  def test_render_menu_node_with_nested_items
+    parent_node = Redmine::MenuManager::MenuItem.new(:parent_node, '/test', { })
+    parent_node << Redmine::MenuManager::MenuItem.new(:child_one_node, '/test', { })
+    parent_node << Redmine::MenuManager::MenuItem.new(:child_two_node, '/test', { })
+    parent_node <<
+      Redmine::MenuManager::MenuItem.new(:child_three_node, '/test', { }) <<
+      Redmine::MenuManager::MenuItem.new(:child_three_inner_node, '/test', { })
+
+    @response.body = render_menu_node(parent_node, nil)
+
+    assert_select("li") do
+      assert_select("a.parent-node", "Parent node")
+      assert_select("ul") do
+        assert_select("li a.child-one-node", "Child one node")
+        assert_select("li a.child-two-node", "Child two node")
+        assert_select("li") do
+          assert_select("a.child-three-node", "Child three node")
+          assert_select("ul") do
+            assert_select("li a.child-three-inner-node", "Child three inner node")
+          end
+        end
+      end
+    end
+    
+  end
+
+  def test_menu_items_for_should_yield_all_items_if_passed_a_block
+    menu_name = :test_menu_items_for_should_yield_all_items_if_passed_a_block
+    Redmine::MenuManager.map menu_name do |menu|
+      menu.push(:a_menu, '/', { })
+      menu.push(:a_menu_2, '/', { })
+      menu.push(:a_menu_3, '/', { })
+    end
+
+    items_yielded = []
+    menu_items_for(menu_name) do |item|
+      items_yielded << item
+    end
+    
+    assert_equal 3, items_yielded.size
+  end
+
+  def test_menu_items_for_should_return_all_items
+    menu_name = :test_menu_items_for_should_return_all_items
+    Redmine::MenuManager.map menu_name do |menu|
+      menu.push(:a_menu, '/', { })
+      menu.push(:a_menu_2, '/', { })
+      menu.push(:a_menu_3, '/', { })
+    end
+
+    items = menu_items_for(menu_name)
+    assert_equal 3, items.size
+  end
+
+  def test_menu_items_for_should_skip_unallowed_items_on_a_project
+    menu_name = :test_menu_items_for_should_skip_unallowed_items_on_a_project
+    Redmine::MenuManager.map menu_name do |menu|
+      menu.push(:a_menu, {:controller => 'issues', :action => 'index' }, { })
+      menu.push(:a_menu_2, {:controller => 'issues', :action => 'index' }, { })
+      menu.push(:unallowed, {:controller => 'issues', :action => 'unallowed' }, { })
+    end
+
+    User.current = User.find(2)
+    
+    items = menu_items_for(menu_name, Project.find(1))
+    assert_equal 2, items.size
+  end
+  
+  def test_menu_items_for_should_skip_items_that_fail_the_conditions
+    menu_name = :test_menu_items_for_should_skip_items_that_fail_the_conditions
+    Redmine::MenuManager.map menu_name do |menu|
+      menu.push(:a_menu, {:controller => 'issues', :action => 'index' }, { })
+      menu.push(:unallowed,
+                {:controller => 'issues', :action => 'index' },
+                { :if => Proc.new { false }})
+    end
+
+    User.current = User.find(2)
+    
+    items = menu_items_for(menu_name, Project.find(1))
+    assert_equal 1, items.size
+  end
+
+end
diff --git a/test/unit/lib/redmine/menu_manager/menu_item_test.rb b/test/unit/lib/redmine/menu_manager/menu_item_test.rb
new file mode 100644
index 000000000..ee302fc00
--- /dev/null
+++ b/test/unit/lib/redmine/menu_manager/menu_item_test.rb
@@ -0,0 +1,108 @@
+# Redmine - project management software
+# Copyright (C) 2006-2009  Jean-Philippe Lang
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+# 
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+
+require File.dirname(__FILE__) + '/../../../../test_helper'
+
+module RedmineMenuTestHelper
+  # Helpers
+  def get_menu_item(menu_name, item_name)
+    Redmine::MenuManager.items(menu_name).find {|item| item.name == item_name.to_sym}
+  end
+end
+
+class Redmine::MenuManager::MenuItemTest < Test::Unit::TestCase
+  include RedmineMenuTestHelper
+
+  Redmine::MenuManager.map :test_menu do |menu|
+    menu.push(:parent_menu, '/test', { })
+    menu.push(:child_menu, '/test', { :parent_menu => :parent_menu})
+    menu.push(:child2_menu, '/test', { :parent_menu => :parent_menu})
+  end
+  
+  context "MenuItem#caption" do
+    should "be tested"
+  end
+
+  context "MenuItem#html_options" do
+    should "be tested"
+  end
+
+  # context new menu item
+  def test_new_menu_item_should_require_a_name
+    assert_raises ArgumentError do
+      Redmine::MenuManager::MenuItem.new
+    end
+  end
+
+  def test_new_menu_item_should_require_an_url
+    assert_raises ArgumentError do
+      Redmine::MenuManager::MenuItem.new(:test_missing_url)
+    end
+  end
+
+  def test_new_menu_item_should_require_the_options
+    assert_raises ArgumentError do
+      Redmine::MenuManager::MenuItem.new(:test_missing_options, '/test')
+    end
+  end
+
+  def test_new_menu_item_with_all_required_parameters
+    assert Redmine::MenuManager::MenuItem.new(:test_good_menu, '/test', {})
+  end
+
+  def test_new_menu_item_should_require_a_proc_to_use_for_the_if_condition
+    assert_raises ArgumentError do
+      Redmine::MenuManager::MenuItem.new(:test_error, '/test',
+                                         {
+                                           :if => ['not_a_proc']
+                                         })
+    end
+
+    assert Redmine::MenuManager::MenuItem.new(:test_good_if, '/test',
+                                              {
+                                                :if => Proc.new{}
+                                              })
+  end
+
+  def test_new_menu_item_should_allow_a_hash_for_extra_html_options
+    assert_raises ArgumentError do
+      Redmine::MenuManager::MenuItem.new(:test_error, '/test',
+                                         {
+                                           :html => ['not_a_hash']
+                                         })
+    end
+
+    assert Redmine::MenuManager::MenuItem.new(:test_good_html, '/test',
+                                              {
+                                                :html => { :onclick => 'doSomething'}
+                                              })
+  end
+
+  def test_new_should_not_allow_setting_the_parent_menu_item_to_the_current_item
+    assert_raises ArgumentError do
+      Redmine::MenuManager::MenuItem.new(:test_error, '/test', { :parent_menu => :test_error })
+    end
+  end
+
+  def test_has_children
+    parent_item = get_menu_item(:test_menu, :parent_menu)
+    assert parent_item.hasChildren?
+    assert_equal 2, parent_item.children.size
+    assert_equal get_menu_item(:test_menu, :child_menu), parent_item.children[0]
+    assert_equal get_menu_item(:test_menu, :child2_menu), parent_item.children[1]
+  end
+end
diff --git a/test/unit/lib/redmine/menu_manager_test.rb b/test/unit/lib/redmine/menu_manager_test.rb
new file mode 100644
index 000000000..8c6ecda92
--- /dev/null
+++ b/test/unit/lib/redmine/menu_manager_test.rb
@@ -0,0 +1,28 @@
+# Redmine - project management software
+# Copyright (C) 2006-2009  Jean-Philippe Lang
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+# 
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+
+require File.dirname(__FILE__) + '/../../../test_helper'
+
+class Redmine::MenuManagerTest < Test::Unit::TestCase
+  context "MenuManager#map" do
+    should "be tested"
+  end
+
+  context "MenuManager#items" do
+    should "be tested"
+  end
+end
diff --git a/test/unit/lib/redmine_test.rb b/test/unit/lib/redmine_test.rb
new file mode 100644
index 000000000..5150da1f2
--- /dev/null
+++ b/test/unit/lib/redmine_test.rb
@@ -0,0 +1,84 @@
+# Redmine - project management software
+# Copyright (C) 2006-2009  Jean-Philippe Lang
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+# 
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+
+require File.dirname(__FILE__) + '/../../test_helper'
+
+module RedmineMenuTestHelper
+  # Assertions
+  def assert_number_of_items_in_menu(menu_name, count)
+    assert Redmine::MenuManager.items(menu_name).size >= count, "Menu has less than #{count} items"
+  end
+
+  def assert_menu_contains_item_named(menu_name, item_name)
+    assert Redmine::MenuManager.items(menu_name).collect(&:name).include?(item_name.to_sym), "Menu did not have an item named #{item_name}"
+  end
+
+  # Helpers
+  def get_menu_item(menu_name, item_name)
+    Redmine::MenuManager.items(menu_name).find {|item| item.name == item_name.to_sym}
+  end
+end
+
+class RedmineTest < Test::Unit::TestCase
+  include RedmineMenuTestHelper
+
+  def test_top_menu
+    assert_number_of_items_in_menu :top_menu, 5
+    assert_menu_contains_item_named :top_menu, :home
+    assert_menu_contains_item_named :top_menu, :my_page
+    assert_menu_contains_item_named :top_menu, :projects
+    assert_menu_contains_item_named :top_menu, :administration
+    assert_menu_contains_item_named :top_menu, :help
+  end
+
+  def test_account_menu
+    assert_number_of_items_in_menu :account_menu, 4
+    assert_menu_contains_item_named :account_menu, :login
+    assert_menu_contains_item_named :account_menu, :register
+    assert_menu_contains_item_named :account_menu, :my_account
+    assert_menu_contains_item_named :account_menu, :logout
+  end
+
+  def test_application_menu
+    assert_number_of_items_in_menu :application_menu, 0
+  end
+
+  def test_admin_menu
+    assert_number_of_items_in_menu :admin_menu, 0
+  end
+
+  def test_project_menu
+    assert_number_of_items_in_menu :project_menu, 12
+    assert_menu_contains_item_named :project_menu, :overview
+    assert_menu_contains_item_named :project_menu, :activity
+    assert_menu_contains_item_named :project_menu, :roadmap
+    assert_menu_contains_item_named :project_menu, :issues
+    assert_menu_contains_item_named :project_menu, :new_issue
+    assert_menu_contains_item_named :project_menu, :news
+    assert_menu_contains_item_named :project_menu, :documents
+    assert_menu_contains_item_named :project_menu, :wiki
+    assert_menu_contains_item_named :project_menu, :boards
+    assert_menu_contains_item_named :project_menu, :files
+    assert_menu_contains_item_named :project_menu, :repository
+    assert_menu_contains_item_named :project_menu, :settings
+  end
+
+  def test_new_issue_should_have_root_as_a_parent
+    new_issue = get_menu_item(:project_menu, :new_issue)
+    assert_equal :root, new_issue.parent.name
+  end
+end
diff --git a/vendor/gems/rubytree-0.5.2/.specification b/vendor/gems/rubytree-0.5.2/.specification
new file mode 100644
index 000000000..2f5d9807f
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/.specification
@@ -0,0 +1,80 @@
+--- !ruby/object:Gem::Specification 
+name: rubytree
+version: !ruby/object:Gem::Version 
+  version: 0.5.2
+platform: ruby
+authors: 
+- Anupam Sengupta
+autorequire: tree
+bindir: bin
+cert_chain: []
+
+date: 2007-12-20 00:00:00 -08:00
+default_executable: 
+dependencies: 
+- !ruby/object:Gem::Dependency 
+  name: hoe
+  type: :runtime
+  version_requirement: 
+  version_requirements: !ruby/object:Gem::Requirement 
+    requirements: 
+    - - ">="
+      - !ruby/object:Gem::Version 
+        version: 1.3.0
+    version: 
+description: "Provides a generic tree data-structure with ability to store keyed node-elements in the tree. The implementation mixes in the Enumerable module.  Website:  http://rubytree.rubyforge.org/"
+email: anupamsg@gmail.com
+executables: []
+
+extensions: []
+
+extra_rdoc_files: 
+- README
+- COPYING
+- ChangeLog
+- History.txt
+files: 
+- COPYING
+- ChangeLog
+- History.txt
+- Manifest.txt
+- README
+- Rakefile
+- TODO
+- lib/tree.rb
+- lib/tree/binarytree.rb
+- setup.rb
+- test/test_binarytree.rb
+- test/test_tree.rb
+has_rdoc: true
+homepage: http://rubytree.rubyforge.org/
+licenses: []
+
+post_install_message: 
+rdoc_options: 
+- --main
+- README
+require_paths: 
+- lib
+required_ruby_version: !ruby/object:Gem::Requirement 
+  requirements: 
+  - - ">="
+    - !ruby/object:Gem::Version 
+      version: "0"
+  version: 
+required_rubygems_version: !ruby/object:Gem::Requirement 
+  requirements: 
+  - - ">="
+    - !ruby/object:Gem::Version 
+      version: "0"
+  version: 
+requirements: []
+
+rubyforge_project: rubytree
+rubygems_version: 1.3.5
+signing_key: 
+specification_version: 2
+summary: Ruby implementation of the Tree data structure.
+test_files: 
+- test/test_binarytree.rb
+- test/test_tree.rb
diff --git a/vendor/gems/rubytree-0.5.2/COPYING b/vendor/gems/rubytree-0.5.2/COPYING
new file mode 100644
index 000000000..09e7768f1
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/COPYING
@@ -0,0 +1,31 @@
+RUBYTREE - http://rubytree.rubyforge.org
+========================================
+
+Copyright (c) 2006, 2007 Anupam Sengupta
+
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without modification,
+are permitted provided that the following conditions are met:
+
+- Redistributions of source code must retain the above copyright notice, this
+  list of conditions and the following disclaimer.
+
+- Redistributions in binary form must reproduce the above copyright notice, this
+  list of conditions and the following disclaimer in the documentation and/or
+  other materials provided with the distribution.
+
+- Neither the name of the organization nor the names of its contributors may
+  be used to endorse or promote products derived from this software without
+  specific prior written permission.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/vendor/gems/rubytree-0.5.2/ChangeLog b/vendor/gems/rubytree-0.5.2/ChangeLog
new file mode 100644
index 000000000..bea9d7861
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/ChangeLog
@@ -0,0 +1,163 @@
+2007-12-21  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* Rakefile: Added the rcov option to exclude rcov itself from
+	coverage reports.
+
+	* lib/tree.rb: Minor comment changes.
+
+	* test/test_tree.rb: Added the TestTree enclosing module, and
+	renamed tests to meet ZenTest requirements. Also added a few
+	missing test cases.
+
+	* test/test_binarytree.rb: Added the TestTree enclosing Module,
+	and renamed the tests to meet ZenTest requirements.
+
+2007-12-19  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* README (Module): Modified the install instructions from source.
+
+	* lib/tree.rb (Tree::TreeNode::initialize): Removed the
+	unnecessary self_initialize method.
+	(Tree::TreeNode): Removed the spurious self_initialize from the
+	protected list.
+	(Module): Updated the minor version number.
+
+	* Rakefile: Fixed a problem with reading the Tree::VERSION for the
+	gem packaging, if any prior version of the gem is already installed.
+
+2007-12-18  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* lib/tree.rb: Updated the marshalling logic to correctly handle
+	non-string content.
+	(Tree::TreeNode::createDumpRep): Minor code change to use symbols
+	instead of string key names.
+	(Tree): Version number change to 0.5.0
+	(Tree::TreeNode::hasContent): Minor fix to the comments.
+
+	* test/test_tree.rb (TC_TreeTest::test_breadth_each): Updated test
+	cases for the marshalling logic.
+
+2007-11-12  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* test/test_binarytree.rb: Minor documentation correction.
+
+	* lib/tree/binarytree.rb (Tree::BinaryTreeNode::isRightChild):
+	Minor documentation change.
+
+2007-10-10  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* README: Restructured the format.
+
+	* Rakefile: Added Hoe related logic. If not present, the Rakefile
+	will default to old behavior.
+
+2007-10-09  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* Rakefile: Added setup.rb related tasks. Also added the setup.rb in the PKG_FILES list.
+
+2007-10-01  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* Rakefile: Added an optional task for rcov code coverage.
+	  Added a dependency for rake in the Gem Specification.
+
+	* test/test_binarytree.rb: Removed the unnecessary dependency on "Person" class.
+
+	* test/test_tree.rb: Removed dependency on the redundant "Person" class.
+	(TC_TreeTest::test_comparator): Added a new test for the spaceship operator.
+	(TC_TreeTest::test_hasContent): Added tests for hasContent? and length methods.
+
+2007-08-30  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* test/test_tree.rb (TC_TreeTest::test_preordered_each, TC_TreeTest::test_breadth_each, TC_TreeTest::test_detached_copy):
+	Added new tests for the new functions added to tree.rb.
+
+	* lib/tree.rb (Tree::TreeNode::detached_copy, Tree::TreeNode::preordered_each, Tree::TreeNode::breadth_each):
+	Added new functions for returning a detached copy of the node and
+	for performing breadth first traversal. Also added the pre-ordered
+	traversal function which is an alias of the existing 'each' method.
+
+	* test/test_binarytree.rb (TC_BinaryTreeTest::test_swap_children):
+	Added a test case for the children swap function.
+
+	* lib/tree/binarytree.rb (Tree::BinaryTreeNode::swap_children):
+	Added new function to swap the children. Other minor changes in
+	comments and code.
+
+2007-07-18  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* lib/tree/binarytree.rb (Tree::BinaryTreeNode::leftChild /
+	rightChild): Minor cosmetic change on the parameter name.
+
+	* test/testbinarytree.rb (TC_BinaryTreeTest::test_isLeftChild):
+	Minor syntax correction.
+
+	* lib/tree.rb (Tree::TreeNode::depth): Added a tree depth
+	computation method.
+	(Tree::TreeNode::breadth): Added a tree breadth method.
+
+	* test/testtree.rb (TC_TreeTest::test_depth/test_breadth): Added a
+	test for the depth and breadth method.
+
+	* lib/tree/binarytree.rb (Tree::BinaryTreeNode::is*Child):
+	Added tests for determining whether a node is a left or right
+	child.
+
+	* test/testbinarytree.rb: Added the test cases for the binary tree
+	implementation.
+	(TC_BinaryTreeTest::test_is*Child): Added tests for right or left
+	childs.
+
+	* lib/tree/binarytree.rb: Added the binary tree implementation.
+
+2007-07-17  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* lib/tree.rb (Tree::TreeNode::parentage): Renamed 'ancestors'
+	method to 'parentage' to avoid clobbering Module.ancestors
+
+2007-07-16  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* Rakefile: Added an optional rtags task to generate TAGS file for
+	Emacs.
+
+	* lib/tree.rb (Tree::TreeNode): Added navigation methods for
+	siblings and children. Also added some convenience methods.
+
+2007-07-08  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* Rakefile: Added a developer target for generating rdoc for the
+	website.
+
+2007-06-24  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* test/testtree.rb, lib/tree.rb: Added the each_leaf traversal method.
+
+	* README: Replaced all occurrances of LICENSE with COPYING
+	and lowercased all instances of the word 'RubyTree'.
+
+	* Rakefile: Replaced all occurrances of LICENSE with COPYING
+
+2007-06-23  Anupam Sengupta  <anupamsg@gmail.com>
+
+	* lib/tree.rb (Tree::TreeNode::isLeaf): Added a isLeaf? method.
+
+	* test/testtree.rb (TC_TreeTest::test_removeFromParent): Added
+	test for isLeaf? method
+
+	* Rakefile: Added the LICENSE and ChangeLog to the extra RDoc files.
+
+	* lib/tree.rb: Minor updates to the comments.
+
+	* test/testtree.rb: Added the Copyright and License header.
+
+	* test/person.rb: Added the Copyright and License header.
+
+	* lib/tree.rb: Added the Copyright and License header.
+
+	* Rakefile: Added the LICENSE and Changelog to be part of the RDoc task.
+
+	* README: Added documentation in the README, including install
+	instructions and an example.
+
+	* LICENSE: Added the BSD LICENSE file.
+
+	* Changelog: Added the Changelog file.
diff --git a/vendor/gems/rubytree-0.5.2/History.txt b/vendor/gems/rubytree-0.5.2/History.txt
new file mode 100644
index 000000000..c43831c94
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/History.txt
@@ -0,0 +1,20 @@
+= 0.5.2 / 2007-12-21
+
+* Added more test cases and enabled ZenTest compatibility for the test case
+  names.
+
+= 0.5.1 / 2007-12-20
+
+* Minor code refactoring.
+
+= 0.5.0 / 2007-12-18
+
+* Fixed the marshalling code to correctly handle non-string content.
+
+= 0.4.3 / 2007-10-09
+
+* Changes to the build mechanism (now uses Hoe).
+
+= 0.4.2 / 2007-10-01
+
+* Minor code refactoring. Changes in the Rakefile.
diff --git a/vendor/gems/rubytree-0.5.2/Manifest.txt b/vendor/gems/rubytree-0.5.2/Manifest.txt
new file mode 100644
index 000000000..171ec7cc0
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/Manifest.txt
@@ -0,0 +1,12 @@
+COPYING
+ChangeLog
+History.txt
+Manifest.txt
+README
+Rakefile
+TODO
+lib/tree.rb
+lib/tree/binarytree.rb
+setup.rb
+test/test_binarytree.rb
+test/test_tree.rb
diff --git a/vendor/gems/rubytree-0.5.2/README b/vendor/gems/rubytree-0.5.2/README
new file mode 100644
index 000000000..db690c95c
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/README
@@ -0,0 +1,147 @@
+

+   __       _           _

+   /__\_   _| |__  _   _| |_ _ __ ___  ___

+  / \// | | | '_ \| | | | __| '__/ _ \/ _ \

+ / _  \ |_| | |_) | |_| | |_| | |  __/  __/

+ \/ \_/\__,_|_.__/ \__, |\__|_|  \___|\___|

+                  |___/

+

+  (c) 2006, 2007 Anupam Sengupta

+  http://rubytree.rubyforge.org

+

+Rubytree is a simple implementation of the generic Tree data structure.  This

+implementation is node-centric, where the individual nodes on the tree are the

+primary objects and drive the structure.

+

+== INSTALL:

+

+Rubytree is an open source project and is hosted at:

+

+   http://rubytree.rubyforge.org

+

+Rubytree can be downloaded as a Rubygem or as a tar/zip file from:

+

+   http://rubyforge.org/frs/?group_id=1215&release_id=8817

+

+The file-name is one of:

+

+    rubytree-<VERSION>.gem - The Rubygem

+    rubytree-<VERSION>.tgz - GZipped source files

+    rubytree-<VERSION>.zip - Zipped  source files

+

+Download the appropriate file-type for your system.

+

+It is recommended to install Rubytree as a Ruby Gem, as this is an easy way to

+keep the version updated, and keep multiple versions of the library available on

+your system.

+

+=== Installing the Gem

+

+To Install the Gem, from a Terminal/CLI command prompt, issue the command:

+

+   gem install rubytree

+

+This should install the gem file for Rubytree. Note that you may need to be a

+super-user (root) to successfully install the gem.

+

+=== Installing from the tgz/zip file

+

+Extract the archive file (tgz or zip) and run the following command from the

+top-level source directory:

+

+    ruby ./setup.rb

+

+You may need administrator/super-user privileges to complete the setup using

+this method.

+

+== DOCUMENTATION:

+

+The primary class for this implementation is Tree::TreeNode. See the

+class documentation for an usage example.

+

+From a command line/terminal prompt, you can issue the following command to view

+the text mode ri documentation:

+

+    ri Tree::TreeNode

+

+Documentation on the web is available at:

+

+http://rubytree.rubyforge.org/rdoc

+

+== EXAMPLE:

+

+The following code-snippet implements this tree structure:

+

+                 +------------+

+                 |    ROOT    |

+                 +-----+------+

+         +-------------+------------+

+         |                          |

+ +-------+-------+          +-------+-------+

+ |  CHILD 1      |          |  CHILD 2      |

+ +-------+-------+          +---------------+

+         |

+         |

+ +-------+-------+

+ | GRANDCHILD 1  |

+ +---------------+

+

+ require 'tree'

+

+ myTreeRoot = Tree::TreeNode.new("ROOT", "Root Content")

+

+ myTreeRoot << Tree::TreeNode.new("CHILD1", "Child1 Content") << Tree::TreeNode.new("GRANDCHILD1", "GrandChild1 Content")

+

+ myTreeRoot << Tree::TreeNode.new("CHILD2", "Child2 Content")

+

+ myTreeRoot.printTree

+

+ child1 = myTreeRoot["CHILD1"]

+

+ grandChild1 = myTreeRoot["CHILD1"]["GRANDCHILD1"]

+

+ siblingsOfChild1Array = child1.siblings

+

+ immediateChildrenArray = myTreeRoot.children

+

+ # Process all nodes

+

+ myTreeRoot.each { |node| node.content.reverse }

+

+ myTreeRoot.remove!(child1) # Remove the child

+

+== LICENSE:

+

+Rubytree is licensed under BSD license.

+

+Copyright (c) 2006, 2007 Anupam Sengupta

+

+All rights reserved.

+

+Redistribution and use in source and binary forms, with or without modification,

+are permitted provided that the following conditions are met:

+

+- Redistributions of source code must retain the above copyright notice, this

+  list of conditions and the following disclaimer.

+

+- Redistributions in binary form must reproduce the above copyright notice, this

+  list of conditions and the following disclaimer in the documentation and/or

+  other materials provided with the distribution.

+

+- Neither the name of the organization nor the names of its contributors may

+  be used to endorse or promote products derived from this software without

+  specific prior written permission.

+

+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE

+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR

+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES

+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON

+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS

+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

+

+

+(Document Revision: $Revision: 1.16 $ by $Author: anupamsg $)

diff --git a/vendor/gems/rubytree-0.5.2/Rakefile b/vendor/gems/rubytree-0.5.2/Rakefile
new file mode 100644
index 000000000..814fb026e
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/Rakefile
@@ -0,0 +1,212 @@
+# Rakefile
+#
+# $Revision: 1.27 $ by $Author: anupamsg $
+# $Name:  $
+#
+# Copyright (c) 2006, 2007 Anupam Sengupta
+#
+# All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without modification,
+# are permitted provided that the following conditions are met:
+#
+# - Redistributions of source code must retain the above copyright notice, this
+#   list of conditions and the following disclaimer.
+#
+# - Redistributions in binary form must reproduce the above copyright notice, this
+#   list of conditions and the following disclaimer in the documentation and/or
+#   other materials provided with the distribution.
+#
+# - Neither the name of the organization nor the names of its contributors may
+#   be used to endorse or promote products derived from this software without
+#   specific prior written permission.
+#
+#   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
+# ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+# ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+#
+
+require 'rubygems'
+require 'rake/gempackagetask'
+
+require 'rake/clean'
+require 'rake/packagetask'
+require 'rake/testtask'
+require 'rake/rdoctask'
+
+require 'fileutils'
+
+# General Stuff ####################################################
+
+$:.insert 0, File.expand_path( File.join( File.dirname(__FILE__), 'lib' ) )
+require 'tree'         # To read the version information.
+
+PKG_NAME        = "rubytree"
+PKG_VERSION     = Tree::VERSION
+PKG_FULLNAME    = PKG_NAME + "-" + PKG_VERSION
+PKG_SUMMARY     = "Ruby implementation of the Tree data structure."
+PKG_DESCRIPTION = <<-END
+    Provides a generic tree data-structure with ability to
+    store keyed node-elements in the tree. The implementation
+    mixes in the Enumerable module.
+
+    Website:  http://rubytree.rubyforge.org/
+    END
+
+PKG_FILES = FileList[
+                     '[A-Z]*',
+                     '*.rb',
+                     'lib/**/*.rb',
+                     'test/**/*.rb'
+                    ]
+
+# Default is to create a rubygem.
+desc "Default Task"
+task :default => :gem
+
+begin                           # Try loading hoe
+  require 'hoe'
+  # If Hoe is found, use it to define tasks
+  # =======================================
+  Hoe.new(PKG_NAME, PKG_VERSION) do |p|
+    p.rubyforge_name = PKG_NAME
+    p.author = "Anupam Sengupta"
+    p.email = "anupamsg@gmail.com"
+    p.summary = PKG_SUMMARY
+    p.description = PKG_DESCRIPTION
+    p.url = "http://rubytree.rubyforge.org/"
+    p.changes = p.paragraphs_of('History.txt', 0..1).join("\n\n")
+    p.remote_rdoc_dir = 'rdoc'
+    p.need_tar = true
+    p.need_zip = true
+    p.test_globs = ['test/test_*.rb']
+    p.spec_extras = {
+      :has_rdoc => true,
+      :platform => Gem::Platform::RUBY,
+      :has_rdoc => true,
+      :extra_rdoc_files => ['README', 'COPYING', 'ChangeLog', 'History.txt'],
+      :rdoc_options => ['--main', 'README'],
+      :autorequire => 'tree'
+    }
+  end
+
+rescue LoadError                # If Hoe is not found
+  # If Hoe is not found, then use the usual Gemspec based Rake tasks
+  # ================================================================
+  spec = Gem::Specification.new do |s|
+    s.name = PKG_NAME
+    s.version = PKG_VERSION
+    s.platform = Gem::Platform::RUBY
+    s.author = "Anupam Sengupta"
+    s.email = "anupamsg@gmail.com"
+    s.homepage = "http://rubytree.rubyforge.org/"
+    s.rubyforge_project = 'rubytree'
+    s.summary = PKG_SUMMARY
+    s.add_dependency('rake', '>= 0.7.2')
+    s.description = PKG_DESCRIPTION
+    s.has_rdoc = true
+    s.extra_rdoc_files = ['README', 'COPYING', 'ChangeLog']
+    s.autorequire = "tree"
+    s.files = PKG_FILES.to_a
+    s.test_files = Dir.glob('test/test*.rb')
+  end
+
+  desc "Prepares for installation"
+  task :prepare do
+    ruby "setup.rb config"
+    ruby "setup.rb setup"
+  end
+
+  desc "Installs the package #{PKG_NAME}"
+  task :install => [:prepare] do
+    ruby "setup.rb install"
+  end
+
+  Rake::GemPackageTask.new(spec) do |pkg|
+    pkg.need_zip = true
+    pkg.need_tar = true
+  end
+
+  Rake::TestTask.new do |t|
+    t.libs << "test"
+    t.test_files = FileList['test/test*.rb']
+    t.verbose = true
+  end
+
+end                            # End loading Hoerc
+# ================================================================
+
+
+# The following tasks are loaded independently of Hoe
+
+# Hoe's rdoc task is ugly.
+Rake::RDocTask.new(:docs) do |rd|
+  rd.rdoc_files.include("README", "COPYING", "ChangeLog", "lib/**/*.rb")
+  rd.rdoc_dir = 'doc'
+  rd.title = "#{PKG_FULLNAME} Documentation"
+
+  # Use the template only if it is present, otherwise, the standard template is
+  # used.
+  template = "../allison/allison.rb"
+  rd.template = template if File.file?(template)
+
+  rd.options << '--line-numbers' << '--inline-source'
+end
+
+# Optional TAGS Task.
+# Needs https://rubyforge.org/projects/rtagstask/
+begin
+  require 'rtagstask'
+  RTagsTask.new do |rd|
+    rd.vi = false
+  end
+rescue LoadError
+end
+
+# Optional RCOV Task
+# Needs http://eigenclass.org/hiki/rcov
+begin
+  require 'rcov/rcovtask'
+  Rcov::RcovTask.new do |t|
+    t.test_files = FileList['test/test*.rb']
+    t.rcov_opts << "--exclude 'rcov.rb'" # rcov itself should not be profiled
+    # t.verbose = true     # uncomment to see the executed commands
+  end
+rescue LoadError
+end
+
+#Rakefile,v $
+# Revision 1.21  2007/07/21 05:14:43  anupamsg
+# Added a VERSION constant to the Tree module,
+# and using the same in the Rakefile.
+#
+# Revision 1.20  2007/07/21 03:24:25  anupamsg
+# Minor edits to parameter names. User visible functionality does not change.
+#
+# Revision 1.19  2007/07/19 02:16:01  anupamsg
+# Release 0.4.0 (and minor fix in Rakefile).
+#
+# Revision 1.18  2007/07/18 20:15:06  anupamsg
+# Added two predicate methods in BinaryTreeNode to determine whether a node
+# is a left or a right node.
+#
+# Revision 1.17  2007/07/18 07:17:34  anupamsg
+# Fixed a  issue where TreeNode.ancestors was shadowing Module.ancestors. This method
+# has been renamed to TreeNode.parentage.
+#
+# Revision 1.16  2007/07/17 05:34:03  anupamsg
+# Added an optional tags Rake-task for generating the TAGS file for Emacs.
+#
+# Revision 1.15  2007/07/17 04:42:45  anupamsg
+# Minor fixes to the Rakefile.
+#
+# Revision 1.14  2007/07/17 03:39:28  anupamsg
+# Moved the CVS Log keyword to end of the files.
+#
diff --git a/vendor/gems/rubytree-0.5.2/TODO b/vendor/gems/rubytree-0.5.2/TODO
new file mode 100644
index 000000000..ae4e74c3f
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/TODO
@@ -0,0 +1,7 @@
+# -*- mode: outline; coding: utf-8-unix; -*-
+
+* Add logic in Rakefile to read the file list from Manifest.txt file.
+
+* Add a YAML export method to the TreeNode class.
+
+
diff --git a/vendor/gems/rubytree-0.5.2/lib/tree.rb b/vendor/gems/rubytree-0.5.2/lib/tree.rb
new file mode 100644
index 000000000..9b5062aa7
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/lib/tree.rb
@@ -0,0 +1,539 @@
+# tree.rb
+#
+# $Revision: 1.29 $ by $Author: anupamsg $
+# $Name:  $
+#
+# = tree.rb - Generic Multi-way Tree implementation
+#
+# Provides a generic tree data structure with ability to
+# store keyed node elements in the tree. The implementation
+# mixes in the Enumerable module.
+#
+# Author:: Anupam Sengupta (anupamsg@gmail.com)
+#
+
+# Copyright (c) 2006, 2007 Anupam Sengupta
+#
+# All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without modification,
+# are permitted provided that the following conditions are met:
+#
+# - Redistributions of source code must retain the above copyright notice, this
+#   list of conditions and the following disclaimer.
+#
+# - Redistributions in binary form must reproduce the above copyright notice, this
+#   list of conditions and the following disclaimer in the documentation and/or
+#   other materials provided with the distribution.
+#
+# - Neither the name of the organization nor the names of its contributors may
+#   be used to endorse or promote products derived from this software without
+#   specific prior written permission.
+#
+#   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
+# ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+# ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+#
+
+# This module provides a TreeNode class which is the primary class for all
+# nodes represented in the Tree.
+# This module mixes in the Enumerable module.
+module Tree
+
+  # Rubytree Package Version
+  VERSION = '0.5.2'
+
+  # == TreeNode Class Description
+  #
+  # The node class for the tree representation. the nodes are named and have a
+  # place-holder for the node data (i.e., the `content' of the node). The node
+  # names are expected to be unique.  In addition, the node provides navigation
+  # methods to traverse the tree.
+  #
+  # The nodes can have any number of child nodes attached to it. Note that while
+  # this implementation does not support directed graphs, the class itself makes
+  # no restrictions on associating a node's CONTENT with multiple parent nodes.
+  #
+  #
+  # == Example
+  #
+  #  The following code-snippet implements this tree structure:
+  #
+  #                    +------------+
+  #                    |    ROOT    |
+  #                    +-----+------+
+  #            +-------------+------------+
+  #            |                          |
+  #    +-------+-------+          +-------+-------+
+  #    |  CHILD 1      |          |  CHILD 2      |
+  #    +-------+-------+          +---------------+
+  #            |
+  #            |
+  #    +-------+-------+
+  #    | GRANDCHILD 1  |
+  #    +---------------+
+  #
+  # require 'tree'
+  #
+  # myTreeRoot = Tree::TreeNode.new("ROOT", "Root Content")
+  #
+  # myTreeRoot << Tree::TreeNode.new("CHILD1", "Child1 Content") << Tree::TreeNode.new("GRANDCHILD1", "GrandChild1 Content")
+  #
+  # myTreeRoot << Tree::TreeNode.new("CHILD2", "Child2 Content")
+  #
+  # myTreeRoot.printTree
+  #
+  # child1 = myTreeRoot["CHILD1"]
+  #
+  # grandChild1 = myTreeRoot["CHILD1"]["GRANDCHILD1"]
+  #
+  # siblingsOfChild1Array = child1.siblings
+  #
+  # immediateChildrenArray = myTreeRoot.children
+  #
+  # # Process all nodes
+  #
+  # myTreeRoot.each { |node| node.content.reverse }
+  #
+  # myTreeRoot.remove!(child1) # Remove the child
+  class TreeNode
+    include Enumerable
+
+    attr_reader :content, :name, :parent
+    attr_writer :content
+
+    # Constructor which expects the name of the node
+    #
+    # Name of the node is expected to be unique across the
+    # tree.
+    #
+    # The content can be of any type, and is defaulted to _nil_.
+    def initialize(name, content = nil)
+      raise "Node name HAS to be provided" if name == nil
+      @name = name
+      @content = content
+      self.setAsRoot!
+
+      @childrenHash = Hash.new
+      @children = []
+    end
+
+    # Returns a copy of this node, with the parent and children links removed.
+    def detached_copy
+      Tree::TreeNode.new(@name, @content ? @content.clone : nil)
+    end
+
+    # Print the string representation of this node.
+    def to_s
+      "Node Name: #{@name}" +
+        " Content: " + (@content || "<Empty>") +
+        " Parent: " + (isRoot?()  ? "<None>" : @parent.name) +
+        " Children: #{@children.length}" +
+        " Total Nodes: #{size()}"
+    end
+
+    # Returns an array of ancestors in reversed order (the first element is the
+    # immediate parent). Returns nil if this is a root node.
+    def parentage
+      return nil if isRoot?
+
+      parentageArray = []
+      prevParent = self.parent
+      while (prevParent)
+        parentageArray << prevParent
+        prevParent = prevParent.parent
+      end
+
+      parentageArray
+    end
+
+    # Protected method to set the parent node.
+    # This method should NOT be invoked by client code.
+    def parent=(parent)
+      @parent = parent
+    end
+
+    # Convenience synonym for TreeNode#add method.  This method allows a convenient
+    # method to add children hierarchies in the tree.
+    #
+    # E.g. root << child << grand_child
+    def <<(child)
+      add(child)
+    end
+
+    # Adds the specified child node to the receiver node.  The child node's
+    # parent is set to be the receiver.  The child is added as the last child in
+    # the current list of children for the receiver node.
+    def add(child)
+      raise "Child already added" if @childrenHash.has_key?(child.name)
+
+      @childrenHash[child.name]  = child
+      @children << child
+      child.parent = self
+      return child
+
+    end
+
+    # Removes the specified child node from the receiver node.  The removed
+    # children nodes are orphaned but available if an alternate reference
+    # exists.
+    #
+    # Returns the child node.
+    def remove!(child)
+      @childrenHash.delete(child.name)
+      @children.delete(child)
+      child.setAsRoot! unless child == nil
+      return child
+    end
+
+    # Removes this node from its parent. If this is the root node, then does
+    # nothing.
+    def removeFromParent!
+      @parent.remove!(self) unless isRoot?
+    end
+
+    # Removes all children from the receiver node.
+    def removeAll!
+      for child in @children
+        child.setAsRoot!
+      end
+      @childrenHash.clear
+      @children.clear
+      self
+    end
+
+    # Indicates whether this node has any associated content.
+    def hasContent?
+      @content != nil
+    end
+
+    # Protected method which sets this node as a root node.
+    def setAsRoot!
+      @parent = nil
+    end
+
+    # Indicates whether this node is a root node. Note that
+    # orphaned children will also be reported as root nodes.
+    def isRoot?
+      @parent == nil
+    end
+
+    # Indicates whether this node has any immediate child nodes.
+    def hasChildren?
+      @children.length != 0
+    end
+
+    # Indicates whether this node is a 'leaf' - i.e., one without
+    # any children
+    def isLeaf?
+      !hasChildren?
+    end
+
+    # Returns an array of all the immediate children.  If a block is given,
+    # yields each child node to the block.
+    def children
+      if block_given?
+        @children.each {|child| yield child}
+      else
+        @children
+      end
+    end
+
+    # Returns the first child of this node. Will return nil if no children are
+    # present.
+    def firstChild
+      children.first
+    end
+
+    # Returns the last child of this node. Will return nil if no children are
+    # present.
+    def lastChild
+      children.last
+    end
+
+    # Returns every node (including the receiver node) from the tree to the
+    # specified block. The traversal is depth first and from left to right in
+    # pre-ordered sequence.
+    def each &block
+      yield self
+      children { |child| child.each(&block) }
+    end
+
+    # Traverses the tree in a pre-ordered sequence. This is equivalent to
+    # TreeNode#each
+    def preordered_each &block
+      each(&block)
+    end
+
+    # Performs breadth first traversal of the tree rooted at this node. The
+    # traversal in a given level is from left to right.
+    def breadth_each &block
+      node_queue = [self]       # Create a queue with self as the initial entry
+
+      # Use a queue to do breadth traversal
+      until node_queue.empty?
+        node_to_traverse = node_queue.shift
+        yield node_to_traverse
+        # Enqueue the children from left to right.
+        node_to_traverse.children { |child| node_queue.push child }
+      end
+    end
+
+    # Yields all leaf nodes from this node to the specified block. May yield
+    # this node as well if this is a leaf node.  Leaf traversal depth first and
+    # left to right.
+    def each_leaf &block
+      self.each { |node| yield(node) if node.isLeaf? }
+    end
+
+    # Returns the requested node from the set of immediate children.
+    #
+    # If the parameter is _numeric_, then the in-sequence array of children is
+    # accessed (see Tree#children).  If the parameter is not _numeric_, then it
+    # is assumed to be the *name* of the child node to be returned.
+    def [](name_or_index)
+      raise "Name_or_index needs to be provided" if name_or_index == nil
+
+      if name_or_index.kind_of?(Integer)
+        @children[name_or_index]
+      else
+        @childrenHash[name_or_index]
+      end
+    end
+
+    # Returns the total number of nodes in this tree, rooted at the receiver
+    # node.
+    def size
+      @children.inject(1) {|sum, node| sum + node.size}
+    end
+
+    # Convenience synonym for Tree#size
+    def length
+      size()
+    end
+
+    # Pretty prints the tree starting with the receiver node.
+    def printTree(level = 0)
+
+      if isRoot?
+        print "*"
+      else
+        print "|" unless parent.isLastSibling?
+        print(' ' * (level - 1) * 4)
+        print(isLastSibling? ? "+" : "|")
+        print "---"
+        print(hasChildren? ? "+" : ">")
+      end
+
+      puts " #{name}"
+
+      children { |child| child.printTree(level + 1)}
+    end
+
+    # Returns the root for this tree. Root's root is itself.
+    def root
+      root = self
+      root = root.parent while !root.isRoot?
+      root
+    end
+
+    # Returns the first sibling for this node. If this is the root node, returns
+    # itself.
+    def firstSibling
+      if isRoot?
+        self
+      else
+        parent.children.first
+      end
+    end
+
+    # Returns true if this node is the first sibling.
+    def isFirstSibling?
+      firstSibling == self
+    end
+
+    # Returns the last sibling for this node.  If this node is the root, returns
+    # itself.
+    def lastSibling
+      if isRoot?
+        self
+      else
+        parent.children.last
+      end
+    end
+
+    # Returns true if his node is the last sibling
+    def isLastSibling?
+      lastSibling == self
+    end
+
+    # Returns an array of siblings for this node.
+    # If a block is provided, yields each of the sibling
+    # nodes to the block. The root always has nil siblings.
+    def siblings
+      return nil if isRoot?
+      if block_given?
+        for sibling in parent.children
+          yield sibling if sibling != self
+        end
+      else
+        siblings = []
+        parent.children {|sibling| siblings << sibling if sibling != self}
+        siblings
+      end
+    end
+
+    # Returns true if this node is the only child of its parent
+    def isOnlyChild?
+      parent.children.size == 1
+    end
+
+    # Returns the next sibling for this node. Will return nil if no subsequent
+    # node is present.
+    def nextSibling
+      if myidx = parent.children.index(self)
+        parent.children.at(myidx + 1)
+      end
+    end
+
+    # Returns the previous sibling for this node. Will return nil if no
+    # subsequent node is present.
+    def previousSibling
+      if myidx = parent.children.index(self)
+        parent.children.at(myidx - 1) if myidx > 0
+      end
+    end
+
+    # Provides a comparision operation for the nodes. Comparision
+    # is based on the natural character-set ordering for the
+    # node names.
+    def <=>(other)
+      return +1 if other == nil
+      self.name <=> other.name
+    end
+
+    # Freezes all nodes in the tree
+    def freezeTree!
+      each {|node| node.freeze}
+    end
+
+    # Creates the marshal-dump represention of the tree rooted at this node.
+    def marshal_dump
+      self.collect { |node| node.createDumpRep }
+    end
+
+    # Creates a dump representation and returns the same as a hash.
+    def createDumpRep
+      { :name => @name, :parent => (isRoot? ? nil : @parent.name),  :content => Marshal.dump(@content)}
+    end
+
+    # Loads a marshalled dump of the tree and returns the root node of the
+    # reconstructed tree. See the Marshal class for additional details.
+    def marshal_load(dumped_tree_array)
+      nodes = { }
+      for node_hash in dumped_tree_array do
+        name        = node_hash[:name]
+        parent_name = node_hash[:parent]
+        content     = Marshal.load(node_hash[:content])
+
+        if parent_name then
+          nodes[name] = current_node = Tree::TreeNode.new(name, content)
+          nodes[parent_name].add current_node
+        else
+          # This is the root node, hence initialize self.
+          initialize(name, content)
+
+          nodes[name] = self    # Add self to the list of nodes
+         end
+      end
+    end
+
+    # Returns depth of the tree from this node. A single leaf node has a
+    # depth of 1.
+    def depth
+      return 1 if isLeaf?
+      1 + @children.collect { |child| child.depth }.max
+    end
+
+    # Returns breadth of the tree at this node level. A single node has a
+    # breadth of 1.
+    def breadth
+      return 1 if isRoot?
+      parent.children.size
+    end
+
+    protected :parent=, :setAsRoot!, :createDumpRep
+
+  end
+end
+
+# $Log: tree.rb,v $
+# Revision 1.29  2007/12/22 00:28:59  anupamsg
+# Added more test cases, and enabled ZenTest compatibility.
+#
+# Revision 1.28  2007/12/20 03:19:33  anupamsg
+# * README (Module): Modified the install instructions from source.
+# (Module): Updated the minor version number.
+#
+# Revision 1.27  2007/12/20 03:00:03  anupamsg
+# Minor code changes. Removed self_initialize from the protected methods' list.
+#
+# Revision 1.26  2007/12/20 02:50:04  anupamsg
+# (Tree::TreeNode): Removed the spurious self_initialize from the protected list.
+#
+# Revision 1.25  2007/12/19 20:28:05  anupamsg
+# Removed the unnecesary self_initialize method.
+#
+# Revision 1.24  2007/12/19 06:39:17  anupamsg
+# Removed the unnecessary field and record separator constants.  Also updated the
+# history.txt file.
+#
+# Revision 1.23  2007/12/19 06:25:00  anupamsg
+# (Tree::TreeNode): Minor fix to the comments.  Also fixed the private/protected
+# scope issue with the createDumpRep method.
+#
+# Revision 1.22  2007/12/19 06:22:03  anupamsg
+# Updated the marshalling logic to correctly handle non-string content. This
+# should fix the bug # 15614 ("When dumping with an Object as the content, you get
+# a delimiter collision")
+#
+# Revision 1.21  2007/12/19 02:24:17  anupamsg
+# Updated the marshalling logic to handle non-string contents on the nodes.
+#
+# Revision 1.20  2007/10/10 08:42:57  anupamsg
+# Release 0.4.3
+#
+# Revision 1.19  2007/08/31 01:16:27  anupamsg
+# Added breadth and pre-order traversals for the tree. Also added a method
+# to return the detached copy of a node from the tree.
+#
+# Revision 1.18  2007/07/21 05:14:44  anupamsg
+# Added a VERSION constant to the Tree module,
+# and using the same in the Rakefile.
+#
+# Revision 1.17  2007/07/21 03:24:25  anupamsg
+# Minor edits to parameter names. User visible functionality does not change.
+#
+# Revision 1.16  2007/07/18 23:38:55  anupamsg
+# Minor updates to tree.rb
+#
+# Revision 1.15  2007/07/18 22:11:50  anupamsg
+# Added depth and breadth methods for the TreeNode.
+#
+# Revision 1.14  2007/07/18 19:33:27  anupamsg
+# Added a new binary tree implementation.
+#
+# Revision 1.13  2007/07/18 07:17:34  anupamsg
+# Fixed a  issue where TreeNode.ancestors was shadowing Module.ancestors. This method
+# has been renamed to TreeNode.parentage.
+#
+# Revision 1.12  2007/07/17 03:39:28  anupamsg
+# Moved the CVS Log keyword to end of the files.
+#
diff --git a/vendor/gems/rubytree-0.5.2/lib/tree/binarytree.rb b/vendor/gems/rubytree-0.5.2/lib/tree/binarytree.rb
new file mode 100644
index 000000000..76c363661
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/lib/tree/binarytree.rb
@@ -0,0 +1,131 @@
+# binarytree.rb
+#
+# $Revision: 1.5 $ by $Author: anupamsg $
+# $Name:  $
+#
+# = binarytree.rb - Binary Tree implementation
+#
+# Provides a generic tree data structure with ability to
+# store keyed node elements in the tree. The implementation
+# mixes in the Enumerable module.
+#
+# Author:: Anupam Sengupta (anupamsg@gmail.com)
+#
+
+# Copyright (c) 2007 Anupam Sengupta
+#
+# All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without modification,
+# are permitted provided that the following conditions are met:
+#
+# - Redistributions of source code must retain the above copyright notice, this
+#   list of conditions and the following disclaimer.
+#
+# - Redistributions in binary form must reproduce the above copyright notice, this
+#   list of conditions and the following disclaimer in the documentation and/or
+#   other materials provided with the distribution.
+#
+# - Neither the name of the organization nor the names of its contributors may
+#   be used to endorse or promote products derived from this software without
+#   specific prior written permission.
+#
+#   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
+# ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+# ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+#
+
+require 'tree'
+
+module Tree
+
+  # Provides a Binary tree implementation. This tree node allows only two child
+  # nodes (left and right childs). It also provides direct access to the left
+  # and right children, including assignment to the same.
+  class BinaryTreeNode < TreeNode
+
+    # Adds the specified child node to the receiver node.  The child node's
+    # parent is set to be the receiver.  The child nodes are added in the order
+    # of addition, i.e., the first child added becomes the left node, and the
+    # second child will be the second node.
+    # If only one child is present, then this will be the left child.
+    def add(child)
+      raise "Already has two child nodes" if @children.size == 2
+
+      super(child)
+    end
+
+    # Returns the left child node. Note that
+    # left Child == first Child
+    def leftChild
+      children.first
+    end
+
+    # Returns the right child node. Note that
+    # right child == last child unless there is only one child.
+    # Returns nil if the right child does not exist.
+    def rightChild
+      children[1]
+    end
+
+    # Sets the left child. If a previous child existed, it is replaced.
+    def leftChild=(child)
+      @children[0] = child
+      @childrenHash[child.name] = child if child # Assign the name mapping
+    end
+
+    # Sets the right child. If a previous child existed, it is replaced.
+    def rightChild=(child)
+      @children[1] = child
+      @childrenHash[child.name] = child if child # Assign the name mapping
+    end
+
+    # Returns true if this is the left child of its parent. Always returns false
+    # if this is the root node.
+    def isLeftChild?
+      return nil if isRoot?
+      self == parent.leftChild
+    end
+
+    # Returns true if this is the right child of its parent. Always returns false
+    # if this is the root node.
+    def isRightChild?
+      return nil if isRoot?
+      self == parent.rightChild
+    end
+
+    # Swaps the left and right children with each other
+    def swap_children
+      tempChild = leftChild
+      self.leftChild= rightChild
+      self.rightChild= tempChild
+    end
+  end
+
+end
+
+# $Log: binarytree.rb,v $
+# Revision 1.5  2007/12/18 23:11:29  anupamsg
+# Minor documentation changes in the binarytree class.
+#
+# Revision 1.4  2007/08/30 22:08:58  anupamsg
+# Added a new swap_children method for Binary Tree. Also added minor
+# documentation and test updates.
+#
+# Revision 1.3  2007/07/21 03:24:25  anupamsg
+# Minor edits to parameter names. User visible functionality does not change.
+#
+# Revision 1.2  2007/07/18 20:15:06  anupamsg
+# Added two predicate methods in BinaryTreeNode to determine whether a node
+# is a left or a right node.
+#
+# Revision 1.1  2007/07/18 19:33:27  anupamsg
+# Added a new binary tree implementation.
+#
diff --git a/vendor/gems/rubytree-0.5.2/setup.rb b/vendor/gems/rubytree-0.5.2/setup.rb
new file mode 100644
index 000000000..424a5f37c
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/setup.rb
@@ -0,0 +1,1585 @@
+#
+# setup.rb
+#
+# Copyright (c) 2000-2005 Minero Aoki
+#
+# This program is free software.
+# You can distribute/modify this program under the terms of
+# the GNU LGPL, Lesser General Public License version 2.1.
+#
+
+unless Enumerable.method_defined?(:map)   # Ruby 1.4.6
+  module Enumerable
+    alias map collect
+  end
+end
+
+unless File.respond_to?(:read)   # Ruby 1.6
+  def File.read(fname)
+    open(fname) {|f|
+      return f.read
+    }
+  end
+end
+
+unless Errno.const_defined?(:ENOTEMPTY)   # Windows?
+  module Errno
+    class ENOTEMPTY
+      # We do not raise this exception, implementation is not needed.
+    end
+  end
+end
+
+def File.binread(fname)
+  open(fname, 'rb') {|f|
+    return f.read
+  }
+end
+
+# for corrupted Windows' stat(2)
+def File.dir?(path)
+  File.directory?((path[-1,1] == '/') ? path : path + '/')
+end
+
+
+class ConfigTable
+
+  include Enumerable
+
+  def initialize(rbconfig)
+    @rbconfig = rbconfig
+    @items = []
+    @table = {}
+    # options
+    @install_prefix = nil
+    @config_opt = nil
+    @verbose = true
+    @no_harm = false
+  end
+
+  attr_accessor :install_prefix
+  attr_accessor :config_opt
+
+  attr_writer :verbose
+
+  def verbose?
+    @verbose
+  end
+
+  attr_writer :no_harm
+
+  def no_harm?
+    @no_harm
+  end
+
+  def [](key)
+    lookup(key).resolve(self)
+  end
+
+  def []=(key, val)
+    lookup(key).set val
+  end
+
+  def names
+    @items.map {|i| i.name }
+  end
+
+  def each(&block)
+    @items.each(&block)
+  end
+
+  def key?(name)
+    @table.key?(name)
+  end
+
+  def lookup(name)
+    @table[name] or setup_rb_error "no such config item: #{name}"
+  end
+
+  def add(item)
+    @items.push item
+    @table[item.name] = item
+  end
+
+  def remove(name)
+    item = lookup(name)
+    @items.delete_if {|i| i.name == name }
+    @table.delete_if {|name, i| i.name == name }
+    item
+  end
+
+  def load_script(path, inst = nil)
+    if File.file?(path)
+      MetaConfigEnvironment.new(self, inst).instance_eval File.read(path), path
+    end
+  end
+
+  def savefile
+    '.config'
+  end
+
+  def load_savefile
+    begin
+      File.foreach(savefile()) do |line|
+        k, v = *line.split(/=/, 2)
+        self[k] = v.strip
+      end
+    rescue Errno::ENOENT
+      setup_rb_error $!.message + "\n#{File.basename($0)} config first"
+    end
+  end
+
+  def save
+    @items.each {|i| i.value }
+    File.open(savefile(), 'w') {|f|
+      @items.each do |i|
+        f.printf "%s=%s\n", i.name, i.value if i.value? and i.value
+      end
+    }
+  end
+
+  def load_standard_entries
+    standard_entries(@rbconfig).each do |ent|
+      add ent
+    end
+  end
+
+  def standard_entries(rbconfig)
+    c = rbconfig
+
+    rubypath = File.join(c['bindir'], c['ruby_install_name'] + c['EXEEXT'])
+
+    major = c['MAJOR'].to_i
+    minor = c['MINOR'].to_i
+    teeny = c['TEENY'].to_i
+    version = "#{major}.#{minor}"
+
+    # ruby ver. >= 1.4.4?
+    newpath_p = ((major >= 2) or
+                 ((major == 1) and
+                  ((minor >= 5) or
+                   ((minor == 4) and (teeny >= 4)))))
+
+    if c['rubylibdir']
+      # V > 1.6.3
+      libruby         = "#{c['prefix']}/lib/ruby"
+      librubyver      = c['rubylibdir']
+      librubyverarch  = c['archdir']
+      siteruby        = c['sitedir']
+      siterubyver     = c['sitelibdir']
+      siterubyverarch = c['sitearchdir']
+    elsif newpath_p
+      # 1.4.4 <= V <= 1.6.3
+      libruby         = "#{c['prefix']}/lib/ruby"
+      librubyver      = "#{c['prefix']}/lib/ruby/#{version}"
+      librubyverarch  = "#{c['prefix']}/lib/ruby/#{version}/#{c['arch']}"
+      siteruby        = c['sitedir']
+      siterubyver     = "$siteruby/#{version}"
+      siterubyverarch = "$siterubyver/#{c['arch']}"
+    else
+      # V < 1.4.4
+      libruby         = "#{c['prefix']}/lib/ruby"
+      librubyver      = "#{c['prefix']}/lib/ruby/#{version}"
+      librubyverarch  = "#{c['prefix']}/lib/ruby/#{version}/#{c['arch']}"
+      siteruby        = "#{c['prefix']}/lib/ruby/#{version}/site_ruby"
+      siterubyver     = siteruby
+      siterubyverarch = "$siterubyver/#{c['arch']}"
+    end
+    parameterize = lambda {|path|
+      path.sub(/\A#{Regexp.quote(c['prefix'])}/, '$prefix')
+    }
+
+    if arg = c['configure_args'].split.detect {|arg| /--with-make-prog=/ =~ arg }
+      makeprog = arg.sub(/'/, '').split(/=/, 2)[1]
+    else
+      makeprog = 'make'
+    end
+
+    [
+      ExecItem.new('installdirs', 'std/site/home',
+                   'std: install under libruby; site: install under site_ruby; home: install under $HOME')\
+          {|val, table|
+            case val
+            when 'std'
+              table['rbdir'] = '$librubyver'
+              table['sodir'] = '$librubyverarch'
+            when 'site'
+              table['rbdir'] = '$siterubyver'
+              table['sodir'] = '$siterubyverarch'
+            when 'home'
+              setup_rb_error '$HOME was not set' unless ENV['HOME']
+              table['prefix'] = ENV['HOME']
+              table['rbdir'] = '$libdir/ruby'
+              table['sodir'] = '$libdir/ruby'
+            end
+          },
+      PathItem.new('prefix', 'path', c['prefix'],
+                   'path prefix of target environment'),
+      PathItem.new('bindir', 'path', parameterize.call(c['bindir']),
+                   'the directory for commands'),
+      PathItem.new('libdir', 'path', parameterize.call(c['libdir']),
+                   'the directory for libraries'),
+      PathItem.new('datadir', 'path', parameterize.call(c['datadir']),
+                   'the directory for shared data'),
+      PathItem.new('mandir', 'path', parameterize.call(c['mandir']),
+                   'the directory for man pages'),
+      PathItem.new('sysconfdir', 'path', parameterize.call(c['sysconfdir']),
+                   'the directory for system configuration files'),
+      PathItem.new('localstatedir', 'path', parameterize.call(c['localstatedir']),
+                   'the directory for local state data'),
+      PathItem.new('libruby', 'path', libruby,
+                   'the directory for ruby libraries'),
+      PathItem.new('librubyver', 'path', librubyver,
+                   'the directory for standard ruby libraries'),
+      PathItem.new('librubyverarch', 'path', librubyverarch,
+                   'the directory for standard ruby extensions'),
+      PathItem.new('siteruby', 'path', siteruby,
+          'the directory for version-independent aux ruby libraries'),
+      PathItem.new('siterubyver', 'path', siterubyver,
+                   'the directory for aux ruby libraries'),
+      PathItem.new('siterubyverarch', 'path', siterubyverarch,
+                   'the directory for aux ruby binaries'),
+      PathItem.new('rbdir', 'path', '$siterubyver',
+                   'the directory for ruby scripts'),
+      PathItem.new('sodir', 'path', '$siterubyverarch',
+                   'the directory for ruby extentions'),
+      PathItem.new('rubypath', 'path', rubypath,
+                   'the path to set to #! line'),
+      ProgramItem.new('rubyprog', 'name', rubypath,
+                      'the ruby program using for installation'),
+      ProgramItem.new('makeprog', 'name', makeprog,
+                      'the make program to compile ruby extentions'),
+      SelectItem.new('shebang', 'all/ruby/never', 'ruby',
+                     'shebang line (#!) editing mode'),
+      BoolItem.new('without-ext', 'yes/no', 'no',
+                   'does not compile/install ruby extentions')
+    ]
+  end
+  private :standard_entries
+
+  def load_multipackage_entries
+    multipackage_entries().each do |ent|
+      add ent
+    end
+  end
+
+  def multipackage_entries
+    [
+      PackageSelectionItem.new('with', 'name,name...', '', 'ALL',
+                               'package names that you want to install'),
+      PackageSelectionItem.new('without', 'name,name...', '', 'NONE',
+                               'package names that you do not want to install')
+    ]
+  end
+  private :multipackage_entries
+
+  ALIASES = {
+    'std-ruby'         => 'librubyver',
+    'stdruby'          => 'librubyver',
+    'rubylibdir'       => 'librubyver',
+    'archdir'          => 'librubyverarch',
+    'site-ruby-common' => 'siteruby',     # For backward compatibility
+    'site-ruby'        => 'siterubyver',  # For backward compatibility
+    'bin-dir'          => 'bindir',
+    'bin-dir'          => 'bindir',
+    'rb-dir'           => 'rbdir',
+    'so-dir'           => 'sodir',
+    'data-dir'         => 'datadir',
+    'ruby-path'        => 'rubypath',
+    'ruby-prog'        => 'rubyprog',
+    'ruby'             => 'rubyprog',
+    'make-prog'        => 'makeprog',
+    'make'             => 'makeprog'
+  }
+
+  def fixup
+    ALIASES.each do |ali, name|
+      @table[ali] = @table[name]
+    end
+    @items.freeze
+    @table.freeze
+    @options_re = /\A--(#{@table.keys.join('|')})(?:=(.*))?\z/
+  end
+
+  def parse_opt(opt)
+    m = @options_re.match(opt) or setup_rb_error "config: unknown option #{opt}"
+    m.to_a[1,2]
+  end
+
+  def dllext
+    @rbconfig['DLEXT']
+  end
+
+  def value_config?(name)
+    lookup(name).value?
+  end
+
+  class Item
+    def initialize(name, template, default, desc)
+      @name = name.freeze
+      @template = template
+      @value = default
+      @default = default
+      @description = desc
+    end
+
+    attr_reader :name
+    attr_reader :description
+
+    attr_accessor :default
+    alias help_default default
+
+    def help_opt
+      "--#{@name}=#{@template}"
+    end
+
+    def value?
+      true
+    end
+
+    def value
+      @value
+    end
+
+    def resolve(table)
+      @value.gsub(%r<\$([^/]+)>) { table[$1] }
+    end
+
+    def set(val)
+      @value = check(val)
+    end
+
+    private
+
+    def check(val)
+      setup_rb_error "config: --#{name} requires argument" unless val
+      val
+    end
+  end
+
+  class BoolItem < Item
+    def config_type
+      'bool'
+    end
+
+    def help_opt
+      "--#{@name}"
+    end
+
+    private
+
+    def check(val)
+      return 'yes' unless val
+      case val
+      when /\Ay(es)?\z/i, /\At(rue)?\z/i then 'yes'
+      when /\An(o)?\z/i, /\Af(alse)\z/i  then 'no'
+      else
+        setup_rb_error "config: --#{@name} accepts only yes/no for argument"
+      end
+    end
+  end
+
+  class PathItem < Item
+    def config_type
+      'path'
+    end
+
+    private
+
+    def check(path)
+      setup_rb_error "config: --#{@name} requires argument"  unless path
+      path[0,1] == '$' ? path : File.expand_path(path)
+    end
+  end
+
+  class ProgramItem < Item
+    def config_type
+      'program'
+    end
+  end
+
+  class SelectItem < Item
+    def initialize(name, selection, default, desc)
+      super
+      @ok = selection.split('/')
+    end
+
+    def config_type
+      'select'
+    end
+
+    private
+
+    def check(val)
+      unless @ok.include?(val.strip)
+        setup_rb_error "config: use --#{@name}=#{@template} (#{val})"
+      end
+      val.strip
+    end
+  end
+
+  class ExecItem < Item
+    def initialize(name, selection, desc, &block)
+      super name, selection, nil, desc
+      @ok = selection.split('/')
+      @action = block
+    end
+
+    def config_type
+      'exec'
+    end
+
+    def value?
+      false
+    end
+
+    def resolve(table)
+      setup_rb_error "$#{name()} wrongly used as option value"
+    end
+
+    undef set
+
+    def evaluate(val, table)
+      v = val.strip.downcase
+      unless @ok.include?(v)
+        setup_rb_error "invalid option --#{@name}=#{val} (use #{@template})"
+      end
+      @action.call v, table
+    end
+  end
+
+  class PackageSelectionItem < Item
+    def initialize(name, template, default, help_default, desc)
+      super name, template, default, desc
+      @help_default = help_default
+    end
+
+    attr_reader :help_default
+
+    def config_type
+      'package'
+    end
+
+    private
+
+    def check(val)
+      unless File.dir?("packages/#{val}")
+        setup_rb_error "config: no such package: #{val}"
+      end
+      val
+    end
+  end
+
+  class MetaConfigEnvironment
+    def initialize(config, installer)
+      @config = config
+      @installer = installer
+    end
+
+    def config_names
+      @config.names
+    end
+
+    def config?(name)
+      @config.key?(name)
+    end
+
+    def bool_config?(name)
+      @config.lookup(name).config_type == 'bool'
+    end
+
+    def path_config?(name)
+      @config.lookup(name).config_type == 'path'
+    end
+
+    def value_config?(name)
+      @config.lookup(name).config_type != 'exec'
+    end
+
+    def add_config(item)
+      @config.add item
+    end
+
+    def add_bool_config(name, default, desc)
+      @config.add BoolItem.new(name, 'yes/no', default ? 'yes' : 'no', desc)
+    end
+
+    def add_path_config(name, default, desc)
+      @config.add PathItem.new(name, 'path', default, desc)
+    end
+
+    def set_config_default(name, default)
+      @config.lookup(name).default = default
+    end
+
+    def remove_config(name)
+      @config.remove(name)
+    end
+
+    # For only multipackage
+    def packages
+      raise '[setup.rb fatal] multi-package metaconfig API packages() called for single-package; contact application package vendor' unless @installer
+      @installer.packages
+    end
+
+    # For only multipackage
+    def declare_packages(list)
+      raise '[setup.rb fatal] multi-package metaconfig API declare_packages() called for single-package; contact application package vendor' unless @installer
+      @installer.packages = list
+    end
+  end
+
+end   # class ConfigTable
+
+
+# This module requires: #verbose?, #no_harm?
+module FileOperations
+
+  def mkdir_p(dirname, prefix = nil)
+    dirname = prefix + File.expand_path(dirname) if prefix
+    $stderr.puts "mkdir -p #{dirname}" if verbose?
+    return if no_harm?
+
+    # Does not check '/', it's too abnormal.
+    dirs = File.expand_path(dirname).split(%r<(?=/)>)
+    if /\A[a-z]:\z/i =~ dirs[0]
+      disk = dirs.shift
+      dirs[0] = disk + dirs[0]
+    end
+    dirs.each_index do |idx|
+      path = dirs[0..idx].join('')
+      Dir.mkdir path unless File.dir?(path)
+    end
+  end
+
+  def rm_f(path)
+    $stderr.puts "rm -f #{path}" if verbose?
+    return if no_harm?
+    force_remove_file path
+  end
+
+  def rm_rf(path)
+    $stderr.puts "rm -rf #{path}" if verbose?
+    return if no_harm?
+    remove_tree path
+  end
+
+  def remove_tree(path)
+    if File.symlink?(path)
+      remove_file path
+    elsif File.dir?(path)
+      remove_tree0 path
+    else
+      force_remove_file path
+    end
+  end
+
+  def remove_tree0(path)
+    Dir.foreach(path) do |ent|
+      next if ent == '.'
+      next if ent == '..'
+      entpath = "#{path}/#{ent}"
+      if File.symlink?(entpath)
+        remove_file entpath
+      elsif File.dir?(entpath)
+        remove_tree0 entpath
+      else
+        force_remove_file entpath
+      end
+    end
+    begin
+      Dir.rmdir path
+    rescue Errno::ENOTEMPTY
+      # directory may not be empty
+    end
+  end
+
+  def move_file(src, dest)
+    force_remove_file dest
+    begin
+      File.rename src, dest
+    rescue
+      File.open(dest, 'wb') {|f|
+        f.write File.binread(src)
+      }
+      File.chmod File.stat(src).mode, dest
+      File.unlink src
+    end
+  end
+
+  def force_remove_file(path)
+    begin
+      remove_file path
+    rescue
+    end
+  end
+
+  def remove_file(path)
+    File.chmod 0777, path
+    File.unlink path
+  end
+
+  def install(from, dest, mode, prefix = nil)
+    $stderr.puts "install #{from} #{dest}" if verbose?
+    return if no_harm?
+
+    realdest = prefix ? prefix + File.expand_path(dest) : dest
+    realdest = File.join(realdest, File.basename(from)) if File.dir?(realdest)
+    str = File.binread(from)
+    if diff?(str, realdest)
+      verbose_off {
+        rm_f realdest if File.exist?(realdest)
+      }
+      File.open(realdest, 'wb') {|f|
+        f.write str
+      }
+      File.chmod mode, realdest
+
+      File.open("#{objdir_root()}/InstalledFiles", 'a') {|f|
+        if prefix
+          f.puts realdest.sub(prefix, '')
+        else
+          f.puts realdest
+        end
+      }
+    end
+  end
+
+  def diff?(new_content, path)
+    return true unless File.exist?(path)
+    new_content != File.binread(path)
+  end
+
+  def command(*args)
+    $stderr.puts args.join(' ') if verbose?
+    system(*args) or raise RuntimeError,
+        "system(#{args.map{|a| a.inspect }.join(' ')}) failed"
+  end
+
+  def ruby(*args)
+    command config('rubyprog'), *args
+  end
+  
+  def make(task = nil)
+    command(*[config('makeprog'), task].compact)
+  end
+
+  def extdir?(dir)
+    File.exist?("#{dir}/MANIFEST") or File.exist?("#{dir}/extconf.rb")
+  end
+
+  def files_of(dir)
+    Dir.open(dir) {|d|
+      return d.select {|ent| File.file?("#{dir}/#{ent}") }
+    }
+  end
+
+  DIR_REJECT = %w( . .. CVS SCCS RCS CVS.adm .svn )
+
+  def directories_of(dir)
+    Dir.open(dir) {|d|
+      return d.select {|ent| File.dir?("#{dir}/#{ent}") } - DIR_REJECT
+    }
+  end
+
+end
+
+
+# This module requires: #srcdir_root, #objdir_root, #relpath
+module HookScriptAPI
+
+  def get_config(key)
+    @config[key]
+  end
+
+  alias config get_config
+
+  # obsolete: use metaconfig to change configuration
+  def set_config(key, val)
+    @config[key] = val
+  end
+
+  #
+  # srcdir/objdir (works only in the package directory)
+  #
+
+  def curr_srcdir
+    "#{srcdir_root()}/#{relpath()}"
+  end
+
+  def curr_objdir
+    "#{objdir_root()}/#{relpath()}"
+  end
+
+  def srcfile(path)
+    "#{curr_srcdir()}/#{path}"
+  end
+
+  def srcexist?(path)
+    File.exist?(srcfile(path))
+  end
+
+  def srcdirectory?(path)
+    File.dir?(srcfile(path))
+  end
+  
+  def srcfile?(path)
+    File.file?(srcfile(path))
+  end
+
+  def srcentries(path = '.')
+    Dir.open("#{curr_srcdir()}/#{path}") {|d|
+      return d.to_a - %w(. ..)
+    }
+  end
+
+  def srcfiles(path = '.')
+    srcentries(path).select {|fname|
+      File.file?(File.join(curr_srcdir(), path, fname))
+    }
+  end
+
+  def srcdirectories(path = '.')
+    srcentries(path).select {|fname|
+      File.dir?(File.join(curr_srcdir(), path, fname))
+    }
+  end
+
+end
+
+
+class ToplevelInstaller
+
+  Version   = '3.4.1'
+  Copyright = 'Copyright (c) 2000-2005 Minero Aoki'
+
+  TASKS = [
+    [ 'all',      'do config, setup, then install' ],
+    [ 'config',   'saves your configurations' ],
+    [ 'show',     'shows current configuration' ],
+    [ 'setup',    'compiles ruby extentions and others' ],
+    [ 'install',  'installs files' ],
+    [ 'test',     'run all tests in test/' ],
+    [ 'clean',    "does `make clean' for each extention" ],
+    [ 'distclean',"does `make distclean' for each extention" ]
+  ]
+
+  def ToplevelInstaller.invoke
+    config = ConfigTable.new(load_rbconfig())
+    config.load_standard_entries
+    config.load_multipackage_entries if multipackage?
+    config.fixup
+    klass = (multipackage?() ? ToplevelInstallerMulti : ToplevelInstaller)
+    klass.new(File.dirname($0), config).invoke
+  end
+
+  def ToplevelInstaller.multipackage?
+    File.dir?(File.dirname($0) + '/packages')
+  end
+
+  def ToplevelInstaller.load_rbconfig
+    if arg = ARGV.detect {|arg| /\A--rbconfig=/ =~ arg }
+      ARGV.delete(arg)
+      load File.expand_path(arg.split(/=/, 2)[1])
+      $".push 'rbconfig.rb'
+    else
+      require 'rbconfig'
+    end
+    ::Config::CONFIG
+  end
+
+  def initialize(ardir_root, config)
+    @ardir = File.expand_path(ardir_root)
+    @config = config
+    # cache
+    @valid_task_re = nil
+  end
+
+  def config(key)
+    @config[key]
+  end
+
+  def inspect
+    "#<#{self.class} #{__id__()}>"
+  end
+
+  def invoke
+    run_metaconfigs
+    case task = parsearg_global()
+    when nil, 'all'
+      parsearg_config
+      init_installers
+      exec_config
+      exec_setup
+      exec_install
+    else
+      case task
+      when 'config', 'test'
+        ;
+      when 'clean', 'distclean'
+        @config.load_savefile if File.exist?(@config.savefile)
+      else
+        @config.load_savefile
+      end
+      __send__ "parsearg_#{task}"
+      init_installers
+      __send__ "exec_#{task}"
+    end
+  end
+  
+  def run_metaconfigs
+    @config.load_script "#{@ardir}/metaconfig"
+  end
+
+  def init_installers
+    @installer = Installer.new(@config, @ardir, File.expand_path('.'))
+  end
+
+  #
+  # Hook Script API bases
+  #
+
+  def srcdir_root
+    @ardir
+  end
+
+  def objdir_root
+    '.'
+  end
+
+  def relpath
+    '.'
+  end
+
+  #
+  # Option Parsing
+  #
+
+  def parsearg_global
+    while arg = ARGV.shift
+      case arg
+      when /\A\w+\z/
+        setup_rb_error "invalid task: #{arg}" unless valid_task?(arg)
+        return arg
+      when '-q', '--quiet'
+        @config.verbose = false
+      when '--verbose'
+        @config.verbose = true
+      when '--help'
+        print_usage $stdout
+        exit 0
+      when '--version'
+        puts "#{File.basename($0)} version #{Version}"
+        exit 0
+      when '--copyright'
+        puts Copyright
+        exit 0
+      else
+        setup_rb_error "unknown global option '#{arg}'"
+      end
+    end
+    nil
+  end
+
+  def valid_task?(t)
+    valid_task_re() =~ t
+  end
+
+  def valid_task_re
+    @valid_task_re ||= /\A(?:#{TASKS.map {|task,desc| task }.join('|')})\z/
+  end
+
+  def parsearg_no_options
+    unless ARGV.empty?
+      task = caller(0).first.slice(%r<`parsearg_(\w+)'>, 1)
+      setup_rb_error "#{task}: unknown options: #{ARGV.join(' ')}"
+    end
+  end
+
+  alias parsearg_show       parsearg_no_options
+  alias parsearg_setup      parsearg_no_options
+  alias parsearg_test       parsearg_no_options
+  alias parsearg_clean      parsearg_no_options
+  alias parsearg_distclean  parsearg_no_options
+
+  def parsearg_config
+    evalopt = []
+    set = []
+    @config.config_opt = []
+    while i = ARGV.shift
+      if /\A--?\z/ =~ i
+        @config.config_opt = ARGV.dup
+        break
+      end
+      name, value = *@config.parse_opt(i)
+      if @config.value_config?(name)
+        @config[name] = value
+      else
+        evalopt.push [name, value]
+      end
+      set.push name
+    end
+    evalopt.each do |name, value|
+      @config.lookup(name).evaluate value, @config
+    end
+    # Check if configuration is valid
+    set.each do |n|
+      @config[n] if @config.value_config?(n)
+    end
+  end
+
+  def parsearg_install
+    @config.no_harm = false
+    @config.install_prefix = ''
+    while a = ARGV.shift
+      case a
+      when '--no-harm'
+        @config.no_harm = true
+      when /\A--prefix=/
+        path = a.split(/=/, 2)[1]
+        path = File.expand_path(path) unless path[0,1] == '/'
+        @config.install_prefix = path
+      else
+        setup_rb_error "install: unknown option #{a}"
+      end
+    end
+  end
+
+  def print_usage(out)
+    out.puts 'Typical Installation Procedure:'
+    out.puts "  $ ruby #{File.basename $0} config"
+    out.puts "  $ ruby #{File.basename $0} setup"
+    out.puts "  # ruby #{File.basename $0} install (may require root privilege)"
+    out.puts
+    out.puts 'Detailed Usage:'
+    out.puts "  ruby #{File.basename $0} <global option>"
+    out.puts "  ruby #{File.basename $0} [<global options>] <task> [<task options>]"
+
+    fmt = "  %-24s %s\n"
+    out.puts
+    out.puts 'Global options:'
+    out.printf fmt, '-q,--quiet',   'suppress message outputs'
+    out.printf fmt, '   --verbose', 'output messages verbosely'
+    out.printf fmt, '   --help',    'print this message'
+    out.printf fmt, '   --version', 'print version and quit'
+    out.printf fmt, '   --copyright',  'print copyright and quit'
+    out.puts
+    out.puts 'Tasks:'
+    TASKS.each do |name, desc|
+      out.printf fmt, name, desc
+    end
+
+    fmt = "  %-24s %s [%s]\n"
+    out.puts
+    out.puts 'Options for CONFIG or ALL:'
+    @config.each do |item|
+      out.printf fmt, item.help_opt, item.description, item.help_default
+    end
+    out.printf fmt, '--rbconfig=path', 'rbconfig.rb to load',"running ruby's"
+    out.puts
+    out.puts 'Options for INSTALL:'
+    out.printf fmt, '--no-harm', 'only display what to do if given', 'off'
+    out.printf fmt, '--prefix=path',  'install path prefix', ''
+    out.puts
+  end
+
+  #
+  # Task Handlers
+  #
+
+  def exec_config
+    @installer.exec_config
+    @config.save   # must be final
+  end
+
+  def exec_setup
+    @installer.exec_setup
+  end
+
+  def exec_install
+    @installer.exec_install
+  end
+
+  def exec_test
+    @installer.exec_test
+  end
+
+  def exec_show
+    @config.each do |i|
+      printf "%-20s %s\n", i.name, i.value if i.value?
+    end
+  end
+
+  def exec_clean
+    @installer.exec_clean
+  end
+
+  def exec_distclean
+    @installer.exec_distclean
+  end
+
+end   # class ToplevelInstaller
+
+
+class ToplevelInstallerMulti < ToplevelInstaller
+
+  include FileOperations
+
+  def initialize(ardir_root, config)
+    super
+    @packages = directories_of("#{@ardir}/packages")
+    raise 'no package exists' if @packages.empty?
+    @root_installer = Installer.new(@config, @ardir, File.expand_path('.'))
+  end
+
+  def run_metaconfigs
+    @config.load_script "#{@ardir}/metaconfig", self
+    @packages.each do |name|
+      @config.load_script "#{@ardir}/packages/#{name}/metaconfig"
+    end
+  end
+
+  attr_reader :packages
+
+  def packages=(list)
+    raise 'package list is empty' if list.empty?
+    list.each do |name|
+      raise "directory packages/#{name} does not exist"\
+              unless File.dir?("#{@ardir}/packages/#{name}")
+    end
+    @packages = list
+  end
+
+  def init_installers
+    @installers = {}
+    @packages.each do |pack|
+      @installers[pack] = Installer.new(@config,
+                                       "#{@ardir}/packages/#{pack}",
+                                       "packages/#{pack}")
+    end
+    with    = extract_selection(config('with'))
+    without = extract_selection(config('without'))
+    @selected = @installers.keys.select {|name|
+                  (with.empty? or with.include?(name)) \
+                      and not without.include?(name)
+                }
+  end
+
+  def extract_selection(list)
+    a = list.split(/,/)
+    a.each do |name|
+      setup_rb_error "no such package: #{name}"  unless @installers.key?(name)
+    end
+    a
+  end
+
+  def print_usage(f)
+    super
+    f.puts 'Inluded packages:'
+    f.puts '  ' + @packages.sort.join(' ')
+    f.puts
+  end
+
+  #
+  # Task Handlers
+  #
+
+  def exec_config
+    run_hook 'pre-config'
+    each_selected_installers {|inst| inst.exec_config }
+    run_hook 'post-config'
+    @config.save   # must be final
+  end
+
+  def exec_setup
+    run_hook 'pre-setup'
+    each_selected_installers {|inst| inst.exec_setup }
+    run_hook 'post-setup'
+  end
+
+  def exec_install
+    run_hook 'pre-install'
+    each_selected_installers {|inst| inst.exec_install }
+    run_hook 'post-install'
+  end
+
+  def exec_test
+    run_hook 'pre-test'
+    each_selected_installers {|inst| inst.exec_test }
+    run_hook 'post-test'
+  end
+
+  def exec_clean
+    rm_f @config.savefile
+    run_hook 'pre-clean'
+    each_selected_installers {|inst| inst.exec_clean }
+    run_hook 'post-clean'
+  end
+
+  def exec_distclean
+    rm_f @config.savefile
+    run_hook 'pre-distclean'
+    each_selected_installers {|inst| inst.exec_distclean }
+    run_hook 'post-distclean'
+  end
+
+  #
+  # lib
+  #
+
+  def each_selected_installers
+    Dir.mkdir 'packages' unless File.dir?('packages')
+    @selected.each do |pack|
+      $stderr.puts "Processing the package `#{pack}' ..." if verbose?
+      Dir.mkdir "packages/#{pack}" unless File.dir?("packages/#{pack}")
+      Dir.chdir "packages/#{pack}"
+      yield @installers[pack]
+      Dir.chdir '../..'
+    end
+  end
+
+  def run_hook(id)
+    @root_installer.run_hook id
+  end
+
+  # module FileOperations requires this
+  def verbose?
+    @config.verbose?
+  end
+
+  # module FileOperations requires this
+  def no_harm?
+    @config.no_harm?
+  end
+
+end   # class ToplevelInstallerMulti
+
+
+class Installer
+
+  FILETYPES = %w( bin lib ext data conf man )
+
+  include FileOperations
+  include HookScriptAPI
+
+  def initialize(config, srcroot, objroot)
+    @config = config
+    @srcdir = File.expand_path(srcroot)
+    @objdir = File.expand_path(objroot)
+    @currdir = '.'
+  end
+
+  def inspect
+    "#<#{self.class} #{File.basename(@srcdir)}>"
+  end
+
+  def noop(rel)
+  end
+
+  #
+  # Hook Script API base methods
+  #
+
+  def srcdir_root
+    @srcdir
+  end
+
+  def objdir_root
+    @objdir
+  end
+
+  def relpath
+    @currdir
+  end
+
+  #
+  # Config Access
+  #
+
+  # module FileOperations requires this
+  def verbose?
+    @config.verbose?
+  end
+
+  # module FileOperations requires this
+  def no_harm?
+    @config.no_harm?
+  end
+
+  def verbose_off
+    begin
+      save, @config.verbose = @config.verbose?, false
+      yield
+    ensure
+      @config.verbose = save
+    end
+  end
+
+  #
+  # TASK config
+  #
+
+  def exec_config
+    exec_task_traverse 'config'
+  end
+
+  alias config_dir_bin noop
+  alias config_dir_lib noop
+
+  def config_dir_ext(rel)
+    extconf if extdir?(curr_srcdir())
+  end
+
+  alias config_dir_data noop
+  alias config_dir_conf noop
+  alias config_dir_man noop
+
+  def extconf
+    ruby "#{curr_srcdir()}/extconf.rb", *@config.config_opt
+  end
+
+  #
+  # TASK setup
+  #
+
+  def exec_setup
+    exec_task_traverse 'setup'
+  end
+
+  def setup_dir_bin(rel)
+    files_of(curr_srcdir()).each do |fname|
+      update_shebang_line "#{curr_srcdir()}/#{fname}"
+    end
+  end
+
+  alias setup_dir_lib noop
+
+  def setup_dir_ext(rel)
+    make if extdir?(curr_srcdir())
+  end
+
+  alias setup_dir_data noop
+  alias setup_dir_conf noop
+  alias setup_dir_man noop
+
+  def update_shebang_line(path)
+    return if no_harm?
+    return if config('shebang') == 'never'
+    old = Shebang.load(path)
+    if old
+      $stderr.puts "warning: #{path}: Shebang line includes too many args.  It is not portable and your program may not work." if old.args.size > 1
+      new = new_shebang(old)
+      return if new.to_s == old.to_s
+    else
+      return unless config('shebang') == 'all'
+      new = Shebang.new(config('rubypath'))
+    end
+    $stderr.puts "updating shebang: #{File.basename(path)}" if verbose?
+    open_atomic_writer(path) {|output|
+      File.open(path, 'rb') {|f|
+        f.gets if old   # discard
+        output.puts new.to_s
+        output.print f.read
+      }
+    }
+  end
+
+  def new_shebang(old)
+    if /\Aruby/ =~ File.basename(old.cmd)
+      Shebang.new(config('rubypath'), old.args)
+    elsif File.basename(old.cmd) == 'env' and old.args.first == 'ruby'
+      Shebang.new(config('rubypath'), old.args[1..-1])
+    else
+      return old unless config('shebang') == 'all'
+      Shebang.new(config('rubypath'))
+    end
+  end
+
+  def open_atomic_writer(path, &block)
+    tmpfile = File.basename(path) + '.tmp'
+    begin
+      File.open(tmpfile, 'wb', &block)
+      File.rename tmpfile, File.basename(path)
+    ensure
+      File.unlink tmpfile if File.exist?(tmpfile)
+    end
+  end
+
+  class Shebang
+    def Shebang.load(path)
+      line = nil
+      File.open(path) {|f|
+        line = f.gets
+      }
+      return nil unless /\A#!/ =~ line
+      parse(line)
+    end
+
+    def Shebang.parse(line)
+      cmd, *args = *line.strip.sub(/\A\#!/, '').split(' ')
+      new(cmd, args)
+    end
+
+    def initialize(cmd, args = [])
+      @cmd = cmd
+      @args = args
+    end
+
+    attr_reader :cmd
+    attr_reader :args
+
+    def to_s
+      "#! #{@cmd}" + (@args.empty? ? '' : " #{@args.join(' ')}")
+    end
+  end
+
+  #
+  # TASK install
+  #
+
+  def exec_install
+    rm_f 'InstalledFiles'
+    exec_task_traverse 'install'
+  end
+
+  def install_dir_bin(rel)
+    install_files targetfiles(), "#{config('bindir')}/#{rel}", 0755
+  end
+
+  def install_dir_lib(rel)
+    install_files libfiles(), "#{config('rbdir')}/#{rel}", 0644
+  end
+
+  def install_dir_ext(rel)
+    return unless extdir?(curr_srcdir())
+    install_files rubyextentions('.'),
+                  "#{config('sodir')}/#{File.dirname(rel)}",
+                  0555
+  end
+
+  def install_dir_data(rel)
+    install_files targetfiles(), "#{config('datadir')}/#{rel}", 0644
+  end
+
+  def install_dir_conf(rel)
+    # FIXME: should not remove current config files
+    # (rename previous file to .old/.org)
+    install_files targetfiles(), "#{config('sysconfdir')}/#{rel}", 0644
+  end
+
+  def install_dir_man(rel)
+    install_files targetfiles(), "#{config('mandir')}/#{rel}", 0644
+  end
+
+  def install_files(list, dest, mode)
+    mkdir_p dest, @config.install_prefix
+    list.each do |fname|
+      install fname, dest, mode, @config.install_prefix
+    end
+  end
+
+  def libfiles
+    glob_reject(%w(*.y *.output), targetfiles())
+  end
+
+  def rubyextentions(dir)
+    ents = glob_select("*.#{@config.dllext}", targetfiles())
+    if ents.empty?
+      setup_rb_error "no ruby extention exists: 'ruby #{$0} setup' first"
+    end
+    ents
+  end
+
+  def targetfiles
+    mapdir(existfiles() - hookfiles())
+  end
+
+  def mapdir(ents)
+    ents.map {|ent|
+      if File.exist?(ent)
+      then ent                         # objdir
+      else "#{curr_srcdir()}/#{ent}"   # srcdir
+      end
+    }
+  end
+
+  # picked up many entries from cvs-1.11.1/src/ignore.c
+  JUNK_FILES = %w( 
+    core RCSLOG tags TAGS .make.state
+    .nse_depinfo #* .#* cvslog.* ,* .del-* *.olb
+    *~ *.old *.bak *.BAK *.orig *.rej _$* *$
+
+    *.org *.in .*
+  )
+
+  def existfiles
+    glob_reject(JUNK_FILES, (files_of(curr_srcdir()) | files_of('.')))
+  end
+
+  def hookfiles
+    %w( pre-%s post-%s pre-%s.rb post-%s.rb ).map {|fmt|
+      %w( config setup install clean ).map {|t| sprintf(fmt, t) }
+    }.flatten
+  end
+
+  def glob_select(pat, ents)
+    re = globs2re([pat])
+    ents.select {|ent| re =~ ent }
+  end
+
+  def glob_reject(pats, ents)
+    re = globs2re(pats)
+    ents.reject {|ent| re =~ ent }
+  end
+
+  GLOB2REGEX = {
+    '.' => '\.',
+    '$' => '\$',
+    '#' => '\#',
+    '*' => '.*'
+  }
+
+  def globs2re(pats)
+    /\A(?:#{
+      pats.map {|pat| pat.gsub(/[\.\$\#\*]/) {|ch| GLOB2REGEX[ch] } }.join('|')
+    })\z/
+  end
+
+  #
+  # TASK test
+  #
+
+  TESTDIR = 'test'
+
+  def exec_test
+    unless File.directory?('test')
+      $stderr.puts 'no test in this package' if verbose?
+      return
+    end
+    $stderr.puts 'Running tests...' if verbose?
+    begin
+      require 'test/unit'
+    rescue LoadError
+      setup_rb_error 'test/unit cannot loaded.  You need Ruby 1.8 or later to invoke this task.'
+    end
+    runner = Test::Unit::AutoRunner.new(true)
+    runner.to_run << TESTDIR
+    runner.run
+  end
+
+  #
+  # TASK clean
+  #
+
+  def exec_clean
+    exec_task_traverse 'clean'
+    rm_f @config.savefile
+    rm_f 'InstalledFiles'
+  end
+
+  alias clean_dir_bin noop
+  alias clean_dir_lib noop
+  alias clean_dir_data noop
+  alias clean_dir_conf noop
+  alias clean_dir_man noop
+
+  def clean_dir_ext(rel)
+    return unless extdir?(curr_srcdir())
+    make 'clean' if File.file?('Makefile')
+  end
+
+  #
+  # TASK distclean
+  #
+
+  def exec_distclean
+    exec_task_traverse 'distclean'
+    rm_f @config.savefile
+    rm_f 'InstalledFiles'
+  end
+
+  alias distclean_dir_bin noop
+  alias distclean_dir_lib noop
+
+  def distclean_dir_ext(rel)
+    return unless extdir?(curr_srcdir())
+    make 'distclean' if File.file?('Makefile')
+  end
+
+  alias distclean_dir_data noop
+  alias distclean_dir_conf noop
+  alias distclean_dir_man noop
+
+  #
+  # Traversing
+  #
+
+  def exec_task_traverse(task)
+    run_hook "pre-#{task}"
+    FILETYPES.each do |type|
+      if type == 'ext' and config('without-ext') == 'yes'
+        $stderr.puts 'skipping ext/* by user option' if verbose?
+        next
+      end
+      traverse task, type, "#{task}_dir_#{type}"
+    end
+    run_hook "post-#{task}"
+  end
+
+  def traverse(task, rel, mid)
+    dive_into(rel) {
+      run_hook "pre-#{task}"
+      __send__ mid, rel.sub(%r[\A.*?(?:/|\z)], '')
+      directories_of(curr_srcdir()).each do |d|
+        traverse task, "#{rel}/#{d}", mid
+      end
+      run_hook "post-#{task}"
+    }
+  end
+
+  def dive_into(rel)
+    return unless File.dir?("#{@srcdir}/#{rel}")
+
+    dir = File.basename(rel)
+    Dir.mkdir dir unless File.dir?(dir)
+    prevdir = Dir.pwd
+    Dir.chdir dir
+    $stderr.puts '---> ' + rel if verbose?
+    @currdir = rel
+    yield
+    Dir.chdir prevdir
+    $stderr.puts '<--- ' + rel if verbose?
+    @currdir = File.dirname(rel)
+  end
+
+  def run_hook(id)
+    path = [ "#{curr_srcdir()}/#{id}",
+             "#{curr_srcdir()}/#{id}.rb" ].detect {|cand| File.file?(cand) }
+    return unless path
+    begin
+      instance_eval File.read(path), path, 1
+    rescue
+      raise if $DEBUG
+      setup_rb_error "hook #{path} failed:\n" + $!.message
+    end
+  end
+
+end   # class Installer
+
+
+class SetupError < StandardError; end
+
+def setup_rb_error(msg)
+  raise SetupError, msg
+end
+
+if $0 == __FILE__
+  begin
+    ToplevelInstaller.invoke
+  rescue SetupError
+    raise if $DEBUG
+    $stderr.puts $!.message
+    $stderr.puts "Try 'ruby #{$0} --help' for detailed usage."
+    exit 1
+  end
+end
diff --git a/vendor/gems/rubytree-0.5.2/test/test_binarytree.rb b/vendor/gems/rubytree-0.5.2/test/test_binarytree.rb
new file mode 100644
index 000000000..8d8664565
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/test/test_binarytree.rb
@@ -0,0 +1,204 @@
+#!/usr/bin/env ruby
+
+# test_binarytree.rb
+#
+# $Revision: 1.5 $ by $Author: anupamsg $
+# $Name:  $
+#
+# Copyright (c) 2006, 2007 Anupam Sengupta
+#
+# All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without modification,
+# are permitted provided that the following conditions are met:
+#
+# - Redistributions of source code must retain the above copyright notice, this
+#   list of conditions and the following disclaimer.
+#
+# - Redistributions in binary form must reproduce the above copyright notice, this
+#   list of conditions and the following disclaimer in the documentation and/or
+#   other materials provided with the distribution.
+#
+# - Neither the name of the organization nor the names of its contributors may
+#   be used to endorse or promote products derived from this software without
+#   specific prior written permission.
+#
+#   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
+# ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+# ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+#
+
+require 'test/unit'
+require 'tree/binarytree'
+
+module TestTree
+  # Test class for the Tree node.
+  class TestBinaryTreeNode < Test::Unit::TestCase
+
+    def setup
+      @root = Tree::BinaryTreeNode.new("ROOT", "Root Node")
+
+      @left_child1  = Tree::BinaryTreeNode.new("A Child at Left", "Child Node @ left")
+      @right_child1 = Tree::BinaryTreeNode.new("B Child at Right", "Child Node @ right")
+
+    end
+
+    def teardown
+      @root.remove!(@left_child1)
+      @root.remove!(@right_child1)
+      @root = nil
+    end
+
+    def test_initialize
+      assert_not_nil(@root, "Binary tree's Root should have been created")
+    end
+
+    def test_add
+      @root.add  @left_child1
+      assert_same(@left_child1, @root.leftChild, "The left node should be left_child1")
+      assert_same(@left_child1, @root.firstChild, "The first node should be left_child1")
+
+      @root.add @right_child1
+      assert_same(@right_child1, @root.rightChild, "The right node should be right_child1")
+      assert_same(@right_child1, @root.lastChild, "The first node should be right_child1")
+
+      assert_raise RuntimeError do
+        @root.add Tree::BinaryTreeNode.new("The third child!")
+      end
+
+      assert_raise RuntimeError do
+        @root << Tree::BinaryTreeNode.new("The third child!")
+      end
+    end
+
+    def test_leftChild
+      @root << @left_child1
+      @root << @right_child1
+      assert_same(@left_child1, @root.leftChild, "The left child should be 'left_child1")
+      assert_not_same(@right_child1, @root.leftChild, "The right_child1 is not the left child")
+    end
+
+    def test_rightChild
+      @root << @left_child1
+      @root << @right_child1
+      assert_same(@right_child1, @root.rightChild, "The right child should be 'right_child1")
+      assert_not_same(@left_child1, @root.rightChild, "The left_child1 is not the left child")
+    end
+
+    def test_leftChild_equals
+      @root << @left_child1
+      @root << @right_child1
+      assert_same(@left_child1, @root.leftChild, "The left child should be 'left_child1")
+
+      @root.leftChild = Tree::BinaryTreeNode.new("New Left Child")
+      assert_equal("New Left Child", @root.leftChild.name, "The left child should now be the new child")
+      assert_equal("B Child at Right", @root.lastChild.name, "The last child should now be the right child")
+
+      # Now set the left child as nil, and retest
+      @root.leftChild = nil
+      assert_nil(@root.leftChild, "The left child should now be nil")
+      assert_nil(@root.firstChild, "The first child is now nil")
+      assert_equal("B Child at Right", @root.lastChild.name, "The last child should now be the right child")
+    end
+
+    def test_rightChild_equals
+      @root << @left_child1
+      @root << @right_child1
+      assert_same(@right_child1, @root.rightChild, "The right child should be 'right_child1")
+
+      @root.rightChild = Tree::BinaryTreeNode.new("New Right Child")
+      assert_equal("New Right Child", @root.rightChild.name, "The right child should now be the new child")
+      assert_equal("A Child at Left", @root.firstChild.name, "The first child should now be the left child")
+      assert_equal("New Right Child", @root.lastChild.name, "The last child should now be the right child")
+
+      # Now set the right child as nil, and retest
+      @root.rightChild = nil
+      assert_nil(@root.rightChild, "The right child should now be nil")
+      assert_equal("A Child at Left", @root.firstChild.name, "The first child should now be the left child")
+      assert_nil(@root.lastChild, "The first child is now nil")
+    end
+
+    def test_isLeftChild_eh
+      @root << @left_child1
+      @root << @right_child1
+
+      assert(@left_child1.isLeftChild?, "left_child1 should be the left child")
+      assert(!@right_child1.isLeftChild?, "left_child1 should be the left child")
+
+      # Now set the right child as nil, and retest
+      @root.rightChild = nil
+      assert(@left_child1.isLeftChild?, "left_child1 should be the left child")
+
+      assert(!@root.isLeftChild?, "Root is neither left child nor right")
+    end
+
+    def test_isRightChild_eh
+      @root << @left_child1
+      @root << @right_child1
+
+      assert(@right_child1.isRightChild?, "right_child1 should be the right child")
+      assert(!@left_child1.isRightChild?, "right_child1 should be the right child")
+
+      # Now set the left child as nil, and retest
+      @root.leftChild = nil
+      assert(@right_child1.isRightChild?, "right_child1 should be the right child")
+      assert(!@root.isRightChild?, "Root is neither left child nor right")
+    end
+
+    def test_swap_children
+      @root << @left_child1
+      @root << @right_child1
+
+      assert(@right_child1.isRightChild?, "right_child1 should be the right child")
+      assert(!@left_child1.isRightChild?, "right_child1 should be the right child")
+
+      @root.swap_children
+
+      assert(@right_child1.isLeftChild?, "right_child1 should now be the left child")
+      assert(@left_child1.isRightChild?, "left_child1 should now be the right child")
+      assert_equal(@right_child1, @root.firstChild, "right_child1 should now be the first child")
+      assert_equal(@left_child1, @root.lastChild, "left_child1 should now be the last child")
+      assert_equal(@right_child1, @root[0], "right_child1 should now be the first child")
+      assert_equal(@left_child1, @root[1], "left_child1 should now be the last child")
+    end
+  end
+end
+
+# $Log: test_binarytree.rb,v $
+# Revision 1.5  2007/12/22 00:28:59  anupamsg
+# Added more test cases, and enabled ZenTest compatibility.
+#
+# Revision 1.4  2007/12/18 23:11:29  anupamsg
+# Minor documentation changes in the binarytree class.
+#
+# Revision 1.3  2007/10/02 03:07:30  anupamsg
+# * Rakefile: Added an optional task for rcov code coverage.
+#
+# * test/test_binarytree.rb: Removed the unnecessary dependency on "Person" class.
+#
+# * test/test_tree.rb: Removed dependency on the redundant "Person" class.
+#
+# Revision 1.2  2007/08/30 22:06:13  anupamsg
+# Added a new swap_children method for the Binary Tree class.
+# Also made minor documentation updates and test additions.
+#
+# Revision 1.1  2007/07/21 04:52:37  anupamsg
+# Renamed the test files.
+#
+# Revision 1.4  2007/07/19 02:03:57  anupamsg
+# Minor syntax correction.
+#
+# Revision 1.3  2007/07/19 02:02:12  anupamsg
+# Removed useless files (including rdoc, which should be generated for each release.
+#
+# Revision 1.2  2007/07/18 20:15:06  anupamsg
+# Added two predicate methods in BinaryTreeNode to determine whether a node
+# is a left or a right node.
+#
diff --git a/vendor/gems/rubytree-0.5.2/test/test_tree.rb b/vendor/gems/rubytree-0.5.2/test/test_tree.rb
new file mode 100644
index 000000000..d1aa12116
--- /dev/null
+++ b/vendor/gems/rubytree-0.5.2/test/test_tree.rb
@@ -0,0 +1,718 @@
+#!/usr/bin/env ruby
+
+# testtree.rb
+#
+# $Revision: 1.6 $ by $Author: anupamsg $
+# $Name:  $
+#
+# Copyright (c) 2006, 2007 Anupam Sengupta
+#
+# All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without modification,
+# are permitted provided that the following conditions are met:
+#
+# - Redistributions of source code must retain the above copyright notice, this
+#   list of conditions and the following disclaimer.
+#
+# - Redistributions in binary form must reproduce the above copyright notice, this
+#   list of conditions and the following disclaimer in the documentation and/or
+#   other materials provided with the distribution.
+#
+# - Neither the name of the organization nor the names of its contributors may
+#   be used to endorse or promote products derived from this software without
+#   specific prior written permission.
+#
+#   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
+# ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+# ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+#
+
+require 'test/unit'
+require 'tree'
+
+module TestTree
+  # Test class for the Tree node.
+  class TestTreeNode < Test::Unit::TestCase
+
+    Person = Struct::new(:First, :last)
+
+    def setup
+      @root = Tree::TreeNode.new("ROOT", "Root Node")
+
+      @child1 = Tree::TreeNode.new("Child1", "Child Node 1")
+      @child2 = Tree::TreeNode.new("Child2", "Child Node 2")
+      @child3 = Tree::TreeNode.new("Child3", "Child Node 3")
+      @child4 = Tree::TreeNode.new("Child31", "Grand Child 1")
+
+    end
+
+    # Create this structure for the tests
+    #
+    #          +----------+
+    #          |  ROOT    |
+    #          +-+--------+
+    #            |
+    #            |    +---------------+
+    #            +----+  CHILD1       |
+    #            |    +---------------+
+    #            |
+    #            |    +---------------+
+    #            +----+  CHILD2       |
+    #            |    +---------------+
+    #            |
+    #            |    +---------------+   +------------------+
+    #            +----+  CHILD3       +---+  CHILD4          |
+    #                 +---------------+   +------------------+
+    #
+    def loadChildren
+      @root << @child1
+      @root << @child2
+      @root << @child3 << @child4
+    end
+
+    def teardown
+      @root = nil
+    end
+
+    def test_root_setup
+      assert_not_nil(@root, "Root cannot be nil")
+      assert_nil(@root.parent, "Parent of root node should be nil")
+      assert_not_nil(@root.name, "Name should not be nil")
+      assert_equal("ROOT", @root.name, "Name should be 'ROOT'")
+      assert_equal("Root Node", @root.content, "Content should be 'Root Node'")
+      assert(@root.isRoot?, "Should identify as root")
+      assert(!@root.hasChildren?, "Cannot have any children")
+      assert(@root.hasContent?, "This root should have content")
+      assert_equal(1, @root.size, "Number of nodes should be one")
+      assert_nil(@root.siblings, "Root cannot have any children")
+
+      assert_raise(RuntimeError) { Tree::TreeNode.new(nil) }
+    end
+
+    def test_root
+      loadChildren
+
+      assert_same(@root, @root.root, "Root's root is self")
+      assert_same(@root, @child1.root, "Root should be ROOT")
+      assert_same(@root, @child4.root, "Root should be ROOT")
+    end
+
+    def test_hasContent_eh
+      aNode = Tree::TreeNode.new("A Node")
+      assert_nil(aNode.content, "The node should not have content")
+      assert(!aNode.hasContent?, "The node should not have content")
+
+      aNode.content = "Something"
+      assert_not_nil(aNode.content, "The node should now have content")
+      assert(aNode.hasContent?, "The node should now have content")
+    end
+
+    def test_length
+      loadChildren
+      assert_equal(@root.size, @root.length, "Length and size methods should return the same result")
+    end
+
+    def test_spaceship          # Test the <=> operator.
+      firstNode  = Tree::TreeNode.new(1)
+      secondNode = Tree::TreeNode.new(2)
+
+      assert_equal(firstNode <=> nil, +1)
+      assert_equal(firstNode <=> secondNode, -1)
+
+      secondNode = Tree::TreeNode.new(1)
+      assert_equal(firstNode <=> secondNode, 0)
+
+      firstNode  = Tree::TreeNode.new("ABC")
+      secondNode = Tree::TreeNode.new("XYZ")
+
+      assert_equal(firstNode <=> nil, +1)
+      assert_equal(firstNode <=> secondNode, -1)
+
+      secondNode = Tree::TreeNode.new("ABC")
+      assert_equal(firstNode <=> secondNode, 0)
+    end
+
+    def test_to_s
+      aNode = Tree::TreeNode.new("A Node", "Some Content")
+
+      expectedString = "Node Name: A Node Content: Some Content Parent: <None> Children: 0 Total Nodes: 1"
+
+      assert_equal(expectedString, aNode.to_s, "The string representation should be same")
+    end
+
+    def test_firstSibling
+      loadChildren
+
+      assert_same(@root, @root.firstSibling, "Root's first sibling is itself")
+      assert_same(@child1, @child1.firstSibling, "Child1's first sibling is itself")
+      assert_same(@child1, @child2.firstSibling, "Child2's first sibling should be child1")
+      assert_same(@child1, @child3.firstSibling, "Child3's first sibling should be child1")
+      assert_not_same(@child1, @child4.firstSibling, "Child4's first sibling is itself")
+    end
+
+    def test_isFirstSibling_eh
+      loadChildren
+
+      assert(@root.isFirstSibling?, "Root's first sibling is itself")
+      assert( @child1.isFirstSibling?, "Child1's first sibling is itself")
+      assert(!@child2.isFirstSibling?, "Child2 is not the first sibling")
+      assert(!@child3.isFirstSibling?, "Child3 is not the first sibling")
+      assert( @child4.isFirstSibling?, "Child4's first sibling is itself")
+    end
+
+    def test_isLastSibling_eh
+      loadChildren
+
+      assert(@root.isLastSibling?, "Root's last sibling is itself")
+      assert(!@child1.isLastSibling?, "Child1 is not the last sibling")
+      assert(!@child2.isLastSibling?, "Child2 is not the last sibling")
+      assert( @child3.isLastSibling?, "Child3's last sibling is itself")
+      assert( @child4.isLastSibling?, "Child4's last sibling is itself")
+    end
+
+    def test_lastSibling
+      loadChildren
+
+      assert_same(@root, @root.lastSibling, "Root's last sibling is itself")
+      assert_same(@child3, @child1.lastSibling, "Child1's last sibling should be child3")
+      assert_same(@child3, @child2.lastSibling, "Child2's last sibling should be child3")
+      assert_same(@child3, @child3.lastSibling, "Child3's last sibling should be itself")
+      assert_not_same(@child3, @child4.lastSibling, "Child4's last sibling is itself")
+    end
+
+    def test_siblings
+      loadChildren
+
+      siblings = []
+      @child1.siblings { |sibling| siblings << sibling}
+      assert_equal(2, siblings.length, "Should have two siblings")
+      assert(siblings.include?(@child2), "Should have 2nd child as sibling")
+      assert(siblings.include?(@child3), "Should have 3rd child as sibling")
+
+      siblings.clear
+      siblings = @child1.siblings
+      assert_equal(2, siblings.length, "Should have two siblings")
+
+      siblings.clear
+      @child4.siblings {|sibling| siblings << sibling}
+      assert(siblings.empty?, "Should not have any children")
+
+    end
+
+    def test_isOnlyChild_eh
+      loadChildren
+
+      assert(!@child1.isOnlyChild?, "Child1 is not the only child")
+      assert(!@child2.isOnlyChild?, "Child2 is not the only child")
+      assert(!@child3.isOnlyChild?, "Child3 is not the only child")
+      assert( @child4.isOnlyChild?, "Child4 is not the only child")
+    end
+
+    def test_nextSibling
+      loadChildren
+
+      assert_equal(@child2, @child1.nextSibling, "Child1's next sibling is Child2")
+      assert_equal(@child3, @child2.nextSibling, "Child2's next sibling is Child3")
+      assert_nil(@child3.nextSibling, "Child3 does not have a next sibling")
+      assert_nil(@child4.nextSibling, "Child4 does not have a next sibling")
+    end
+
+    def test_previousSibling
+      loadChildren
+
+      assert_nil(@child1.previousSibling, "Child1 does not have previous sibling")
+      assert_equal(@child1, @child2.previousSibling, "Child2's previous sibling is Child1")
+      assert_equal(@child2, @child3.previousSibling, "Child3's previous sibling is Child2")
+      assert_nil(@child4.previousSibling, "Child4 does not have a previous sibling")
+    end
+
+    def test_add
+      assert(!@root.hasChildren?, "Should not have any children")
+
+      @root.add(@child1)
+
+      @root << @child2
+
+      assert(@root.hasChildren?, "Should have children")
+      assert_equal(3, @root.size, "Should have three nodes")
+
+      @root << @child3 << @child4
+
+      assert_equal(5, @root.size, "Should have five nodes")
+      assert_equal(2, @child3.size, "Should have two nodes")
+
+      assert_raise(RuntimeError) { @root.add(Tree::TreeNode.new(@child1.name)) }
+
+    end
+
+    def test_remove_bang
+      @root << @child1
+      @root << @child2
+
+      assert(@root.hasChildren?, "Should have children")
+      assert_equal(3, @root.size, "Should have three nodes")
+
+      @root.remove!(@child1)
+      assert_equal(2, @root.size, "Should have two nodes")
+      @root.remove!(@child2)
+
+      assert(!@root.hasChildren?, "Should have no children")
+      assert_equal(1, @root.size, "Should have one node")
+
+      @root << @child1
+      @root << @child2
+
+      assert(@root.hasChildren?, "Should have children")
+      assert_equal(3, @root.size, "Should have three nodes")
+
+      @root.removeAll!
+
+      assert(!@root.hasChildren?, "Should have no children")
+      assert_equal(1, @root.size, "Should have one node")
+
+    end
+
+    def test_removeAll_bang
+      loadChildren
+      assert(@root.hasChildren?, "Should have children")
+      @root.removeAll!
+
+      assert(!@root.hasChildren?, "Should have no children")
+      assert_equal(1, @root.size, "Should have one node")
+    end
+
+    def test_removeFromParent_bang
+      loadChildren
+      assert(@root.hasChildren?, "Should have children")
+      assert(!@root.isLeaf?, "Root is not a leaf here")
+
+      child1 = @root[0]
+      assert_not_nil(child1, "Child 1 should exist")
+      assert_same(@root, child1.root, "Child 1's root should be ROOT")
+      assert(@root.include?(child1), "root should have child1")
+      child1.removeFromParent!
+      assert_same(child1, child1.root, "Child 1's root should be self")
+      assert(!@root.include?(child1), "root should not have child1")
+
+      child1.removeFromParent!
+      assert_same(child1, child1.root, "Child 1's root should still be self")
+    end
+
+    def test_children
+      loadChildren
+
+      assert(@root.hasChildren?, "Should have children")
+      assert_equal(5, @root.size, "Should have four nodes")
+      assert(@child3.hasChildren?, "Should have children")
+      assert(!@child3.isLeaf?, "Should not be a leaf")
+
+      children = []
+      for child in @root.children
+        children << child
+      end
+
+      assert_equal(3, children.length, "Should have three direct children")
+      assert(!children.include?(@root), "Should not have root")
+      assert(children.include?(@child1), "Should have child 1")
+      assert(children.include?(@child2), "Should have child 2")
+      assert(children.include?(@child3), "Should have child 3")
+      assert(!children.include?(@child4), "Should not have child 4")
+
+      children.clear
+      children = @root.children
+      assert_equal(3, children.length, "Should have three children")
+
+    end
+
+    def test_firstChild
+      loadChildren
+
+      assert_equal(@child1, @root.firstChild, "Root's first child is Child1")
+      assert_nil(@child1.firstChild, "Child1 does not have any children")
+      assert_equal(@child4, @child3.firstChild, "Child3's first child is Child4")
+
+    end
+
+    def test_lastChild
+      loadChildren
+
+      assert_equal(@child3, @root.lastChild, "Root's last child is Child3")
+      assert_nil(@child1.lastChild, "Child1 does not have any children")
+      assert_equal(@child4, @child3.lastChild, "Child3's last child is Child4")
+
+    end
+
+    def test_find
+      loadChildren
+      foundNode = @root.find { |node| node == @child2}
+      assert_same(@child2, foundNode, "The node should be Child 2")
+
+      foundNode = @root.find { |node| node == @child4}
+      assert_same(@child4, foundNode, "The node should be Child 4")
+
+      foundNode = @root.find { |node| node.name == "Child31" }
+      assert_same(@child4, foundNode, "The node should be Child 4")
+      foundNode = @root.find { |node| node.name == "NOT PRESENT" }
+      assert_nil(foundNode, "The node should not be found")
+    end
+
+    def test_parentage
+      loadChildren
+
+      assert_nil(@root.parentage, "Root does not have any parentage")
+      assert_equal([@root], @child1.parentage, "Child1 has Root as its parent")
+      assert_equal([@child3, @root], @child4.parentage, "Child4 has Child3 and Root as ancestors")
+    end
+
+    def test_each
+      loadChildren
+      assert(@root.hasChildren?, "Should have children")
+      assert_equal(5, @root.size, "Should have five nodes")
+      assert(@child3.hasChildren?, "Should have children")
+
+      nodes = []
+      @root.each { |node| nodes << node }
+
+      assert_equal(5, nodes.length, "Should have FIVE NODES")
+      assert(nodes.include?(@root), "Should have root")
+      assert(nodes.include?(@child1), "Should have child 1")
+      assert(nodes.include?(@child2), "Should have child 2")
+      assert(nodes.include?(@child3), "Should have child 3")
+      assert(nodes.include?(@child4), "Should have child 4")
+    end
+
+    def test_each_leaf
+      loadChildren
+
+      nodes = []
+      @root.each_leaf { |node| nodes << node }
+
+      assert_equal(3, nodes.length, "Should have THREE LEAF NODES")
+      assert(!nodes.include?(@root), "Should not have root")
+      assert(nodes.include?(@child1), "Should have child 1")
+      assert(nodes.include?(@child2), "Should have child 2")
+      assert(!nodes.include?(@child3), "Should not have child 3")
+      assert(nodes.include?(@child4), "Should have child 4")
+    end
+
+    def test_parent
+      loadChildren
+      assert_nil(@root.parent, "Root's parent should be nil")
+      assert_equal(@root, @child1.parent, "Parent should be root")
+      assert_equal(@root, @child3.parent, "Parent should be root")
+      assert_equal(@child3, @child4.parent, "Parent should be child3")
+      assert_equal(@root, @child4.parent.parent, "Parent should be root")
+    end
+
+    def test_indexed_access
+      loadChildren
+      assert_equal(@child1, @root[0], "Should be the first child")
+      assert_equal(@child4, @root[2][0], "Should be the grandchild")
+      assert_nil(@root["TEST"], "Should be nil")
+      assert_raise(RuntimeError) { @root[nil] }
+    end
+
+    def test_printTree
+      loadChildren
+      #puts
+      #@root.printTree
+    end
+
+    # Tests the binary dumping mechanism with an Object content node
+    def test_marshal_dump
+      # Setup Test Data
+      test_root = Tree::TreeNode.new("ROOT", "Root Node")
+      test_content = {"KEY1" => "Value1", "KEY2" => "Value2" }
+      test_child      = Tree::TreeNode.new("Child", test_content)
+      test_content2 = ["AValue1", "AValue2", "AValue3"]
+      test_grand_child = Tree::TreeNode.new("Grand Child 1", test_content2)
+      test_root << test_child << test_grand_child
+
+      # Perform the test operation
+      data = Marshal.dump(test_root) # Marshal
+      new_root = Marshal.load(data)  # And unmarshal
+
+      # Test the root node
+      assert_equal(test_root.name, new_root.name, "Must identify as ROOT")
+      assert_equal(test_root.content, new_root.content, "Must have root's content")
+      assert(new_root.isRoot?, "Must be the ROOT node")
+      assert(new_root.hasChildren?, "Must have a child node")
+
+      # Test the child node
+      new_child = new_root[test_child.name]
+      assert_equal(test_child.name, new_child.name, "Must have child 1")
+      assert(new_child.hasContent?, "Child must have content")
+      assert(new_child.isOnlyChild?, "Child must be the only child")
+
+      new_child_content = new_child.content
+      assert_equal(Hash, new_child_content.class, "Class of child's content should be a hash")
+      assert_equal(test_child.content.size, new_child_content.size, "The content should have same size")
+
+      # Test the grand-child node
+      new_grand_child = new_child[test_grand_child.name]
+      assert_equal(test_grand_child.name, new_grand_child.name, "Must have grand child")
+      assert(new_grand_child.hasContent?, "Grand-child must have content")
+      assert(new_grand_child.isOnlyChild?, "Grand-child must be the only child")
+
+      new_grand_child_content = new_grand_child.content
+      assert_equal(Array, new_grand_child_content.class, "Class of grand-child's content should be an Array")
+      assert_equal(test_grand_child.content.size, new_grand_child_content.size, "The content should have same size")
+    end
+
+    # marshal_load and marshal_dump are symmetric methods
+    # This alias is for satisfying ZenTest
+    alias test_marshal_load test_marshal_dump
+
+    # Test the collect method from the mixed-in Enumerable functionality.
+    def test_collect
+      loadChildren
+      collectArray = @root.collect do |node|
+        node.content = "abc"
+        node
+      end
+      collectArray.each {|node| assert_equal("abc", node.content, "Should be 'abc'")}
+    end
+
+    # Test freezing the tree
+    def test_freezeTree_bang
+      loadChildren
+      @root.content = "ABC"
+      assert_equal("ABC", @root.content, "Content should be 'ABC'")
+      @root.freezeTree!
+      assert_raise(TypeError) {@root.content = "123"}
+      assert_raise(TypeError) {@root[0].content = "123"}
+    end
+
+    # Test whether the content is accesible
+    def test_content
+      pers = Person::new("John", "Doe")
+      @root.content = pers
+      assert_same(pers, @root.content, "Content should be the same")
+    end
+
+    # Test the depth computation algorithm
+    def test_depth
+      assert_equal(1, @root.depth, "A single node's depth is 1")
+
+      @root << @child1
+      assert_equal(2, @root.depth, "This should be of depth 2")
+
+      @root << @child2
+      assert_equal(2, @root.depth, "This should be of depth 2")
+
+      @child2 << @child3
+      assert_equal(3, @root.depth, "This should be of depth 3")
+      assert_equal(2, @child2.depth, "This should be of depth 2")
+
+      @child3 << @child4
+      assert_equal(4, @root.depth, "This should be of depth 4")
+    end
+
+    # Test the breadth computation algorithm
+    def test_breadth
+      assert_equal(1, @root.breadth, "A single node's breadth is 1")
+
+      @root << @child1
+      assert_equal(1, @root.breadth, "This should be of breadth 1")
+
+      @root << @child2
+      assert_equal(2, @child1.breadth, "This should be of breadth 2")
+      assert_equal(2, @child2.breadth, "This should be of breadth 2")
+
+      @root << @child3
+      assert_equal(3, @child1.breadth, "This should be of breadth 3")
+      assert_equal(3, @child2.breadth, "This should be of breadth 3")
+
+      @child3 << @child4
+      assert_equal(1, @child4.breadth, "This should be of breadth 1")
+    end
+
+    # Test the breadth for each
+    def test_breadth_each
+      j = Tree::TreeNode.new("j")
+      f = Tree::TreeNode.new("f")
+      k = Tree::TreeNode.new("k")
+      a = Tree::TreeNode.new("a")
+      d = Tree::TreeNode.new("d")
+      h = Tree::TreeNode.new("h")
+      z = Tree::TreeNode.new("z")
+
+      # The expected order of response
+      expected_array = [j,
+                        f, k,
+                        a, h, z,
+                        d]
+
+      # Create the following Tree
+      #        j         <-- level 0 (Root)
+      #      /   \
+      #     f      k     <-- level 1
+      #   /   \      \
+      #  a     h      z  <-- level 2
+      #   \
+      #    d             <-- level 3
+      j << f << a << d
+      f << h
+      j << k << z
+
+      # Create the response
+      result_array = Array.new
+      j.breadth_each { |node| result_array << node.detached_copy }
+
+      expected_array.each_index do |i|
+        assert_equal(expected_array[i].name, result_array[i].name)      # Match only the names.
+      end
+    end
+
+
+    def test_preordered_each
+      j = Tree::TreeNode.new("j")
+      f = Tree::TreeNode.new("f")
+      k = Tree::TreeNode.new("k")
+      a = Tree::TreeNode.new("a")
+      d = Tree::TreeNode.new("d")
+      h = Tree::TreeNode.new("h")
+      z = Tree::TreeNode.new("z")
+
+      # The expected order of response
+      expected_array = [j, f, a, d, h, k, z]
+
+      # Create the following Tree
+      #        j         <-- level 0 (Root)
+      #      /   \
+      #     f      k     <-- level 1
+      #   /   \      \
+      #  a     h      z  <-- level 2
+      #   \
+      #    d             <-- level 3
+      j << f << a << d
+      f << h
+      j << k << z
+
+      result_array = []
+      j.preordered_each { |node| result_array << node.detached_copy}
+
+      expected_array.each_index do |i|
+        # Match only the names.
+        assert_equal(expected_array[i].name, result_array[i].name)
+      end
+    end
+
+    def test_detached_copy
+      loadChildren
+
+      assert(@root.hasChildren?, "The root should have children")
+      copy_of_root = @root.detached_copy
+      assert(!copy_of_root.hasChildren?, "The copy should not have children")
+      assert_equal(@root.name, copy_of_root.name, "The names should be equal")
+
+      # Try the same test with a child node
+      assert(!@child3.isRoot?, "Child 3 is not a root")
+      assert(@child3.hasChildren?, "Child 3 has children")
+      copy_of_child3 = @child3.detached_copy
+      assert(copy_of_child3.isRoot?, "Child 3's copy is a root")
+      assert(!copy_of_child3.hasChildren?, "Child 3's copy does not have children")
+    end
+
+    def test_hasChildren_eh
+      loadChildren
+      assert(@root.hasChildren?, "The Root node MUST have children")
+    end
+
+    def test_isLeaf_eh
+      loadChildren
+      assert(!@child3.isLeaf?, "Child 3 is not a leaf node")
+      assert(@child4.isLeaf?, "Child 4 is a leaf node")
+    end
+
+    def test_isRoot_eh
+      loadChildren
+      assert(@root.isRoot?, "The ROOT node must respond as the root node")
+    end
+
+    def test_content_equals
+      @root.content = nil
+      assert_nil(@root.content, "Root's content should be nil")
+      @root.content = "ABCD"
+      assert_equal("ABCD", @root.content, "Root's content should now be 'ABCD'")
+    end
+
+    def test_size
+      assert_equal(1, @root.size, "Root's size should be 1")
+      loadChildren
+      assert_equal(5, @root.size, "Root's size should be 5")
+      assert_equal(2, @child3.size, "Child 3's size should be 2")
+    end
+
+    def test_lt2                # Test the << method
+      @root << @child1
+      @root << @child2
+      @root << @child3 << @child4
+      assert_not_nil(@root['Child1'], "Child 1 should have been added to Root")
+      assert_not_nil(@root['Child2'], "Child 2 should have been added to Root")
+      assert_not_nil(@root['Child3'], "Child 3 should have been added to Root")
+      assert_not_nil(@child3['Child31'], "Child 31 should have been added to Child3")
+    end
+
+    def test_index              #  Test the [] method
+      assert_raise(RuntimeError) {@root[nil]}
+
+      @root << @child1
+      @root << @child2
+      assert_equal(@child1.name, @root['Child1'].name, "Child 1 should be returned")
+      assert_equal(@child1.name, @root[0].name, "Child 1 should be returned")
+      assert_equal(@child2.name, @root['Child2'].name, "Child 2 should be returned")
+      assert_equal(@child2.name, @root[1].name, "Child 2 should be returned")
+
+      assert_nil(@root['Some Random Name'], "Should return nil")
+      assert_nil(@root[99], "Should return nil")
+    end
+  end
+end
+
+__END__
+
+# $Log: test_tree.rb,v $
+# Revision 1.6  2007/12/22 00:28:59  anupamsg
+# Added more test cases, and enabled ZenTest compatibility.
+#
+# Revision 1.5  2007/12/19 02:24:18  anupamsg
+# Updated the marshalling logic to handle non-string contents on the nodes.
+#
+# Revision 1.4  2007/10/02 03:38:11  anupamsg
+# Removed dependency on the redundant "Person" class.
+# (TC_TreeTest::test_comparator): Added a new test for the spaceship operator.
+# (TC_TreeTest::test_hasContent): Added tests for hasContent? and length methods.
+#
+# Revision 1.3  2007/10/02 03:07:30  anupamsg
+# * Rakefile: Added an optional task for rcov code coverage.
+#
+# * test/test_binarytree.rb: Removed the unnecessary dependency on "Person" class.
+#
+# * test/test_tree.rb: Removed dependency on the redundant "Person" class.
+#
+# Revision 1.2  2007/08/31 01:16:28  anupamsg
+# Added breadth and pre-order traversals for the tree. Also added a method
+# to return the detached copy of a node from the tree.
+#
+# Revision 1.1  2007/07/21 04:52:38  anupamsg
+# Renamed the test files.
+#
+# Revision 1.13  2007/07/18 22:11:50  anupamsg
+# Added depth and breadth methods for the TreeNode.
+#
+# Revision 1.12  2007/07/18 07:17:34  anupamsg
+# Fixed a  issue where TreeNode.ancestors was shadowing Module.ancestors. This method
+# has been renamed to TreeNode.parentage.
+#
+# Revision 1.11  2007/07/17 03:39:29  anupamsg
+# Moved the CVS Log keyword to end of the files.
+#