junit testing equality of an Iterable

Question

I am trying to write unit tests for a BinarySearchTree class The keys() return an Iterable.It uses another class called Queue in which the keys are enqueued and returned..

The Queue (third party class) however doesn't have any equals() defined.

public class BinarySearchTree<Key extends Comparable<Key>,Value> {
    Node root ;

    private class Node{
        private Key key;
        private Value val;
        private Node left;
        private Node right;
        private int N;
        public Node(Key k, Value v,int N) {
            super();
            this.key = k;
            this.val = v;
            this.N = N;
        }
    }

        public Iterable<Key> keys(){
           Queue<Key> q = new Queue<Key>();
           inOrder(root,q);
           return q;
        }
        private void inOrder(Node x,Queue q){
            if(x == null)return;
            inOrder(x.left,q);
            q.enqueue(x.key);
            inOrder(x.right,q);
        }
  ...
}

trying to write unit test

@Test
public void testKeys(){
    MyBST<String, Integer> st = new MyBST<String, Integer>();
    st.put("S",7);
    st.put("E",2);
    st.put("X",8);

    st.put("A",3);
    st.put("R",4);

    st.put("C",1);

    st.put("H",5);
    st.put("M",6);

    Queue<String> q = new Queue<String>();
    q.enqueue("A");
    q.enqueue("C");
    q.enqueue("E");
    q.enqueue("H");
    q.enqueue("M");
    q.enqueue("R");
    q.enqueue("S");
    q.enqueue("X");

    Iterable<String> actual = st.keys();
    assertEquals(q,actual);
     }

This fails

java.lang.AssertionError: expected: std.Queue<A C E H M R S X > but was: std.Queue<A C E H M R S X >
    at org.junit.Assert.fail(Assert.java:93)
    at org.junit.Assert.failNotEquals(Assert.java:647)
    at org.junit.Assert.assertEquals(Assert.java:128)
    at org.junit.Assert.assertEquals(Assert.java:147)
    at week4.MyBSTTests.testKeys(BSTTests.java:304)

Do I have to implement an equals() in the third party class or is there any other way to do this to check equality? All I could think of was running a loop dequeueing from queue q and comparing it with what the iterator returned.I am not sure if there is a better way.. Please advise..

Iterable<String> actual = st.keys();
Iterator<String> actualit = actual.iterator();
while(actualit.hasNext()){
    String actualkey = actualit.next();
    String exp = q.dequeue();
    assertEquals(actualkey,exp);
}

Answer 1

This is how I did this.

I converted the Iterable to the ArrayList. Then I made another arraylist of expected key values. That way I am able to check if two arrayLists are equal using assertEquals(arrayList1, arrayList2). Here is the code I wrote for testing my preOrder traversal method.

import static org.junit.Assert.*;
import java.util.ArrayList;

import org.junit.Test;

 public class BSTTest
 {
    BST<Integer, String> binaryTree = new BST<Integer, String>();

   @Test
   public void preOrdertest()
   {
       binaryTree.put(87, "Orange");
       binaryTree.put(77, "Black");
       binaryTree.put(81, "Green");
       binaryTree.put(89, "Blue");
       binaryTree.put(4, "Yellow");
       binaryTree.put(26, "white");
       binaryTree.put(23, "Purple");
       binaryTree.put(27, "Violet");
       binaryTree.put(57, "red");
       binaryTree.put(1, "crimson");

       ArrayList<Integer> testList = new ArrayList<>();

       testList.add(87);
       testList.add(77);
       testList.add(4);
       testList.add(1);
       testList.add(26);
       testList.add(23);
       testList.add(27);
       testList.add(57);
       testList.add(81);
       testList.add(89);

       Iterable<Integer> actual = binaryTree.preOrder();

       ArrayList<Integer> actualList = new ArrayList<>();

       if (actual != null)
       {
            for (Integer e : actual)
            actualList.add(e);
       }

        assertEquals(testList, actualList);

   }

  }

Answer 2

you can use the utility class java.util.Arrays. From what I remember the Queue interface has a toArray method. So it would be something like this:

    assertTrue(Arrays.equals(queue1.toArray(),queue2.toArray()));

As it is a third party library, you could use apache commons:

Object[] o = IteratorUtils.toArray(queue1.iterator());
Object[] o2 = IteratorUtils.toArray(queue1.iterator());
assertTrue(Arrays.equals(o,o2));

Answer 3

Use Hamcrest's Matchers.contains (described here). For example:

assertThat(queue1.keys(), Matchers.contains("A", "C", "E", "H", "M", "R", "S", "X"));

This will check the elements that the Iterable returns without needing equality implemented on your queue class.