Java Collections – Sorting Problem

One of my hot favorite topic is sorting.
Description of the problem:
1) Imagine a line of containers which are going to be loaded onto the ship. Assume the desired loading sequence is 1,2,3 eg C1 C2 C3 C4 C5 C6

2) A Container class is has a sequence method .getSeq(). So lets say for C1,
container.getSeq() == 1 For C2, container.getSeq() == 2

If we have an array list:
final List containers = new ArrayList(Arrays.asList(C2, C1, C6, C5, C4, C3));

How do we sort this list? So it’s C1, C2, C3, C4, C5, C6?

Part 2:
Lets say containers in the stack are like:

On top of C2, container C6 is there. we can not lift C2 before lifting the C6.

So C6 must be lifted before C2 – so for this case only C6 must go before C2.

There is a method in the Container class container.getAboveMe()
So for C2, container.getAboveMe() returns a container whitch is C6.

For C1, C2, C3, C4 and C5 container.getAboveMe() returns null.

Similarly getAboveMe(), another method getBelowMe() so for C6.
container.getBelowMe() returns a container which is C2 – every thing else getBelowMe returns null

Java Source Codes :
Container.java

public class Container {
    public Container(final int inSequence) {
        _sequence = inSequence;
        _aboveMe = null;
        _belowMe = null;
    }

    @Override
    public String toString() {
        return String.valueOf(getSequence());
    }
    public int getSequence() {
        return _sequence;
    }
    public void setAboveMe(final Container inAboveMe) {
        _aboveMe = inAboveMe;
    }
    public void setBelowMe(final Container inBelowMe) {
        _belowMe = inBelowMe;
    }

    public Container getAboveMe() {
        return _aboveMe;
    }
    public Container getBelowMe() {
        return _belowMe;
    }

    private final int _sequence;
    private Container _belowMe;
    private Container _aboveMe;
}

SortContainers.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class SortContainers {

    public static void doSort( List containers ) {

        //Remove all null values from the list
        containers.removeAll(Collections.singleton(null));
        Collections.sort(containers, new Comparator() {
            public int compare(final Container c1, final Container c2) {

                if (c1.getAboveMe()!= null && c1.getAboveMe().equals(c2)) {
                    return 1;
                }
                if (c2.getAboveMe()!= null && c2.getAboveMe().equals(c1)) {
                    return -1;
                }

                int c1Value = c1.getSequence();
                int c2Value = c2.getSequence();
                if (c1.getBelowMe() != null) {
                    c1Value = c1.getBelowMe().getSequence();
                }
                if (c2.getBelowMe() != null) {
                    c2Value = c2.getBelowMe().getSequence();
                }
                return c1Value - c2Value;
            }
        });
    }
}

I like Test Driven Development,
I have use cases for this example.

SortContainers.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import org.testng.annotations.Test;
import static org.junit.Assert.assertEquals;

public class SortContainersSaTest {

    @Test
    public void testSortContainersCase1() {
        final Container C1 = new Container(1);
        final Container C2 = new Container(2);
        final Container C3 = new Container(3);
        final Container C4 = new Container(4);
        final Container C5 = new Container(5);
        final Container C6 = new Container(6);

        final List containers = new ArrayList(Arrays.asList(C2, C1, C6, C5, C4, C3));
        SortContainers.doSort( containers );
        final List expectedContainers = 
new ArrayList(Arrays.asList(C1, C2, C3, C4, C5, C6));
        assertEquals( expectedContainers , containers );
    }

    @Test
    public void testSortContainersCase2() {
        final Container C1 = new Container(1);
        final Container C2 = new Container(2);
        final Container C3 = new Container(3);
        final Container C4 = new Container(4);
        final Container C5 = new Container(5);
        final Container C6 = new Container(6);

        C6.setBelowMe(C2);
        C2.setAboveMe(C6);

        final List containers = new ArrayList(Arrays.asList(C2, C1, C6, C5, C4, C3));
        SortContainers.doSort( containers );
        final List expectedContainers = new ArrayList(Arrays.asList(C1, C6, C2, C3, C4, C5));
        assertEquals( expectedContainers , containers );
    }

    @Test
    public void testSortContainersCase3() {
        final Container C1 = new Container(1);
        final Container C2 = new Container(2);
        final Container C3 = new Container(3);
        final Container C4 = new Container(4);
        final Container C5 = new Container(5);
        final Container C6 = new Container(6);
        final Container C7 = new Container(7);

        C6.setBelowMe(C2);
        C2.setAboveMe(C6);

        C7.setBelowMe(C4);
        C4.setAboveMe(C7);

        final List containers = 
new ArrayList(Arrays.asList(C2, C1, C6, C7, C5, C4, C3));
        SortContainers.doSort( containers );
        final List expectedContainers = 
new ArrayList(Arrays.asList(C1, C6, C2, C3, C7, C4, C5));
        assertEquals( expectedContainers , containers );
    }

    @Test
     public void testSortContainersCase4() {
        final Container C1 = new Container(1);
        final Container C2 = new Container(2);
        final Container C3 = new Container(3);
        final Container C4 = new Container(4);
        final Container C5 = new Container(5);
        final Container C6 = new Container(6);
        final Container C7 = new Container(7);

        C6.setBelowMe(C2);
        C2.setAboveMe(C6);

        C4.setBelowMe(C7);
        C7.setAboveMe(C4);

        final List containers = 
                              new ArrayList(Arrays.asList(C2, C1, C6, C7, C5, C4, C3));
        SortContainers.doSort( containers );
        final List expectedContainers = 
                              new ArrayList(Arrays.asList(C1, C6, C2, C3, C5, C4, C7));
        assertEquals( expectedContainers , containers );
    }

    @Test
    public void testSortContainersCase5() {
        final Container C1 = new Container(1);
        final Container C2 = new Container(2);
        final Container C3 = new Container(3);
        final Container C4 = new Container(4);
        final Container C5 = new Container(5);
        final Container C6 = new Container(6);
        final Container C7 = new Container(7);

        C6.setBelowMe(C1);
        C1.setAboveMe(C6);

        final List containers = 
                              new ArrayList(Arrays.asList(C2, C1, C6, C7, C5, C4, C3));
        SortContainers.doSort( containers );
        final List expectedContainers = 
                              new ArrayList(Arrays.asList(C6, C1, C2, C3, C4, C5, C7));
        assertEquals( expectedContainers , containers );
    }

    @Test
    public void testSortContainersCase6() {
        final Container C1 = new Container(1);
        final Container C2 = new Container(2);
        final Container C3 = new Container(3);
        final Container C4 = new Container(4);
        final Container C5 = new Container(5);
        final Container C6 = new Container(6);
        final Container C7 = new Container(7);

        C6.setBelowMe(C1);
        C1.setAboveMe(C6);

        C7.setBelowMe(C5);
        C5.setAboveMe(C7);

        final List containers = new ArrayList(Arrays.asList(C2, C1, C6, C7, C5, C4, C3));
        SortContainers.doSort( containers );
        final List expectedContainers = new ArrayList(Arrays.asList(C6, C1, C2, C3, C4, C7, C5));
        assertEquals( expectedContainers , containers );
    }

    @Test
    public void testSortContainersCase7() {
        final Container C1 = new Container(1);
        final Container C2 = new Container(2);
        final Container C3 = new Container(3);
        final Container C4 = new Container(4);
        final Container C5 = new Container(5);
        final Container C6 = new Container(6);
        final Container C7 = new Container(7);

        C1.setBelowMe(C4);
        C4.setAboveMe(C1);

        C2.setBelowMe(C5);
        C5.setAboveMe(C2);

        C3.setBelowMe(C6);
        C6.setAboveMe(C3);

        final List containers = 
new ArrayList(Arrays.asList(C2, C1, C6, C7, C5, C4, C3));
        SortContainers.doSort( containers );
        final List expectedContainers = 
new ArrayList(Arrays.asList(C1, C4, C2, C5, C3, C6, C7));
        assertEquals( expectedContainers , containers );
    }
}