README.md

Iterating Iteratively

Given a forward linked list, define an iterator wich traverses each node in the linked list calling next function repeatively?

linked_list_iterate_iteratively.coffee

class Node
  constructor: (@value) ->
    @iterator = new Iterator(this)
    @children = []
    

class Iterator
  constructor: (@rootNode) ->
    @curNode = @rootNode
    @parentNode = []

  next: () ->
    if @curNode.children.length > 0
      @parentNode.push(@curNode)
      @curNode = @curNode.children[0]
      return @curNode
    else 
      return @curNodeParentNext()

  curNodeParentNext: () ->
    return null if @parentNode.length == 0
    lastParentNode = @parentNode[@parentNode.length - 1]
    indexOfCurNode = lastParentNode.children.indexOf(@curNode)
    if lastParentNode.children.length - 1 > indexOfCurNode
      @curNode = lastParentNode.children[indexOfCurNode + 1]
      return @curNode
    else
      @curNode = @parentNode.pop()
      return @curNodeParentNext()
    
    
      

node0 = new Node(0)
node1 = new Node(1)
node2 = new Node(2)
node0.children.push(node1)
node0.children.push(node2)


node1.children.push(new Node(3))
node1.children.push(new Node(4))
node2.children.push(new Node(5))
node2.children.push(new Node(6))
node2.children.push(new Node(7))


loop
  nextNode = node0.iterator.next()
  break if nextNode == null
  console.log(nextNode.value)

###
outpus:
1
3
4
2
5
6
7
###

linked_list_iterate_iteratively.rb

#using ruby 2.0.0
require 'fiber'

class Node
  attr :value
  attr_accessor :children
  attr :iterator

  def initialize value
    @value = value
  end

  def next
    if @iterator.nil? # first time this is called
      @iterator = Fiber.new do
        self.next_child
      end
    end
    return @iterator.alive? ? @iterator.resume : nil
  end
  def next_child
    @children.each do |child|
        Fiber.yield child
        child.next_child
    end unless @children.nil?
    return nil
  end
end


node0 = Node.new(0)

node0.children = [ (node1 = Node.new(1)), (node2 = Node.new(2))]
node1.children = [ Node.new(3), Node.new(4)]
node2.children = [ Node.new(5), Node.new(6), Node.new(7)]


begin
  next_node = node0.next
  puts next_node.value unless next_node.nil?
end while !next_node.nil?

=begin
outputs:
1
3
4
2
5
6
7
=end