Bug 573025 - Introduce and apply builder for NamespaceListY20210708-0800Y20210706-1050Y20210706-0800S4_21_0_M1I20210712-0340I20210712-0240I20210711-1800I20210710-1800I20210710-0000I20210709-0030I20210707-1800I20210707-0600I20210706-1800I20210706-0600I20210705-1800I20210705-0600I20210704-1800I20210704-0600I20210703-1800I20210703-0600I20210702-1800I20210701-1800

To simplify and speed up the build of NamespaceLists a Builder is added,
which acts like a modifiable Collection and can efficiently be build
into a NamsepaceList or modified.

The new builder is applied where suitable.

Change-Id: I5269cb34512d0470df9c47849727929720d74cd3
Signed-off-by: Hannes Wellmann <wellmann.hannes1@gmx.net>
Reviewed-on: https://git.eclipse.org/r/c/equinox/rt.equinox.framework/+/180177
Tested-by: Equinox Bot <equinox-bot@eclipse.org>
Reviewed-by: Thomas Watson <tjwatson@us.ibm.com>

8 files changed, 1413 insertions, 463 deletions

diff --git a/bundles/org.eclipse.osgi.tests/src/org/eclipse/osgi/tests/container/AllTests.java b/bundles/org.eclipse.osgi.tests/src/org/eclipse/osgi/tests/container/AllTests.java
index ab08f8e4d..e3ef17db1 100644
--- a/bundles/org.eclipse.osgi.tests/src/org/eclipse/osgi/tests/container/AllTests.java
+++ b/bundles/org.eclipse.osgi.tests/src/org/eclipse/osgi/tests/container/AllTests.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2013 IBM Corporation and others.
+ * Copyright (c) 2013, 2021 IBM Corporation and others.
  *
  * This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License 2.0
@@ -24,6 +24,7 @@ public class AllTests {
 		suite.addTest(new JUnit4TestAdapter(ResolutionReportTest.class));
 		suite.addTest(new JUnit4TestAdapter(ModuleContainerUsageTest.class));
 		suite.addTest(new JUnit4TestAdapter(NamespaceListTest.class));
+		suite.addTest(new JUnit4TestAdapter(NamespaceListBuilderTest.class));
 		return suite;
 	}
 }
diff --git a/bundles/org.eclipse.osgi.tests/src/org/eclipse/osgi/tests/container/NamespaceListBuilderTest.java b/bundles/org.eclipse.osgi.tests/src/org/eclipse/osgi/tests/container/NamespaceListBuilderTest.java
new file mode 100644
index 000000000..9e4553013
--- /dev/null
+++ b/bundles/org.eclipse.osgi.tests/src/org/eclipse/osgi/tests/container/NamespaceListBuilderTest.java
@@ -0,0 +1,819 @@
+/*******************************************************************************
+ * Copyright (c) 2021 Hannes Wellmann and others.
+ *
+ * This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License 2.0
+ * which accompanies this distribution, and is available at
+ * https://www.eclipse.org/legal/epl-2.0/
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ *
+ * Contributors:
+ *     Hannes Wellmann - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.osgi.tests.container;
+
+import static org.eclipse.osgi.tests.container.NamespaceListTest.build;
+import static org.eclipse.osgi.tests.container.NamespaceListTest.builderAddAfterLastMatch;
+import static org.eclipse.osgi.tests.container.NamespaceListTest.builderAddAll;
+import static org.eclipse.osgi.tests.container.NamespaceListTest.builderCreate;
+import static org.eclipse.osgi.tests.container.NamespaceListTest.builderRemoveElementsOfNamespaceIf;
+import static org.eclipse.osgi.tests.container.NamespaceListTest.builderRemoveNamespaceIf;
+import static org.eclipse.osgi.tests.container.NamespaceListTest.createEmptyNamespaceList;
+import static org.eclipse.osgi.tests.container.NamespaceListTest.getList;
+import static org.eclipse.osgi.tests.container.NamespaceListTest.newNamespace;
+import static org.eclipse.osgi.tests.container.NamespaceListTest.populate;
+import static org.eclipse.osgi.tests.container.NamespaceListTest.randomListSort;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertThrows;
+import static org.junit.Assert.assertTrue;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.NoSuchElementException;
+import java.util.function.Function;
+import org.eclipse.osgi.tests.container.NamespaceListTest.NamespaceElement;
+import org.junit.Test;
+
+public class NamespaceListBuilderTest {
+
+	@Test
+	public void testCreate() throws Exception {
+
+		Collection<NamespaceElement> builder = builderCreate();
+
+		assertTrue("Builder is not initially empty", builder.isEmpty());
+	}
+
+	@Test
+	public void testIteratorsElementSequence_multipleNamespace() throws Exception {
+		List<NamespaceElement> elements = populate(4, 3);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		Iterator<NamespaceElement> iterator = builder.iterator();
+
+		for (int i = 0; i < 12; i++) {
+			assertTrue(iterator.hasNext());
+			assertSame(elements.get(i), iterator.next());
+		}
+		assertFalse(iterator.hasNext());
+	}
+
+	@Test
+	public void testIteratorsElementSequence_oneNamespace() throws Exception {
+		List<NamespaceElement> elements = populate(3, "ns-1");
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		Iterator<NamespaceElement> iterator = builder.iterator();
+
+		for (int i = 0; i < 3; i++) {
+			assertTrue(iterator.hasNext());
+			assertSame(elements.get(i), iterator.next());
+		}
+		assertFalse(iterator.hasNext());
+	}
+
+	@Test
+	public void testIteratorsElementSequence_empty() throws Exception {
+
+		Collection<NamespaceElement> builder = builderCreate();
+
+		Iterator<NamespaceElement> iterator = builder.iterator();
+
+		assertFalse(iterator.hasNext());
+	}
+
+	@Test
+	public void testIteratorsElementSequence_iterationBeyoundEnd_NoSuchElementException() throws Exception {
+		List<NamespaceElement> elements = populate(2, 3);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		Iterator<NamespaceElement> iterator = builder.iterator();
+
+		for (int i = 0; i < 6; i++) {
+			assertTrue(iterator.hasNext());
+			assertSame(elements.get(i), iterator.next());
+		}
+		assertFalse(iterator.hasNext());
+		assertThrows(NoSuchElementException.class, iterator::next);
+	}
+
+	@Test
+	public void testIteratorsElementSequence_iterationBeyoundEndOfEmptyBuilder_NoSuchElementException()
+			throws Exception {
+
+		Collection<NamespaceElement> builder = builderCreate();
+
+		Iterator<NamespaceElement> iterator = builder.iterator();
+
+		assertFalse(iterator.hasNext());
+		assertThrows(NoSuchElementException.class, iterator::next);
+	}
+
+	@Test
+	public void testIteratorRemove_removeOneElement() throws Exception {
+
+		List<NamespaceElement> elements = populate(4, 3);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		Iterator<NamespaceElement> iterator = builder.iterator();
+
+		for (int i = 0; i < 6; i++) {
+			iterator.next();
+		}
+		iterator.remove();
+
+		elements.remove(5);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testIteratorRemove_RemoveAllElements() throws Exception {
+
+		List<NamespaceElement> elements = populate(4, 3);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		Iterator<NamespaceElement> iterator = builder.iterator();
+
+		for (int i = 0; i < 12; i++) {
+			iterator.next();
+			iterator.remove();
+		}
+
+		assertStricEqualContent(builder, Collections.emptyList());
+	}
+
+	@Test
+	public void testIteratorRemove_RemoveTwice_IllegalStateException() throws Exception {
+
+		List<NamespaceElement> elements = populate(4, 3);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		Iterator<NamespaceElement> iterator = builder.iterator();
+
+		iterator.next();
+		iterator.remove();
+		assertThrows(IllegalStateException.class, iterator::remove);
+
+		elements.remove(0);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testIteratorRemove_NextNotCalled_IllegalStateException() throws Exception {
+
+		List<NamespaceElement> elements = populate(1, 1);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		Iterator<NamespaceElement> iterator = builder.iterator();
+
+		assertThrows(IllegalStateException.class, iterator::remove);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testClear() throws Exception {
+		List<NamespaceElement> elements = populate(3, 2);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		Object namespaceList = build(builder);
+
+		builder.clear();
+
+		assertEquals(0, builder.size());
+		assertIterationOrderEquals(Collections.emptyList(), builder);
+
+		// assert that a previously build list is not affected
+
+		assertEquals(getList(namespaceList, null), elements);
+		assertEquals(getList(namespaceList, "ns-0"), elements.subList(0, 3));
+		assertEquals(getList(namespaceList, "ns-1"), elements.subList(3, 6));
+	}
+
+	// --- test addition ---
+
+	@Test
+	public void testAdd_singleElement() throws Exception {
+		NamespaceElement e = new NamespaceElement(1, "ns-1");
+
+		Collection<NamespaceElement> builder = builderCreate();
+
+		builder.add(e);
+
+		assertEquals(Collections.singletonList(e), getList(build(builder), "ns-1"));
+
+		assertStricEqualContent(builder, Collections.singletonList(e));
+	}
+
+	@Test
+	public void testAdd_multipleElements() throws Exception {
+		List<NamespaceElement> elements = populate(4, 3);
+
+		Collection<NamespaceElement> builder = builderCreate();
+
+		for (NamespaceElement element : elements) {
+			builder.add(element);
+		}
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testAddAll_namespaceSortedList() throws Exception {
+		List<NamespaceElement> elements = populate(4, 7);
+
+		Collection<NamespaceElement> builder = builderCreate();
+
+		builder.addAll(elements);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testAddAll_randomlySortedList() throws Exception {
+		List<NamespaceElement> elements = populate(4, 7);
+		randomListSort(elements);
+
+		Collection<NamespaceElement> builder = builderCreate();
+
+		builder.addAll(elements);
+
+		assertEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testAddAll_emptyList() throws Exception {
+
+		Collection<NamespaceElement> builder = builderCreate();
+
+		builder.addAll(Collections.emptyList());
+
+		assertEqualContent(builder, Collections.emptyList());
+	}
+
+	@Test
+	public void testAddAll_namespaceList() throws Exception {
+		List<NamespaceElement> elements = populate(5, 5);
+
+		Object namespaceList = newNamespace(elements);
+
+		Collection<NamespaceElement> builder = builderCreate();
+
+		builderAddAll(builder, namespaceList);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testAddAll_emptyNamespaceList() throws Exception {
+
+		Object namespaceList = createEmptyNamespaceList(NamespaceElement::getNamespace);
+
+		Collection<NamespaceElement> builder = builderCreate();
+
+		builderAddAll(builder, namespaceList);
+
+		assertStricEqualContent(builder, Collections.emptyList());
+	}
+
+	@Test
+	public void testAddAfterLastMatch_matchUpUntilTheMiddle() throws Exception {
+		List<NamespaceElement> elements = populate(4, "ns-0");
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		NamespaceElement element = new NamespaceElement(5, "ns-0");
+		builderAddAfterLastMatch(builder, element, e -> e.id < 2);
+
+		elements.add(2, element);
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testAddAfterLastMatch_allElementsMatches() throws Exception {
+		List<NamespaceElement> elements = populate(4, "ns-0");
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		NamespaceElement element = new NamespaceElement(5, "ns-0");
+		builderAddAfterLastMatch(builder, element, e -> true);
+
+		elements.add(4, element);
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testAddAfterLastMatch_noMatch() throws Exception {
+		List<NamespaceElement> elements = populate(4, "ns-0");
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		NamespaceElement element = new NamespaceElement(5, "ns-0");
+		builderAddAfterLastMatch(builder, element, e -> e.id > 100);
+
+		elements.add(0, element);
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testAddAfterLastMatch_emptyNamespaceList() throws Exception {
+		Collection<NamespaceElement> builder = builderCreate();
+
+		NamespaceElement element = new NamespaceElement(5, "ns-0");
+		builderAddAfterLastMatch(builder, element, e -> e.id < 2);
+
+		assertStricEqualContent(builder, Collections.singletonList(element));
+	}
+
+	// --- test removal ---
+
+	@Test
+	public void testRemove_elementIsOneOfMultipleOfNamespace() throws Exception {
+		List<NamespaceElement> elements = populate(4, 4);
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		assertTrue(builder.remove(new NamespaceElement(2, "ns-0")));
+
+		elements.remove(2);
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemove_onlyElementOfNamspace() throws Exception {
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.add(new NamespaceElement(3, "ns-0"));
+
+		assertTrue(builder.remove(new NamespaceElement(3, "ns-0")));
+
+		assertStricEqualContent(builder, Collections.emptyList());
+	}
+
+	@Test
+	public void testRemove_elementNotContainedInNamespaceList() throws Exception {
+		List<NamespaceElement> elements = populate(4, 3);
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		assertFalse(builder.remove(new NamespaceElement(100, "ns-0")));
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemove_elementWithNotPresentNamespace() throws Exception {
+		List<NamespaceElement> elements = populate(4, 3);
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		assertFalse(builder.remove(new NamespaceElement(1, "ns-100")));
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemove_emptyBuilder() throws Exception {
+		Collection<NamespaceElement> builder = builderCreate();
+
+		assertFalse(builder.remove(new NamespaceElement(3, "ns-0")));
+
+		assertStricEqualContent(builder, Collections.emptyList());
+	}
+
+	@Test
+	@SuppressWarnings("unlikely-arg-type")
+	public void testRemove_argumentOfOtherClass() throws Exception {
+		List<NamespaceElement> elements = populate(2, 3);
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		assertFalse(builder.remove("someString"));
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemoveAll_multipleElementsInMultipleNamsespaces() throws Exception {
+		List<NamespaceElement> elements = populate(4, 5);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		List<NamespaceElement> toRemove = new ArrayList<>();
+		toRemove.add(new NamespaceElement(1, "ns-0")); // has total index 1
+		toRemove.add(new NamespaceElement(2, "ns-1")); // has total index 6
+		toRemove.add(new NamespaceElement(0, "ns-1")); // has total index 4
+		toRemove.add(new NamespaceElement(3, "ns-3")); // has total index 15
+		toRemove.add(new NamespaceElement(2, "ns-3")); // has total index 14
+
+		assertTrue(builder.removeAll(toRemove));
+
+		elements.remove(15);
+		elements.remove(14);
+		elements.remove(6);
+		elements.remove(4);
+		elements.remove(1);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemoveAll_multipleElementsInMultipleNamsespacesAndSomeNotPresent() throws Exception {
+		List<NamespaceElement> elements = populate(4, 5);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		List<NamespaceElement> toRemove = new ArrayList<>();
+		toRemove.add(new NamespaceElement(1, "ns-0")); // has total index 1
+		toRemove.add(new NamespaceElement(2, "ns-1")); // has total index 6
+		toRemove.add(new NamespaceElement(100, "ns-2")); // not present
+		toRemove.add(new NamespaceElement(0, "ns-1")); // has total index 4
+		toRemove.add(new NamespaceElement(3, "ns-3")); // has total index 15
+		toRemove.add(new NamespaceElement(100, "ns-3")); // not present
+		toRemove.add(new NamespaceElement(2, "ns-3")); // has total index 14
+		toRemove.add(new NamespaceElement(100, "ns-3")); // not present
+		toRemove.add(new NamespaceElement(1, "ns-100")); // not present
+
+		assertTrue(builder.removeAll(toRemove));
+
+		elements.remove(15);
+		elements.remove(14);
+		elements.remove(6);
+		elements.remove(4);
+		elements.remove(1);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemoveAll_listOfAllElementsInBuilder() throws Exception {
+		List<NamespaceElement> elements = populate(4, 5);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		assertTrue(builder.removeAll(elements));
+
+		assertStricEqualContent(builder, Collections.emptyList());
+	}
+
+	@Test
+	public void testRemoveAll_emptyList() throws Exception {
+		List<NamespaceElement> elements = populate(4, 5);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		assertFalse(builder.removeAll(Collections.emptyList()));
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemoveAll_emptyBuilder() throws Exception {
+		Collection<NamespaceElement> builder = builderCreate();
+
+		assertFalse(builder.removeAll(populate(4, 3)));
+
+		assertStricEqualContent(builder, Collections.emptyList());
+	}
+
+	@Test
+	@SuppressWarnings("unlikely-arg-type")
+	public void testRemoveAll_argumentListOfOtherClass() throws Exception {
+		List<NamespaceElement> elements = populate(2, 3);
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		List<String> listOfOtherElements = Arrays.asList("someString", "other");
+		assertFalse(builder.removeAll(listOfOtherElements));
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemoveNamespaceIf_NamespaceMatches() throws Exception {
+		List<NamespaceElement> elements = populate(4, 5);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		Collection<String> namespacesToRemove = Arrays.asList("ns-0", "ns-2");
+
+		builderRemoveNamespaceIf(builder, namespacesToRemove::contains);
+
+		elements.subList(8, 12).clear();
+		elements.subList(0, 4).clear();
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemoveNamespaceIf_NamespaceMatchesExpunging() throws Exception {
+		List<NamespaceElement> elements = populate(3, 2);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		builderRemoveNamespaceIf(builder, n -> true);
+
+		assertStricEqualContent(builder, Collections.emptyList());
+	}
+
+	@Test
+	public void testRemoveNamespaceIf_NoNamespaceMatches() throws Exception {
+		List<NamespaceElement> elements = populate(3, 3);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		builderRemoveNamespaceIf(builder, "ns-100"::equals);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemoveIf_multipleMatches() throws Exception {
+		List<NamespaceElement> elements = populate(5, 5);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		builder.removeIf(e -> e.id % 3 == 0 || "ns-1".equals(e.namespace));
+
+		elements.remove(23); // first and third of 20-25
+		elements.remove(20);
+
+		elements.remove(18); // first and third of 15-20
+		elements.remove(15);
+
+		elements.remove(13); // first and third of 10-15
+		elements.remove(10);
+
+		elements.subList(5, 10).clear(); // all of 5-10
+
+		elements.remove(3); // first and third of 0-5
+		elements.remove(0);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemoveIf_allMatches() throws Exception {
+		List<NamespaceElement> elements = populate(4, 3);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		builder.removeIf(e -> true);
+
+		assertStricEqualContent(builder, Collections.emptyList());
+	}
+
+	@Test
+	public void testRemoveIf_noMatches() throws Exception {
+		List<NamespaceElement> elements = populate(4, 3);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		builder.removeIf(e -> false);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemoveElementsOfNamespaceIf_multipleMatches() throws Exception {
+		List<NamespaceElement> elements = populate(4, 2);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		builderRemoveElementsOfNamespaceIf(builder, "ns-0", e -> e.id == 1 || e.id == 2);
+
+		elements.remove(2);
+		elements.remove(1);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemoveElementsOfNamespaceIf_allElementsOfNamespaceMatch() throws Exception {
+		List<NamespaceElement> elements = populate(4, 2);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		builderRemoveElementsOfNamespaceIf(builder, "ns-0", e -> e.id == 1 || e.id == 2);
+
+		elements.remove(2);
+		elements.remove(1);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemoveElementsOfNamespaceIf_allElementsMatch() throws Exception {
+		List<NamespaceElement> elements = populate(4, 1);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		builderRemoveElementsOfNamespaceIf(builder, "ns-0", e -> true);
+
+		assertStricEqualContent(builder, Collections.emptyList());
+	}
+
+	@Test
+	public void testRemoveElementsOfNamespaceIf_noMatch() throws Exception {
+		List<NamespaceElement> elements = populate(4, 1);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		builderRemoveElementsOfNamespaceIf(builder, "ns-0", e -> false);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	@Test
+	public void testRemoveElementsOfNamespaceIf_namespaceNotPresent() throws Exception {
+		List<NamespaceElement> elements = populate(4, 1);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		builderRemoveElementsOfNamespaceIf(builder, "ns-100", e -> true);
+
+		assertStricEqualContent(builder, elements);
+	}
+
+	// --- test build ---
+
+	@Test
+	public void testBuild_notEmptyBuilder() throws Exception {
+		List<NamespaceElement> elements = populate(4, 2);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		Object namespaceList1 = build(builder);
+
+		assertEquals(elements, getList(namespaceList1, null));
+		assertEquals(elements.subList(0, 4), getList(namespaceList1, "ns-0"));
+		assertEquals(elements.subList(4, 8), getList(namespaceList1, "ns-1"));
+
+		Object namespaceList2 = build(builder);
+
+		assertEquals(elements, getList(namespaceList1, null));
+		assertEquals(elements.subList(0, 4), getList(namespaceList1, "ns-0"));
+		assertEquals(elements.subList(4, 8), getList(namespaceList1, "ns-1"));
+
+		assertEquals(elements, getList(namespaceList2, null));
+		assertEquals(elements.subList(0, 4), getList(namespaceList2, "ns-0"));
+		assertEquals(elements.subList(4, 8), getList(namespaceList2, "ns-1"));
+	}
+
+	@Test
+	public void testBuild_emptyBuilder() throws Exception {
+		Collection<NamespaceElement> builder = builderCreate();
+
+		Object namespaceList = build(builder);
+
+		assertEquals(Collections.emptyList(), getList(namespaceList, null));
+	}
+
+	@Test
+	public void testBuild_subsequentModificationOfBuilder() throws Exception {
+		List<NamespaceElement> elements = populate(4, 2);
+
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+
+		Object namespaceList1 = build(builder);
+
+		assertEquals(elements, getList(namespaceList1, null));
+		assertEquals(elements.subList(0, 4), getList(namespaceList1, "ns-0"));
+		assertEquals(elements.subList(4, 8), getList(namespaceList1, "ns-1"));
+
+		List<NamespaceElement> additionalElements = populate(1, 3);
+		builder.addAll(additionalElements);
+
+		List<NamespaceElement> newElements = new ArrayList<>(elements);
+
+		newElements.add(8, additionalElements.get(2));
+		newElements.add(8, additionalElements.get(1));
+		newElements.add(4, additionalElements.get(0));
+
+		// assert the first list build is not modified
+		assertEquals(elements, getList(namespaceList1, null));
+		assertEquals(elements.subList(0, 4), getList(namespaceList1, "ns-0"));
+		assertEquals(elements.subList(4, 8), getList(namespaceList1, "ns-1"));
+
+		// asser the new content of the builder is as expected
+		assertStricEqualContent(builder, newElements);
+	}
+
+	// --- utility methods ---
+
+	private static void assertStricEqualContent(Collection<NamespaceElement> builder,
+			List<NamespaceElement> expectedElements) throws Exception {
+		assertStricEqualContent(builder, expectedElements, NamespaceElement::getNamespace);
+	}
+
+	private static <E> void assertStricEqualContent(Collection<E> builder, List<E> expectedElements,
+			Function<E, String> getNamespace) throws Exception {
+		// test all properties of the builder and its build list in order to ensure they
+		// are updated correctly
+
+		assertIterationOrderEquals(expectedElements, builder);
+		assertEquals(expectedElements.size(), builder.size());
+
+		Map<String, List<E>> namespaceElements = getNamespaceElements(expectedElements, getNamespace);
+		Object namespaceList = build(builder);
+
+		assertEquals(expectedElements.size(), getList(namespaceList, null).size());
+
+		for (Entry<String, List<E>> entry : namespaceElements.entrySet()) {
+			String namespace = entry.getKey();
+			List<E> elements = entry.getValue();
+			assertEquals(elements, getList(namespaceList, namespace));
+		}
+
+		assertEquals(expectedElements, getList(namespaceList, null));
+	}
+
+	private static void assertEqualContent(Collection<NamespaceElement> builder,
+			List<NamespaceElement> expectedElements) throws Exception {
+		// test all properties of the builder and its build list in order to ensure they
+		// are updated correctly
+
+		assertContentEquals(expectedElements, builder);
+		assertEquals(expectedElements.size(), builder.size());
+
+		Map<String, List<NamespaceElement>> namespaceElements = getNamespaceElements(expectedElements,
+				NamespaceElement::getNamespace);
+		Object namespaceList = build(builder);
+
+		assertEquals(expectedElements.size(), getList(namespaceList, null).size());
+
+		for (Entry<String, List<NamespaceElement>> entry : namespaceElements.entrySet()) {
+			String namespace = entry.getKey();
+			List<NamespaceElement> elements = entry.getValue();
+			assertContentEquals(elements, getList(namespaceList, namespace));
+		}
+
+		assertContentEquals(expectedElements, getList(namespaceList, null));
+	}
+
+	private static <E> void assertIterationOrderEquals(Collection<E> expected, Collection<E> actual) {
+		// instead of comparing the iterators, simply compare List-copies. They reflect
+		// the iteration order.
+		assertEquals(new ArrayList<>(expected), new ArrayList<>(actual));
+	}
+
+	private static <E> void assertContentEquals(List<E> expected, Collection<E> actual) {
+		assertEquals(new HashSet<>(expected), new HashSet<>(actual));
+	}
+
+	private static <E> Map<String, List<E>> getNamespaceElements(List<E> elements, Function<E, String> getNamespace) {
+		Map<String, List<E>> namespaceElements = new HashMap<>();
+		for (E element : elements) {
+			namespaceElements.computeIfAbsent(getNamespace.apply(element), n -> new ArrayList<>()).add(element);
+		}
+		return namespaceElements;
+	}
+}
diff --git a/bundles/org.eclipse.osgi.tests/src/org/eclipse/osgi/tests/container/NamespaceListTest.java b/bundles/org.eclipse.osgi.tests/src/org/eclipse/osgi/tests/container/NamespaceListTest.java
index dea96f908..65a8af757 100644
--- a/bundles/org.eclipse.osgi.tests/src/org/eclipse/osgi/tests/container/NamespaceListTest.java
+++ b/bundles/org.eclipse.osgi.tests/src/org/eclipse/osgi/tests/container/NamespaceListTest.java
@@ -10,23 +10,24 @@
  *
  * Contributors:
  *     IBM Corporation - initial API and implementation
+ *     Hannes Wellmann - Bug 573025: introduce and apply NamespaceList.Builder
  *******************************************************************************/
 package org.eclipse.osgi.tests.container;
 
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
-import static org.junit.Assert.assertNotNull;
-import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertThrows;
 import static org.junit.Assert.assertTrue;
-import static org.junit.Assert.fail;
 
-import java.lang.reflect.Constructor;
 import java.lang.reflect.Method;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
-import java.util.Map.Entry;
+import java.util.Objects;
+import java.util.Random;
 import java.util.function.Function;
+import java.util.function.Predicate;
 import org.junit.Test;
 import org.osgi.framework.Bundle;
 
@@ -34,24 +35,96 @@ import org.osgi.framework.Bundle;
  * Using reflection because to avoid exporting internals.
  */
 public class NamespaceListTest extends AbstractTest {
-	static final Method getList;
-	static final Method isEmpty;
-	static final Method getNamespaceIndex;
-	static final Method copyList;
-	static final Constructor<?> newNamespaceList;
+	static final Method NAMESPACELIST_GET_LIST;
+	static final Method NAMESPACELIST_IS_EMPTY;
+	static final Method NAMESPACELIST_EMPTY;
+	static final Method NAMESPACELIST_CREATE_BUILDER;
+
+	// only access fields reflectively that are not part of the Collection-API
+	static final Method BUILDER_CREATE;
+	static final Method BUILDER_ADD_ALL;
+	static final Method BUILDER_ADD_AFTER_LAST_MATCH;
+	static final Method BUILDER_REMOVE_NAMESPACE_IF;
+	static final Method BUILDER_REMOVE_ELEMENTS_OF_NAMESPACE_IF;
+	static final Method BUILDER_BUILD;
+
 	static {
 		try {
-			Class<?> namespaceList = Bundle.class.getClassLoader()
-					.loadClass("org.eclipse.osgi.internal.container.NamespaceList");
-			getList = namespaceList.getMethod("getList", String.class);
-			isEmpty = namespaceList.getMethod("isEmpty");
-			getNamespaceIndex = namespaceList.getMethod("getNamespaceIndex", String.class);
-			copyList = namespaceList.getMethod("copyList");
-			newNamespaceList = namespaceList.getConstructor(List.class, Function.class);
+			ClassLoader classLoader = Bundle.class.getClassLoader();
+			Class<?> namespaceList = classLoader.loadClass("org.eclipse.osgi.internal.container.NamespaceList");
+			Class<?> namespaceListBuilder = classLoader
+					.loadClass("org.eclipse.osgi.internal.container.NamespaceList$Builder");
+
+			NAMESPACELIST_GET_LIST = namespaceList.getMethod("getList", String.class);
+			NAMESPACELIST_IS_EMPTY = namespaceList.getMethod("isEmpty");
+			NAMESPACELIST_EMPTY = namespaceList.getMethod("empty", Function.class);
+			NAMESPACELIST_CREATE_BUILDER = namespaceList.getMethod("createBuilder");
+
+			BUILDER_CREATE = namespaceListBuilder.getMethod("create", Function.class);
+			BUILDER_ADD_ALL = namespaceListBuilder.getMethod("addAll", namespaceList);
+			BUILDER_ADD_AFTER_LAST_MATCH = namespaceListBuilder.getMethod("addAfterLastMatch", Object.class,
+					Predicate.class);
+			BUILDER_REMOVE_NAMESPACE_IF = namespaceListBuilder.getMethod("removeNamespaceIf", Predicate.class);
+			BUILDER_REMOVE_ELEMENTS_OF_NAMESPACE_IF = namespaceListBuilder.getMethod("removeElementsOfNamespaceIf",
+					String.class, Predicate.class);
+			BUILDER_BUILD = namespaceListBuilder.getMethod("build");
 		} catch (Throwable t) {
 			throw new RuntimeException(t);
 		}
 	}
+
+	static Object newNamespace(List<NamespaceElement> elements) throws Exception {
+		Collection<NamespaceElement> builder = builderCreate();
+		builder.addAll(elements);
+		return build(builder);
+	}
+
+	// --- reflectively invoked methods of NamespaceList ---
+
+	static <E> Object createEmptyNamespaceList(Function<E, String> getNamespace) throws Exception {
+		return NAMESPACELIST_EMPTY.invoke(null, getNamespace);
+	}
+
+	static boolean isEmpty(Object namespaceList) throws Exception {
+		return (boolean) NAMESPACELIST_IS_EMPTY.invoke(namespaceList);
+	}
+
+	static List<NamespaceElement> getList(Object namespaceList, String namespace) throws Exception {
+		return (List<NamespaceElement>) NAMESPACELIST_GET_LIST.invoke(namespaceList, namespace);
+	}
+
+	static Collection<NamespaceElement> createBuilder(Object namespaceList) throws Exception {
+		return (Collection<NamespaceElement>) NAMESPACELIST_CREATE_BUILDER.invoke(namespaceList);
+	}
+
+	// --- reflectively invoked non-Collection methods of NamespaceList$Builder ---
+
+	static Collection<NamespaceElement> builderCreate() throws Exception {
+		Function<NamespaceElement, String> getNamespace = NamespaceElement::getNamespace;
+		return (Collection<NamespaceElement>) BUILDER_CREATE.invoke(null, getNamespace);
+	}
+
+	static <E> void builderAddAll(Collection<E> builder, Object namespaceList) throws Exception {
+		BUILDER_ADD_ALL.invoke(builder, namespaceList);
+	}
+
+	static <E> void builderAddAfterLastMatch(Collection<E> builder, E e, Predicate<E> matcher) throws Exception {
+		BUILDER_ADD_AFTER_LAST_MATCH.invoke(builder, e, matcher);
+	}
+
+	static <E> void builderRemoveNamespaceIf(Collection<E> builder, Predicate<String> filter) throws Exception {
+		BUILDER_REMOVE_NAMESPACE_IF.invoke(builder, filter);
+	}
+
+	static <E> void builderRemoveElementsOfNamespaceIf(Collection<E> builder, String namespace, Predicate<E> filter)
+			throws Exception {
+		BUILDER_REMOVE_ELEMENTS_OF_NAMESPACE_IF.invoke(builder, namespace, filter);
+	}
+
+	static <E> Object build(Collection<E> builder) throws Exception {
+		return BUILDER_BUILD.invoke(builder);
+	}
+
 	static class NamespaceElement {
 		final int id;
 		final String namespace;
@@ -81,7 +154,7 @@ public class NamespaceListTest extends AbstractTest {
 
 		@Override
 		public int hashCode() {
-			return namespace.hashCode() ^ id;
+			return Objects.hash(namespace, id);
 		}
 
 		@Override
@@ -90,10 +163,14 @@ public class NamespaceListTest extends AbstractTest {
 		}
 	}
 
-	static final Function<NamespaceElement, String> getNamespaceFunc = (Function<NamespaceElement, String>) NamespaceElement::getNamespace;
-	Object newNamespace(List<NamespaceElement> elements) throws Exception {
-		return newNamespaceList.newInstance(elements, getNamespaceFunc);
+	// --- tests ---
+
+	@Test
+	public void testCreateEmptyList() throws Exception {
+		Object namespaceList = createEmptyNamespaceList(NamespaceElement::getNamespace);
+		assertTrue("List is not empty.", isEmpty(namespaceList));
 	}
+
 	@Test
 	public void testIsEmpty() throws Exception {
 		Object namespaceList = newNamespace(Collections.emptyList());
@@ -109,14 +186,6 @@ public class NamespaceListTest extends AbstractTest {
 		assertFalse("List is empty.", isEmpty(namespaceList));
 	}
 
-	private boolean isEmpty(Object namespaceList) throws Exception {
-		return (boolean) isEmpty.invoke(namespaceList);
-	}
-
-	private List<NamespaceElement> getList(Object namespaceList, String namespace) throws Exception {
-		return (List<NamespaceElement>) getList.invoke(namespaceList, namespace);
-	}
-
 	@Test
 	public void testGetList() throws Exception {
 		Object namespaceList = newNamespace(Collections.emptyList());
@@ -145,31 +214,9 @@ public class NamespaceListTest extends AbstractTest {
 	}
 
 	@Test
-	public void testGetNamespaceIndex() throws Exception {
-		Object namespaceList = newNamespace(Collections.emptyList());
-		assertNull("Unexpected index.", getNamespaceIndex(namespaceList, "ns-0"));
-
-		List<NamespaceElement> elements = populate(21, 13);
-
-		namespaceList = newNamespace(elements);
-		Entry<Integer, Integer> nsIndex = getNamespaceIndex(namespaceList, "ns-0");
-		assertNotNull("Expected an index", nsIndex);
-		checkIndex(nsIndex, 0, 21);
-
-		nsIndex = getNamespaceIndex(namespaceList, "ns-12");
-		assertNotNull("Expected an index", nsIndex);
-		checkIndex(nsIndex, 21 * 12, 21 * 13);
-
-		nsIndex = getNamespaceIndex(namespaceList, "ns-4");
-		assertNotNull("Expected an index", nsIndex);
-		checkIndex(nsIndex, 21 * 4, 21 * 5);
-	}
-
-	@Test
 	public void testOutOfOrderNamespace() throws Exception {
 		List<NamespaceElement> elements = populate(4, 4);
-		// random sort by hashcode
-		elements.sort((n1, n2) -> n1.hashCode() - n2.hashCode());
+		randomListSort(elements);
 		Object namespaceList = newNamespace(elements);
 		for (int i = 0; i < 4; i++) {
 			List<NamespaceElement> list = getList(namespaceList, "ns-" + i);
@@ -183,54 +230,29 @@ public class NamespaceListTest extends AbstractTest {
 	}
 
 	@Test
-	public void testCopyList() throws Exception {
-		Object namespaceList = newNamespace(Collections.emptyList());
-		List<NamespaceElement> copy = copyList(namespaceList);
-		assertEquals("Wrong list.", Collections.emptyList(), copy);
-		successAdd(copy);
-		copy = copyList(namespaceList);
-		assertEquals("Wrong list.", Collections.emptyList(), copy);
+	public void testCreateBuilder() throws Exception {
 
-		List<NamespaceElement> elements = populate(100, 13);
-		namespaceList = newNamespace(elements);
-		copy = copyList(namespaceList);
-		assertEquals("Wrong list.", elements, copy);
-		successAdd(copy);
-		copy = copyList(namespaceList);
-		assertEquals("Wrong list.", elements, copy);
-	}
+		List<NamespaceElement> elements = populate(5, 10);
+		Object namespaceList = newNamespace(elements);
+		Collection<NamespaceElement> builder = createBuilder(namespaceList);
 
-	private List<NamespaceElement> copyList(Object namespaceList) throws Exception {
-		return (List<NamespaceElement>) copyList.invoke(namespaceList);
-	}
+		Object buildNamespaceList = build(builder);
 
-	private void checkIndex(Entry<Integer, Integer> nsIndex, int start, int end) {
-		assertEquals("Unexpected Start", start, (int) nsIndex.getKey());
-	}
+		// The order of all elements should be maintained
 
-	private Entry<Integer, Integer> getNamespaceIndex(Object namespaceList, String namespace) throws Exception {
-		return (Entry<Integer, Integer>) getNamespaceIndex.invoke(namespaceList, namespace);
+		assertEquals("Builder not populated correctly", getList(buildNamespaceList, null),
+				getList(namespaceList, null));
 	}
 
-	private void failAdd(List<NamespaceElement> list) {
-		try {
-			list.add(new NamespaceElement(0, "ns"));
-			fail("Should fail to modify list");
-		} catch (UnsupportedOperationException e) {
-			// expected
-		}
-	}
+	// --- uility methods ---
 
-	private void successAdd(List<NamespaceElement> list) {
-		try {
-			list.add(new NamespaceElement(0, "ns"));
-		} catch (UnsupportedOperationException e) {
-			fail("Should not fail to modify list");
-		}
+	private void failAdd(List<NamespaceElement> list) {
+		NamespaceElement e = new NamespaceElement(0, "ns");
+		assertThrows(UnsupportedOperationException.class, () -> list.add(e));
 	}
 
-	private List<NamespaceElement> populate(int numElementsPerNS, int numNS) {
-		ArrayList<NamespaceElement> elements = new ArrayList<>(numElementsPerNS * numNS);
+	static List<NamespaceElement> populate(int numElementsPerNS, int numNS) {
+		List<NamespaceElement> elements = new ArrayList<>(numElementsPerNS * numNS);
 		for (int namespace = 0; namespace < numNS; namespace++) {
 			for (int element = 0; element < numElementsPerNS; element++) {
 				elements.add(new NamespaceElement(element, "ns-" + namespace));
@@ -239,11 +261,16 @@ public class NamespaceListTest extends AbstractTest {
 		return elements;
 	}
 
-	private List<NamespaceElement> populate(int numElements, String namespace) {
-		ArrayList<NamespaceElement> elements = new ArrayList<>(numElements);
+	static List<NamespaceElement> populate(int numElements, String namespace) {
+		List<NamespaceElement> elements = new ArrayList<>(numElements);
 		for (int element = 0; element < numElements; element++) {
 			elements.add(new NamespaceElement(element, namespace));
 		}
 		return elements;
 	}
+
+	static void randomListSort(List<NamespaceElement> elements) {
+		// random sort in reproducible order
+		Collections.shuffle(elements, new Random(43L));
+	}
 }
diff --git a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleContainer.java b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleContainer.java
index 52367f348..c8f1919b8 100644
--- a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleContainer.java
+++ b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleContainer.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2012, 2020 IBM Corporation and others.
+ * Copyright (c) 2012, 2021 IBM Corporation and others.
  *
  * This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License 2.0
@@ -13,8 +13,6 @@
  *******************************************************************************/
 package org.eclipse.osgi.container;
 
-import static org.eclipse.osgi.internal.container.NamespaceList.WIRE;
-
 import java.io.Closeable;
 import java.security.AccessController;
 import java.security.PrivilegedAction;
@@ -1049,9 +1047,9 @@ public final class ModuleContainer implements DebugOptionsListener {
 					return null; // need to try again
 				// remove any wires from unresolved wirings that got removed
 				for (Map.Entry<ModuleWiring, Collection<ModuleWire>> entry : toRemoveWireLists.entrySet()) {
-					List<ModuleWire> provided = entry.getKey().getProvidedWires().copyList();
+					NamespaceList.Builder<ModuleWire> provided = entry.getKey().getProvidedWires().createBuilder();
 					provided.removeAll(entry.getValue());
-					entry.getKey().setProvidedWires(new NamespaceList<>(provided, WIRE));
+					entry.getKey().setProvidedWires(provided.build());
 					for (ModuleWire removedWire : entry.getValue()) {
 						// invalidate the wire
 						removedWire.invalidate();
diff --git a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleDatabase.java b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleDatabase.java
index 4e8689a1b..108714d05 100644
--- a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleDatabase.java
+++ b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleDatabase.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2012, 2020 IBM Corporation and others.
+ * Copyright (c) 2012, 2021 IBM Corporation and others.
  *
  * This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License 2.0
@@ -13,8 +13,6 @@
  *******************************************************************************/
 package org.eclipse.osgi.container;
 
-import static org.eclipse.osgi.internal.container.NamespaceList.WIRE;
-
 import java.io.DataInputStream;
 import java.io.DataOutputStream;
 import java.io.IOException;
@@ -44,6 +42,7 @@ import org.eclipse.osgi.framework.util.ObjectPool;
 import org.eclipse.osgi.internal.container.Capabilities;
 import org.eclipse.osgi.internal.container.ComputeNodeOrder;
 import org.eclipse.osgi.internal.container.NamespaceList;
+import org.eclipse.osgi.internal.container.NamespaceList.Builder;
 import org.eclipse.osgi.internal.framework.EquinoxConfiguration;
 import org.osgi.framework.BundleException;
 import org.osgi.framework.Constants;
@@ -412,9 +411,9 @@ public class ModuleDatabase {
 				}
 				// remove any wires from unresolved wirings that got removed
 				for (Map.Entry<ModuleWiring, Collection<ModuleWire>> entry : toRemoveWireLists.entrySet()) {
-					List<ModuleWire> provided = entry.getKey().getProvidedWires().copyList();
+					NamespaceList.Builder<ModuleWire> provided = entry.getKey().getProvidedWires().createBuilder();
 					provided.removeAll(entry.getValue());
-					entry.getKey().setProvidedWires(new NamespaceList<>(provided, WIRE));
+					entry.getKey().setProvidedWires(provided.build());
 					for (ModuleWire removedWire : entry.getValue()) {
 						// invalidate the wire
 						removedWire.invalidate();
@@ -503,13 +502,9 @@ public class ModuleDatabase {
 	final Map<ModuleRevision, ModuleWiring> getWiringsClone() {
 		readLock();
 		try {
-			Map<ModuleRevision, ModuleWiring> clonedWirings = new HashMap<>();
-			for (Map.Entry<ModuleRevision, ModuleWiring> entry : wirings.entrySet()) {
-				ModuleWiring wiring = new ModuleWiring(entry.getKey(), entry.getValue().getCapabilities(),
-						entry.getValue().getRequirements(), entry.getValue().getProvidedWires(),
-						entry.getValue().getRequiredWires(), entry.getValue().getSubstitutedNames());
-				clonedWirings.put(entry.getKey(), wiring);
-			}
+			Map<ModuleRevision, ModuleWiring> clonedWirings = new HashMap<>(wirings);
+			clonedWirings.replaceAll((r, w) -> new ModuleWiring(r, w.getCapabilities(), w.getRequirements(),
+					w.getProvidedWires(), w.getRequiredWires(), w.getSubstitutedNames()));
 			return clonedWirings;
 		} finally {
 			readUnlock();
@@ -1393,25 +1388,25 @@ public class ModuleDatabase {
 				throw new NullPointerException("Could not find revision for wiring."); //$NON-NLS-1$
 
 			int numCapabilities = in.readInt();
-			List<ModuleCapability> capabilities = new ArrayList<>(numCapabilities);
+			NamespaceList.Builder<ModuleCapability> capabilities = Builder.create(NamespaceList.CAPABILITY);
 			for (int i = 0; i < numCapabilities; i++) {
 				capabilities.add((ModuleCapability) objectTable.get(in.readInt()));
 			}
 
 			int numRequirements = in.readInt();
-			List<ModuleRequirement> requirements = new ArrayList<>(numRequirements);
+			NamespaceList.Builder<ModuleRequirement> requirements = Builder.create(NamespaceList.REQUIREMENT);
 			for (int i = 0; i < numRequirements; i++) {
 				requirements.add((ModuleRequirement) objectTable.get(in.readInt()));
 			}
 
 			int numProvidedWires = in.readInt();
-			List<ModuleWire> providedWires = new ArrayList<>(numProvidedWires);
+			NamespaceList.Builder<ModuleWire> providedWires = Builder.create(NamespaceList.WIRE);
 			for (int i = 0; i < numProvidedWires; i++) {
 				providedWires.add((ModuleWire) objectTable.get(in.readInt()));
 			}
 
 			int numRequiredWires = in.readInt();
-			List<ModuleWire> requiredWires = new ArrayList<>(numRequiredWires);
+			NamespaceList.Builder<ModuleWire> requiredWires = Builder.create(NamespaceList.WIRE);
 			for (int i = 0; i < numRequiredWires; i++) {
 				requiredWires.add((ModuleWire) objectTable.get(in.readInt()));
 			}
@@ -1422,7 +1417,8 @@ public class ModuleDatabase {
 				substituted.add(readString(in, objectTable));
 			}
 
-			return new ModuleWiring(revision, capabilities, requirements, providedWires, requiredWires, substituted);
+			return new ModuleWiring(revision, capabilities.build(), requirements.build(), providedWires.build(),
+					requiredWires.build(), substituted);
 		}
 
 		private static void writeGenericInfo(String namespace, Map<String, ?> attributes, Map<String, String> directives, DataOutputStream out, Map<Object, Integer> objectTable) throws IOException {
diff --git a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleResolver.java b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleResolver.java
index 3a40b5bec..91eebcf11 100644
--- a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleResolver.java
+++ b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleResolver.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2012, 2020 IBM Corporation and others.
+ * Copyright (c) 2012, 2021 IBM Corporation and others.
  *
  * This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License 2.0
@@ -29,7 +29,6 @@ import java.util.Iterator;
 import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
-import java.util.ListIterator;
 import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.CancellationException;
@@ -40,7 +39,6 @@ import java.util.concurrent.ScheduledFuture;
 import java.util.concurrent.TimeUnit;
 import java.util.concurrent.atomic.AtomicBoolean;
 import java.util.concurrent.atomic.AtomicReference;
-import java.util.function.Function;
 import org.apache.felix.resolver.Logger;
 import org.apache.felix.resolver.ResolutionError;
 import org.apache.felix.resolver.ResolverImpl;
@@ -48,6 +46,7 @@ import org.eclipse.osgi.container.ModuleRequirement.DynamicModuleRequirement;
 import org.eclipse.osgi.container.namespaces.EquinoxFragmentNamespace;
 import org.eclipse.osgi.internal.container.InternalUtils;
 import org.eclipse.osgi.internal.container.NamespaceList;
+import org.eclipse.osgi.internal.container.NamespaceList.Builder;
 import org.eclipse.osgi.internal.debug.Debug;
 import org.eclipse.osgi.internal.framework.EquinoxConfiguration;
 import org.eclipse.osgi.internal.framework.EquinoxContainer;
@@ -183,17 +182,15 @@ final class ModuleResolver {
 
 	Map<ModuleRevision, ModuleWiring> generateDelta(Map<Resource, List<Wire>> result, Map<ModuleRevision, ModuleWiring> wiringCopy) {
 		Map<ModuleRevision, Map<ModuleCapability, List<ModuleWire>>> provided = new HashMap<>();
-		Map<ModuleRevision, List<ModuleWire>> required = new HashMap<>();
+		Map<ModuleRevision, NamespaceList<ModuleWire>> required = new HashMap<>(result.size() * 4 / 3 + 1);
 		// First populate the list of provided and required wires for revision
 		// This is done this way to share the wire object between both the provider and requirer
 		for (Map.Entry<Resource, List<Wire>> resultEntry : result.entrySet()) {
 			ModuleRevision revision = (ModuleRevision) resultEntry.getKey();
-			List<ModuleWire> requiredWires = new ArrayList<>(resultEntry.getValue().size());
-			List<String> seen = new ArrayList<>(5);
+			NamespaceList.Builder<ModuleWire> requiredWires = NamespaceList.Builder.create(WIRE);
 			for (Wire wire : resultEntry.getValue()) {
 				ModuleWire moduleWire = new ModuleWire((ModuleCapability) wire.getCapability(), (ModuleRevision) wire.getProvider(), (ModuleRequirement) wire.getRequirement(), (ModuleRevision) wire.getRequirer());
-				requiredWires.add(getInsertIndex(moduleWire.getCapability().getNamespace(), requiredWires, seen,
-						NamespaceList.WIRE), moduleWire);
+				requiredWires.add(moduleWire);
 				Map<ModuleCapability, List<ModuleWire>> providedWiresMap = provided.get(moduleWire.getProvider());
 				if (providedWiresMap == null) {
 					providedWiresMap = new HashMap<>();
@@ -206,7 +203,7 @@ final class ModuleResolver {
 				}
 				providedWires.add(moduleWire);
 			}
-			required.put(revision, requiredWires);
+			required.put(revision, requiredWires.build());
 		}
 
 		Map<ModuleRevision, ModuleWiring> delta = new HashMap<>();
@@ -232,148 +229,96 @@ final class ModuleResolver {
 		return delta;
 	}
 
-	private ModuleWiring createNewWiring(ModuleRevision revision, Map<ModuleRevision, Map<ModuleCapability, List<ModuleWire>>> provided, Map<ModuleRevision, List<ModuleWire>> required) {
-		Map<ModuleCapability, List<ModuleWire>> providedWireMap = provided.get(revision);
-		if (providedWireMap == null)
-			providedWireMap = Collections.emptyMap();
-		List<ModuleWire> requiredWires = required.get(revision);
-		if (requiredWires == null)
-			requiredWires = Collections.emptyList();
+	private ModuleWiring createNewWiring(ModuleRevision revision, Map<ModuleRevision, Map<ModuleCapability, List<ModuleWire>>> provided, Map<ModuleRevision, NamespaceList<ModuleWire>> required) {
 
-		List<ModuleCapability> capabilities = sortByNamespaceCopy(revision.getModuleCapabilities(null), CAPABILITY);
-		ListIterator<ModuleCapability> iCapabilities = capabilities.listIterator(capabilities.size());
-		List<ModuleRequirement> requirements = sortByNamespaceCopy(revision.getModuleRequirements(null), REQUIREMENT);
-		ListIterator<ModuleRequirement> iRequirements = requirements.listIterator(requirements.size());
+		Map<ModuleCapability, List<ModuleWire>> providedWireMap = provided.getOrDefault(revision, Collections.emptyMap());
+		NamespaceList<ModuleWire> requiredWires = required.getOrDefault(revision, NamespaceList.empty(WIRE));
+
+		NamespaceList.Builder<ModuleCapability> capabilities = Builder.create(CAPABILITY);
+		capabilities.addAll(revision.getModuleCapabilities(null));
+		NamespaceList.Builder<ModuleRequirement> requirements = Builder.create(REQUIREMENT);
+		requirements.addAll(revision.getModuleRequirements(null));
 
 		// if revision is a fragment remove payload requirements and capabilities
 		if ((BundleRevision.TYPE_FRAGMENT & revision.getTypes()) != 0) {
-			removePayloadContent(iCapabilities, iRequirements);
+			removePayloadContent(capabilities, requirements);
 		} else {
 			// add fragment capabilities and requirements
 			List<ModuleCapability> hostCapabilities = revision.getModuleCapabilities(HostNamespace.HOST_NAMESPACE);
 			ModuleCapability hostCapability = hostCapabilities.isEmpty() ? null : hostCapabilities.get(0);
 			if (hostCapability != null) {
-				addPayloadContent(providedWireMap.get(hostCapability), iCapabilities, iRequirements);
+				addPayloadContent(providedWireMap.get(hostCapability), capabilities, requirements);
 			}
 		}
 
-		removeNonEffectiveCapabilities(iCapabilities);
-		removeNonEffectiveRequirements(iRequirements, requiredWires);
-		Collection<String> substituted = removeSubstitutedCapabilities(iCapabilities, requiredWires);
+		removeNonEffectiveCapabilities(capabilities);
+		removeNonEffectiveRequirements(requirements, requiredWires);
+		Collection<String> substituted = removeSubstitutedCapabilities(capabilities, requiredWires);
 
-		List<ModuleWire> providedWires = new ArrayList<>();
+		NamespaceList.Builder<ModuleWire> providedWires = NamespaceList.Builder.create(WIRE);
 		addProvidedWires(providedWireMap, providedWires, capabilities);
 
 		InternalUtils.filterCapabilityPermissions(capabilities);
-		return new ModuleWiring(revision, new NamespaceList<>(capabilities, CAPABILITY),
-				new NamespaceList<>(requirements, REQUIREMENT), new NamespaceList<>(providedWires, WIRE),
-				new NamespaceList<>(requiredWires, WIRE), substituted);
-	}
+		return new ModuleWiring(revision, capabilities.build(), requirements.build(), providedWires.build(),
+				requiredWires, substituted);
 
-	private <E> List<E> sortByNamespaceCopy(List<E> elements, Function<E, String> getNamespace) {
-		List<E> result = new ArrayList<>(elements.size());
-		List<String> seen = new ArrayList<>();
-		for (E e : elements) {
-			String namespace = getNamespace.apply(e);
-			result.add(getInsertIndex(namespace, result, seen, getNamespace), e);
-		}
-		return result;
 	}
 
-	private <E> int getInsertIndex(String namespace, List<E> elements, List<String> seen,
-			Function<E, String> getNamespace) {
-		if (seen.contains(namespace)) {
-			for (int i = elements.size() - 1; i > -1; i--) {
-				if (namespace.equals(getNamespace.apply(elements.get(i)))) {
-					return i + 1;
-				}
-			}
-			throw new IllegalStateException();
-		}
-		seen.add(namespace);
-		return elements.size();
-	}
-
-	private static void removePayloadContent(ListIterator<ModuleCapability> iCapabilities, ListIterator<ModuleRequirement> iRequirements) {
-		rewind(iCapabilities);
-		while (iCapabilities.hasNext()) {
-			if (!NON_PAYLOAD_CAPABILITIES.contains(iCapabilities.next().getNamespace())) {
-				iCapabilities.remove();
-			}
-		}
+	private static void removePayloadContent(NamespaceList.Builder<ModuleCapability> capabilities,
+			NamespaceList.Builder<ModuleRequirement> requirements) {
 
-		rewind(iRequirements);
-		while (iRequirements.hasNext()) {
-			if (!NON_PAYLOAD_REQUIREMENTS.contains(iRequirements.next().getNamespace())) {
-				iRequirements.remove();
-			}
-		}
+		capabilities.removeNamespaceIf(namespace -> !NON_PAYLOAD_CAPABILITIES.contains(namespace));
+		requirements.removeNamespaceIf(namespace -> !NON_PAYLOAD_REQUIREMENTS.contains(namespace));
 	}
 
-	private static Collection<String> removeSubstitutedCapabilities(ListIterator<ModuleCapability> iCapabilities, List<ModuleWire> requiredWires) {
-		Collection<String> substituted = null;
-		for (ModuleWire moduleWire : requiredWires) {
-			if (!PackageNamespace.PACKAGE_NAMESPACE.equals(moduleWire.getCapability().getNamespace()))
-				continue;
+	private static Collection<String> removeSubstitutedCapabilities(NamespaceList.Builder<ModuleCapability> capabilities, NamespaceList<ModuleWire> requiredWires) {
+		Collection<String> substituted = new ArrayList<>();
+		for (ModuleWire moduleWire : requiredWires.getList(PackageNamespace.PACKAGE_NAMESPACE)) {
 			String packageName = (String) moduleWire.getCapability().getAttributes().get(PackageNamespace.PACKAGE_NAMESPACE);
-			rewind(iCapabilities);
-			while (iCapabilities.hasNext()) {
-				ModuleCapability capability = iCapabilities.next();
-				if (PackageNamespace.PACKAGE_NAMESPACE.equals(capability.getNamespace())) {
-					if (packageName.equals(capability.getAttributes().get(PackageNamespace.PACKAGE_NAMESPACE))) {
-						// found a package capability with the same name as a package that got imported
-						// this indicates a substitution
-						iCapabilities.remove();
-						if (substituted == null) {
-							substituted = new ArrayList<>();
-						}
-						if (!substituted.contains(packageName)) {
-							substituted.add(packageName);
-						}
+			capabilities.removeElementsOfNamespaceIf(PackageNamespace.PACKAGE_NAMESPACE, capability -> {
+				if (packageName.equals(capability.getAttributes().get(PackageNamespace.PACKAGE_NAMESPACE))) {
+					// found a package capability with the same name as a package that got imported
+					// this indicates a substitution
+					if (!substituted.contains(packageName)) {
+						substituted.add(packageName);
 					}
+					return true;
 				}
-			}
+				return false;
+			});
 		}
-		return substituted == null ? Collections.<String> emptyList() : substituted;
+		return substituted.isEmpty() ? Collections.emptyList() : substituted;
 	}
 
-	private static void removeNonEffectiveRequirements(ListIterator<ModuleRequirement> iRequirements, List<ModuleWire> requiredWires) {
+	private static void removeNonEffectiveRequirements(NamespaceList.Builder<ModuleRequirement> requirements, NamespaceList<ModuleWire> requiredWires) {
 
 		Set<ModuleRequirement> wireRequirements = new HashSet<>();
-		for (ModuleWire mw : requiredWires) {
+		for (ModuleWire mw : requiredWires.getList(null)) {
 			wireRequirements.add(mw.getRequirement());
 		}
-
-		rewind(iRequirements);
-		while (iRequirements.hasNext()) {
-			ModuleRequirement requirement = iRequirements.next();
+		requirements.removeIf(requirement -> {
 			// check the effective directive;
 			Object effective = requirement.getDirectives().get(Namespace.REQUIREMENT_EFFECTIVE_DIRECTIVE);
 			if (effective != null && !Namespace.EFFECTIVE_RESOLVE.equals(effective)) {
-				iRequirements.remove();
-			} else {
-
-				if (!wireRequirements.contains(requirement)) {
-					if (!PackageNamespace.PACKAGE_NAMESPACE.equals(requirement.getNamespace())) {
-						iRequirements.remove();
-					} else {
-						Object resolution = requirement.getDirectives().get(Namespace.REQUIREMENT_RESOLUTION_DIRECTIVE);
-						if (!PackageNamespace.RESOLUTION_DYNAMIC.equals(resolution)) {
-							iRequirements.remove();
-						}
-					}
+				return true;
+			}
+			if (!wireRequirements.contains(requirement)) {
+				if (!PackageNamespace.PACKAGE_NAMESPACE.equals(requirement.getNamespace())) {
+					return true;
+				}
+				Object resolution = requirement.getDirectives().get(Namespace.REQUIREMENT_RESOLUTION_DIRECTIVE);
+				if (!PackageNamespace.RESOLUTION_DYNAMIC.equals(resolution)) {
+					return true;
 				}
 			}
-		}
+			return false;
+		});
 	}
 
-	void removeNonEffectiveCapabilities(ListIterator<ModuleCapability> iCapabilities) {
-		rewind(iCapabilities);
-		while (iCapabilities.hasNext()) {
-			Capability capability = iCapabilities.next();
+	void removeNonEffectiveCapabilities(Collection<ModuleCapability> capabilities) {
+		capabilities.removeIf(capability -> {
 			Object effective = capability.getDirectives().get(Namespace.CAPABILITY_EFFECTIVE_DIRECTIVE);
 			if (effective != null && !Namespace.EFFECTIVE_RESOLVE.equals(effective)) {
-				iCapabilities.remove();
 				if (DEBUG_PROVIDERS) {
 					Debug.println(new StringBuilder("RESOLVER: Capability filtered because it was not effective") //$NON-NLS-1$
 							.append(SEPARATOR).append(TAB) //
@@ -384,16 +329,18 @@ final class ModuleResolver {
 							.append(capability.getResource()) //
 							.toString());
 				}
+				return true;
 			}
-		}
+			return false;
+		});
 	}
 
-	private static void addPayloadContent(List<ModuleWire> hostWires, ListIterator<ModuleCapability> iCapabilities, ListIterator<ModuleRequirement> iRequirements) {
+	private static void addPayloadContent(List<ModuleWire> hostWires, NamespaceList.Builder<ModuleCapability> capabilities, NamespaceList.Builder<ModuleRequirement> requirements) {
 		if (hostWires == null)
 			return;
 		for (ModuleWire hostWire : hostWires) {
+
 			// add fragment capabilities
-			String currentNamespace = null;
 			List<ModuleCapability> fragmentCapabilities = hostWire.getRequirer().getModuleCapabilities(null);
 			for (ModuleCapability fragmentCapability : fragmentCapabilities) {
 				if (NON_PAYLOAD_CAPABILITIES.contains(fragmentCapability.getNamespace())) {
@@ -403,23 +350,10 @@ final class ModuleResolver {
 				if (effective != null && !Namespace.EFFECTIVE_RESOLVE.equals(effective)) {
 					continue; // don't include, not effective
 				}
-				if (!fragmentCapability.getNamespace().equals(currentNamespace)) {
-					currentNamespace = fragmentCapability.getNamespace();
-					fastForward(iCapabilities);
-					while (iCapabilities.hasPrevious()) {
-						if (iCapabilities.previous().getNamespace().equals(currentNamespace)) {
-							iCapabilities.next(); // put position after the last one
-							break;
-						}
-					}
-				}
-				if (!iCapabilities.hasPrevious()) {
-					fastForward(iCapabilities);
-				}
-				iCapabilities.add(fragmentCapability);
+				capabilities.add(fragmentCapability);
 			}
+
 			// add fragment requirements
-			currentNamespace = null;
 			List<ModuleRequirement> fragmentRequriements = hostWire.getRequirer().getModuleRequirements(null);
 			for (ModuleRequirement fragmentRequirement : fragmentRequriements) {
 				if (NON_PAYLOAD_REQUIREMENTS.contains(fragmentRequirement.getNamespace())) {
@@ -429,24 +363,12 @@ final class ModuleResolver {
 				if (effective != null && !Namespace.EFFECTIVE_RESOLVE.equals(effective)) {
 					continue; // don't include, not effective
 				}
-				if (!fragmentRequirement.getNamespace().equals(currentNamespace)) {
-					currentNamespace = fragmentRequirement.getNamespace();
-					boolean isDynamic = isDynamic(fragmentRequirement);
-					fastForward(iRequirements);
-					while (iRequirements.hasPrevious()) {
-						ModuleRequirement previous = iRequirements.previous();
-						if (previous.getNamespace().equals(currentNamespace)) {
-							if (isDynamic || !isDynamic(previous)) {
-								iRequirements.next(); // put position after the last one
-								break;
-							}
-						}
-					}
-				}
-				if (!iRequirements.hasPrevious()) {
-					fastForward(iRequirements);
+				if (!PackageNamespace.PACKAGE_NAMESPACE.equals(fragmentRequirement.getNamespace())
+						|| isDynamic(fragmentRequirement)) {
+					requirements.add(fragmentRequirement);
+				} else {
+					requirements.addAfterLastMatch(fragmentRequirement, r -> !isDynamic(r));
 				}
-				iRequirements.add(fragmentRequirement);
 			}
 		}
 	}
@@ -455,61 +377,24 @@ final class ModuleResolver {
 		return PackageNamespace.PACKAGE_NAMESPACE.equals(requirement.getNamespace()) && PackageNamespace.RESOLUTION_DYNAMIC.equals(requirement.getDirectives().get(Namespace.REQUIREMENT_RESOLUTION_DIRECTIVE));
 	}
 
-	private static void addProvidedWires(Map<ModuleCapability, List<ModuleWire>> toAdd, List<ModuleWire> existing, final List<ModuleCapability> orderedCapabilities) {
+	private static void addProvidedWires(Map<ModuleCapability, List<ModuleWire>> toAdd,
+			NamespaceList.Builder<ModuleWire> existing, NamespaceList.Builder<ModuleCapability> capabilities) {
 		if (toAdd == null)
 			return;
-		int originalSize = existing.size();
-		for (ModuleCapability capability : orderedCapabilities) {
+		for (ModuleCapability capability : capabilities) {
 			List<ModuleWire> newWires = toAdd.get(capability);
 			if (newWires != null) {
 				existing.addAll(newWires);
 			}
 		}
-		if (originalSize != 0) {
-			Collections.sort(existing, new Comparator<ModuleWire>() {
-				@Override
-				public int compare(ModuleWire w1, ModuleWire w2) {
-					int index1 = orderedCapabilities.indexOf(w1.getCapability());
-					int index2 = orderedCapabilities.indexOf(w2.getCapability());
-					return index1 - index2;
-				}
-			});
-		}
-	}
-
-	private static void addRequiredWires(List<ModuleWire> toAdd, List<ModuleWire> existing, final List<ModuleRequirement> orderedRequirements) {
-		if (toAdd == null)
-			return;
-		int originalSize = existing.size();
-		existing.addAll(toAdd);
-		if (originalSize != 0) {
-			Collections.sort(existing, new Comparator<ModuleWire>() {
-				@Override
-				public int compare(ModuleWire w1, ModuleWire w2) {
-					int index1 = orderedRequirements.indexOf(w1.getRequirement());
-					int index2 = orderedRequirements.indexOf(w2.getRequirement());
-					return index1 - index2;
-				}
-			});
-		}
 	}
 
-	private static void fastForward(ListIterator<?> listIterator) {
-		while (listIterator.hasNext())
-			listIterator.next();
-	}
-
-	static void rewind(ListIterator<?> listIterator) {
-		while (listIterator.hasPrevious())
-			listIterator.previous();
-	}
-
-	private static ModuleWiring createWiringDelta(ModuleRevision revision, ModuleWiring existingWiring, Map<ModuleCapability, List<ModuleWire>> providedWireMap, List<ModuleWire> requiredWires) {
+	private static ModuleWiring createWiringDelta(ModuleRevision revision, ModuleWiring existingWiring, Map<ModuleCapability, List<ModuleWire>> providedWireMap, NamespaceList<ModuleWire> requiredWires) {
 		// No null checks are done here on the wires since this is a copy.
-		List<ModuleWire> existingProvidedWires = existingWiring.getProvidedWires().copyList();
-		List<ModuleCapability> existingCapabilities = existingWiring.getCapabilities().copyList();
-		List<ModuleWire> existingRequiredWires = existingWiring.getRequiredWires().copyList();
-		List<ModuleRequirement> existingRequirements = existingWiring.getRequirements().copyList();
+		NamespaceList.Builder<ModuleWire> existingProvidedWires = existingWiring.getProvidedWires().createBuilder();
+		NamespaceList.Builder<ModuleCapability> existingCapabilities = existingWiring.getCapabilities().createBuilder();
+		NamespaceList.Builder<ModuleWire> existingRequiredWires = existingWiring.getRequiredWires().createBuilder();
+		NamespaceList.Builder<ModuleRequirement> existingRequirements = existingWiring.getRequirements().createBuilder();
 
 		// First, add newly resolved fragment capabilities and requirements
 		if (providedWireMap != null) {
@@ -517,7 +402,7 @@ final class ModuleResolver {
 			ModuleCapability hostCapability = hostCapabilities.isEmpty() ? null : hostCapabilities.get(0);
 			List<ModuleWire> newHostWires = hostCapability == null ? null : providedWireMap.get(hostCapability);
 			if (newHostWires != null) {
-				addPayloadContent(newHostWires, existingCapabilities.listIterator(), existingRequirements.listIterator());
+				addPayloadContent(newHostWires, existingCapabilities, existingRequirements);
 			}
 		}
 
@@ -526,11 +411,13 @@ final class ModuleResolver {
 
 		// Also need to include any new required wires that may have be added for fragment hosts
 		// Also will be needed for dynamic imports
-		addRequiredWires(requiredWires, existingRequiredWires, existingRequirements);
+		if (requiredWires != null) {
+			existingRequiredWires.addAll(requiredWires);
+		}
 
 		InternalUtils.filterCapabilityPermissions(existingCapabilities);
-		return new ModuleWiring(revision, existingCapabilities, existingRequirements, existingProvidedWires,
-				existingRequiredWires, existingWiring.getSubstitutedNames());
+		return new ModuleWiring(revision, existingCapabilities.build(), existingRequirements.build(),
+				existingProvidedWires.build(), existingRequiredWires.build(), existingWiring.getSubstitutedNames());
 	}
 
 	static boolean isSingleton(ModuleRevision revision) {
@@ -721,11 +608,10 @@ final class ModuleResolver {
 		}
 
 		List<Capability> filterProviders(Requirement requirement, List<ModuleCapability> candidates, boolean filterResolvedHosts) {
-			ListIterator<ModuleCapability> iCandidates = candidates.listIterator();
-			filterDisabled(iCandidates);
-			removeNonEffectiveCapabilities(iCandidates);
-			removeSubstituted(iCandidates);
-			filterPermissions((BundleRequirement) requirement, iCandidates);
+			filterDisabled(candidates);
+			removeNonEffectiveCapabilities(candidates);
+			removeSubstituted(candidates);
+			filterPermissions((BundleRequirement) requirement, candidates);
 
 			List<ModuleCapability> filteredMatches = null;
 			if (DEBUG_PROVIDERS || DEBUG_HOOKS) {
@@ -800,9 +686,8 @@ final class ModuleResolver {
 			}
 		}
 
-		private void filterPermissions(BundleRequirement requirement, ListIterator<ModuleCapability> iCandidates) {
-			rewind(iCandidates);
-			if (System.getSecurityManager() == null || !iCandidates.hasNext()) {
+		private void filterPermissions(BundleRequirement requirement, List<ModuleCapability> candidates) {
+			if (System.getSecurityManager() == null) {
 				return;
 			}
 
@@ -811,18 +696,16 @@ final class ModuleResolver {
 				return;
 			}
 
-			candidates: while (iCandidates.hasNext()) {
-				ModuleCapability candidate = iCandidates.next();
+			candidates.removeIf(candidate -> {
 				// TODO this is a hack for when a bundle imports and exports the same package
 				if (PackageNamespace.PACKAGE_NAMESPACE.equals(requirement.getNamespace())) {
 					if (requirement.getRevision().equals(candidate.getRevision())) {
-						continue candidates;
+						return false;
 					}
 				}
 				Permission requirePermission = InternalUtils.getRequirePermission(candidate);
 				Permission providePermission = InternalUtils.getProvidePermission(candidate);
 				if (!requirement.getRevision().getBundle().hasPermission(requirePermission)) {
-					iCandidates.remove();
 					if (DEBUG_PROVIDERS) {
 						Debug.println(new StringBuilder("RESOLVER: Capability filtered because requirer did not have permission") //$NON-NLS-1$
 								.append(SEPARATOR).append(TAB) //
@@ -833,8 +716,8 @@ final class ModuleResolver {
 								.append(candidate.getResource()) //
 								.toString());
 					}
+					return true;
 				} else if (!candidate.getRevision().getBundle().hasPermission(providePermission)) {
-					iCandidates.remove();
 					if (DEBUG_PROVIDERS) {
 						Debug.println(new StringBuilder("RESOLVER: Capability filtered because provider did not have permission") //$NON-NLS-1$
 								.append(SEPARATOR).append(TAB) //
@@ -845,16 +728,15 @@ final class ModuleResolver {
 								.append(candidate.getResource()) //
 								.toString());
 					}
+					return true;
 				}
-			}
+				return false;
+			});
 		}
 
-		private void filterDisabled(ListIterator<ModuleCapability> iCandidates) {
-			rewind(iCandidates);
-			while (iCandidates.hasNext()) {
-				Capability capability = iCandidates.next();
+		private void filterDisabled(List<ModuleCapability> candidates) {
+			candidates.removeIf(capability -> {
 				if (disabled.contains(capability.getResource())) {
-					iCandidates.remove();
 					if (DEBUG_PROVIDERS) {
 						Debug.println(new StringBuilder("RESOLVER: Capability filtered because it was disabled") //$NON-NLS-1$
 								.append(SEPARATOR).append(TAB) //
@@ -865,17 +747,16 @@ final class ModuleResolver {
 								.append(capability.getResource()) //
 								.toString());
 					}
+					return true;
 				}
-			}
+				return false;
+			});
 		}
 
-		private void removeSubstituted(ListIterator<ModuleCapability> iCapabilities) {
-			rewind(iCapabilities);
-			while (iCapabilities.hasNext()) {
-				ModuleCapability capability = iCapabilities.next();
+		private void removeSubstituted(List<ModuleCapability> capabilities) {
+			capabilities.removeIf(capability -> {
 				ModuleWiring wiring = wirings.get(capability.getRevision());
 				if (wiring != null && wiring.isSubtituted(capability)) {
-					iCapabilities.remove();
 					if (DEBUG_PROVIDERS) {
 						Debug.println(new StringBuilder("RESOLVER: Capability filtered because it was substituted") //$NON-NLS-1$
 								.append(SEPARATOR).append(TAB) //
@@ -886,8 +767,10 @@ final class ModuleResolver {
 								.append(capability.getResource()) //
 								.toString());
 					}
+					return true;
 				}
-			}
+				return false;
+			});
 		}
 
 		@Override
@@ -942,7 +825,7 @@ final class ModuleResolver {
 				Requirement fragmentRequirement = ModuleContainer.createRequirement(EquinoxFragmentNamespace.FRAGMENT_NAMESPACE, Collections.<String, String> singletonMap(Namespace.REQUIREMENT_FILTER_DIRECTIVE, matchFilter), Collections.<String, Object> emptyMap());
 				List<ModuleCapability> candidates = moduleDatabase.findCapabilities(fragmentRequirement);
 				// filter out disabled fragments and singletons
-				filterDisabled(candidates.listIterator());
+				filterDisabled(candidates);
 				for (ModuleCapability candidate : candidates) {
 					ModuleRequirement hostReq = candidate.getRevision().getModuleRequirements(HostNamespace.HOST_NAMESPACE).get(0);
 					for (ModuleCapability hostCap : hostCaps) {
diff --git a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleWiring.java b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleWiring.java
index e63df7f4f..9e6777e9e 100644
--- a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleWiring.java
+++ b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/container/ModuleWiring.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2012, 2017 IBM Corporation and others.
+ * Copyright (c) 2012, 2021 IBM Corporation and others.
  *
  * This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License 2.0
@@ -13,10 +13,6 @@
  *******************************************************************************/
 package org.eclipse.osgi.container;
 
-import static org.eclipse.osgi.internal.container.NamespaceList.CAPABILITY;
-import static org.eclipse.osgi.internal.container.NamespaceList.REQUIREMENT;
-import static org.eclipse.osgi.internal.container.NamespaceList.WIRE;
-
 import java.net.URL;
 import java.util.ArrayList;
 import java.util.Collection;
@@ -26,7 +22,6 @@ import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
-import java.util.Map.Entry;
 import java.util.Set;
 import java.util.concurrent.Callable;
 import java.util.concurrent.atomic.AtomicReference;
@@ -75,17 +70,6 @@ public final class ModuleWiring implements BundleWiring {
 	volatile boolean isValid = true;
 	private final AtomicReference<Set<String>> dynamicMissRef = new AtomicReference<>();
 
-	ModuleWiring(ModuleRevision revision, List<ModuleCapability> capabilities, List<ModuleRequirement> requirements,
-			List<ModuleWire> providedWires, List<ModuleWire> requiredWires, Collection<String> substitutedPkgNames) {
-		super();
-		this.revision = revision;
-		this.capabilities = new NamespaceList<>(capabilities, CAPABILITY);
-		this.requirements = new NamespaceList<>(requirements, REQUIREMENT);
-		this.providedWires = new NamespaceList<>(providedWires, WIRE);
-		this.requiredWires = new NamespaceList<>(requiredWires, WIRE);
-		this.substitutedPkgNames = substitutedPkgNames.isEmpty() ? Collections.<String> emptyList() : substitutedPkgNames;
-	}
-
 	ModuleWiring(ModuleRevision revision, NamespaceList<ModuleCapability> capabilities,
 			NamespaceList<ModuleRequirement> requirements, NamespaceList<ModuleWire> providedWires,
 			NamespaceList<ModuleWire> requiredWires, Collection<String> substitutedPkgNames) {
@@ -156,7 +140,7 @@ public final class ModuleWiring implements BundleWiring {
 		if (!isValid) {
 			return null;
 		}
-		List<ModuleRequirement> persistentRequriements = requirements.copyList();
+		List<ModuleRequirement> persistentRequriements = new ArrayList<>(requirements.getList(null));
 		for (Iterator<ModuleRequirement> iRequirements = persistentRequriements.iterator(); iRequirements.hasNext();) {
 			ModuleRequirement requirement = iRequirements.next();
 			if (PackageNamespace.PACKAGE_NAMESPACE.equals(requirement.getNamespace())) {
@@ -213,7 +197,7 @@ public final class ModuleWiring implements BundleWiring {
 		if (!isValid) {
 			return null;
 		}
-		List<ModuleWire> persistentWires = allWires.copyList();
+		List<ModuleWire> persistentWires = new ArrayList<>(allWires.getList(null));
 		for (Iterator<ModuleWire> iWires = persistentWires.iterator(); iWires.hasNext();) {
 			ModuleWire wire = iWires.next();
 			if (PackageNamespace.PACKAGE_NAMESPACE.equals(wire.getRequirement().getNamespace())) {
@@ -436,15 +420,9 @@ public final class ModuleWiring implements BundleWiring {
 		ModuleDatabase moduleDatabase = revision.getRevisions().getContainer().moduleDatabase;
 		moduleDatabase.writeLock();
 		try {
-			List<ModuleRequirement> updatedRequirements = requirements.copyList();
-			Entry<Integer, Integer> packageStartEnd = requirements
-					.getNamespaceIndex(PackageNamespace.PACKAGE_NAMESPACE);
-			if (packageStartEnd == null) {
-				updatedRequirements.addAll(newRequirements);
-			} else {
-				updatedRequirements.addAll(packageStartEnd.getValue(), newRequirements);
-			}
-			requirements = new NamespaceList<>(updatedRequirements, REQUIREMENT);
+			NamespaceList.Builder<ModuleRequirement> requirmentsBuilder = requirements.createBuilder();
+			requirmentsBuilder.addAll(newRequirements);
+			requirements = requirmentsBuilder.build();
 		} finally {
 			moduleDatabase.writeUnlock();
 		}
diff --git a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/internal/container/NamespaceList.java b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/internal/container/NamespaceList.java
index 74375c108..ce320de75 100644
--- a/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/internal/container/NamespaceList.java
+++ b/bundles/org.eclipse.osgi/container/src/org/eclipse/osgi/internal/container/NamespaceList.java
@@ -10,154 +10,402 @@
  *
  * Contributors:
  *     IBM Corporation - initial API and implementation
+ *     Hannes Wellmann - Bug 573025: introduce and apply NamespaceList.Builder
  *******************************************************************************/
 package org.eclipse.osgi.internal.container;
 
-import java.util.AbstractMap;
+import java.util.AbstractCollection;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
+import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
-import java.util.Map.Entry;
+import java.util.NoSuchElementException;
 import java.util.function.Function;
+import java.util.function.Predicate;
 import org.eclipse.osgi.container.ModuleCapability;
 import org.eclipse.osgi.container.ModuleRequirement;
 import org.eclipse.osgi.container.ModuleWire;
 
 /**
- * An immutable list of elements for which each element has a name space. All
- * elements are kept in a single list to avoid creating a list for each name
- * space. The elements provided at construction are assumed to be ordered such
- * that all elements with the same name space are ordered together in one
- * continuous sequence An indexes list is used to keep track of the beginning
- * indexes for each namespace contained in the list. Assuming the number of
- * namespaces used by a bundle is relatively small compared to the overall
- * number of elements this makes it faster to find the first index for a
- * specific namespace without having to iterate over the complete list of
- * elements.
+ * An immutable list of elements for which each element has a namespace.
+ * <p>
+ * The elements are stored in a map where each key is a namespace and the
+ * associated value is the list of all elements with that namespace in this
+ * NamespaceList. Within one namespace the element's order is stable. Due to
+ * this internal structure access to the elements of off one or all namespace(s)
+ * has always constant runtime regardless of the number of namespaces present.
+ * <p>
  * 
- * @param <E> The element type which will have a name space associated with it
+ * @param <E> the type of elements in this list, which have a name-space
+ *            associated
  */
 public class NamespaceList<E> {
 
-	public final static Function<ModuleWire, String> WIRE = wire -> {
-		return wire.getCapability().getNamespace();
-	};
+	public final static Function<ModuleWire, String> WIRE = wire -> wire.getCapability().getNamespace();
 	public final static Function<ModuleCapability, String> CAPABILITY = ModuleCapability::getNamespace;
 	public final static Function<ModuleRequirement, String> REQUIREMENT = ModuleRequirement::getNamespace;
 
-	private final List<E> elements;
-	private final Map<String, List<E>> namespaces;
-
 	/**
-	 * Create a new name space list with the specified elements. The elements must
-	 * be sorted properly by name space.
+	 * Returns an empty NamespaceList.
+	 * <p>
+	 * The required argument is used to derive the type of elements and if a builder
+	 * is created from the returned list.
+	 * </p>
 	 * 
-	 * @param elements     the ordered list of elements
-	 * @param getNamespace a function that retrieves the namespace for each element
+	 * @param <E>          the type of elements in the NamespaceList
+	 * @param getNamespace the function to compute the namespace of an element
+	 * @return an empty NamespaceList
 	 */
-	public NamespaceList(List<E> elements, Function<E, String> getNamespace) {
-		List<E> unmodifiableElements = Collections.unmodifiableList(elements);
-
-		Map<String, List<E>> tmpNamespaces = new LinkedHashMap<>(5);
-		int size = unmodifiableElements.size();
-		int currentStart = 0;
-		String current = null;
-
-		boolean consolidated = false;
-		for (int i = 0; i < size; i++) {
-			String namespace = getNamespace.apply(unmodifiableElements.get(i));
-			if (current == null) {
-				current = namespace;
-			}
-			if (!current.equals(namespace)) {
-				int currentEnd = i;
-				consolidated |= addNamespaceList(tmpNamespaces, unmodifiableElements, current, currentStart,
-						currentEnd);
-				current = namespace;
-				currentStart = i;
-			}
-		}
-		if (size > 0) {
-			// add the last namespace
-			consolidated |= addNamespaceList(tmpNamespaces, unmodifiableElements, current, currentStart, size);
-		}
-		if (consolidated) {
-			List<E> tmpElements = new ArrayList<>(size);
-			for (Entry<String, List<E>> e : tmpNamespaces.entrySet()) {
-				tmpElements.addAll(e.getValue());
-			}
-			this.elements = Collections.unmodifiableList(tmpElements);
-		} else {
-			this.elements = unmodifiableElements;
-		}
-		this.namespaces = Collections.unmodifiableMap(tmpNamespaces);
+	public static <E> NamespaceList<E> empty(Function<E, String> getNamespace) {
+		return new NamespaceList<>(getNamespace, Collections.emptyMap(), Collections.emptyList());
 	}
 
-	private boolean addNamespaceList(Map<String, List<E>> tmpNamespaces, List<E> unmodifiableElements, String namespace,
-			int start, int end) {
-		List<E> namespaceList = unmodifiableElements.subList(start, end);
-		List<E> existing = tmpNamespaces.get(namespace);
-		boolean consolidated = false;
-		if (existing != null) {
-			// This should be an error, consolidate the lists
-			List<E> consolidateList = new ArrayList<>(existing);
-			consolidateList.addAll(namespaceList);
-			namespaceList = Collections.unmodifiableList(consolidateList);
-			consolidated = true;
-		}
-		tmpNamespaces.put(namespace, namespaceList);
-		return consolidated;
+	private final List<E> elements;
+	private final Map<String, List<E>> namespaces;
+	private final Function<E, String> getNamespace;
+
+	NamespaceList(Function<E, String> getNamespace, Map<String, List<E>> namespaces, List<E> fullList) {
+		this.getNamespace = getNamespace;
+		this.namespaces = namespaces;
+		this.elements = fullList;
 	}
 
+	Map<String, List<E>> namespaces() {
+		return namespaces;
+	}
+
+	/**
+	 * Returns {@code true} if this NamespaceList contains no elements.
+	 * 
+	 * @return {@code true} if this list contains no elements
+	 */
 	public boolean isEmpty() {
 		return elements.isEmpty();
 	}
 
 	/**
-	 * returns an unmodifiable list of elements with the specified name space. An
-	 * empty list is returned if there are no elements with the specified namespace.
-	 * A {@code null} namespace can be used to get all elements.
+	 * Returns an immutable list of elements with the specified namespace.
+	 * <p>
+	 * An empty list is returned if there are no elements with the specified
+	 * namespace. For the {@code null} namespace the elements of all namespaces are
+	 * returned as flat.
+	 * </p>
 	 * 
-	 * @param namespace the name space of the elements to return. May be
-	 *                  {@code null}
+	 * @param namespace the namespace of the elements to return. May be {@code null}
 	 * @return The list of elements found
 	 */
 	public List<E> getList(String namespace) {
 		if (namespace == null) {
 			return elements;
 		}
-
 		return namespaces.getOrDefault(namespace, Collections.emptyList());
 	}
 
 	/**
-	 * Returns the beginning index (inclusively) and ending index (exclusively) or
-	 * {@code null} if no element has the specified namespace
+	 * Returns a new {@link Builder NamespaceList.Builder} that contains all
+	 * elements of this NamespaceList.
+	 * <p>
+	 * The returned builder uses the same function to compute the namespace of an
+	 * element like this NamespaceList.
+	 * </p>
 	 * 
-	 * @param namespace the name space to find the indexes for
-	 * @return indexes found for the namespace or {@code null} if no elements exist
-	 *         with the name space.
+	 * @return a new builder containing all elements of this list
 	 */
-	public Entry<Integer, Integer> getNamespaceIndex(String namespace) {
-		int startIndex = 0;
-		for (Entry<String, ? extends List<E>> entry : namespaces.entrySet()) {
-			if (entry.getKey().equals(namespace)) {
-				int end = startIndex + entry.getValue().size();
-				return new AbstractMap.SimpleEntry<>(startIndex, end);
-			}
-			startIndex += entry.getValue().size();
-		}
-		return null;
+	public Builder<E> createBuilder() {
+		Builder<E> builder = Builder.create(getNamespace);
+		builder.addAll(this);
+		return builder;
 	}
 
 	/**
-	 * Returns a copy of all the elements in this list
+	 * A reusable builder to create {@link NamespaceList NamespaceLists}.
 	 * 
-	 * @return a copy of all the elements in this list
+	 * @param <E> the type of elements in this builder
+	 * @author Hannes Wellmann
 	 */
-	public List<E> copyList() {
-		return new ArrayList<>(elements);
+	public static class Builder<E> extends AbstractCollection<E> {
+
+		/**
+		 * Returns a new {@link Builder NamespaceList.Builder} that uses the specified
+		 * function to compute the namespace of its elements.
+		 * 
+		 * @param <E>          the type of elements in this builder
+		 * @param getNamespace the function to compute the namespace of an element
+		 * @return a new builder
+		 */
+		public static <E> Builder<E> create(Function<E, String> getNamespace) {
+			return new Builder<>(getNamespace, 3);
+		}
+
+		private final Function<E, String> getNamespace;
+		private LinkedHashMap<String, List<E>> namespaceElements;
+		private int size = 0;
+
+		private List<E> lastBuildElements;
+
+		private Builder(Function<E, String> getNamespace, int expectedNamespaces) {
+			this.getNamespace = getNamespace;
+			this.namespaceElements = new LinkedHashMap<>(expectedNamespaces * 4 / 3 + 1);
+		}
+
+		@Override
+		public int size() {
+			return size;
+		}
+
+		@Override
+		public Iterator<E> iterator() {
+			prepareModification();
+
+			final Iterator<? extends List<E>> outer = namespaceElements.values().iterator();
+			return new Iterator<E>() {
+				Iterator<E> inner = Collections.emptyIterator();
+				List<E> lastInnerList = null;
+
+				@Override
+				public boolean hasNext() {
+					while (!inner.hasNext() && outer.hasNext()) {
+						lastInnerList = outer.next();
+						inner = lastInnerList.iterator();
+					}
+					return inner.hasNext();
+				}
+
+				public E next() {
+					if (!hasNext()) {
+						throw new NoSuchElementException();
+					}
+					return inner.next();
+				}
+
+				@Override
+				@SuppressWarnings("synthetic-access")
+				public void remove() {
+					inner.remove();
+					Builder.this.size--;
+					if (lastInnerList.isEmpty()) {
+						outer.remove();
+					}
+				}
+			};
+		}
+
+		@Override
+		public void clear() {
+			namespaceElements = new LinkedHashMap<>(); // could have been build before, so map must not be cleared
+			lastBuildElements = null;
+			size = 0;
+		}
+
+		// --- addition ---
+
+		@Override
+		public boolean add(E e) {
+			prepareModification();
+
+			String namespace = getNamespace.apply(e);
+			getNamespaceList(namespace).add(e);
+			this.size++;
+			return true;
+		}
+
+		@Override
+		public boolean addAll(Collection<? extends E> c) {
+			if (c.isEmpty()) {
+				return false;
+			}
+			prepareModification();
+
+			String currentNamespace = null; // $NON-NLS-1$
+			List<E> currentNamespaceList = null;
+			for (E e : c) {
+				String namespace = getNamespace.apply(e);
+				// optimization if elements are already grouped per namespace
+				if (currentNamespace == null || !currentNamespace.equals(namespace)) {
+					currentNamespace = namespace;
+					currentNamespaceList = getNamespaceList(namespace);
+				}
+				currentNamespaceList.add(e);
+			}
+			this.size += c.size();
+			return true;
+		}
+
+		/**
+		 * Adds all elements in the specified NamespaceList to this builder.
+		 * 
+		 * @param list the NamespaceList containing elements to be added
+		 * @return true if any element was added to this builder
+		 */
+		public boolean addAll(NamespaceList<E> list) {
+			if (list.isEmpty()) {
+				return false;
+			}
+			prepareModification();
+
+			list.namespaces().forEach((n, es) -> {
+				getNamespaceList(n).addAll(es);
+				this.size += es.size();
+			});
+			return true;
+		}
+
+		private List<E> getNamespaceList(String namespace) {
+			return namespaceElements.computeIfAbsent(namespace, n -> new ArrayList<>());
+		}
+
+		public void addAfterLastMatch(E toAdd, Predicate<E> matcher) {
+			prepareModification();
+
+			String namespace = getNamespace.apply(toAdd);
+			List<E> namespaceList = getNamespaceList(namespace);
+			addAfterLastMatch(toAdd, namespaceList, matcher);
+			this.size++;
+		}
+
+		private void addAfterLastMatch(E e, List<E> list, Predicate<E> matcher) {
+			for (int i = list.size() - 1; 0 <= i; i--) {
+				if (matcher.test(list.get(i))) {
+					list.add(i + 1, e);
+					return;
+				}
+			}
+			list.add(0, e);
+		}
+
+		// --- removal ---
+
+		@Override
+		public boolean remove(Object o) {
+			@SuppressWarnings("unchecked")
+			E e = (E) o;
+			String namespace;
+			try {
+				namespace = getNamespace.apply(e);
+			} catch (ClassCastException ex) {
+				return false; // e does not seem to be of type E after all
+			}
+			prepareModification();
+
+			int sizeBefore = this.size;
+			removeNamespaceElement(namespace, e);
+			return this.size < sizeBefore;
+		}
+
+		private void removeNamespaceElement(String namespace, E element) {
+			namespaceElements.computeIfPresent(namespace, (n, es) -> {
+				if (es.remove(element)) {
+					this.size--;
+				}
+				return es.isEmpty() ? null : es;
+			});
+		}
+
+		@Override
+		public boolean removeAll(Collection<?> c) {
+			if (c.isEmpty()) {
+				return false;
+			}
+			prepareModification();
+
+			// this is more efficient than the super implementation
+			boolean removed = false;
+			for (Object e : c) {
+				removed |= remove(e);
+			}
+			return removed;
+		}
+
+		/**
+		 * Removes from this builder all elements of each namespace that satisfies the
+		 * specified predicate.
+		 * 
+		 * @param filter the predicate which returns true for a namespace to remove
+		 */
+		public void removeNamespaceIf(Predicate<String> filter) {
+			prepareModification();
+
+			namespaceElements.entrySet().removeIf(e -> {
+				if (filter.test(e.getKey())) {
+					this.size -= e.getValue().size();
+					return true;
+				}
+				return false;
+			});
+		}
+
+		@Override
+		public boolean removeIf(Predicate<? super E> filter) {
+			prepareModification();
+
+			int s = size;
+			namespaceElements.values().removeIf(es -> removeElementsIf(es, filter) == null);
+			return size < s;
+		}
+
+		/**
+		 * Removes from this builder those elements of the specified namespace that
+		 * satisfy the specified predicate.
+		 * 
+		 * @param namespace the namespace of
+		 * @param filter    the predicate which returns true for elements to remove
+		 */
+		public void removeElementsOfNamespaceIf(String namespace, Predicate<? super E> filter) {
+			prepareModification();
+
+			namespaceElements.computeIfPresent(namespace, (n, es) -> removeElementsIf(es, filter));
+		}
+
+		private List<E> removeElementsIf(List<E> list, Predicate<? super E> filter) {
+			int sizeBefore = list.size();
+			list.removeIf(filter);
+			this.size -= sizeBefore - list.size();
+			return list.isEmpty() ? null : list;
+		}
+
+		// --- build ---
+
+		/**
+		 * Returns an immutable {@link NamespaceList} containing a snapshot of the
+		 * current elements of this builder.
+		 * <p>
+		 * The content of this builder is not changed by this call and subsequent
+		 * modifications to this builder do not reflect into the returned list (the
+		 * returned list is not connected to this builder at all).
+		 * </p>
+		 * 
+		 * @return a {@link NamespaceList} reflecting the current state of this builder
+		 */
+		public NamespaceList<E> build() {
+			if (size == 0) {
+				return empty(getNamespace);
+			}
+			if (lastBuildElements == null) {
+				lastBuildElements = new ArrayList<>(size);
+				namespaceElements.values().forEach(lastBuildElements::addAll);
+				lastBuildElements = Collections.unmodifiableList(lastBuildElements);
+
+				int[] start = new int[] { 0 };
+				namespaceElements.replaceAll((n, es) -> {
+					int from = start[0];
+					int to = start[0] += es.size();
+					return lastBuildElements.subList(from, to);
+				});
+			}
+			return new NamespaceList<>(getNamespace, namespaceElements, lastBuildElements);
+		}
+
+		private void prepareModification() {
+			if (lastBuildElements != null) {
+				// this builder was build before. Create a copy of the Map and their
+				// namespace-lists for subsequent modification
+				namespaceElements = new LinkedHashMap<>(namespaceElements);
+				namespaceElements.replaceAll((n, es) -> new ArrayList<>(es));
+				lastBuildElements = null;
+			}
+		}
 	}
 }