Java: "минус" элемент в список

У меня есть Item, у которого есть метод List<Item> getChildren() (который возвращает неизменный список), и для каждого из элементов, которые у меня есть, мне нужно создать список элемента, за которым следуют его дочерние элементы.

Какой самый быстрый способ "cons" (в смысле Lisp/Scheme) мой элемент для создания нового неизменяемого списка? Я могу, конечно, сделать следующее, но это кажется неправильным/расточительным:

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);
    }
}

Ответы

Ответ 1

Я бы изменил свои требования. В большинстве случаев вам не нужен List в вашем интерфейсе, Iterable будет хорошо. Здесь метод:

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

и здесь сокращенная версия (со статическим импортом):

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

Ответ 2

Возможность создания нового неизменяемого списка путем объединения элемента заголовка в хвост, который может быть разделен между другими списками, требует реализации односвязного списка. Java не предоставляет ничего подобного, поэтому ваше решение ArrayList так же хорошо, как и все.

Он также будет относительно эффективным, если предположить, что эти списки недолговечны, и у вас нет десятков тысяч элементов в списке. Если вы это сделаете, и если эта операция займет значительную часть вашего времени выполнения, то может потребоваться внедрение вашего собственного односвязного списка.

Мое одно изменение для улучшения существующей эффективности: постройте новый список с емкостью (1 + размер старого списка).

Ответ 3

Вам не нужно, чтобы в специальном случае был Item без детей.

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

Кроме того, если вы хотите использовать язык, который не является многословным, то Java является плохим выбором. Я уверен, что вы можете делать то, что вам нравится, в гораздо меньшем количестве кода в Groovy и Scala, которые оба запускаются на JVM. (Не говоря уже о JRuby или Jython.)

Ответ 4

Похоже, вы ищете нечто вроде CompositeList, похожее на Apache Commons 'CompositeCollection. Реализация может быть такой же наивной, как это:

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();
    }
}

И вы можете использовать его следующим образом:

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

Но есть огромные оговорки, которые затрудняют использование такого класса... главная проблема заключается в том, что интерфейс List не может сам утверждать, что он не поддается изменению. Если вы собираетесь использовать что-то вроде этого, вы должны обеспечить, чтобы клиенты этого кода никогда не изменяли детей!

Ответ 5

Я использую их. (используя guava ImmutableList и 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())));
}

Но никто из них не эффективен.

Пример добавления/присоединения элемента к списку:

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

Для более эффективных неизменяемых/постоянных коллекций вы должны, как указывает @eneveu, посмотреть на pcollections, хотя я не знаю, каково качество этой библиотеки.

Ответ 6

pcollections - это постоянная библиотека коллекции Java, которая может вас заинтересовать. Я добавил ее в закладки некоторое время назад и еще не использовал это, но проект кажется относительно активным.

Если вы хотите использовать Guava, вы можете использовать немодифицируемое представление, возвращенное Lists.asList(сначала E, E [] rest). Он работает с массивами, и его основной задачей является упрощение использования методов var-args. Но я не вижу причин, по которым вы не могли бы использовать его в своем случае:

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

Возвращенный List - это немодифицируемое представление, но оно может измениться, если исходный массив изменен. В вашем случае это не проблема, так как метод getChildren() возвращает неизменный список. Даже если он был изменен, метод toArray() предположительно возвращает "безопасный" массив...

Если вы хотите быть более безопасным, вы можете сделать:

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

Обратите внимание, что Lists.asList() избегает ненужного создания ArrayList, поскольку это представление. Кроме того, ImmutableList.copyOf() делегирует значение ImmutableList.of(E element), когда список дочерних элементов пуст (что, подобно Collections.singletonList(), является экономически эффективным).

Ответ 7

Вы должны создать экземпляр своего списка с точным номером, который вы будете помещать в него, чтобы исключить копии расширения, когда вы добавляете больше.

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

должен быть

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

в противном случае то, что вы делаете, - это как идиоматическая Java, которую вы можете получить.

Другое дело, можете ли вы использовать Guava и ImmutableList, а не Collections.unmodifiableList().

В отличие от Collections.unmodifiableList(java.util.List), который является видом отдельной коллекции, которая все еще может измениться, экземпляр ImmutableList содержит свои личные данные и никогда не будет меняться. ImmutableList удобно для публичных статических окончательных списков ( "константа списки" ), а также позволяет легко сделать "защитную копию" списка предоставляемый вашему классу вызывающим абонентом.