AK: Add an abstraction over multiple disjoint buffers

DisjointChunks<T> provides a nice interface over multiple sequential
Vector<T>'s, allowing the user to iterate over/index into/slice from
said buffers as if they were a single contiguous buffer.
To work with views on such objects, DisjointSpans<T> is provided, which
has the same behaviour but does not own the underlying objects.

2 files changed, 82 insertions, 0 deletions

diff --git a/Tests/AK/CMakeLists.txt b/Tests/AK/CMakeLists.txt
index 30429cc93a..f1cd7d0129 100644
--- a/Tests/AK/CMakeLists.txt
+++ b/Tests/AK/CMakeLists.txt
@@ -17,6 +17,7 @@ set(AK_TEST_SOURCES
     TestCircularDuplexStream.cpp
     TestCircularQueue.cpp
     TestComplex.cpp
+    TestDisjointChunks.cpp
     TestDistinctNumeric.cpp
     TestDoublyLinkedList.cpp
     TestEndian.cpp
diff --git a/Tests/AK/TestDisjointChunks.cpp b/Tests/AK/TestDisjointChunks.cpp
new file mode 100644
index 0000000000..5c8f982d36
--- /dev/null
+++ b/Tests/AK/TestDisjointChunks.cpp
@@ -0,0 +1,81 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/DisjointChunks.h>
+#include <AK/String.h>
+
+TEST_CASE(basic)
+{
+    DisjointChunks<size_t> chunks;
+    chunks.append({});
+    chunks.last_chunk().append(0);
+    chunks.append({});
+    chunks.last_chunk().append(1);
+    chunks.last_chunk().append(2);
+    chunks.last_chunk().append(3);
+    chunks.append({});
+    chunks.append({});
+    chunks.last_chunk().append(4);
+
+    for (size_t i = 0; i < 5u; ++i)
+        EXPECT_EQ(chunks.at(i), i);
+
+    auto it = chunks.begin();
+    for (size_t i = 0; i < 5u; ++i, ++it)
+        EXPECT_EQ(*it, i);
+
+    EXPECT_EQ(it, chunks.end());
+
+    DisjointChunks<size_t> new_chunks;
+    new_chunks.extend(move(chunks));
+    EXPECT_EQ(new_chunks.size(), 5u);
+
+    new_chunks.last_chunk().append(5);
+
+    auto cut_off_slice = new_chunks.release_slice(2, 3);
+    EXPECT_EQ(new_chunks.size(), 3u);
+    EXPECT_EQ(cut_off_slice.size(), 3u);
+
+    EXPECT_EQ(cut_off_slice[0], 2u);
+    EXPECT_EQ(cut_off_slice[1], 3u);
+    EXPECT_EQ(cut_off_slice[2], 4u);
+
+    EXPECT_EQ(new_chunks[0], 0u);
+    EXPECT_EQ(new_chunks[1], 1u);
+    EXPECT_EQ(new_chunks[2], 5u);
+}
+
+TEST_CASE(spans)
+{
+    DisjointChunks<size_t> chunks;
+    chunks.append({ 0, 1, 2, 3, 4, 5 });
+    chunks.append({ 6, 7, 8, 9 });
+
+    auto spans = chunks.spans();
+    EXPECT_EQ(spans.size(), 10u);
+
+    auto slice = spans.slice(1, 4);
+    EXPECT_EQ(slice.size(), 4u);
+    EXPECT_EQ(slice[0], 1u);
+    EXPECT_EQ(slice[1], 2u);
+    EXPECT_EQ(slice[2], 3u);
+    EXPECT_EQ(slice[3], 4u);
+
+    auto cross_chunk_slice = spans.slice(4, 4);
+    EXPECT_EQ(cross_chunk_slice.size(), 4u);
+    EXPECT_EQ(cross_chunk_slice[0], 4u);
+    EXPECT_EQ(cross_chunk_slice[1], 5u);
+    EXPECT_EQ(cross_chunk_slice[2], 6u);
+    EXPECT_EQ(cross_chunk_slice[3], 7u);
+
+    auto it = cross_chunk_slice.begin();
+    for (size_t i = 0; i < 4u; ++i, ++it)
+        EXPECT_EQ(*it, i + 4u);
+
+    EXPECT_EQ(it, cross_chunk_slice.end());
+}