'2018-06-04T14:10:02
'SPARSE ARRAY

  type element
  ============
  int d        'data
  int x,y,z    'location
  int ha       'hash code
  int prev,next'links
  end type

class SparseArray
=================

  'BODY
  =====
  element*el  'element pointer
  element*pl  'prev element pointer
  int hb[512] 'hash buckets
  int ha      'hash code
  int hi      'hash bucket index
  int ne      'max number of elements
  sys bu      'element buffer
  int ce      'element count
  int ke      'current element
  '
  method constructor(int n=1000)
  ==============================
  ne=n
  bu=getmemory sizeof element*ne
  end method
  '
  method destructor()
  ===================
  freememory bu
  ne=0
  end method
  '
  method Append()
  ===============
  if ce>=ne then
    sys bp=bu
    int np=ne
    ne+=1000
    bu=getmemory ne*sizeof(element)
    copy bu,bp,np*sizeof(element)
    freememory bp
  end if
  @el=bu+ce*sizeof(element)
  end method
  '
  method v(int x,y,z, int d)
  ==========================
  'SET
  ha=x*y*z 'hash of location
  hi=ha and 511
  ke=hb[hi]
  if not ke then
    'append
    Append()
    el={d,x,y,z,ha,0,0}
    ce++
    hb[hi]=ce
  else
    'lookup
    int p
    do 'from last to first
      ke-- 'base 0
      @el=bu+ke*sizeof(element)
      if ha=el.ha
        if (el.x=x)and(el.y=y)and(el.z=z)
          'match
          el.d=d
          exit do
        end if
      end if
      'no match, try previous
      ke=el.prev
      if not ke then 'append
        Append()
        p=hb[hi]
        el={d,x,y,z,ha,p,0}
        ce++
        if @pl then pl.next=ce
        hb[hi]=ce
        exit do
      end if
      @pl=@el
    loop   
  end if  
  end method
  '
  method v(int x,y,z) as int
  ==========================
  'GET
  ha=x*y*z 'hash of location
  hi=ha and 511
  ke=hb[hi]
  if not ke then return 0
  'lookup
  do
    ke-- 'base 0
    @el=bu+ke*sizeof(element)
    if ha=el.ha
      if (el.x=x)and(el.y=y)and(el.z=z)
        'match
        return el.d
      end if
    end if
    'no match, try previous
    ke=el.prev
    if not ke then return 0
  loop   
  end method
  '
end class

'TESTS
======
new SparseArray aa
aa.v(100,200,300)=42
print aa.v(100,200,300)
'print aa.ce
del aa
