Java: "cons" an item to a list

I have an Item which has a method List<Item> getChildren() (which returns an immutable list) and for each of the items I have, I need to create a list of the item followed by its children.

What's the quickest way to "cons" (in the Lisp/Scheme sense) my item to create a new immutable list? I can certainly do the following, but it seems wrong/wasteful:

public 开发者_运维技巧List<Item> getItemAndItsChildren(Item item)
{
    if (item.getChildren.isEmpty())
        return Collections.singletonList(item);
    else
    {
        // would rather just "return cons(item, item.getChildren())"
        // than do the following -- which, although straightforward,
        // seems wrong/wasteful.
        List<Item> items = new ArrayList<Item>();
        items.add(item);
        items.addAll(item.getChildren());
        return Collections.unmodifiableList(items);
    }
}

I'd change my requirements. In most cases, you don't need a List in your interface, an Iterable will do nicely. Here's the method:

public Iterable<Item> getItemWithChildren(Item item)    {
    return Iterables.unmodifiableIterable(
        Iterables.concat(
            Collections.singleton(item),
            item.getChildren()
        )
    );
}

and here's the shortened version (with static imports):

return unmodifiableIterable(concat(singleton(item), item.getChildren()));

The ability to create a new immutable list by concatenating a head element to a tail that may be shared between other lists requires a singly-linked list implementation. Java doesn't provide anything like this out of the box, so your ArrayList solution is as good as anything.

It's also going to be relatively efficient, assuming that these lists are short-lived and you don't have tens of thousands of element in the list. If you do, and if this operation is taking a significant portion of your execution time, then implmenting your own single-linked list might be worthwhile.

My one change to improve your existing efficiency: construct the new list with a capacity (1 + size of old list).

You shouldn't need to special case an Item with no children.

public List<Item> getItemAndItsChildren(Item item)
{
    List<Item> items = new ArrayList<Item>();
    items.add(item);
    items.addAll(item.getChildren());
    return Collections.unmodifiableList(items);
}

Also, if you are looking to use a language that isn't verbose, then Java is a poor choice. I'm sure you can do what you like in far less code in Groovy and Scala which both run on the JVM. (Not to mention JRuby or Jython.)

It sounds like you're looking for something like a CompositeList, similar to the Apache Commons' CompositeCollection. An implementation could be as naive as this:

public class CompositeList<T> extends AbstractList<T>{
    private final List<T> first, second;

    public CompositeList(List<T> first, List<T> second) {
        this.second = second;
        this.first = first;
    }

    @Override
    public T get(int index) {
        if ( index < first.size() ) {
            return first.get(index);
        } else {
            return second.get(index - first.size());
        }
    }

    @Override
    public int size() {
        return first.size() + second.size();
    }
}

And you could use it like this:

public List<Item> getItemAndItsChildren(Item item)
{
    return Collections.unmodifiableList( 
        new CompositeList<Item>(Collections.singletonList(item), item.getChildren()) );
}

But there are huge caveats that make such a class difficult to use...the main problem being that the List interface cannot itself mandate that it is unmodifiable. If you are going to use something like this you must ensure that clients of this code never modify the children!

I use these. (using guava's ImmutableList and Iterables)

/** Returns a new ImmutableList with the given element added */
public static <T> ImmutableList<T> add(final Iterable<? extends T> list, final T elem) {
    return ImmutableList.copyOf(Iterables.concat(list, Collections.singleton(elem)));
}

/** Returns a new ImmutableList with the given elements added */
public static <T> ImmutableList<T> add(final Iterable<? extends T> list, final Iterable<? extends T> elems) {
    return ImmutableList.copyOf(Iterables.concat(list, elems));
}

/** Returns a new ImmutableList with the given element inserted at the given index */
public static <T> ImmutableList<T> add(final List<? extends T> list, final int index, final T elem) {
    return ImmutableList.copyOf(Iterables.concat(list.subList(0, index), Collections.singleton(elem), list.subList(index, list.size())));
}

/** Returns a new ImmutableList with the given element inserted at the given index */
public static <T> ImmutableList<T> add(final List<? extends T> list, final int index, final Iterable<?extends T> elems) {
    return ImmutableList.copyOf(Iterables.concat(list.subList(0, index), elems, list.subList(index, list.size())));
}

But none of them are efficient.

Example of prepending/consing an item to a list:

ImmutableList<String> letters = ImmutableList.of("a", "b", "c");
add(letters, 0, "d");

For more efficient immutable/persistent collections you should, as @eneveu points out, look at pcollections, although I have no idea what the quality of that library is.

pcollections is a persistent Java collection library you might be interested in. I bookmarked it a while ago, and haven't yet used it, but the project seems relatively active.

If you want to use Guava, you could use the unmodifiable view returned by Lists.asList(E first, E[] rest). It works with arrays, and its primary goal is to simplify the use of var-args methods. But I see no reason you couldn't use it in your case:

public List<Item> getItemAndItsChildren(Item item) {
    return Lists.asList(item, item.getChildren().toArray());
}

The List returned is an unmodifiable view, but it may change if the source array is modified. In your case, it's not a problem, since the getChildren() method returns an immutable list. Even if it were mutable, the toArray() method supposedly returns a "safe" array...

If you want to be extra safe, you could do:

public ImmutableList<Item> getItemAndItsChildren(Item item) {
    return ImmutableList.copyOf(Lists.asList(item, item.getChildren().toArray()));
}

Note that Lists.asList() avoids un-necessary ArrayList instantiation, since it's a view. Also, ImmutableList.copyOf() would delegate to ImmutableList.of(E element) when the children list is empty (which, similarly to Collections.singletonList(), is space-efficient).

You should instantiate your list with the exact number you will be putting into it to eliminate expansion copies when you add more.

List<Item> items = new ArrayList<Item>();

should be

List<Item> items = new ArrayList<Item>(item.getChildren() + 1);

otherwise what you are doing is about as idiomatic Java as you can get.

Another thing, is you might consider using Guava and its ImmutableList implementation rather than an Collections.unmodifiableList().

Unlike Collections.unmodifiableList(java.util.List), which is a view of a separate collection that can still change, an instance of ImmutableList contains its own private data and will never change. ImmutableList is convenient for public static final lists ("constant lists") and also lets you easily make a "defensive copy" of a list provided to your class by a caller.