type error = enum int8 (
    ### Generic error code when no more specific one exists
    generic = -1
    ### Out of memory
    outofmem = -2
    ### Internal error, caused by a bug (or by memory corruption)
    internal = -3
    ### Not supported. The operation is optional, and is not available
    notsupp = -4
    ### A parameter is invalid
    param = -5
    ### Out of range
    outofrange = -6
    ### Non-existent
    nonexistent = -7
)

func <T>alloc(size bytes = sizeof T, size align = alignof T) return uninit rwref takeown T|error.outofmem
# FIXME how should this work with ownership inside the returned data (for example if it is a struct)
func <T>calloc(size bytes = sizeof T, size algin = alignof T) return rwref takeown T|error.outofmem
func <T>free(ref takeown T elem, size = sizeof T)
func <T>free_opt(?ref takeown T elem, size = sizeof T)

type Arena = private
func arena_new(shared ?rwref Arena base_arena) return takeown Arena|error.outofmem
func arena_free_all(rwref takeown Arena this)
func <T>arena_alloc(shared rwref Arena this, size bytes = sizeof T, size align = alignof T) return uninit rwref own(this) T|error.outofmem


func <[len]T>alloc_array(size elembytes = T, size len) return uninit rwref takeown T|error.outofmem
# FIXME how should this work with ownership inside the array
func <[len]T>calloc_array(size elembytes = T, size len) return uninit rwref takeown T|error.outofmem
# FIXME uninit from new location!
func <[len]T>realloc_array(size elembytes = T, size len, ref takeown [len]T array) return uninit rwref takeown T|error.outofmem
func <[len]T>crealloc_array(size elembytes = T, size len, ref takeown [len]T array) return uninit rwref takeown T|error.outofmem
# it would also be nice to have a "realloc_if_no_move", "realloc_up_to"
func <[len]T>free_array(ref takeown [len]T array, size elembytes = T, size len)

# flexible alloc. does not require knowing the size when freeing, and allows reallocing (like C malloc)
func <T>flex_alloc(size bytes = sizeof T) return uninit rwref takeown T|error.outofmem
# TODO


openinterface <T>Eq
{
    func equals(dedup ref T a, dedup ref T b) return bool
}

openinterface <T>Hashable
{
    func hashcode(dedup ref this) return size
}

type CmpResult = enum (ALess = -1, Equal, AGreater)

openinterface <T>Cmp
{
    func compare(dedup ref a, dedup ref b) return CmpResult
}

###
# Classes implementing this interface allow getting an iterator,
# which allows iterating (steppin through) elements in the object.
#
# @param T Element type
#
openinterface <T>Iterable
{
    # TODO: Ownership of the iterator?
    #   - one iterator per list? but that uses memory for unused iterators
    #   - use only a single pointer? limits what objects we can iterate over
    #   - allocate a new object on the heap? would be nice to avoid.
    #   - declare a fixed size? i.e. all iterators are 4*size/pointer.
    #   - optionally heap allocate and require free'ing iterators?

    ###
    # Returns an iterator of the object, that iterators through all
    # elements. The object may not be modified while using the
    # iterator.
    #
    # @return Iterator
    #
    func iter(ref this) return reading(this) <T>Iter
}

###
# An iterator, that allows iterating (stepping through) elements.
#
# @param T Element type
#
openinterface <T>Iter
{
    ###
    # Whetver the iterator has more elements
    func more(ref this) return bool

    ###
    # Gets the current element, and moves the iterator forward
    #
    # Calling this method when more() returns false (or without calling it
    # first), is forbidden.
    func next(rwref this) return dedup ref T
}

###
# A set of elements without duplicates
#
# @param T Element type
#
classtree <T>Set implements <T>Iterable
{
    CustomSet
    HashSet [T implements Hash,Eq]
    OrderedHashSet <T implements Hash,Eq>
    TreeSet where T implements Cmp

    size elemsize = sizeof T

    ###
    # Adds a new element
    #
    # @return true if the element was added, false if it already existed
    func add(rwref this, dedup ref takeown T elem) return bool|error.outofmem

    ###
    # Checks if an element already exists in the set
    func contains(ref this, dedup ref T elem) return bool

    ###
    # Removes an element
    #
    # @return true if the element was removed. false if it didn't exist
    func remove(rwref this, dedup ref dropown T elem) return bool

    ###
    # Checks if the set is empty
    func empty(ref this) return bool

    ###
    # Returns the number of elements in the set
    func count(ref this) return size

    ###
    # Removes all elements from the set
    func clear(wref this) when is_dedup T
}

###
# A list of elements
#
# @param T Element type
#
classtree <T>List implements <T>Iterable
{
    CustomSet
    ###
    # An array list. Uses little memory and allows very fast iteration.
    ArrayList
    ###
    # A chunked list. Uses little memory and allows very fast iteration.
    ChunkedList
    ###
    # A linked list. Allows fast insertions and removal in the middle
    # of the list
    LinkedList

    size elemsize = sizeof T

    ###
    # Adds a new element at the end of the list
    #
    # @param elem Element to add
    # @return Nothing, unless there is an out-of-memory error
    func append(rwref this, dedup ref takeown T elem) return |error.outofmem

    ###
    # Adds a new element at the beginning of the list
    #
    # @param elem Element to add
    # @return Nothing, unless there is an out-of-memory error
    func prepend(rwref this, dedup ref takeown T elem) return |error.outofmem

    ###
    # Inserts a new element at the given position. After the insertion,
    # any element at that position and any later elements will appear
    # at one step higher.
    #
    # @param elem Element to add
    # @return Nothing, unless there is an out-of-memory error
    func insert(rwref this, dedup ref takeown T elem, size index) return |error.outofmem

    ###
    # Removes the first element
    #
    # @return The element that was removed, if any existed.
    func pop(rwref this) return dedup ref takeown T|error.nonexistent

    ###
    # Removes an element
    #
    # @return The element that was removed, if it existed.
    func remove(rwref this, size index) return dedup ref takeown T|error.nonexistent

    ###
    # Checks if the set is empty
    func empty(ref this) return bool

    ###
    # Returns the number of elements in the set
    func count(ref this) return size

    ###
    # Removes all elements
    func clear(wref this) when is_dedup T
}

###
# Bitmask for matching various strings:
# - whitespace/letters/digits
# - hexadecimal digits
# - identifiers
# - html/sgml/xml
# - base64
typedef CharGroup = bitmask ushort (
    Control
    Space
    Digit
    HexLower    # 4
    HexUpper
    OtherLower
    OtherUpper
    Plus        # 8
    Minus
    Underscore
    Equals
    Less        # 12
    Greater
    Slash
    DblQuote
    SingleQuote # 16
)

# We should also have an interface for raw bytes (e.g. like memmem, memchr, memrchr)
openinterface CharSeq extends <uint32>Iterable, Eq<CharSeq>, Cmp<CharSeq>, Hsh<CharSeq>
{
    func begins_with(ref this, ref CharSeq seq) return true
    func begins_with_asciicase(ref this, ref CharSeq seq) return true
    # FIXME cannot return errors with "size" type... or can we require size to be non-negative?
    #func hash_beginning(ref this, size length) return size|error.outofrange
    func hash_beginning(ref this, size length) return size
    func hash_to_char(ref this, uint32 char) return size
    func hash_to_chargroup(ref this, CharGroup chargroup) return size
    
    # TODO. would be nice to have
    # - strspn
    # - strcspn
    # - strchr
    # - strstr
    # And maybe (slow on zero-terminated strings)
    # - strrchr
    # - strrstr
    # - ends_with
    # And maybe (needs sub-sequence handling)
    # - substr
    # - trim
    # - pointer-strspn i.e. strpbrk
    # - pointer-strcspn
    # - after_char
    # - before_char
    # - after_string
    # - before_string
    # - split (returning an iterator)
    # - begins_with that returns a pointer
}