# Copyright (c) 2010-2011 David Love
#
# Permission to use, copy, modify, and/or distribute this software for 
# any purpose with or without fee is hereby granted, provided that the 
# above copyright notice and this permission notice appear in all copies.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 
# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 
# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 
# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 
# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 
# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 
# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
#

# @author David Love

module WhiteCloth::DataStructures
  
  # The {StandardTree} is, as the name implies, the basic data structure for a realm. 
  # All mutations operate over a {StandardTree}, and all projections to and from the 
  # void create or imply a {StandardTree} as a result.
  class StandardTree
    
    ###
    ### Constructors
    ###
    
    # Default constructor. Create a new tree, with a single node at the root.
    def initialize(root_id = nil)
      # Create the root id from supplied +root_id+, or a random one if the
      # +root_id+ is missing
      unless root_id.nil?
        begin
          @root_id = UUIDTools::UUID.parse(root_id)
        rescue
          @root_id = UUIDTools::UUID.random_create
        end
      else
        @root_id = UUIDTools::UUID.random_create
      end
      @next_id = @root_id.next 
      
      # Create the root node for the tree
      @nodes = StandardNode.new(@root_id.to_s, nil)
    end
    
    ###
    ### Operators
    ###
    
    # Adds the specified nodes to the tree. The +node_list+ is a block, which is taken
    # to be a hash of node names/node identities and the contents to add to the identified
    # nodes. If the +block_name+ is +nil+ or +ROOT+, than we add to the root of the tree.
    #
    # @note: Since the argument list is a {Hash}, each node in the list *must* be unique.
    # Otherwise later arguments will override earlier ones, and you *will not* get the
    # behaviour you think.
    def << (node_list)
      Hash[*node_list.flatten].each{|parent, contents|
        add_child(parent, contents)
      }
    end
    
    # Look for the designated block within tree starting at the current node. If the 
    # +block_name+ is +nil+ or +ROOT+, than we add to the root of the tree.
    def [] (block_name)
      return @nodes[block_name]
    end
    
    ###
    ### Helper functions
    ###
    
    # Adds a new node to the tree, below the +parent+ node and with the specified
    # +contents+.
    def add_child(parent, contents)
      
      # Find the parent node
      if parent.nil? then
        # Add to the root node
        @nodes << StandardNode.new(@next_id.to_s, contents)
      else
        # Add to the relevant node
        @nodes[parent] << StandardNode.new(@next_id.to_s, contents)
      end
      
      # Increment the node index
      @next_id = @next_id.next
      
    end
    
    ###
    ### Query functions
    ###
    
    # Is the tree 'empty' (i.e. it has only the root node)?
    def empty?
      return !@nodes.has_children?
    end
    
  end
  
end