Thread Tools Display Modes
08-23-10, 03:42 PM   #1
sacrife
An Onyxian Warder
 
sacrife's Avatar
AddOn Author - Click to view addons
Join Date: Mar 2009
Posts: 384
Itemsort stack overflow.

I added a piece of code to my modification of cargbags_gnomed borrowed from ouf_nivaya if I remember correctly.

The code works fine, but the first login of a character (first login ever with no wtf/savedvariables files created etc) I get a stack overflow from the line: (5)
local pe = t[floor((l+r)/2)][c] -- pivot element

Anyone know why?

Code:
local function QuickSort(tTable)
    local function QS_int(left,right,t,c)
        if left < right then
            local l, r = left, right
            local pe = t[floor((l+r)/2)][c] -- pivot element
            if pe then 
                while l < r do
                    if t[l][c] then while t[l][c] > pe do l = l + 1 end end
                    if t[r][c] then while t[r][c] < pe do r = r - 1 end end
                    if l <= r then
                        local tItem = t[l]
                        t[l] = t[r]
                        t[r] = tItem
                        l = l + 1
                        r = r - 1
                    end
                end 
            end
            if left < r then QS_int(left, r, t, c) end
            if right > l then QS_int(l, right, t, c) end
        end
    end

    local function tcount(tTable)
        local n = #tTable
        if (n == 0) then for _ in pairs(tTable) do n = n + 1 end end
        return n
    end

    -- sort by quality first:
    local tNum = tcount(tTable)
    QS_int(1, tNum, tTable, 2)
    
    -- then sort by itemID:
    local s, tQ = 1, 0
    if tTable[1] then tQ = tTable[1][2] end
    for e,v in ipairs(tTable) do
        if (v[2] ~= tQ) or (e >= tNum) then
            local b = (e >= tNum) and (v[2] == tQ)
            QS_int(s, b and e or e-1, tTable, 1)
            s, tQ = e, v[2]
        end
    end

    return tTable
end

-- The function for positioning the item buttons in the bag object
local UpdateButtonPositions = function(self)
	local col, row = 0, 0
    local yPosOffs = self.Caption and 20 or 0
--~     local isEmpty = true
	local empty = false

    local buttonIDs = {}
  	for i, button in self:IterateButtons() do
        local tLink = GetContainerItemLink(button.bagID, button.slotID)
        if tLink then
            local _,_,tStr = string.find(tLink, "^|c%x+|H(.+)|h%[.*%]")
            local _,tID = strsplit(":", tStr)
            local _,_,tQ = GetItemInfo(tLink)
            buttonIDs[i] = { tonumber(tID), tQ, button }
        else
            buttonIDs[i] = { 0, -2, button }
        end
    end
    QuickSort(buttonIDs)

	for _,v in ipairs(buttonIDs) do
        local button = v[3]
		button:ClearAllPoints()
      
        local xPos = col * 38
        local yPos = (-1 * row * 38) - yPosOffs

        button:SetPoint("TOPLEFT", self, "TOPLEFT", xPos, yPos)
        if(col >= self.Columns-1) then
            col = 0
            row = row + 1
        else
            col = col + 1
        end
        empty = false
    end
	
	-- Hide if empty 
	-- This variable stores the size of the item button container 
	self.ContainerHeight = (row + (col>0 and 1 or 0)) * 38 
 
	-- checks if our bag is empty. If yes then hide it 
	if(self.ContainerHeight == 0) then empty = true end -- CHANGES 
 
	if(empty) then -- CHANGES 
		self:Hide() 
	else 
		if(self.Name ~= "cB_Shakes_Bag" and self.Name ~= "cB_Shakes_Bank") then 
			self:Show() 
		end 
	end 
 
	if(self.UpdateDimensions) then self:UpdateDimensions() end -- Update the bag's height 
end
__________________

  Reply With Quote
08-23-10, 05:44 PM   #2
SDPhantom
A Pyroguard Emberseer
 
SDPhantom's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2006
Posts: 2,308
This happens a lot when you have a function call itself recursively.
This is what QS_int() seems to be doing.
My advise is find a way to write a formula or put the code in a loop until it comes out with what you want it to do.



Edit1: Hopefully, I successfully integrated a loop in the code to stop the recursive calling and produce the same result. I'm still not sure what the code is supposed to do, but it should be fixed now. It'll either work or be thrown into an infinite loop. *shrugs*

Edit2: Revised the code again, discovered a possibility that wouldn't have resulted in the code running exactly the same way as OP.

Edit3: Hopefully the last revision now that I've worked around with the code a little. I'm still seeing a lot of possibilities for infinite loops, for example, any time pe is nil. This might be what caused the problem in the first place. Added an else break clause to prevent it.

Edit4: Corrected variable contamination before the last check.

lua Code:
  1. local function QS_int(left,right,t,c)
  2.     if left < right then
  3.         local l, r = left, right
  4.         while l < r then
  5.             local pe = t[floor((l+r)/2)][c] -- pivot element
  6.             if pe then
  7.                 while l < r do
  8.                     if t[l][c] then while t[l][c] > pe do l = l + 1 end end
  9.                     if t[r][c] then while t[r][c] < pe do r = r - 1 end end
  10.                     if l <= r then
  11.                         local tItem = t[l]
  12.                         t[l] = t[r]
  13.                         t[r] = tItem
  14.                         l = l + 1
  15.                         r = r - 1
  16.                     end
  17.                 end
  18.             else
  19.                 break
  20.             end
  21.  
  22.             local tl, tr = l, r
  23.             if left < tr then l=left end
  24.             if right > tl then r=right end
  25.         end
  26.     end
  27. end
__________________
WoWInterface AddOns
"All I want is a pretty girl, a decent meal, and the right to shoot lightning at fools."
-Anders (Dragon Age: Origins - Awakening)

Last edited by SDPhantom : 08-23-10 at 06:39 PM.
  Reply With Quote
08-23-10, 11:29 PM   #3
sacrife
An Onyxian Warder
 
sacrife's Avatar
AddOn Author - Click to view addons
Join Date: Mar 2009
Posts: 384
I'm guessing I'm supposed to change line 4 to do instead of then. However, then resulted in an error expecting a do, and a do resulted in an endless load and wow not responding.
__________________

  Reply With Quote
08-23-10, 11:37 PM   #4
SDPhantom
A Pyroguard Emberseer
 
SDPhantom's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2006
Posts: 2,308
This is one reason I went back to using table.sort() with a custom check function. I highly doubt any code written in Lua would be any faster than its C library code.

This is a rough draft for a function that should do the same thing.
lua Code:
  1. local SortByElement;
  2. do
  3.     local idx;
  4.     local chkfunc=function(v1,v2)
  5.         if type(v1)=="table" and type(v2)=="table" and type(idx)~="nil" then
  6.             return v1[idx]<v2[idx];
  7.         elseif type(v1)~="nil" and type(v2)~="nil" then
  8.             return v1<v2;
  9.         else
  10.             return (v1 and true or false);
  11.         end
  12.     end;
  13.     SortByElement=function(tbl,key)
  14.         idx=key;
  15.         table.sort(tbl,chkfunc);
  16.     end
  17. end
__________________
WoWInterface AddOns
"All I want is a pretty girl, a decent meal, and the right to shoot lightning at fools."
-Anders (Dragon Age: Origins - Awakening)

Last edited by SDPhantom : 08-24-10 at 12:15 AM.
  Reply With Quote
08-24-10, 12:31 AM   #5
sacrife
An Onyxian Warder
 
sacrife's Avatar
AddOn Author - Click to view addons
Join Date: Mar 2009
Posts: 384
How would I go about implementing that in my bag addon?

http://pastey.net/139944

Line 140 to 222
__________________

  Reply With Quote
08-24-10, 12:51 AM   #6
SDPhantom
A Pyroguard Emberseer
 
SDPhantom's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2006
Posts: 2,308
The code itself is just a function declaration with isolated upvalues, it can be pasted practically anywhere.

The syntax is similar to table.sort() for the exception it can take an index for what values to compare in a 2d table.
This however doesn't support defining your own check function.

For example, when you're sorting for quality, the call would look like this (assuming the quality is index 2):
Code:
SortByElement(tTable,2)
Note that this'll only handle sorting by only one index.
I can get to work on a complete function rewrite of QuickSort().
You do want to sort by indicies 2 then 1, right?
__________________
WoWInterface AddOns
"All I want is a pretty girl, a decent meal, and the right to shoot lightning at fools."
-Anders (Dragon Age: Origins - Awakening)
  Reply With Quote
08-24-10, 12:57 AM   #7
SDPhantom
A Pyroguard Emberseer
 
SDPhantom's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2006
Posts: 2,308
Go ahead and replace the entire definition of QuickSort() on line 140 with this.

lua Code:
  1. local QuickSort;
  2. do
  3.     local func=function(v1,v2)
  4.         if not v1 or not v2 then return (v1 and true or false); end
  5.         if v1[2]~=v2[2] then
  6.             return v1[2]<v2[2];
  7.         else
  8.             return v1[1]<=v2[1];
  9.         end
  10.     end;
  11.     QuickSort=function(tbl) table.sort(tbl,func); end
  12. end
__________________
WoWInterface AddOns
"All I want is a pretty girl, a decent meal, and the right to shoot lightning at fools."
-Anders (Dragon Age: Origins - Awakening)

Last edited by SDPhantom : 08-24-10 at 12:44 PM.
  Reply With Quote
08-24-10, 01:44 AM   #8
sacrife
An Onyxian Warder
 
sacrife's Avatar
AddOn Author - Click to view addons
Join Date: Mar 2009
Posts: 384
The code returns no errors, but the sorting is weird.

Old Code:


Your code / New code:
__________________

  Reply With Quote
08-24-10, 02:34 AM   #9
SDPhantom
A Pyroguard Emberseer
 
SDPhantom's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2006
Posts: 2,308
Do you have the full addon available for download so I can try to do some debugging?

Edit: Nevermind, I think I found the problem. I corrected the QuickSort() replacement code, try it again.
__________________
WoWInterface AddOns
"All I want is a pretty girl, a decent meal, and the right to shoot lightning at fools."
-Anders (Dragon Age: Origins - Awakening)

Last edited by SDPhantom : 08-24-10 at 02:41 AM.
  Reply With Quote
08-24-10, 06:44 AM   #10
sacrife
An Onyxian Warder
 
sacrife's Avatar
AddOn Author - Click to view addons
Join Date: Mar 2009
Posts: 384
v1 not a value or something :P
I'm at school atm but as far as I remember the v1 in line1 returned an error as nil or non existant or something of the sorts.
__________________

  Reply With Quote
08-24-10, 12:51 PM   #11
SDPhantom
A Pyroguard Emberseer
 
SDPhantom's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2006
Posts: 2,308
I added a condition for if v1 or v2 is nil, shouldn't happen, but I've seen it on rare occasion. I've also seen the sort function complain about the return from the check function too.
__________________
WoWInterface AddOns
"All I want is a pretty girl, a decent meal, and the right to shoot lightning at fools."
-Anders (Dragon Age: Origins - Awakening)
  Reply With Quote
08-24-10, 05:35 PM   #12
sacrife
An Onyxian Warder
 
sacrife's Avatar
AddOn Author - Click to view addons
Join Date: Mar 2009
Posts: 384
Interface\AddOns\cargBags_Shakes\layout.lua:150: invalid order function for sorting
Count: 2


That line is QuickSort=function(tbl) table.sort(tbl,func); end
__________________

  Reply With Quote
08-24-10, 07:22 PM   #13
Saiket
A Chromatic Dragonspawn
 
Saiket's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2008
Posts: 154
Originally Posted by SDPhantom View Post
I added a condition for if v1 or v2 is nil, shouldn't happen, but I've seen it on rare occasion. I've also seen the sort function complain about the return from the check function too.
The bolded part's a bug in the sort implementation, and only happens right before this error would normally fire:
Code:
invalid order function for sorting
It happens when your sort function is non-deterministic, I think.
  Reply With Quote
08-24-10, 08:33 PM   #14
SDPhantom
A Pyroguard Emberseer
 
SDPhantom's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2006
Posts: 2,308
It's a glitch with table.sort() that's been a thorn in my side ever since the beginning. It's supposed to take a boolean return value from the comparison function, but it isn't exactly stable and throws errors on a lot of valid code.
__________________
WoWInterface AddOns
"All I want is a pretty girl, a decent meal, and the right to shoot lightning at fools."
-Anders (Dragon Age: Origins - Awakening)
  Reply With Quote
08-24-10, 10:35 PM   #15
Saiket
A Chromatic Dragonspawn
 
Saiket's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2008
Posts: 154
Originally Posted by SDPhantom View Post
It's a glitch with table.sort() that's been a thorn in my side ever since the beginning. It's supposed to take a boolean return value from the comparison function, but it isn't exactly stable and throws errors on a lot of valid code.
IIRC, it should work alright as long as your sort function always returns consistent results for the same two elements to test, and test(a,b) is always the inverse of test(b,a).
  Reply With Quote
08-25-10, 12:05 AM   #16
haste
Featured Artist
 
haste's Avatar
Premium Member
Featured
Join Date: Dec 2005
Posts: 1,027
You can use a tail call to reuse the stack entry instead of creating a new one like you normally would:
Code:
function a() a() end a() -- fills the stack
function a() return a() end a() -- infinite loop
I haven't really reviewed any of your code however. I also have a train to catch, wups~
__________________
「貴方は1人じゃないよ」
  Reply With Quote
08-25-10, 03:43 AM   #17
SDPhantom
A Pyroguard Emberseer
 
SDPhantom's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2006
Posts: 2,308
Originally Posted by Saiket View Post
IIRC, it should work alright as long as your sort function always returns consistent results for the same two elements to test, and test(a,b) is always the inverse of test(b,a).
Be my guest to look through the latest code I proposed and try to fix it.

From what understanding I make out of that, the sort function doesn't like being told not to swap values for the reason both values are equal?
__________________
WoWInterface AddOns
"All I want is a pretty girl, a decent meal, and the right to shoot lightning at fools."
-Anders (Dragon Age: Origins - Awakening)

Last edited by SDPhantom : 08-25-10 at 03:49 AM.
  Reply With Quote
08-25-10, 04:46 AM   #18
Luzzifus
A Warpwood Thunder Caller
 
Luzzifus's Avatar
AddOn Author - Click to view addons
Join Date: Aug 2007
Posts: 94
Originally Posted by SDPhantom View Post
Be my guest to look through the latest code I proposed and try to fix it.

From what understanding I make out of that, the sort function doesn't like being told not to swap values for the reason both values are equal?
A working version would be this:
lua Code:
  1. local QuickSort;
  2. do
  3.     local func = function(v1, v2)
  4.         if not v1 or not v2 then return (v1 and true or false); end
  5.         if v1[2] ~= v2[2] then
  6.             return v1[2] < v2[2];
  7.         else
  8.             return v1[1] < v2[1];
  9.         end
  10.     end;
  11.     QuickSort = function(tbl) table.sort(tbl, func); end
  12. end

I wrote that recursive sorting function because I didn't find a way to use table.sort with my data structure. I was also aware of the stack overflow errors it produced but I didn't find a way around it. So I hope it's ok if I use your code as a replacement in cargbags_Nivaya too?
  Reply With Quote
08-25-10, 05:34 AM   #19
sacrife
An Onyxian Warder
 
sacrife's Avatar
AddOn Author - Click to view addons
Join Date: Mar 2009
Posts: 384
Originally Posted by Luzzifus View Post
A working version would be this:
lua Code:
  1. local QuickSort;
  2. do
  3.     local func = function(v1, v2)
  4.         if not v1 or not v2 then return (v1 and true or false); end
  5.         if v1[2] ~= v2[2] then
  6.             return v1[2] < v2[2];
  7.         else
  8.             return v1[1] < v2[1];
  9.         end
  10.     end;
  11.     QuickSort = function(tbl) table.sort(tbl, func); end
  12. end

I wrote that recursive sorting function because I didn't find a way to use table.sort with my data structure. I was also aware of the stack overflow errors it produced but I didn't find a way around it. So I hope it's ok if I use your code as a replacement in cargbags_Nivaya too?
I can't see the difference between this code and the one above from SDPhantom. What did you change?

*EDIT*
I added the code from nivaya so it works fine now. Thanks a lot to all parties involved
However, is it possible to add a third sorting? Now it's quality, itemid. Is it possible to add itemcount as a third sort?

And also, how would I go about reversing the quality sort? Now its green > blue > epic. I want to see how it looks the other way.
Its not very important though so don't stress yourself if it's hard ;P
__________________


Last edited by sacrife : 08-25-10 at 05:49 AM.
  Reply With Quote
08-25-10, 08:15 AM   #20
Saiket
A Chromatic Dragonspawn
 
Saiket's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2008
Posts: 154
Originally Posted by sacrife View Post
However, is it possible to add a third sorting? Now it's quality, itemid. Is it possible to add itemcount as a third sort?

And also, how would I go about reversing the quality sort? Now its green > blue > epic. I want to see how it looks the other way.
Its not very important though so don't stress yourself if it's hard ;P
This should flip the item quality sort (just replace '<' with '>' to invert) and fall back on item stack counts if two buttons contain the same itemID.
lua Code:
  1. local QuickSort;
  2. do
  3.     local func = function(v1, v2)
  4.         if v1[2] ~= v2[2] then
  5.             return v1[2] > v2[2]; -- Higher quality first
  6.         elseif v1[1] ~= v2[1] then
  7.             return v1[1] < v2[1];
  8.         else -- Compare stack counts
  9.             local _, c1 = GetContainerItemInfo(v1[3].bagID, v1[3].slotID);
  10.             local _, c2 = GetContainerItemInfo(v2[3].bagID, v2[3].slotID);
  11.             return c1 < c2;
  12.         end
  13.     end;
  14.     QuickSort = function(tbl) table.sort(tbl, func); end
  15. end
  Reply With Quote

WoWInterface » Developer Discussions » Lua/XML Help » Itemsort stack overflow.

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off