Recursive Enumeration in Java

Question

Hello everyone.

I still have a question about Enumerations. Here's a quick sketch of the situation. I have a class Backpack that has a Hashmap content with as keys a variable of type long, and as value an ArrayList with Items. I have to write an Enumeration that iterates over the content of a Backpack. But here's the catch: in a Backpack, there can also be another Backpack. And the Enumeration should also be able to iterate over the content of a backpack that is in the backpack. (I hope you can follow, I'm not really good at explaining..)

Here is the code I have:

public Enumeration<Object> getEnumeration() {
    return new Enumeration<Object>() {
        private int itemsDone = 0;
        //I make a new array with all the values of the HashMap, so I can use
        //them in nextElement()
        Collection<Long> keysCollection = getContent().keySet();            
        Long [] keys = keysCollection.toArray(new Long[keysCollection.size()]);

        public boolean hasMoreElements() {
            if(itemsDone < getContent().size()) {
                return true;
            }else {
                return false;
            }

        }

        public Object nextElement() {               
            ArrayList<Item> temporaryList= getContent().get(keys[itemsDone]);
            for(int i = 0; i < temporaryList.size(); i++) {
                if(temporaryList.get(i) instanceof Backpack) {
                    return temporaryList.get(i).getEnumeration();                       
                }else {
                    return getContent().get(keys[itemsDone++]);
                }
            }
        }
    };

Will this code work decently? It's just the "return temporaryList.get(i).getEnumeration();" I'm worried about. Will the users still be able to use just the hasMoreElemens() and nextElement() like he would normally do?

Any help is appreciated,

Harm De Weirdt

Answer 1

If it was for practical purposes and not homework, I would use the Iterator interface instead of the old Enumeration. For iterators you have some nice utilities in the apache collections project.

Secondly, your solution seems to have a bug. The method nextElement() should return the elements themselves, but the line return temporaryList.get(i).getEnumeration() returns an Enumeration object instead.

--EDIT--

polygenelubricants suggested a nice, elegant solution. I thought of something else. You can implement a generic ChainEnumeration class (implements Enumeration), that receives a list of Enumerations and allows enumerating the underlying items. In your tree structure, return a simple enumeration with one item for leafs, and a chain enumeration of inner nodes.

The implementation of ChainEnumeration is simple: it manages a list of iterators, plus a reference to the current active iterator, where items are taken from.

Answer 2

You need to create a Stack<Enumeration<Object>>. When you see another Backpack, you push a new Enumeration on that element into the Stack. You always nextElement() from the top of the stack. If the top element is empty, you pop it off. Repeat until the Stack.isEmpty().

---

Another perhaps simpler technique (depending on how comfortable you are with recursion) is to use "inner" enumerations, which itself can have inner enumerations. Here's a code sample using Iterator on Object[]. It recursively iterates into any nested Object[].

public class RecursiveIterator implements Iterator<Object> {
    final Object[] arr;
    int index = 0;
    Iterator<Object> inner;
    RecursiveIterator(Object[] arr) {
        this.arr = arr;
    }
    @Override public boolean hasNext() {
        while (true) {
            if (inner != null) {
                if (inner.hasNext()) {
                    return true;
                } else {
                    inner = null;
                    index++;
                }
            }
            if (index == arr.length) return false;
            if (arr[index] instanceof Object[]) {
                inner = new RecursiveIterator((Object[]) arr[index]);
            } else {
                return true;
            }
        }
    }
    @Override public Object next() {
        if (!hasNext()) throw new NoSuchElementException();
        return (inner != null) ? inner.next() : arr[index++];
    }
    @Override public void remove() {
        throw new UnsupportedOperationException();
    }       
}

Here's a test harness:

static void dump(Object[] arr) {
    Iterator<Object> iter = new RecursiveIterator(arr);
    while (iter.hasNext()) {
        System.out.print(iter.next() + " ");
    }
    System.out.println("(done)");
}
public static void main(String[] args) throws FileNotFoundException {
    dump(new Object[] {
        1,
        2,
        new Object[] {
            3,
            new Object[] { 4 },
            5,
        },
        6,
        new Object[] {},
        7,
    });
    dump(new Object[] {
        new Object[] {},
        new Object[] {
            new Object[] {          
                new Object[] {},
            },
        },
        new Object[] {},
        new Object[] { null },
    });
}

This prints:

1 2 3 4 5 6 7 (done)
null (done)