sourcelibs/Search/src/Search.xtl
1⍝# Search: searching and ranking -- positions in sorted lists, merges,
2⍝# the k largest, ranks with ties, nearest items, order statistics,
3⍝# ranges.
4⍝# Import it with an alias of your choice: "sr:" u_se< "Search".
5⍝# Put libs/Search/src on XETAL_PATH ("just path"); the reference is libs/Search/docs.
6⍝# Names with l: are exported; those under h: are private to this file.
7⍝#
8⍝# Positions count from 1, as everywhere in X_eTaL. Binary search is
9⍝# Lists' q:b_search; the rest works on whole lists at once.
10
11"q:" u̲se< "Lists"
12
13⍝## Finding
14
15⍝# s p_osition x: where each x is in the sorted list s (its first
16⍝# place), 0 where it is not there.
17ˡp̲osition ← { s x →
18 after ← s q:b̲search x ⍝ how many are <= x
19 before ← '{ y → t̲ally w̲here s < y } e̲ach x
20 found ← (after > before)
21 found × before + 1
22}
23
24⍝# a m_erge b: two sorted lists as one sorted list (stable: a's items
25⍝# before b's equals).
26ˡm̲erge ← { a b → v ← a c̲at b◆ (g̲rade v) s̲elect v }
27
28⍝## Ranking
29
30⍝# k t_opAt v: the positions of the k largest items, largest first
31⍝# (ties in order of position).
32ˡt̲opAt ← { k v →
33 (k < 0) ∨ k > t̲ally v ? @ p̲anic< "there are {t_ally v} items, so not {k} largest"
34 k t̲ake g̲rade n̲eg v
35}
36
37⍝# k t_op v: the k largest items, largest first.
38ˡt̲op ← { k v → (k ˡt̲opAt v) s̲elect v }
39
40⍝# k k_th v: the k-th smallest item (1 is the least).
41ˡk̲th ← { k v →
42 (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}"
43 f̲irst k s̲elect s̲ort v
44}
45
46⍝# r_ank v: each item's rank, 1 for the least; tied items share the
47⍝# mean of their places (1 2.5 2.5 4).
48ˡr̲ank ← { v →
49 less ← '+ r̲/₂ v '> t̲able v
50 same ← '+ r̲/₂ v '= t̲able v
51 (f̲loat less) + (f̲loat same + 1) ÷ 2.0
52}
53
54⍝# d_enseRank v: each item's rank among the distinct values (1 2 2 3).
55ˡd̲enseRank ← { v → (s̲ort u̲nique v) i̲ndexOf v }
56
57⍝## Nearest and ranges
58
59⍝# v n_earest x: for each x, the position of the item of v closest to
60⍝# it (the first, on a tie).
61ˡn̲earest ← { v x → '{ y → f̲irst g̲rade a̲bs (f̲loat v) − f̲loat y } e̲ach x }
62
63⍝# range b_etween v: range is two numbers, lo and hi; whether each
64⍝# item of v lies from lo to hi, both included.
65ˡb̲etween ← { r v → (v ≥ f̲irst r) ∧ v ≤ f̲irst 1 d̲rop r }
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"))
p̲anic< expands to
(⎕P̲ANIC ("there are " c̲at (f̲ormat (t̲ally v)) c̲at " items: the k-th smallest is for k from 1 to " c̲at (f̲ormat (t̲ally v)) c̲at ", not " c̲at (f̲ormat (k))))