Skip to content

Instantly share code, notes, and snippets.

@kyouko-taiga
Created December 6, 2022 20:17
Show Gist options
  • Save kyouko-taiga/38b2749a32494b1611b2b4891e960ecd to your computer and use it in GitHub Desktop.
Save kyouko-taiga/38b2749a32494b1611b2b4891e960ecd to your computer and use it in GitHub Desktop.
Iterators in Val
/// A type representing a collection of values.
public trait Collection {
/// The type of the `Self`'s elements.
type Element
/// The type of a position in `Self`.
type Index: Equatable
/// Returns `self`'s first position.
fun first_index() -> Index
/// Returns `self`'s "past the end" position.
fun end_index() -> Index
/// Returns the position after `index` in `self`.
///
/// - Requires: `index` is a valid index in the collection other than `end_index()`.
fun index_after(_ index: Index) -> Index
/// Projects the element at `index` in `self`.
///
/// - Requires: `index` is a valid index in the collection other than `end_index()`.
subscript(_ index: Index) : Element { let }
}
/// A forward iterator in a collection.
public type Iterator<Base: Collection, base_access: let> {
/// A projection of the base collection.
var base: remote base_access Base
/// The position of `self` in `base`.
var position: Base.Index
/// Creates an iterator projecting the elements of `base` from `position`.
public init(_ base: base_access Base, at position: Base.Index) {
self.base = base
self.position = position
}
/// Projects the element currently pointed by `self`.
public subscript() : Base.Element {
let { base[index] }
}
/// Advances `self`.
public fun advances() inout {
position = base.index_after(position)
}
}
extension Iterator where base_access: inout {
public subscript() : Base.Element {
inout { &base[index] }
}
}
extension Iterator where base_access: sink {
public subscript() : Base.Element {
sink { &base[index] }
}
}
public type Vector<Element> {
/// A pointer to the start `self`'s storage.
var storage: MutablePointer<Element>
/// The number of elements `self`.
var _count: MutablePointer<Element>
/// The capacity of the vector.
var _capacity: Int
/// Creates an empty vector.
public init() {
storage = .null
_count = 0
_capacity = 0
}
/// Returns the number of elements in `self`.
public fun count() -> Int { _count.copy() }
/// Returns the number of elements that can be stored in `self` before allocating new storage.
public fun capacity() -> Int { _capacity.count() }
}
public conformance Vector: Collection {
public typealias Index = Int
public fun first_index() -> Int { 0 }
public fun end_index() -> Int { count() }
fun index_after(_ index: Index) -> Index { index + 1 }
subscript(_ index: Index) : Element {
let {
precondition((index >= 0) && (index < count()), "index is out of bounds")
yield unsafe storage[index]
}
}
}
@kyouko-taiga
Copy link
Author

kyouko-taiga commented Dec 8, 2022

Yes. I used Vector to make the correspondence with C++'s std::vector clear.

Also I think our arrays should not store three words but have their header laid out before the out-of-line storage (like Swift, AFAIK).

@dabrahams
Copy link

Yes; all I meant was that if you are going to implement something called Vector with C++ std::vector semantics, you should use Val.Array to do it, so you don't have to worry about things like the missing deinit. Nothing in the standard mandates any particular data layout for std::vector.

@kyouko-taiga
Copy link
Author

Oh, didn't know that. So yep, agreed completely.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment