/**
<p>An implementation and visualization of Kanerva's Sparse Distributed Memory as described by <a href="http://cs.gmu.edu/cne/pjd/PUBS/amsci-sdm.pdf">Peter Denning</a>. Each color represents a piece of information stored in memory.</p>
<p>The idea is to mimic human memory with a structure that can make connections between seemingly unrelated information, recall more salient information more accurately, and have quick recall of all information.</p>
<p>This implementation (done in collaboration with <a href="http://lonelypinkelephants.com/">Jason LaPorte</a>) is mostly an exercise in efficiency &mdash; the spirit of SDM is highly parallel, which makes it hard to implement on serial machines.</p>
<p>Future work may include applying the SDM to algorithmic composition (aural and visual) and adaptive dithering.</p>
*/

int step;
int updateRate = 30; // in ms
SparseDistributedMemory s;

void setup () {
  size (256, 256, P3D);
  frameRate (60);
  
  step = 0;
  s = new SparseDistributedMemory (16, 2);
  
  for (int i = 1; i < 16; ++i)
    s.remember ((int) random (s.s), (int) random (s.s));
}

void draw () {
  if (step < s.s) {
    int m = millis ();
  
    loadPixels ();
    while (step < s.s && millis () - m < updateRate) {
      pixels[step] = i16toi24 (s.recall (step));
      ++step;
    }
    updatePixels ();
  }
}

void mousePressed () { setup (); }

int i16toi24 (int i) {
  return (( i        & 3) << 22) |
         (((i >>  2) & 3) << 19) |
         (((i >>  4) & 3) << 16) |
         (((i >>  6) & 3) << 13) |
         (((i >>  8) & 3) << 10) |
         (((i >> 10) & 3) <<  7) |
         (((i >> 12) & 3) <<  4) |
         (((i >> 14) & 3) <<  1);
}

  class SparseDistributedMemory {
  public final int s, n, d;
  
  private short[][] memory;
  private int[] masks;
  
  SparseDistributedMemory (int n, int d) {
    if (n > 31) n = 31;
    if (d > n) d = n;
    
    this.s = 1 << n;
    this.n = n;
    this.d = d;
    
    memory = new short[s][n];
    
    // generate a lookup table
    // (this makes it much easier to figure out how many bits in a bitstring are set.)
    byte[] setBits = new byte[256];
    for (int i = 0; i < 256; ++i) setBits[i] = (byte) ((i & 1) + setBits[i >> 1]);
    
    // for every possible key mask...
    masks = new int[0];
    for (int i = 0; i < s; ++i)
      // if d or fewer bits are set...
      if (setBits[(i >> 24) & 0xFF] +
          setBits[(i >> 16) & 0xFF] +
          setBits[(i >>  8) & 0xFF] +
          setBits[ i        & 0xFF] <= d)
        // add it to the list of masks.
        masks = append (masks, i);
    
    // then, later on, we can just XOR the key and the masks
    // to get each integer within d bits from the key.
  }
  
  void remember (int key, int value) {
    for (int i = 0; i < masks.length; ++i) {
      short[] cell = memory[masks[i] ^ key];
      
      for (int j = 0; j < n; ++j)
        cell[j] += ((value >> j) & 1) == 1 ? +1 : -1;
    }
  }
  
  int recall (int key) {
    int result = 0;
    int[] sum = new int[n];
    
    for (int i = 0; i < masks.length; ++i) {
      short[] cell = memory[masks[i] ^ key];
      
      for (int j = 0; j < n; ++j)
        sum[j] += cell[j];
    }
    
    // convert back to an integer
    for (int i = 0; i < n; ++i) if (sum[i] > 0) result += (1 << i);
    return result;
  }
}