list type
=========

we want to be able to handle several different scenarios:

- list in read only memory (this should perhaps be a separate type, or?)
- list in arena
- list in heap
- list in fragmented heap

    type List<T> = (
        enum .... # for type (List, Set, etc)? or just have one Set and one List type, and then a Collection wrapper which has the enum?
        size length
        size capacity
        ref [capacity]T data
    )

    # we would like to have index types also (both for lists and arrays)
    # Based type for both lists and collections?
    # FIXME "type" needs only a byte but the following size/refs needs 32 or 64 bit alignment
    # - for 32 bit we have 2 bits in the address that could be used, for 4 types
    # - for 64 bit we have 3 bits, for 8 types
    type Collection<E> =
    case (
        .EmptyList ( )
        .EmptySet ( )
        .MergedList ( size length, [length]E elems )
        .KnownLengthList ( [length]E elems )
        # Should we also have versions with relative pointers?
        .ReadOnlyView (
            size length
            ref [length]E elems
        )
        .OneChunkList (
            size length
            size capacity
            ownrwref [length]E elems
        )
        .MultiChunkList (
            size length
            size num_chunks
            #ownrwref ChunkNode<E> root
            ownrwref List<E> root_node
            #ownrwref [num_chunks]ListChunk<E>
        )
        .ChunkNode (
            size lowindex
            [4](
                ownrwref List<E> node
                size highindex
            ) sub_nodes
        )
        #.JaggedList (
        #    when T is []U   # XXX complex!
        #    size length
        #    [length]relative(data) ref offsets   # XXX forward reference!
        #    []U
        #)
#        .JaggedByteList ( # XXX probably not needed?
#            when type E == [*]byte   # or char, if we should have a char type
#            size length
#            size total_length
#            #[length]relative(data) ref offsets   # XXX forward reference!
#            [length]size[< total_length] offsets
#            [total_length]byte data
#        )
        .JaggedList (
            size length
            #[length]size offsets
            #
            jaggedlist[length] E elems   # generates elems_offsets and elems_data
        )
        .UnordedSet # TODO hashset
        .OrderedSet # TODO linkedhashset or treeset
        .JaggedSet # TODO how to initialize this at compile time?
        .CustomList (
            ...vtable here...
        )
        .CustomSet (
            ...vtable here...
        )
    )

    type List<T> = Collection<T> where case in
        [.EmptyList, .MergedList, .KnownLengthList, .ReadOnlyView, .OneChunkList, .MultiChunkList, .JaggedList, .CustomList]
    type Set<T> = Collection<T> where case in
        [.EmptySet, .UnorderedSet, .OrderedSet, .JaggedSet, .CustomSet]

    # Should it have a hashcode? and encoding (to support non-UTF-8/ASCII)?
    type String = List<byte>
    #type String = (uint32 hashcode, List<Byte>) # Alignment waste on 64-bit!

    # So the following becomes a jagged array (List<String.Merged>.JaggedList)
    const List<String> = ["Hello", "world", "!"]