Documentation

buildDepths :: Vector v a => LEq a -> v a -> Vector Int Source

O(n). Given a comparison function and a vector, this function constructs a Vector Int with the property that the minimum index between i and j in the result vector is the same as the minimum index between i and j in the original vector. (In both cases, ties are broken by which index comes first.)

This allows us to use the specialized range-min implementation on Vector Int, even for other Vector implementations, other element types, and other comparison functions.

Internally, this function constructs the Cartesian tree of the input vector (implicitly, to save memory and stack space), and returns the vector of the depth of each element in the tree.