F# array with O(1) lookup and O(1) slice

Question

I need an Array-like data structure that supports

a.[i]

in time O(1) and

a.[i..j]

also in time O(1).

O(1) updates are not a requirement. Really, all I need is a constant Array with a notion of in-place slice or subarray.

I could of course construct such a thing from Array, but I'd be happier if I could use one that already existed?

Answer 1

The .NET standard library has the type ArraySegment<'T> for this purpose. Unfortunately it doesn't have the methods Item and GetSlice that allow you to use the .[x] and .[x..y] syntaxes, respectively. But you can add them with an augmentation:

type System.ArraySegment<'T> with

    member this.Item(x) =
        if x < 0 || x >= this.Count then
            raise (System.IndexOutOfRangeException("Index was outside the bounds of the array segment."))
        this.Array.[x + this.Offset]

    member this.GetSlice(start: int option, finish : int option) =
        let start = defaultArg start 0
        let finish = defaultArg finish (this.Count - 1)
        if start < 0 || finish >= this.Count then
            raise (System.IndexOutOfRangeException("Index was outside the bounds of the array segment."))
        new ArraySegment<'T>(this.Array, this.Offset + start, finish - start + 1)