Java: есть коллекция элементов, где каждый элемент имеет поле «previousItem», что является наиболее эффективным способом заказа коллекции?

Question

У меня есть коллекция иерархических элементов в несортированной коллекции. Каждый из этих элементов имеет поле previousItem:

public class Item{ 
    public Item previousItem; 
} 

Что является наиболее эффективным способом обработки этих элементов, так что выход представляет собой набор, где деталь без previousItem является первым элементом коллекции и каждого subesequent Предыдущий элемент предыдущего элемента - это предыдущий элемент в коллекции?

Моя первая идея была бы реализовать Сопоставимые интерфейс в классе Item:

public int compareTo(Item that) { 
    final int BEFORE = -1; 
    final int EQUAL = 0; 
    final int AFTER = 1; 

    if(this.previousItem==null){ 
     return BEFORE; 
    } 

    if(that.previousItem==null){ 
     return AFTER; 
    } 

    if(this.previousItem.equals(that){ 
     return AFTER; 
    }else if(that.previousItem.equals(this){ 
     return BEFORE; 
    } 

    return EQUAL; 
} 

и затем цикл по пунктам добавить их к TreeSet:

SortedSet<Item> itemSortedSet = new TreeSet<Item>(); 
for (Item item : itemCollection) { 
    itemSortedSet.add(item); 
} 

Есть ли более эффективный способ (меньше времени на обработку/количество требуемых итераций), чтобы упорядочить коллекцию, чтобы они находились в логическом, иерархическом порядке?

Answer 1

Ваш компаратор не работает: он не обеспечивает транзитивность, то есть он будет делать неправильную вещь, если вы сравните элементы A и C в случае A-> B-> C.

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

Item last = ...; 

while (last != null) { 
    result.add(last) 
    last = last.previousItem 
} 

Если у вас нет способа узнать, какой элемент является последним , то вы могли бы использовать IdentityHashMap для отображения каждого previousItem значения для Item объекта, который использует его:

IdentityHashMap<Item,Item> m = new IdentityHashMap<Item,Item>(itemset.size()); 

for (Item i : itemset) 
    m.put(i.previousItem, i); 

Item i = m.get(null); 

while (i != null) { 
    result.add(i); 

    i = m.get(i); 
} 

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

Оба метода имеют грубую линейную сложность w.r.t. количество элементов, но они делают два предположения, которые не могут быть допустимы в вашем случае:

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

• Что есть одна «нить» предметов.

Если какое-либо из этих допущений недействительно, вам понадобится гораздо более сложный алгоритм для его сортировки.

Answer 2

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

public class Item { 
    Item previousItem; 

    public void putToCollection(ArrayList<Item> list) { 
    list.add(this); 
    if (previousItem == null) { 
     Collections.reverse(list); 
    } else { 
     previousItem.putToCollection(list); 
    } 
    } 
} 

Answer 3

Если вы правильно поняли, у вас есть десант объекта Item без предыдущего объекта. Вы можете просто пропустить элементы (например,с циклом while) и добавьте их в ArrayList или LinkedList, потому что метод add() для этих списков просто добавляет новый элемент в конце списка. Таким образом, вы пройдете через O (n) -time.

Answer 4

Вы можете использовать HashSet<Item>, в котором вы изначально поместили все предметы. Затем вы просматриваете элементы в цикле и удаляете каждый из previousItem из вашего набора. В конце вам нужно оставить один элемент в наборе, последний, который не был previousItem для любого другого элемента. И тогда вы можете просто добавлять элементы, начиная с этого и просматривая ссылки.