Log In  



I found myself doing BFS over a very large graph space and with vertices that carry a lot of information. My for this solution in C++ was to use bitsets to store the information in a vertex. I found no documentation of bitsets for Pico or Lua, so I thought of something I call a "nibbleset." A nibbleset is a metatable that holds numbers, and each nibble of the set of numbers can be accessed. 

nibbleset = {}

--Set nibble at index i to a value v:
function nibbleset.set(a,i,v)
  if i/8 > #a then
    return
  end

  local n = ceil(i/8)
  local s = tostr(a[n],1)
  local tr = "0x"
  i-=1 i%=8 i+=1
  if(i>4) i+=1

  for j=1,9 do
     if j==i then
       tr..=v
     else
       tr..=s[j+2]
     end
  end
  a[n]=tonum(tr)
end

--Set nibble at index i to zero:
function nibbleset.reset(a,i)
  if i/8 > #a then
    return
  end

  local n = ceil(i/8)
  local s = tostr(a[n],1)
  local tr = "0x"
  i-=1 i%=8 i+=1
  if(i>4) i+=1

  for j=1,9 do
     if j==i then
       tr..="0"
     else
       tr..=s[j+2]
     end
  end
  a[n]=tonum(tr)
end

nibbleset.__index = nibbleset

--nibbleset constructor that can hold n nibbles:
function make_nibbleset(n)
  local a = {}
  local b = (n/8)+1
  for i=1,b do
  	 add(a,0)
  end
  setmetatable(a,nibbleset)
  return a
end

function nibbleset.__eq(a,b)
  if #a != #b  then
   return false
  end
  for i=1,#a do 
  		if(a[i]!=b[i])return false
  end
  return true
end

function nibbleset.__tostring(a)
	local s =""
	for i=1,#a do
	  local t=tostr(a[i],1)
	  s..=t
	  s..="\n"
	end
	return s
end

any optimization suggestions are welcome!

1



[Please log in to post a comment]