diff options
author | drbrain <drbrain@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2013-10-11 21:35:01 +0000 |
---|---|---|
committer | drbrain <drbrain@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2013-10-11 21:35:01 +0000 |
commit | 9cadc95b28da1cf6ca8f802292d12cc96a4f2c2d (patch) | |
tree | 73280968d3426b31c5d0b9da1d3e558aa6f9fcb9 /lib/rake/linked_list.rb | |
parent | 52c1331763d8b9b8d6362987e6f8847b65ed7f57 (diff) | |
download | ruby-9cadc95b28da1cf6ca8f802292d12cc96a4f2c2d.tar.gz |
* NEWS (with all sufficient information):
* lib/rake: Update to rake 10.1.0
* bin/rake: ditto.
* test/rake: ditto.
* NEWS: Update NEWS to include rake 10.1.0 and links to release notes.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@43264 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'lib/rake/linked_list.rb')
-rw-r--r-- | lib/rake/linked_list.rb | 103 |
1 files changed, 103 insertions, 0 deletions
diff --git a/lib/rake/linked_list.rb b/lib/rake/linked_list.rb new file mode 100644 index 0000000000..26483703f4 --- /dev/null +++ b/lib/rake/linked_list.rb @@ -0,0 +1,103 @@ +module Rake + + # Polylithic linked list structure used to implement several data + # structures in Rake. + class LinkedList + include Enumerable + + attr_reader :head, :tail + + def initialize(head, tail=EMPTY) + @head = head + @tail = tail + end + + # Polymorphically add a new element to the head of a list. The + # type of head node will be the same list type has the tail. + def conj(item) + self.class.cons(item, self) + end + + # Is the list empty? + def empty? + false + end + + # Lists are structurally equivalent. + def ==(other) + current = self + while ! current.empty? && ! other.empty? + return false if current.head != other.head + current = current.tail + other = other.tail + end + current.empty? && other.empty? + end + + # Convert to string: LL(item, item...) + def to_s + items = map { |item| item.to_s }.join(", ") + "LL(#{items})" + end + + # Same as +to_s+, but with inspected items. + def inspect + items = map { |item| item.inspect }.join(", ") + "LL(#{items})" + end + + # For each item in the list. + def each + current = self + while ! current.empty? + yield(current.head) + current = current.tail + end + self + end + + # Make a list out of the given arguments. This method is + # polymorphic + def self.make(*args) + result = empty + args.reverse_each do |item| + result = cons(item, result) + end + result + end + + # Cons a new head onto the tail list. + def self.cons(head, tail) + new(head, tail) + end + + # The standard empty list class for the given LinkedList class. + def self.empty + self::EMPTY + end + + # Represent an empty list, using the Null Object Pattern. + # + # When inheriting from the LinkedList class, you should implement + # a type specific Empty class as well. Make sure you set the class + # instance variable @parent to the assocated list class (this + # allows conj, cons and make to work polymorphically). + class EmptyLinkedList < LinkedList + @parent = LinkedList + + def initialize + end + + def empty? + true + end + + def self.cons(head, tail) + @parent.cons(head, tail) + end + end + + EMPTY = EmptyLinkedList.new + end + +end |