ActsAsGenetree
==============

   a) A hierarchical object is an object which has a parent hierarchical object.
      Hence, there can be a tree of hierarchical objects.

   b) Given a tree of hierarchical objects, each object can answer the following questions:
      1) What is the subtree rooted under this hierarchical object?
      2) What is the ordered list of ancestor objects for this hierarchical object?
      3) What are the sibiling hierarchical objects of this hierarchical object?
      4) What is the depth of this hierarchical objects in its tree?

   c) An implementation of a tree data structure using a relational database would have to address
      two issues related to each object:
      1) The object's identification
      2) The object's position in the tree

      In the current implementation:
      1) The primary key field is used to unquiely identify the object.
      2) The sortkey field stores the "genelogical order" of an object, as described in Miguel Sofer's paper.
      3) The sortkey is not derived from the object's primary key identifier (unlike as described in
         Sofer's paper).
      4) The sortkey is a base159 encoded string. Lexical ordering of sortkeys forms the basis for
         representing the tree. Tree operations can be performed using lexical comparsions or substring
         operations on the sortkey.

      5) To after installing the plugin run the generator to create the tree_encodings migrations.
         shell$ ./script/generate acts_as_genetree  create_tree_encoding
         After this run the migration that was created.

Example
=======

      1) A simple exmaple class:

       Create the table which will hold the hierarchical records. It should at least have a primary key and
       the fllowing columns:
        a) parent_id - type integer
        b) sortkey - type text

       Example migration:
        create_table :hierarchical_objects, :force => true do |t|
          t.column :parent_id, :integer
          t.column :sortkey, :text
        end

       Example model class:
         class HierarchicalObject < ActiveRecord::Base
           acts_as_genetree
         end

       Refer to the following files in the plugin dir:
         db/schema.rb
         spec/hobj_spec.rb 
         spec/tree_encodings_spec.rb 

      2) Creating a root object:

      root = HierarchicalObject.new
      root.id = 1999
      saved_p = root.save

      3) Creating a child object:

      node2 = HierarchicalObject.new
      node2.id = 2876
      node2.parent_id = 1999
      node2.save

      node3 = HierarchicalObject.new
      node3.id = 2877
      node3.parent_id = 1999
      node3.save

      Upon execution of above, we would have the following rows:

      mysql> select * from hierarchical_objects order by sortkey;
      +------+-----------+--------------+
      | id   | parent_id | sortkey      |
      +------+-----------+--------------+
      | 1999 |      NULL | /00          | 
      | 2876 |      1999 | /00/00       | 
      | 2877 |      1999 | /00/01       | 
      +------+-----------+--------------+

      Notice, how the sortkey holds both the depth and the ordering of a record.

      4) To delete a (sub)tree we can do the following:

      HierarchicalObject.find( 1999 ).subtree.reverse.each {
        |obj|
        obj.destroy
      }

      5) We can also iterate through the ordered list of ancestors:

      HierarchicalObject.find( 21 ).ancestors.each {
        |obj|
        .....
      }

Running specs
=============
      1) Edit vendor/plugins/acts_as_genetree/db/database.yml as required.
      2) spec ./spec/tree_encodings_spec.rb
         spec ./spec/hobj_spec.rb

Notes
=====

      1) When using with rails 2.2.2 we get the following warning:

DEPRECATION WARNING: String#chars has been deprecated in favor of String#mb_chars.. (called from mvgid_base159_incr at (eval):44)

      If you want to avoid this warning, I suggest you replace the occurences of calls to chars with mb_chars in lib/genetree/acts_as_genetree.rb. (Replacing chars with mb_chars in the repository would mean the plugin would break in pre 2.2.2 versions)

Copyright (c) 2008 gautam.chekuri@gmail.com, released under the MIT licence