inverted indexing (part 2)

Index mappings $n2o: N\rightarrow O$ and $o2n: O\rightarrow N\cup\bot$ can be seen as functions between two type domains $O=1...n$ and $N=1...m.\, m<n$. The inverse operation $o2n=f(n2o,n)$ is defined uniquely by a given $n2o$. This scheme (selecting a remaining subset by $n2o$ and then modifying remaining references and subsets) is very common in all non-functional array programming. 

A practical example is in place. Let $O=1...10$, with two subsets $O_1=1..5$ and $O_2=6...10$. Let $n2o=[1,3,8,9]= \{i\in O\,|\, \phi(i)\}$ be the indices of the selected elements. Then $o2n= [1,-1,2,-1,-1,-1,-1,-1,3,4,-1]$. One can then update the new values of the subsets:
$O_1'\cup\bot= o2n(O_1)= \{1,2,-1\}$ and $O_2'\cup\bot= o2n(O_2)= \{3,4,-1\}$.

The above notation uses ordered sets for the convenience reasons. The rule is to place the 'bottom' marker -1 ($\bot=\{-1\}$ on the index domain) as the last value.

Here is a pseudocode for the inversion, a very useful little function indeed:
def f(n2o, n):
   o2n= [-1]*n  # [-1,-1,-1,...]
   o2n[n2o]= 1..m

All of the above happens at the realm of indices. Such languages as julia allow a direct application of o2n, e.g. in this way:

Asubset= A[subsetInds]
Anew= A[n2o] // initial selection by indices
AsubsetNew= At[o2n[subsetInds]] 
AsubsetNew[-1]= [] // removal of the index slot -1

Inverted indexing (part 1)

Inverted indexing is useful everywhere, not only at the text indexing. In point clouds, the simplest example is when a subset of points $P_-\subset P$ becomes obsolete, but each point $p\in P$ has e.g. a nearest neighborhood set $NN(p)\subset P$, which should be updated to $NN'(p):= NN(p)\backslash P_-$. Let us see how the inverted index can help in this.

The point set is actually an array, so we can state  $P'[n2o]\subset P$ and $P'\cup\bot \equiv P[o2n]$. You can read $n2o$ as 'new-to-old' and vice versa. Both index sets are surjections (there is an index value for all points), so that we need a $\bot$ set for those points, which were not chosen ($\bot$ spells as 'bottom' and is similar to $/dev/null$).  Mathematically:
\[
   n2o= \{ i\,|\, \phi(p_i), p_i\in P\}
\]
and computationally:

inds= list(range(N)) # N== P.shape[0]
n2o= [i for i in range(i) if phi(i)] # just some logical test $\phi(.)$ which defines $P'$

The index array $n2o$ gets its name from that the $j$'th place containing $i$ is actually
$j$'th place of the new point set (and $i$ refers to the old point set). But the substitution
from old to new happens this way: $P':= P[n2o]$! (Remember, mathematically $P'[n2o]\subset P$
but this mathematical indexing is not for computing, but for -uhm- sensible accounting...)

If we had an inverse index $o2n$, we could define:  $NN'\cup\bot := NN(p)[o2n]$ and update all these subsets. Now comes the interesting part, the inversion $n2o \rightarrow o2n$ :

n'= max(n2o)+1 # n' == |P'|
o2n= np.zeros((m,)) -1*np.ones((m,)) # -1 marks an element destined to the bottom
for in in range(n'): # read 'in' as $i_n$!
     io= n2o[in]
     o2n[io]= in

Some languages allow a dictionary to be updated by: $NN':= NN[n2o]$, which would
delete the key values not belonging to the domain of $n2o$. In python, one has to update
the NN dictionary by a loop:

P'= P[n2o] # details like actual coordinate columns are omitted!
NNn= dict([])
for in,io in zip(range(n'),n2o):
    NNn[in]:= NN[io]
NN= NNn

Note that there are some -1's in $o2n$ marking the elements, which belong to $\bot$ (another name
for this could be 'basura'). The actual application of $o2n$ is the updating the subsets $NN(p) \rightarrow NN'(p)$ for those $p$ which made it through the selection i.e. $\phi(p)= True$:

for i in range(n'):
       temp= o2n[NN[i]]
       temp= temp[np.where(temp != -1)]
       NN[i].inds= temp

Inversion of indexing is a common requirement in all kinds of algorithms, but it is often obscured by sloppy coding practices. Do you promise to always use inverse indexing when the occasion reveals itself, for this year 2020 at least?