14. Interval Index

I←{¯1+(≢⍺)↓i⊣i[i]←+\(≢⍺)>i←⍋⍺⍪⍵}

⍺ is required to be duplicate-free and sorted in ascending order, and therefore partitions the domain into contiguous intervals from ¯∞ to ∞ . If ⍵ has the shape of a major cell of ⍺ , then ⍺ I ⍵ is the largest j , the interval index, such that j⌷⍺ precedes ⍵ in the ordering, or ¯1 if ⍵ precedes the first major cell of ⍺ or if ⍺ has no major cells.

An example with numbers:

   x← ¯1 2 3 7 8.5
   y← 0 4 7 6 11 2 1 3 ¯5

   x I y
0 2 3 2 4 1 0 2 ¯1

The following schematic illustrates the intervals formed by x :

¯∞     ¯1     2      3      7      8.5   ∞
↓      ↓      ↓      ↓      ↓      ↓     ↓
(     )[     )[     )[     )[     )[     )
  ¯1      0      1      2      3      4

An example with character matrices:

   c ← ↑ 'Fi' 'Jay' 'John' 'Morten' 'Roger'
   d ← ↑ 'JD' 'Jd' 'Geoff' 'Anna' 'Scott' 'Zeus  '

   c I d
0 1 0 ¯1 4 4

The following schematic illustrates the intervals formed by c :

¯∞       Fi       Jay      John     Morten   Roger   ∞
↓        ↓        ↓        ↓        ↓        ↓       ↓
(       )[       )[       )[       )[       )[       )
   ¯1        0        1        2        3        4   
  Anna     JD        Jd                        Scott
           Geoff                               Zeus

In general, interval index applies to the rank 0⌈(⍴⍴⍺)-1 cells of ⍵ . If ⍵ has rank greater than that of ⍺ , the function needs to be modified as follows:

   I1←{¯1+(r↓⍴⍵)⍴(≢⍺)↓i⊣i[i]←+\(≢⍺)>i←⍋⍺⍪,[r↓⍳⍴⍴⍵]⍵⊣r←1-⍴⍴⍺}

   x I1 y
0 2 3 2 4 1 0 2 ¯1
   x I1 3 3⍴y
0 2  3
2 4  1
0 2 ¯1

Interval index has been proposed as a primitive in Dyalog APL [52]. A total array ordering [51a, 53] would increase its usefulness.

Similar ideas were presented in [49b, 51b].