Repository: james-project Updated Branches: refs/heads/master c96225d44 -> af4934b63
JAMES-1711 setMailboxes : sort requests Create a tree of Mailbox objects based on create / update / destroy field of setMailboxes method. Once this tree is created, sort the tree in a root-to-leaf ordering using a specialized library. Also handle reverse ordering (for update and destroy) Project: http://git-wip-us.apache.org/repos/asf/james-project/repo Commit: http://git-wip-us.apache.org/repos/asf/james-project/commit/af4934b6 Tree: http://git-wip-us.apache.org/repos/asf/james-project/tree/af4934b6 Diff: http://git-wip-us.apache.org/repos/asf/james-project/diff/af4934b6 Branch: refs/heads/master Commit: af4934b6398de4f9f1420e339a109897d1e3d877 Parents: c96225d Author: Fabien Vignon <[email protected]> Authored: Thu Mar 24 15:23:40 2016 +0100 Committer: Antoine Duprat <[email protected]> Committed: Tue Mar 29 14:33:37 2016 +0200 ---------------------------------------------------------------------- .../apache/james/util/streams/Iterators.java | 32 +++++ .../james/util/streams/IteratorsTest.java | 58 ++++++++ server/protocols/jmap/pom.xml | 5 + .../james/jmap/utils/DependencyGraph.java | 56 ++++++++ .../jmap/utils/MailboxHierarchySorter.java | 53 +++++++ .../james/jmap/utils/DependencyGraphTest.java | 143 +++++++++++++++++++ .../jmap/utils/MailboxHierarchySorterTest.java | 116 +++++++++++++++ 7 files changed, 463 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/james-project/blob/af4934b6/server/container/util-java8/src/main/java/org/apache/james/util/streams/Iterators.java ---------------------------------------------------------------------- diff --git a/server/container/util-java8/src/main/java/org/apache/james/util/streams/Iterators.java b/server/container/util-java8/src/main/java/org/apache/james/util/streams/Iterators.java new file mode 100644 index 0000000..ba3a06b --- /dev/null +++ b/server/container/util-java8/src/main/java/org/apache/james/util/streams/Iterators.java @@ -0,0 +1,32 @@ +/**************************************************************** + * Licensed to the Apache Software Foundation (ASF) under one * + * or more contributor license agreements. See the NOTICE file * + * distributed with this work for additional information * + * regarding copyright ownership. The ASF licenses this file * + * to you under the Apache License, Version 2.0 (the * + * "License"); you may not use this file except in compliance * + * with the License. You may obtain a copy of the License at * + * * + * http://www.apache.org/licenses/LICENSE-2.0 * + * * + * Unless required by applicable law or agreed to in writing, * + * software distributed under the License is distributed on an * + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * + * KIND, either express or implied. See the License for the * + * specific language governing permissions and limitations * + * under the License. * + ****************************************************************/ + +package org.apache.james.util.streams; + +import java.util.Iterator; +import java.util.stream.Stream; +import java.util.stream.StreamSupport; + +public class Iterators { + + public static <T> Stream<T> toStream(Iterator<T> iterator) { + Iterable<T> iterable = () -> iterator; + return StreamSupport.stream(iterable.spliterator(), false); + } +} http://git-wip-us.apache.org/repos/asf/james-project/blob/af4934b6/server/container/util-java8/src/test/java/org/apache/james/util/streams/IteratorsTest.java ---------------------------------------------------------------------- diff --git a/server/container/util-java8/src/test/java/org/apache/james/util/streams/IteratorsTest.java b/server/container/util-java8/src/test/java/org/apache/james/util/streams/IteratorsTest.java new file mode 100644 index 0000000..cad060d --- /dev/null +++ b/server/container/util-java8/src/test/java/org/apache/james/util/streams/IteratorsTest.java @@ -0,0 +1,58 @@ +/**************************************************************** + * Licensed to the Apache Software Foundation (ASF) under one * + * or more contributor license agreements. See the NOTICE file * + * distributed with this work for additional information * + * regarding copyright ownership. The ASF licenses this file * + * to you under the Apache License, Version 2.0 (the * + * "License"); you may not use this file except in compliance * + * with the License. You may obtain a copy of the License at * + * * + * http://www.apache.org/licenses/LICENSE-2.0 * + * * + * Unless required by applicable law or agreed to in writing, * + * software distributed under the License is distributed on an * + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * + * KIND, either express or implied. See the License for the * + * specific language governing permissions and limitations * + * under the License. * + ****************************************************************/ + +package org.apache.james.util.streams; + +import static java.util.stream.Collectors.toList; +import static org.assertj.core.api.Assertions.assertThat; + +import java.util.stream.*; + +import org.junit.Test; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.UnmodifiableIterator; + +public class IteratorsTest { + + @Test + public void toStreamShouldReturnEmptyStreamWhenEmptyIterator() { + //Given + UnmodifiableIterator<String> emptyIterator = ImmutableList.<String>of().iterator(); + + //When + Stream<String> actual = Iterators.toStream(emptyIterator); + + //Then + assertThat(actual.count()).isEqualTo(0); + } + + @Test + public void toStreamShouldReturnSameContent() { + //Given + UnmodifiableIterator<String> iterator = ImmutableList.of("a", "b", "c").iterator(); + + //When + Stream<String> actual = Iterators.toStream(iterator); + + //Then + assertThat(actual.collect(toList())).containsExactly("a", "b", "c"); + } + +} http://git-wip-us.apache.org/repos/asf/james-project/blob/af4934b6/server/protocols/jmap/pom.xml ---------------------------------------------------------------------- diff --git a/server/protocols/jmap/pom.xml b/server/protocols/jmap/pom.xml index 1745231..296d752 100644 --- a/server/protocols/jmap/pom.xml +++ b/server/protocols/jmap/pom.xml @@ -316,6 +316,11 @@ <version>1.2</version> </dependency> <dependency> + <groupId>org.jgrapht</groupId> + <artifactId>jgrapht-core</artifactId> + <version>0.9.1</version> + </dependency> + <dependency> <groupId>org.mockito</groupId> <artifactId>mockito-core</artifactId> <scope>test</scope> http://git-wip-us.apache.org/repos/asf/james-project/blob/af4934b6/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/DependencyGraph.java ---------------------------------------------------------------------- diff --git a/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/DependencyGraph.java b/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/DependencyGraph.java new file mode 100644 index 0000000..96c5ff6 --- /dev/null +++ b/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/DependencyGraph.java @@ -0,0 +1,56 @@ +/**************************************************************** + * Licensed to the Apache Software Foundation (ASF) under one * + * or more contributor license agreements. See the NOTICE file * + * distributed with this work for additional information * + * regarding copyright ownership. The ASF licenses this file * + * to you under the Apache License, Version 2.0 (the * + * "License"); you may not use this file except in compliance * + * with the License. You may obtain a copy of the License at * + * * + * http://www.apache.org/licenses/LICENSE-2.0 * + * * + * Unless required by applicable law or agreed to in writing, * + * software distributed under the License is distributed on an * + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * + * KIND, either express or implied. See the License for the * + * specific language governing permissions and limitations * + * under the License. * + ****************************************************************/ + +package org.apache.james.jmap.utils; + +import java.util.Optional; +import java.util.function.Function; +import java.util.stream.Stream; + +import org.apache.james.util.streams.Iterators; +import org.jgrapht.graph.DefaultDirectedGraph; +import org.jgrapht.graph.DefaultEdge; +import org.jgrapht.graph.builder.DirectedGraphBuilder; +import org.jgrapht.traverse.TopologicalOrderIterator; + +public class DependencyGraph<T> { + + private final DirectedGraphBuilder<T, DefaultEdge, DefaultDirectedGraph<T, DefaultEdge>> builder; + private final Function<T, Optional<T>> getParent; + + public DependencyGraph(Function<T, Optional<T>> getParent) { + this.getParent = getParent; + this.builder = new DirectedGraphBuilder<>(new DefaultDirectedGraph<>(DefaultEdge.class)); + } + + public void registerItem(T item) { + builder.addVertex(item); + getParent.apply(item) + .map(parentNode -> builder.addEdge(parentNode, item)); + } + + public Stream<T> getBuildChain() { + DefaultDirectedGraph<T, DefaultEdge> graph = builder.build(); + return Iterators.toStream(new TopologicalOrderIterator<>(graph)); + } + + public String toString() { + return builder.build().toString(); + } +} http://git-wip-us.apache.org/repos/asf/james-project/blob/af4934b6/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/MailboxHierarchySorter.java ---------------------------------------------------------------------- diff --git a/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/MailboxHierarchySorter.java b/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/MailboxHierarchySorter.java new file mode 100644 index 0000000..67efd2e --- /dev/null +++ b/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/MailboxHierarchySorter.java @@ -0,0 +1,53 @@ +/**************************************************************** + * Licensed to the Apache Software Foundation (ASF) under one * + * or more contributor license agreements. See the NOTICE file * + * distributed with this work for additional information * + * regarding copyright ownership. The ASF licenses this file * + * to you under the Apache License, Version 2.0 (the * + * "License"); you may not use this file except in compliance * + * with the License. You may obtain a copy of the License at * + * * + * http://www.apache.org/licenses/LICENSE-2.0 * + * * + * Unless required by applicable law or agreed to in writing, * + * software distributed under the License is distributed on an * + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * + * KIND, either express or implied. See the License for the * + * specific language governing permissions and limitations * + * under the License. * + ****************************************************************/ + +package org.apache.james.jmap.utils; + +import java.util.List; +import java.util.Map; +import java.util.function.Function; +import java.util.stream.Collectors; + +import org.apache.james.jmap.model.mailbox.Mailbox; + +import com.google.common.collect.Lists; + +public class MailboxHierarchySorter { + + public List<Mailbox> sortFromRootToLeaf(List<Mailbox> mailboxes) { + + Map<String, Mailbox> mapOfMailboxesById = indexMailboxesById(mailboxes); + + DependencyGraph<Mailbox> graph = new DependencyGraph<>(m -> + m.getParentId().map(mapOfMailboxesById::get)); + + mailboxes.stream().forEach(graph::registerItem); + + return graph.getBuildChain().collect(Collectors.toList()); + } + + private Map<String, Mailbox> indexMailboxesById(List<Mailbox> mailboxes) { + return mailboxes.stream() + .collect(Collectors.toMap(Mailbox::getId, Function.identity())); + } + + public List<Mailbox> sortFromLeafToRoot(List<Mailbox> mailboxes) { + return Lists.reverse(sortFromRootToLeaf(mailboxes)); + } +} http://git-wip-us.apache.org/repos/asf/james-project/blob/af4934b6/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/DependencyGraphTest.java ---------------------------------------------------------------------- diff --git a/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/DependencyGraphTest.java b/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/DependencyGraphTest.java new file mode 100644 index 0000000..96c2658 --- /dev/null +++ b/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/DependencyGraphTest.java @@ -0,0 +1,143 @@ +/**************************************************************** + * Licensed to the Apache Software Foundation (ASF) under one * + * or more contributor license agreements. See the NOTICE file * + * distributed with this work for additional information * + * regarding copyright ownership. The ASF licenses this file * + * to you under the Apache License, Version 2.0 (the * + * "License"); you may not use this file except in compliance * + * with the License. You may obtain a copy of the License at * + * * + * http://www.apache.org/licenses/LICENSE-2.0 * + * * + * Unless required by applicable law or agreed to in writing, * + * software distributed under the License is distributed on an * + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * + * KIND, either express or implied. See the License for the * + * specific language governing permissions and limitations * + * under the License. * + ****************************************************************/ + +package org.apache.james.jmap.utils; + +import static org.assertj.core.api.Assertions.assertThat; + +import java.util.List; +import java.util.Optional; +import java.util.Set; +import java.util.stream.Collectors; +import java.util.stream.Stream; + +import org.junit.Test; + +import com.google.common.annotations.VisibleForTesting; +import com.google.common.base.Preconditions; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; + +public class DependencyGraphTest { + + @Test + public void getBuildChainShouldReturnOrderedMailbox() { + // Given + Commit a = new Commit("A"); + Commit b = new Commit("B", a); + Commit c = new Commit("C", b); + + DependencyGraph<Commit> graph = new DependencyGraph<>(Commit::getParent); + Set<Commit> mailboxes = ImmutableSet.of(b, a, c); + mailboxes.stream().forEach(graph::registerItem); + + // When + Stream<Commit> orderedMailboxes = graph.getBuildChain(); + + // Then + assertThat(orderedMailboxes).extracting(Commit::getMessage).containsExactly("A", "B", "C"); + } + + @Test + public void getBuildChainWithEmptyGraphShouldReturnEmpty() { + DependencyGraph<Commit> graph = new DependencyGraph<>(m -> null); + assertThat(graph.getBuildChain()).isEmpty(); + } + + @Test + public void getBuildChainOnIsolatedVerticesShouldReturnSameOrder() { + DependencyGraph<Commit> graph = new DependencyGraph<>(m -> Optional.empty()); + ImmutableList<Commit> isolatedMailboxes = ImmutableList.of(new Commit("A"), new Commit("B"), new Commit("C")); + isolatedMailboxes.stream().forEach(graph::registerItem); + + List<Commit> orderedResultList = graph.getBuildChain().collect(Collectors.toList()); + + assertThat(orderedResultList).isEqualTo(isolatedMailboxes); + } + + @Test + public void getBuildChainOnTwoIsolatedTreesShouldWork() { + // a-b d-e + // \c \f + + //Given + Commit a = new Commit("A"); + Commit b = new Commit("B", a); + Commit c = new Commit("C", b); + Commit d = new Commit("D"); + Commit e = new Commit("E", d); + Commit f = new Commit("F", d); + List<Commit> input = ImmutableList.of(b, a, e, d, f, c); + DependencyGraph<Commit> testee = new DependencyGraph<>(Commit::getParent); + input.stream().forEach(testee::registerItem); + + //When + Stream<Commit> actual = testee.getBuildChain(); + + //Then + assertThat(actual).extracting(Commit::getMessage).containsExactly("A", "D", "B", "E", "F", "C"); + } + + @Test + public void getBuildChainOnComplexTreeShouldWork() { + //Given + Commit a = new Commit("A"); + Commit b = new Commit("B", a); + Commit c = new Commit("C", a); + Commit d = new Commit("D", b); + Commit e = new Commit("E", b); + Commit f = new Commit("F", c); + Commit g = new Commit("G", e); + List<Commit> input = ImmutableList.of(b, a, e, g, d, f, c); + DependencyGraph<Commit> testee = new DependencyGraph<>(Commit::getParent); + input.stream().forEach(testee::registerItem); + + //When + Stream<Commit> actual = testee.getBuildChain(); + + //Then + assertThat(actual).extracting(Commit::getMessage).containsExactly("A", "B", "C", "E", "D", "F", "G"); + } + + + private static class Commit { + private final String message; + private final Optional<Commit> parent; + + @VisibleForTesting + Commit(String message) { + this(message, null); + } + + @VisibleForTesting + Commit(String message, Commit parent) { + Preconditions.checkArgument(message != null); + this.message = message; + this.parent = Optional.ofNullable(parent); + } + + public Optional<Commit> getParent() { + return parent; + } + + public String getMessage() { + return message; + } + } +} http://git-wip-us.apache.org/repos/asf/james-project/blob/af4934b6/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/MailboxHierarchySorterTest.java ---------------------------------------------------------------------- diff --git a/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/MailboxHierarchySorterTest.java b/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/MailboxHierarchySorterTest.java new file mode 100644 index 0000000..692f038 --- /dev/null +++ b/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/MailboxHierarchySorterTest.java @@ -0,0 +1,116 @@ +/**************************************************************** + * Licensed to the Apache Software Foundation (ASF) under one * + * or more contributor license agreements. See the NOTICE file * + * distributed with this work for additional information * + * regarding copyright ownership. The ASF licenses this file * + * to you under the Apache License, Version 2.0 (the * + * "License"); you may not use this file except in compliance * + * with the License. You may obtain a copy of the License at * + * * + * http://www.apache.org/licenses/LICENSE-2.0 * + * * + * Unless required by applicable law or agreed to in writing, * + * software distributed under the License is distributed on an * + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * + * KIND, either express or implied. See the License for the * + * specific language governing permissions and limitations * + * under the License. * + ****************************************************************/ + +package org.apache.james.jmap.utils; + +import static org.assertj.core.api.Assertions.assertThat; + +import java.util.List; +import java.util.stream.Collectors; + +import org.apache.james.jmap.model.mailbox.Mailbox; +import org.junit.Test; + +import com.google.common.collect.ImmutableList; + +public class MailboxHierarchySorterTest { + + @Test + public void sortFromRootToLeafShouldReturnOrderedMailbox() { + // Given + Mailbox inbox = Mailbox.builder().name("INBOX").id("INBOX").build(); + Mailbox a = Mailbox.builder().name("A").id("A").parentId("INBOX").build(); + Mailbox b = Mailbox.builder().name("B").id("B").parentId("INBOX").build(); + Mailbox c = Mailbox.builder().name("C").id("C").parentId("B").build(); + Mailbox d = Mailbox.builder().name("D").id("D").parentId("A").build(); + Mailbox e = Mailbox.builder().name("E").id("E").parentId("C").build(); + ImmutableList<Mailbox> input = ImmutableList.of(b, c, d, a, inbox, e); + + MailboxHierarchySorter sut = new MailboxHierarchySorter(); + // When + List<Mailbox> result = sut.sortFromRootToLeaf(input); + + // Then + assertThat(result).extracting(Mailbox::getName).endsWith("C", "D", "E").startsWith("INBOX"); + } + + @Test + public void sortFromRootToLeafEmptyMailboxShouldReturnEmpty() { + MailboxHierarchySorter sut = new MailboxHierarchySorter(); + ImmutableList<Mailbox> input = ImmutableList.of(); + List<Mailbox> result = sut.sortFromRootToLeaf(input); + assertThat(result).isEmpty(); + } + + @Test + public void sortFromRootToLeafOrphanMailboxesShouldReturnInput() { + Mailbox a = Mailbox.builder().name("A").id("A").build(); + Mailbox b = Mailbox.builder().name("B").id("B").build(); + Mailbox c = Mailbox.builder().name("C").id("C").build(); + + MailboxHierarchySorter sut = new MailboxHierarchySorter(); + ImmutableList<Mailbox> input = ImmutableList.of(a, b, c); + List<String> result = sut.sortFromRootToLeaf(input).stream() + .map(Mailbox::getName) + .collect(Collectors.toList()); + + assertThat(result).containsExactly("A", "B", "C"); + } + + @Test + public void sortFromLeafToRootShouldReturnOrderedMailbox() { + //Given + Mailbox inbox = Mailbox.builder().name("INBOX").id("INBOX").build(); + Mailbox a = Mailbox.builder().name("A").id("A").parentId("INBOX").build(); + Mailbox b = Mailbox.builder().name("B").id("B").parentId("INBOX").build(); + Mailbox c = Mailbox.builder().name("C").id("C").parentId("B").build(); + Mailbox d = Mailbox.builder().name("D").id("D").parentId("A").build(); + Mailbox e = Mailbox.builder().name("E").id("E").parentId("C").build(); + MailboxHierarchySorter sut = new MailboxHierarchySorter(); + ImmutableList<Mailbox> input = ImmutableList.of(b, c, d, a, inbox, e); + + //When + List<Mailbox> result = sut.sortFromLeafToRoot(input); + + assertThat(result).extracting(Mailbox::getName).endsWith("INBOX").startsWith("E"); + } + + @Test + public void sortFromLeafToRootEmptyMailboxShouldReturnEmpty() { + MailboxHierarchySorter sut = new MailboxHierarchySorter(); + ImmutableList<Mailbox> input = ImmutableList.of(); + List<Mailbox> result = sut.sortFromLeafToRoot(input); + assertThat(result).isEmpty(); + } + + @Test + public void sortFromLeafToRootOrphanMailboxesShouldReturnInput() { + Mailbox a = Mailbox.builder().name("A").id("A").build(); + Mailbox b = Mailbox.builder().name("B").id("B").build(); + Mailbox c = Mailbox.builder().name("C").id("C").build(); + + MailboxHierarchySorter sut = new MailboxHierarchySorter(); + ImmutableList<Mailbox> input = ImmutableList.of(a, b, c); + List<String> result = sut.sortFromLeafToRoot(input).stream() + .map(Mailbox::getName) + .collect(Collectors.toList()); + + assertThat(result).containsExactly("C", "B", "A"); + } +} \ No newline at end of file --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
