diff options
author | Jari Vetoniemi <jari.vetoniemi@indooratlas.com> | 2020-03-16 18:49:26 +0900 |
---|---|---|
committer | Jari Vetoniemi <jari.vetoniemi@indooratlas.com> | 2020-03-30 00:39:06 +0900 |
commit | fcbf63e62c627deae76c1b8cb8c0876c536ed811 (patch) | |
tree | 64cb17de3f41a2b6fef2368028fbd00349946994 /jni/ruby/lib/rake/linked_list.rb |
Fresh start
Diffstat (limited to 'jni/ruby/lib/rake/linked_list.rb')
-rw-r--r-- | jni/ruby/lib/rake/linked_list.rb | 103 |
1 files changed, 103 insertions, 0 deletions
diff --git a/jni/ruby/lib/rake/linked_list.rb b/jni/ruby/lib/rake/linked_list.rb new file mode 100644 index 0000000..b5ab797 --- /dev/null +++ b/jni/ruby/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 as 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 associated 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 |