Partial implementation of array and lists

1 files changed, 58 insertions, 0 deletions

diff --git a/projects/std/src/Std/Lists.shed b/projects/std/src/Std/Lists.shed
new file mode 100644
index 00000000..8771eb74
--- /dev/null
+++ b/projects/std/src/Std/Lists.shed
@@ -0,0 +1,58 @@
+struct List[T](array: Array[T]) {
+    // TODO: generic effect
+    fun forEach(this, func: fn (T) ! Io -> Unit) ! Io -> Unit {
+        var index = 0;
+        val size = this.array.size();
+
+        while (index < size) {
+            func!(this.array.unsafeGet(index));
+            assign index = index + 1;
+        }
+    }
+}
+
+struct ListBuilder[T](arrayBuilder: ArrayBuilder[T]) {
+    fun add(this, element: T) -> ListBuilder[T] {
+        if (this.arrayBuilder.size() < this.arrayBuilder.capacity()) {
+            ListBuilder(this.arrayBuilder.unsafeAdd(element))
+        } else {
+            val newCapacity = this.arrayBuilder.capacity() * 2;
+            val newArrayBuilder = this.arrayBuilder
+                .unsafeEnlarge(.capacity = newCapacity)
+                .unsafeAdd(element);
+            ListBuilder(newArrayBuilder)
+        }
+    }
+
+    fun build(this) -> List[T] {
+        List(this.arrayBuilder.build())
+    }
+}
+
+pub fun listBuilder[T]() -> ListBuilder[T] {
+    ListBuilder[T](arrayBuilder[T](.capacity = 16))
+}
+
+native type Array[T] {
+    // Precondition: the index is in the range [0, size).
+    native fun unsafeGet(This, Int) -> T;
+
+    native fun size(This) -> Int;
+}
+
+native type ArrayBuilder[T] {
+    native fun capacity(This) -> Int;
+
+    native fun size(This) -> Int;
+
+    // Precondition: size < capacity.
+    native fun unsafeAdd(This, T) -> ArrayBuilder[T];
+
+    // Precondition: the new capacity is greater than or equal to the current
+    // capacity.
+    native fun unsafeEnlarge(This, .capacity: Int) -> ArrayBuilder[T];
+
+    native fun build(This) -> Array[T];
+}
+
+native fun arrayBuilder[T](.capacity: Int) -> ArrayBuilder[T];