Lists; a fast way to store objects.

[airstruck]

Glad all of you agree on something, but that still doesn't change the fact that my original example airstruck took apart didn't have the issue you guys were discussing.

I think it is affected by the assignment order issue, but not in the way I originally described. The problem is that when i==#t, first e is copied into the last position in t, but then the value that was previously there is copied back over it again, so in the end e never makes it into the table. As far as I can tell, anyway.

Not sure what I was thinking with the two copies of e thing, I think I was looking at it as if the t on the right would be evaluated between the first and second assignment.

[zorg]

Not sure what I was thinking with the two copies of e thing, I think I was looking at it as if the t on the right would be evaluated between the first and second assignment.

It's cool, don't worry.

I think it is affected by the assignment order issue, but not in the way I originally described. The problem is that when i==#t, first e is copied into the last position in t, but then the value that was previously there is copied back over it again, so in the end e never makes it into the table. As far as I can tell, anyway.

Although the online testbed still agrees with me, it seems:

Code: Select all

local t = {1,2,3,4,5,6}
local i = #t -- As you suggested
local e = 7
t[#t+1], t[i] = t[i], e
for i=1,#t do print(i,t[i]) end
--[[result:
1   1
2   2
3   3
4   4
5   5
6   7
7   6
--]]

Basically, going by what Inny proved, evaluating from LtR gives us 6, 7 on the RHS, and assigning from RtL means that 7 (not e now, since it's eval'd) gets put into t, and 6 (not t, since again, it has been evaluated) gets put into t[#t+1].

So again, unless both LHS places point to the same location, the assignment order should not matter.

[airstruck]

t[#t+1], t = t, e

Didn't you originally write t[#t], t = t, e? That was the code I was referring to.

So again, unless both LHS places point to the same location, the assignment order should not matter.

Right, so in the case of t[#t], t = t, e, both LHS are the same location when i==#t, and you run into the assignment order problem.

Code: Select all

t = { 1, 2, 3, 4, 5 }
i = #t
e = 6
t[#t], t[i] = t[i], e
print(table.concat(t)) -- prints 12345, not 12346

whether it's #t or #t+1 should not matter much

I must have missed the change from #t to #t+1, but I think it does matter. If i is supposed to be <= #t then #t+1 will never be equal to i, so you won't have the assignment order problem. But #t will sometimes equal i, so you'll have the problem there.

[Positive07]

Is there any benefit on this approach? I mean you insert into an specific position, but you can't guarantee it will be there next time you look, since other object may have been inserted in the same position right? So yeah, insertion is fast but is pointless cause the list will never be ordered. You could use a simpler append and that would do it too right?

[zorg]

Well, the whole thing started with two things;
- kikito mentioning removing from within a sequence, and
- me adding an example for adding to an arbitrary location in a sequence, displacing the old value to the end.

I did mess up by writing [#t] instead of [#t+1] at first though... and i only wrote that as an example for another uncommon scenario, which was fast, but i didn't see a point to actually do.

In any case, i think we can all agree that it was fun banter.

[Positive07]

I think that the objective of a sequence is that the objects should be in some kind of order, and adding/removing should keep the sequence organized, in lists that is if you remove the fourth element then the fifth takes it's place and the sixth takes the place of the fifth and so on.

So if you are adding or removing in an unorganized fashion then you are working with arrays which aren't necesarily ordered, and if that is the case there is no need to insert at an specific position, you can simply insert at the end, if you don't want holes then removing is the most costly part but you could take the element from the end and insert it in the place of the element you want to remove then you set the last object to nil.

Code: Select all

local luaCode = function (...) end
--Insert at the end
t[#t + 1] = new
--Removal of nth item (should work even if n == #t)
t[n] = t[#t]
t[#t] = nil

This should be pretty fast for arrays (unordered items). Lists/Sequences are harder because as I said you need to keep the order, so you would need similar functionality to what [manual]table.remove[/manual] and [manual]table.insert[/manual] do, shifting the elements.

[prixt]

Code: Select all

--==List==--

local list = {}
list.__index = list

list.__len = function(self)
	return self.size
end

list._init = function(self)
    self.p,self.n = {},{}
    self.size = 0
    self.current = false
    
    self.p[self] = self
    self.n[self] = self
end

list.has = function(self,item)
    if not item or item == self or not self.p[item] then return false
    else return true end
end

list.insert = function(self,item)
    if not item or item == self or self:has(item) then return false end
    if self.size == 0 then self.current = item end
    self.size = self.size + 1
    local tail = self.p[self]
    self.n[tail] = item
    self.p[item] = tail
    self.n[item] = self
    self.p[self] = item
    return true
end
list.remove = function(self,item)
    local item = item or self.p[self]
    if not self:has(item) then return false end
    self.size = self.size - 1
    if self.size == 0 then self.current = false end
    if item == self.current then
        self:goNext()
    end
    local p,n = self.p[item],self.n[item]
    self.n[p] = n
    self.p[n] = p
    self.n[item] = nil
    self.p[item] = nil
    return item
end

list.swap = function(self,item1,item2)
	if not (self:has(item1) and self:has(item2)) then return false end
	
	local temp
	temp = self.p[item1]
	self.p[item1] = self.p[item2]
	self.p[item2] = temp
	temp = self.n[item1]
	self.n[item1] = self.n[item2]
	self.n[item2] = temp
	
	return true
end

list.getNext = function(self,item)
    local item = item
    if not self:has(item) then return false end
    item = self.n[item]
    if item == self then item = self.n[item] end
    return item
end
list.getPrev = function(self,item)
    local item = item
    if not self:has(item) then return false end
    item = self.p[item]
    if item == self then item = self.p[item] end
    return item
end

list.getCurrent = function(self)
    return self.current
end
list.setCurrent = function(self,item)
    if not self:has(item) then return false end
    self.current = item
    return true
end

list.goNext = function(self)
    if not self.current then return false end
    self.current = self:getNext(self.current)
    return true
end
list.goPrev = function(self)
    if not self.current then return false end
    self.current = self:getPrev(self.current)
    return true
end

list.iter = function(self)
    self.current = self.n[self]
    local item
    return function()
        if self.size == 0 or item == self.p[self] then return end
        if item == self.current then self:goNext() end
        item = self.current
        return item
    end
end

list.loop = function(self)
    local item
    return function()
        if self.size == 0 then return end
        if item == self.current then self:goNext() end
        item = self.current
        return item
    end
end

return setmetatable({},{
	__index = list,
	__call = function(self)
		local t = setmetatable({},list)
		list._init(t)
		return t
	end
})

Pros:
-Easy to see if something is in the list or not.
-Should be fast to remove.
-Can be looped indefinitely, allowing for use in game loops and/or coroutines.

Cons:
-Doens't allow false values(false, nil)
-Cannot insert the list within itself.
-Cannot have duplicate items in the list.