Redmine

  config.gem 'rubytree', :lib => 'tree'

config.gem "shoulda"

config.gem "edavis10-object_daddy", :lib => "object_daddy"

config.gem "mocha"

--- !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

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.

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.

= 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.

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

   __       _           _

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

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

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

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

                  |___/

  (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 $)

# 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.

#

# -*- 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.

# 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.

#

# 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 $