将复杂的while循环重构为Java 8流

Question

我有一个复杂的实体结构。，它包含上一项的ID ("previodElementId")

interface IPreviousElementEntity<PK> {
    public void setId(PK id);
    public PK getId();
    public void setPreviousElementId(PK previousElementId);
    public PK getPreviousElementId();
}

在从DB接收所有实体之后，我需要将结果列表转换为一个链接列表，并且链接列表应该由前面的id来组织。

我编写了以下转换代码：

static <T extends IPreviousElementEntity> LinkedList<T> getLinkedListByPreviousId(Collection<T> collection) {
    LinkedList<T> linkedList = new LinkedList<>();
    if (collection == null || collection.isEmpty())
        return linkedList;

    // first find root element
    collection.stream()
            .filter(element -> element.getPreviousElementId() == null)
            .forEach(linkedList::add);

    if (linkedList.isEmpty()) return linkedList;

    // TODO: convert to use stream. Please help!
    Boolean isRun = true;
    while (isRun) {
        for (T element : collection) {
            isRun = false;
            if (linkedList.getLast().getId().equals(element.getPreviousElementId())) {
                linkedList.add(element);
                isRun = true;
                break;
            }
        }
    }

    return linkedList;
}

但是这个代码太糟糕了！是否有可能在流上编写所有这些转换？我特别想摆脱雷鸣的同时循环。

我的完整代码：

import java.util.*;

public class App {
    public static void main(String[] args) {
        Entity entity1 = new Entity(3L, 2L, "third");
        Entity entity2 = new Entity(2L, 1L, "second");
        Entity entity3 = new Entity(4L, 3L, "forth");
        Entity entity4 = new Entity(1L, null, "first");

        List<Entity> entities = new ArrayList<>();
        entities.add(entity1);
        entities.add(entity2);
        entities.add(entity3);
        entities.add(entity4);

        LinkedList<Entity> linkedListByPreviousId = getLinkedListByPreviousId(entities);
        System.out.println(linkedListByPreviousId);
    }

    private static <T extends IPreviousElementEntity> LinkedList<T> getLinkedListByPreviousId(Collection<T> collection) {
        LinkedList<T> linkedList = new LinkedList<>();
        if (collection == null || collection.isEmpty())
            return linkedList;

        // first find root element
        collection.stream()
                .filter(element -> element.getPreviousElementId() == null)
                .forEach(linkedList::add);

        if (linkedList.isEmpty()) return linkedList;

        //TODO: convert to use stream. Please help!
        Boolean isRun = true;
        while (isRun) {
            for (T element : collection) {
                isRun = false;
                if (linkedList.getLast().getId().equals(element.getPreviousElementId())) {
                    linkedList.add(element);
                    isRun = true;
                    break;
                }
            }
        }

        return linkedList;
    }
}

interface IPreviousElementEntity<PK> {
    public void setId(PK id);
    public PK getId();
    public void setPreviousElementId(PK previousElementId);
    public PK getPreviousElementId();
}

class Entity implements IPreviousElementEntity<Long> {
    private Long id;
    private Long previousElementId;
    private String name;

    public Entity(Long id, Long previousElementId, String name) {
        this.id = id;
        this.previousElementId = previousElementId;
        this.name = name;
    }

    @Override
    public Long getId() {
        return id;
    }

    @Override
    public void setId(Long id) {
        this.id = id;
    }

    @Override
    public Long getPreviousElementId() {
        return previousElementId;
    }

    @Override
    public void setPreviousElementId(Long previousElementId) {
        this.previousElementId = previousElementId;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Entity entity = (Entity) o;
        return Objects.equals(id, entity.id) &&
                Objects.equals(previousElementId, entity.previousElementId) &&
                Objects.equals(name, entity.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, previousElementId, name);
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("Entity{");
        sb.append("id=").append(id);
        sb.append(", previousElementId=").append(previousElementId);
        sb.append(", name='").append(name).append('\'');
        sb.append('}');
        return sb.toString();
    }
}

Answer 1

while循环令人讨厌，因为它尝试使用list执行O(n^2)操作，并不断重复，直到没有更多的选项。

通过使用使用previousElementId作为键的映射，O(n)操作更合适。

if (linkedList.isEmpty()) return linkedList;

//create a map with previousElementId as Key, T as Object
Map<Integer, T> map = collection.stream().collect(
            Collectors.toMap(T::getPreviousElementId, Function.identity()));

//we fetch nodes using the current ID as the key
T node = map.get(linkedList.getLast().getId());
while(node != null) {
    linkedList.add(node);
    node = map.get(node.getId());
}

Answer 2

您有一个常见的用例，我认为您应该能够提出使用流的更干净的解决方案。以下是只使用流的方法：

private static < T extends IPreviousElementEntity<?> > LinkedList<T> getLinkedListByPreviousId(
Collection<T> collection) {
    //first create map with previous id mapped to element, this assumes 
    //whatever id you use has proper implementation of equals and hashCode
    Map<?, T> map = collection.stream()
        .collect( 
            Collectors.toMap(
                IPreviousElementEntity::getPreviousElementId, Function.identity(), 
            (i1, i2) -> i1 ) ); 

    //then create infinite stream which starts with element that has null previous id
    //and moves on to the next element that points to it via previous id
    //since this is an infinite stream we need to limit it by the number of elements in the map
    return Stream
        .iterate( map.get(null), i -> map.get( i.getId() ) )
        .limit( map.size() )
        .collect( Collectors.toCollection(LinkedList::new) );
}