From: Simon Strandgaard <qj5nd7l02@...>
Date: 2003-11-20T07:02:16+09:00
Subject: Re: Multi-dimensioned sparse array ?

On Thu, 20 Nov 2003 06:00:03 +0900, Charles Hixson wrote:

> Simon Strandgaard wrote:
> 
>>>>On Wed, 19 Nov 2003 14:21:19 +0900, Charles Hixson wrote:
>>>> 
>>>>>Does anyone have an implementation of a multi-dimensioned sparse
>>>>>array?
>>>>>   
>>>
>>
>>I am curious to how many dimension you need?  3, 7, 50 ?
>>
>>Which kind of algorithm are you implementing?
[snip]
> column, row, and move number you could quickly determine which (if any) 
> piece was on that square.  I'm actually considering many more than eight 
> rows & columns, and more than 200 moves, and perhaps there'll be a third 
> (unknown as yet) dimension.  Like, perhaps, in a game of Angband.  I 


How about just using a one-dimentional sparse array, and this many2one
dimension converter ?


server> ruby a.rb
0
4
16
63
server> expand -t2 a.rb 
class SparseMatrix
  def initialize(*size)
    @size = size
    @data = nil
  end
  attr_accessor :data
  def calc_index(*where)   # many2one dimension conversion
    index = 0
    where.each_with_index{|val, i|
      index *= @size[i]
      index += val
    }
    index
  end
  def [](*where)
    @data[calc_index(*where)]
  end
end

m = SparseMatrix.new(4, 4, 4) 
m.data = (0..63).to_a   # TODO: use sparse matrix array instead
p m[0, 0, 0] # 0
p m[0, 1, 0] # 4
p m[1, 0, 0] # 16
p m[3, 3, 3] # 63
server> 

--
Simon Strandgaard