Feature #5638 » bundler-for-redmine.patch
| Gemfile | ||
|---|---|---|
|
source :rubygems
|
||
|
gem "bundler", "0.9.25"
|
||
|
gem "rails", "2.3.5"
|
||
|
gem "rack", "1.0.1"
|
||
|
gem "rubytree", "0.5.2", :require => "tree"
|
||
|
gem "RedCloth", "~>4.2.3", :require => "redcloth" # for CodeRay
|
||
|
# Please uncomment lines for your databases.
|
||
|
# Alternatively you may want to add these lines to specific groups below.
|
||
|
# gem "sqlite3-ruby", :require => "sqlite3" # for SQLite 3
|
||
|
# gem "mysql" # MySQL
|
||
|
# gem "pg" # PostgreSQL
|
||
|
group :development do
|
||
|
end
|
||
|
group :production do
|
||
|
end
|
||
|
group :test do
|
||
|
gem "shoulda"
|
||
|
gem "mocha", :require => nil # ":require => nil" fixes obscure bugs - remote and run all tests
|
||
|
gem "edavis10-object_daddy", :require => "object_daddy"
|
||
|
end
|
||
|
# Load plugins' Gemfiles
|
||
|
Dir.glob(File.join(File.dirname(__FILE__), %w(vendor plugins * Gemfile))) do |file|
|
||
|
puts "Loading #{file} ..."
|
||
|
instance_eval File.read(file)
|
||
|
end
|
||
| config/boot.rb | ||
|---|---|---|
|
end
|
||
|
end
|
||
|
# Bundler
|
||
|
class Rails::Boot
|
||
|
def run
|
||
|
load_initializer
|
||
|
Rails::Initializer.class_eval do
|
||
|
def load_gems
|
||
|
@bundler_loaded ||= Bundler.require :default, Rails.env.to_sym
|
||
|
end
|
||
|
end
|
||
|
Rails::Initializer.run(:set_load_path)
|
||
|
end
|
||
|
end
|
||
|
# All that for this:
|
||
|
Rails.boot!
|
||
| config/environment.rb | ||
|---|---|---|
|
# It will automatically turn deliveries on
|
||
|
config.action_mailer.perform_deliveries = false
|
||
|
config.gem 'rubytree', :lib => 'tree'
|
||
|
# No 'config.gem' there, please use Gemfile instead.
|
||
|
|
||
|
# Load any local configuration that is kept out of source control
|
||
|
# (e.g. gems, patches).
|
||
| config/environments/test.rb | ||
|---|---|---|
|
# Skip protect_from_forgery in requests http://m.onkey.org/2007/9/28/csrf-protection-for-your-existing-rails-application
|
||
|
config.action_controller.allow_forgery_protection = false
|
||
|
config.gem "shoulda"
|
||
|
config.gem "edavis10-object_daddy", :lib => "object_daddy"
|
||
|
config.gem "mocha"
|
||
|
# No 'config.gem' there, please use Gemfile instead.
|
||
| config/preinitializer.rb | ||
|---|---|---|
|
# Bundler
|
||
|
begin
|
||
|
# Require the preresolved locked set of gems.
|
||
|
require File.expand_path('../../.bundle/environment', __FILE__)
|
||
|
rescue LoadError
|
||
|
# Fallback on doing the resolve at runtime.
|
||
|
require "rubygems"
|
||
|
require "bundler"
|
||
|
ENV["BUNDLE_GEMFILE"] = File.expand_path("../../Gemfile", __FILE__)
|
||
|
Bundler.setup
|
||
|
end
|
||
| vendor/gems/rubytree-0.5.2/.specification | ||
|---|---|---|
|
--- !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
|
||
| vendor/gems/rubytree-0.5.2/COPYING | ||
|---|---|---|
|
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.
|
||
| vendor/gems/rubytree-0.5.2/ChangeLog | ||
|---|---|---|
|
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.
|
||
| vendor/gems/rubytree-0.5.2/History.txt | ||
|---|---|---|
|
= 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.
|
||
| vendor/gems/rubytree-0.5.2/Manifest.txt | ||
|---|---|---|
|
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
|
||
| vendor/gems/rubytree-0.5.2/README | ||
|---|---|---|
|
|
||
|
__ _ _
|
||
|
/__\_ _| |__ _ _| |_ _ __ ___ ___
|
||
|
/ \// | | | '_ \| | | | __| '__/ _ \/ _ \
|
||
|
/ _ \ |_| | |_) | |_| | |_| | | __/ __/
|
||
|
\/ \_/\__,_|_.__/ \__, |\__|_| \___|\___|
|
||
|
|___/
|
||
|
|
||
|
(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 $)
|
||
| vendor/gems/rubytree-0.5.2/Rakefile | ||
|---|---|---|
|
# 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.
|
||
|
#
|
||
| vendor/gems/rubytree-0.5.2/TODO | ||
|---|---|---|
|
# -*- 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.
|
||
| vendor/gems/rubytree-0.5.2/lib/tree.rb | ||
|---|---|---|
|
# 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.
|
||
|
#
|
||
| vendor/gems/rubytree-0.5.2/lib/tree/binarytree.rb | ||
|---|---|---|
|
# 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 $
|
||