Code Excursion

Algorithmathon Day 8: Double Linked List Unflattening

On Day 8 we will be unflattening the Double Linked List (DoLL) that we flattened on Day 7 of the Algorithmathon. As always we will be following the Rules of Algorithmathon. For your viewing pleasure the source code is also available. How do we go about achieving this unflattening? It seems likely, what we need to do is to reverse the flattening process.

We should be able to reuse our test that verified our helper methods to help us write our first test.

double_linked_list_spec.rb (excerpt)

# code omitted here
    it "should have method 'unflatten!'" do
      DoubleLinkedList.method_defined?(:element_at).should be_true
    end  
# code omitted here
    it "should have the correct non flat list when the 'unflatten!' method is called." do
      list = build_master_list()
      list.flatten!()
      list.unflatten!()
      list.length().should == 12
      list.element_at(0).child.length().should == 6
      list.element_at(0).child.last().child.length().should == 8
      list.element_at(4).child.length().should == 8
      list.element_at(4).child.element_at(2).child.length().should == 8
      list.element_at(11).child.length().should == 3
      list.element_at(11).child.element_at(0).child.length().should == 6
    end

# code omitted here

To try to grasp how we might solve this problem we can list out the rules we used for flattening the list.

• Starting at the head check each element for a child
• If the element has a child
  • link the child elements into the top list.
  • Return to step 1 with the child list’s first element as a target.
• Continue to the next element. (Which will be the first element in the child list if one existed)

What needs to be done to reverse this process? Well we should probably start at the beginning much like the flattening process.

• Starting at the head check each element for a child
• If the element has a child
  • unlink the child elements from the top list.
  • Return to step 1 with the child list’s first element as a target.
• Continue to the next element. (Which will be the element after the last element in the child list if one existed)

While it sounds correct this plan will prove ultimately futile. When we flattened our list we started at the bottom and worked our way up. If we reverse this process we need to start at the top and work our way down. It would look something more like this.

• Starting at the head check each element for a child
• If the element has a child goto step 1 with the child’s first element as a target.
• Make the elements next node equal to the next node of the last element of the child list.
• Continue to the next element. (Which will be the element after the last element in the child list if one existed)

In this case the code seems easier to understand than the aforementioned steps.

double_linked_list.rb (excerpt)

# code omitted here
  def unflatten!()
    unflatten_by_recursion(@head)
  end
# code omitted here
  def unflatten_by_recursion(element)
    unless element.nil?
      if element.child.nil?
        unflatten_by_recursion(element.next_node)
      else
        unflatten_by_recursion(element.child.element_at(0))        
        @length = @length - element.child.length()
        element.next_node=element.child.last.next_node        
      end
    end
  end
# code omitted here

Tomorrow we will start our first foray into Trees and Graphs.