librarylibs/Search/src/Search.xtl
Search: searching and ranking -- positions in sorted lists, merges, the k largest, ranks with ties, nearest items, order statistics, ranges. Import it with an alias of your choice: "sr:" u_se< "Search". Put libs/Search/src on XETAL_PATH ("just path"); the reference is libs/Search/docs. Names with l: are exported; those under h: are private to this file.
Positions count from 1, as everywhere in X_eTaL. Binary search is Lists' q:b_search; the rest works on whole lists at once.
Finding
ˡp̲osition : Ord a => a -> a -> Int
s p_osition x: where each x is in the sorted list s (its first place), 0 where it is not there.
ˡp̲osition ← { s x → after ← s q:b̲search x ⍝ how many are <= x before ← '{ y → t̲ally w̲here s < y } e̲ach x found ← (after > before) found × before + 1 }
ˡm̲erge : Ord a => a -> a -> a
a m_erge b: two sorted lists as one sorted list (stable: a's items before b's equals).
ˡm̲erge ← { a b → v ← a c̲at b◆ (g̲rade v) s̲elect v }
Ranking
ˡt̲opAt : Num a => Int -> a -> Int
k t_opAt v: the positions of the k largest items, largest first (ties in order of position).
ˡt̲opAt ← { k v → (k < 0) ∨ k > t̲ally v ? @ p̲anic< "there are {t_ally v} items, so not {k} largest" k t̲ake g̲rade n̲eg v }
p̲anic< expands to
(⎕P̲ANIC ("there are " c̲at (f̲ormat (t̲ally v)) c̲at " items, so not " c̲at (f̲ormat (k)) c̲at " largest"))
ˡt̲op : Num a => Int -> a -> a
k t_op v: the k largest items, largest first.
ˡt̲op ← { k v → (k ˡt̲opAt v) s̲elect v }
ˡk̲th : Ord a => Int -> a -> a
k k_th v: the k-th smallest item (1 is the least).
ˡk̲th ← { k v → (k < 1) ∨ k > t̲ally v ? @ p̲anic< "there are {t_ally v} items: the k-th smallest is for k from 1 to {t_ally v}, not {k}" f̲irst k s̲elect s̲ort v }
ˡr̲ank : Ord a => a -> Float
r_ank v: each item's rank, 1 for the least; tied items share the mean of their places (1 2.5 2.5 4).
ˡr̲ank ← { v → less ← '+ r̲/₂ v '> t̲able v same ← '+ r̲/₂ v '= t̲able v (f̲loat less) + (f̲loat same + 1) ÷ 2.0 }
ˡd̲enseRank : Ord a => a -> Int
d_enseRank v: each item's rank among the distinct values (1 2 2 3).
ˡd̲enseRank ← { v → (s̲ort u̲nique v) i̲ndexOf v }