How do I remove gaps in an ordered list

I am lookin for a way that will take an ordered table and remove all gaps.
so that the table:

a[13] = "Just"
a[42] = "an"
a[500] = "example!"

will become:

a[1] = "Just"
a[2] = "an"
a[3] = "example!"

is there something built into lua to do this or do I have to right code for this?

I don't know of anything build straight from lua but try this
EDIT: added missing code tags..

function table.condense(tab,rewrite)
--this function condenses a tables numerical keys into the lowest it can.
--note, if rewrite is false, it will just return the condensed form. It will not rewrite the table.
--initiation of variables
  if type(rewrite) ~="boolean" then rewrite = true end
  local condensing = {}
  assert(type(tab) == "table",
  "Bad item to 'condense'. (table expected, got "..type(tab)..")")
  --part to get all the numeric pairs off.
  for key,value in pairs(tab) do
	if type(key)=="number" then
	  condensing[#condensing+1]=tab[key]
	  if rewrite then tab[key]=nil end
	end
  end
  --part to stick them back in.
  if rewrite then
	for i=1,#condensing do
	  tab[i]=condensing[i]
	end
  else
	return condensing
  end
end

CCJJSax, on 28 April 2014 - 08:27 PM said:

function table.condense(tab,rewrite)
–this function condenses a tables numerical keys into the lowest it can.
–note, if rewrite is false, it will just return the condensed form. It will not rewrite the table.
–initiation of variables
if type(rewrite) ~="boolean" then rewrite = true end
local condensing = {}
assert(type(tab) == "table",
"Bad item to 'condense'. (table expected, got "..type(tab)..")")
–part to get all the numeric pairs off.
for key,value in pairs(tab) do
if type(key)=="number" then
condensing[#condensing+1]=tab[key]
if rewrite then tab[key]=nil end
end
end
–part to stick them back in.
if rewrite then
for i=1,#condensing do
tab=condensing
end
else
return condensing
end
end

that is hard to read when it is not inside the code tags, when going to quote on you post I couldsee the spacing
-=EDIT=-
I know with ipairs it will go thought the ordered part in order till it hits a gap, will pairs keep that order? I know pairs goes though all the keys.

Termanater13, on 28 April 2014 - 08:31 PM said:

CCJJSax, on 28 April 2014 - 08:27 PM said:

function table.condense(tab,rewrite)
–this function condenses a tables numerical keys into the lowest it can.
–note, if rewrite is false, it will just return the condensed form. It will not rewrite the table.
–initiation of variables
if type(rewrite) ~="boolean" then rewrite = true end
local condensing = {}
assert(type(tab) == "table",
"Bad item to 'condense'. (table expected, got "..type(tab)..")")
–part to get all the numeric pairs off.
for key,value in pairs(tab) do
if type(key)=="number" then
condensing[#condensing+1]=tab[key]
if rewrite then tab[key]=nil end
end
end
–part to stick them back in.
if rewrite then
for i=1,#condensing do
tab=condensing
end
else
return condensing
end
end

that is hard to read when it is not inside the code tags, when going to quote on you post I couldsee the spacing

I have been trying actually. Just made a note on that post. two space tabbing isn't working. Idk why

CCJJSax, on 28 April 2014 - 08:32 PM said:

I have been trying actually. Just made a note on that post. two space tabbing isn't working. Idk why

tryi wraping the text in the code tags and since you posted for my edit here it is again

Termanater13, on 28 April 2014 - 08:31 PM said:

-=EDIT=-
I know with ipairs it will go thought the ordered part in order till it hits a gap, will pairs keep that order? I know pairs goes though all the keys.

let me try that again

function table.condense(tab, rewrite)
  if type(rewrite) ~= "boolean" then rewrite = true end
  local condensing = {}
  assert(type(tab) == "table",
    "Bad item to 'condense'. (table expected, got "..type(tab)..")")
  for key, value in pairs(tab) do
    if type(key) == "number" then
      condensing[#condensing+1]=tab[key]
      if rewrite then tab[key] = nil end
    end
  end
  if rewrite then
    for i = 1, #condensing do
      tab[i] = condensing[i]
    end
  else
    return condensing
  end
end

Termanater13, on 28 April 2014 - 08:37 PM said:

CCJJSax, on 28 April 2014 - 08:32 PM said:

I have been trying actually. Just made a note on that post. two space tabbing isn't working. Idk why

tryi wraping the text in the code tags and since you posted for my edit here it is again

Termanater13, on 28 April 2014 - 08:31 PM said:

-=EDIT=-
I know with ipairs it will go thought the ordered part in order till it hits a gap, will pairs keep that order? I know pairs goes though all the keys.

Crap. I'm usually really good at that too. don't know how I missed it lol

BTW, I got that code from here. I didn't write it.

The code you posted won't actually order the table, as a pairs loop returns the table indexes in a seemingly random order. table.sort is probably more akin to what you actually need, i have however never used it myself.
http://www.lua.org/pil/19.3.html

CometWolf, on 28 April 2014 - 08:44 PM said:

The code you posted won't actually order the table, as a pairs loop returns the table indexes in a seemingly random order. table.sort is probably more akin to what you actually need, i have however never used it myself.
http://www.lua.org/pil/19.3.html

I had tested table.sort() but it doesn't appear to sort the keys. only the variables if they are numbers.

Yes, if you use the default table.sort, it will sort the table based on the size of the table values. However, you can pass it an optional second argument, which is an order function. Something like this, would do the trick.

t = {
  [2] = "derp",
  [5] = "what",
  [500] = "sortdat"
}
local compressed = {}
for k,v in pairs(t) do
  compressed[#compressed+1] = {
	key = k,
	value = v
  }
end
table.sort(
  compressed,
  function(v1,v2)
	return v1.key < v2.key
  end
)
local ordered = {}
for i=1,#compressed do
  ordered[i] = compressed[i].value
end

Edit: I just tested this, it works as desired… So there you go i guess :P/>

CometWolf, on 28 April 2014 - 08:56 PM said:

Yes, if you use the default table.sort, it will sort the table based on the size of the table values. However, you can pass it an optional second argument, which is an order function. Something like this, would do the trick.

t = {
  [2] = "derp",
  [5] = "what",
  [500] = "sortdat"
}
local compressed = {}
for k,v in pairs(t) do
  compressed[#compressed+1] = {
	key = k,
	value = v
  }
end
table.sort(
  compressed,
  function(v1,v2)
	return v1.key < v2.key
  end
)
local ordered = {}
for i=1,#compressed do
  ordered[i] = compressed[i].value
end

Edit: I just tested this, it works as desired… So there you go i guess :P/>

so if im reading this right, to get it to work with the keys, I would have to turn them into a value then sort based on that. Which the code you provided does automatically.

Essentially table.sort's order function gets 2 variables from the table, and should return true if the first variable should be before the second in the new ordered table. So i figured if i could access the keyes, while retaining the values aswell, i could sort it based on the keyes. Then the last for loop is used to convert it back to a regular table. So, basically yes that is what you would have to do.

CometWolf, on 28 April 2014 - 09:47 PM said:

Essentially table.sort's order function gets 2 variables from the table, and should return true if the first variable should be before the second in the new ordered table. So i figured if i could access the keyes, while retaining the values aswell, i could sort it based on the keyes. Then the last for loop is used to convert it back to a regular table. So, basically yes that is what you would have to do.

thanks, that is exactly what I needed. The value has no affect on the order but the key does. I was just asking to better understand the code you gave.

Concerning this table:

a[13] = "Just"
a[42] = "an"
a[500] = "example!"

… it may be handy to know that while a quick #a will return 0, a slower table.maxn(a) call will return 500.

Given this, you could have:

local function squash(myTable)
	local curIndex = 1

	for i=1,table.maxn(myTable) do
		if myTable[i] then
			myTable[curIndex] = myTable[i]
			myTable[i] = nil
			curIndex = curIndex + 1
		end
	end
end

Bomb, yes but that seems very slow… There has to be a better way…

Oh wait, I just saw the other guy's script.

If the table were very very large and very very empty, Comet's method might just win out. I'm thinking he wrote it on the basis that he'd forgotten how to get the highest table index, however.

Another thing worth mentioning - if you use table.remove() to get rid of entries in a numerically indexed table, the following entries will automatically be moved down the list to plug the gap.

There are a couple of issues with doing this. For starters, if you've set up a loop using pairs(myTable), removing entries from myTable in the middle of that loop will likely trigger a crash (pairs / ipairs tend to get confused if the table they're operating on suddenly changes length mid-way), and even a basic "for i=1,#myTable do" loop might run into trouble if the body's not coded to account for it. Manually condensing the table after the entry-removing loop is indeed one way around that.

The other is that table.remove() operates in a similar manner to the code I provided - using it every time you remove an entry is hence a lot slower than removing lots of entries by setting them to nil, then running my function a single time to pack 'em all down in one go.

On the other hand, table.remove() can indeed be the best tool for the job on occasion.

Yeah but the OP's table is quite empty, wouldn't you agree?

You can also get away with using a variant on CometWolf's method that doesn't require a custom table.sort:

function compressSparse(tab)
    local keySet = {}
    for i in pairs(tab) do
        table.insert(keySet, i)
    end
    
    table.sort(keySet)
    
    local retVal = {}
    for i = 1, #keySet do
        retVal[i] = tab[keySet[i]]
    end
    
    return retVal
end

HometownPotato, on 29 April 2014 - 04:00 AM said:

Yeah but the OP's table is quite empty, wouldn't you agree?

I would, though it's also an example. I'm not inclined to argue; whichever code he feels suits his actual use-case is fine by me.

Ohh, Lyqyd is interesting. Never though of that

Also, Bomb Bloke's point above about table.remove touches on an important issue that should be addressed in this post–why is the table sparse in the first place? There are usually better ways of doing things than allowing a table to become sparse when you're going to want to have it be array-like later. I'm having trouble thinking of something that would result in having this sort of problem in the first place.

Lyqyd, on 29 April 2014 - 04:23 AM said:

Also, Bomb Bloke's point above about table.remove touches on an important issue that should be addressed in this post–why is the table sparse in the first place? There are usually better ways of doing things than allowing a table to become sparse when you're going to want to have it be array-like later. I'm having trouble thinking of something that would result in having this sort of problem in the first place.

I'm creating a system that adds a z axis to the x,y of a monitor, where the user can use an arbitrary number for z and it creates a gapless ordered list based on that. this way a perosn can use (1,2,5,63,708) as the z numbers and when the code runs it the order will be (1,2,3,4,5), the values of those numbers will point to a differint place in the bigger table. I have plans that if z is not set the latest to be crated will have the highest z and thus placed ontop of everthing else.

So once the initial table setup is complete, how would the user add any more entries to eg z layer 63 (or even locate a layer with that number), given that you've changed it to 4?

If there won't be any changes after the table is built, or the user isn't intended to be able to browse through the layers, then why bother tracking anything other then the "top-most" entry? Couldn't all the others simply be discarded if covered?

Bomb Bloke, on 30 April 2014 - 02:54 AM said:

So once the initial table setup is complete, how would the user add any more entries to eg z layer 63 (or even locate a layer with that number), given that you've changed it to 4?

If there won't be any changes after the table is built, or the user isn't intended to be able to browse through the layers, then why bother tracking anything other then the "top-most" entry? Couldn't all the others simply be discarded if covered?

the list created by the users code I was going to have avaliable to them, and the one created by this code use it to display each element in the right order. There are probably better ways to get the same result, but right now I am just looking for something to get that part working and that was the best way I could think of. Setting how the second argumemt in the sort function works I may find a different way of doing it, but this will allow me to get it working till I find a better way.