⍝ Quad-tree packing:

    pack4 10 20 30/'abc'
┌───┬──┬──────────────────────┐
│abc│60│¯3 0 ¯2 0 ¯1 0 1 1 1 2│
└───┴──┴──────────────────────┘

    0 pack4 pack4 10 20 30/'abc'    ⍝ round-trip
aaaaaaaaaabbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccccccccc

    chk←{⍵≡0 pack4 pack4 ⍵}         ⍝ check round-trip

    chk 10 20/'ab'
1
    chk¨ 99 (⊂'hello')              ⍝ check scalar cases
1 1
    chk (4/4)↑4                     ⍝ check higher-rank array
1
    chk ⎕a                          ⍝ worst case: no similar regions.
1
    ∧/ chk¨ '' 'a' 'aa' 'ab' 'aab' 'abb'    ⍝ edge cases.
1
    chk{⍵⍴⍳×/⍵}5/3                  ⍝ worst case: check default ⍺ is adequate.
1
    chk 2 3 0 5 6 ⍴ 88              ⍝ check empty array
1
    pack4{⍵≡0 ⍺⍺ 0 ⍺⍺¨ ⍺⍺¨ ⍺⍺ ⍵} 10 20/'ab'     ⍝ pack of pack.
1
    quads←{⌊/¨⌊((⍳⍺/⍵×⍵)-⎕io)÷⍵}    ⍝ "quadrants" image

    1 quads 4                       ⍝ 1-quad
0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3

    2 quads 4                       ⍝ 2-quad
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 2 2 2 2 2 2 2 2
0 0 0 0 1 1 1 1 2 2 2 2 2 2 2 2
0 0 0 0 1 1 1 1 2 2 2 2 2 2 2 2
0 0 0 0 1 1 1 1 2 2 2 2 2 2 2 2
0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3
0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3
0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3
0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3

    pack4 2 quads 4                 ⍝ pack of 2-quad
┌───────┬─────┬────────────────────────────────────────────┐
│0 1 2 3│16 16│¯3 0 ¯1 0 1 ¯1 0 1 ¯3 0 1 ¯1 0 1 ¯1 2 ¯1 2 3│
└───────┴─────┴────────────────────────────────────────────┘

    cmp←{(⍴,⍵)(⍴¨pack4 ⍵)}          ⍝ compare ravel-shape with pack shapes for:

    cmp 2 quads 4                   ⍝ 2-quad
┌───┬────────┐
│256│┌─┬─┬──┐│
│   ││4│2│19││
│   │└─┴─┴──┘│
└───┴────────┘

    {(⍴,⍵)(⍴¨pack4 ⍵)}3 quads 4     ⍝ 3-quad
┌────┬────────┐
│4096│┌─┬─┬──┐│
│    ││4│3│58││
│    │└─┴─┴──┘│
└────┴────────┘

    {(⍴,⍵)(⍴¨pack4 ⍵)}4 quads 4     ⍝ 4-quad
┌─────┬─────────┐
│65536│┌─┬─┬───┐│
│     ││4│4│179││
│     │└─┴─┴───┘│
└─────┴─────────┘

    image←⌈0.5×∘.⌊⍨⍳8

    image
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 2 2 2 2 2 2
1 1 2 2 2 2 2 2
1 1 2 2 3 3 3 3
1 1 2 2 3 3 3 3
1 1 2 2 3 3 4 4
1 1 2 2 3 3 4 4

    ⍕,[⍬]disp¨{⍵ pack4 image}¨1 to 5        ⍝ decreasing resolution.
 ┌───────┬───┬────────────────────────────────────────────┐ 
 │1 2 3 4│8 8│¯3 0 ¯1 0 1 ¯1 0 1 ¯3 0 1 ¯1 0 1 ¯1 2 ¯1 2 3│ 
 └───────┴───┴────────────────────────────────────────────┘ 
 ┌───────┬───┬───────────┐                                  
 │1 2 3 4│8 8│¯1 0 ¯1 0 2│                                  
 └───────┴───┴───────────┘                                  
 ┌───────┬───┬───────────┐                                  
 │1 2 3 4│8 8│¯1 0 ¯1 0 2│                                  
 └───────┴───┴───────────┘                                  
 ┌───────┬───┬─┐                                            
 │1 2 3 4│8 8│0│                                            
 └───────┴───┴─┘                                            
 ┌───────┬───┬─┐                                            
 │1 2 3 4│8 8│0│                                            
 └───────┴───┴─┘                                            

    {0 pack4 ⍵ pack4 image}¨1 to 5          ⍝ decreasing resolution
┌───────────────┬───────────────┬───────────────┬───────────────┬───────────────┐
│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│
│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│
│1 1 2 2 2 2 2 2│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│
│1 1 2 2 2 2 2 2│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│
│1 1 2 2 3 3 3 3│1 1 1 1 3 3 3 3│1 1 1 1 3 3 3 3│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│
│1 1 2 2 3 3 3 3│1 1 1 1 3 3 3 3│1 1 1 1 3 3 3 3│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│
│1 1 2 2 3 3 4 4│1 1 1 1 3 3 3 3│1 1 1 1 3 3 3 3│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│
│1 1 2 2 3 3 4 4│1 1 1 1 3 3 3 3│1 1 1 1 3 3 3 3│1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1│
└───────────────┴───────────────┴───────────────┴───────────────┴───────────────┘

Back to: code

Back to: Workspaces