Segment Descriptors
- data USegd
- mkUSegd :: Vector Int -> Vector Int -> Int -> USegd
- emptyUSegd :: USegd
- singletonUSegd :: Int -> USegd
- lengthsToUSegd :: Vector Int -> USegd
- lengthUSegd :: USegd -> Int
- lengthsUSegd :: USegd -> Vector Int
- indicesUSegd :: USegd -> Vector Int
- elementsUSegd :: USegd -> Int
- sliceUSegd :: USegd -> Int -> Int -> USegd
- extractUSegd :: USegd -> Int -> Int -> USegd
Types
Segment descriptors represent the structure of nested arrays. For each segment, it stores the length and the starting index in the flat data array.
Example:
flat array data: [1, 2, 3, 4, 5, 6, 7, 8] (segmentation) ---- ------- - ---- segd lengths: [2, 3, 1, 2] indices: [0, 2, 5, 6] elements: 8
Constructors
:: Vector Int | length of each segment |
-> Vector Int | starting index of each segment |
-> Int | total number of elements in the flat array |
-> USegd |
O(1). Construct a new segment descriptor.
O(1). Yield an empty segment descriptor, with no elements or segments.
singletonUSegd :: Int -> USegdSource
O(1). Yield a singleton segment descriptor. The single segment covers the given number of elements.
lengthsToUSegd :: Vector Int -> USegdSource
O(n). Convert a length array into a segment descriptor.
The array contains the length of each segment, and we compute the indices from that. Runtime is O(n) in the number of segments.
Projections
lengthUSegd :: USegd -> IntSource
O(1). Yield the overall number of segments.
lengthsUSegd :: USegd -> Vector IntSource
O(1). Yield the lengths of the individual segments.
indicesUSegd :: USegd -> Vector IntSource
O(1). Yield the segment indices of a segment descriptor.
elementsUSegd :: USegd -> IntSource
O(1). Yield the number of data elements.
Operations
:: USegd | source segment descriptor |
-> Int | index of first segment |
-> Int | number of segments to slice out |
-> USegd |
O(n). Extract a slice of a segment descriptor, avoiding copying where possible.
We can share the segment lengths with the original segment descriptor, but still need to recompute the starting indices of each. Hence runtime is O(n) in the number of segments sliced out.
NOTE: In the new segment descriptor, the starting index of the first segment will be 0.
:: USegd | source segment desciptor |
-> Int | index of the first segment |
-> Int | number of segments to extract out |
-> USegd |
O(n). Extract a slice of a segment descriptor, copying everything.
In contrast to sliceUSegd
, this function copies the array of
segment lengths as well as recomputing the starting indices of each.
NOTE: In the new segment descriptor, the starting index of the first segment will be 0.