vanilla-wow-addons – Rev 1

?pathlinks?

Blame – Last modification – View Log – Download

--[[
        Version: 3.9.0.1000 (Kangaroo)
        Revision: $Id: BalancedList.lua 958 2006-08-16 04:21:17Z mentalpower $

        License:
                This program is free software; you can redistribute it and/or
                modify it under the terms of the GNU General Public License
                as published by the Free Software Foundation; either version 2
                of the License, or (at your option) any later version.

                This program is distributed in the hope that it will be useful,
                but WITHOUT ANY WARRANTY; without even the implied warranty of
                MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
                GNU General Public License for more details.

                You should have received a copy of the GNU General Public License
                along with this program(see GPL.txt); if not, write to the Free Software
                Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
]]
-----------------------------------------------------------------------------
-- A balanced list object that always does ordered inserts and pushes off the end
-- values in the correct direction to keep the list balanced and median values
-- in the center
-----------------------------------------------------------------------------
local function newBalancedList(paramSize)
        local self = {maxSize = paramSize, list = {}};

        -- Does an ordered insert and pushes the an end value off if maxsize
        -- is exceeded. The end value that is pushed of depends on the location in
        -- the list that the value was inserted. If it is inserted on the left half
        -- of the list then the right end value will be pushed off and vise versa.
        -- This is what keeps the list balanced. For example if your list is {1,2,3,4}
        -- and you insert(2) then your list would become {1,2,2,3}.
        local insert =  function (value)
        if (not value) then return; end
                local val = tonumber(value) or 0;

                local insertPos = 0
                local left              = 1
                local right             = table.getn(self.list)
                local middleVal
                local middle
                -- insert in sorted order
                if (right) then
                        while (left <= right) do
                                middle = math.floor((right-left) / 2) + left
                                middleVal = tonumber(self.list[middle]) or 0
                                if (val < middleVal) then
                                        right = middle - 1
                                elseif (val > middleVal) then
                                        left = middle + 1
                                else
                                        insertPos = middle
                                        break
                                end
                        end
                end
                -- TODO: Check how to optimize that too
                if (insertPos == 0) then
                        insertPos = left;
                end

                table.insert(self.list, insertPos, val);

                -- see if we need to balance the list
                if (self.maxSize ~= nil and table.getn(self.list) > self.maxSize) then
                        if (insertPos <= math.floor(self.maxSize / 2) + 1) then
                                table.remove(self.list); -- remove from the right side
                        else
                                table.remove(self.list, 1); -- remove from the left side
                        end
                end
        end

        local clear = function()
                self.list = {};
        end

        -- set the list from a list, if the size exeeds maxSize it it truncated
        local setList = function(externalList)
                clear();
                if (externalList ~= nil) then
                        for i,v in pairs(externalList) do
                                insert(v);
                        end
                end
        end

        -- returns the median value of the list
        local getMedian = function()
                return getMedian(self.list);
        end

        -- returns the current size of the list
        local size = function()
                return table.getn(self.list);
        end

        -- retrieves the value in the list at this position
        local get = function(pos)
                return tonumber(self.list[pos]);
        end

        local getMaxSize = function()
                return self.maxSize;
        end

        local getList = function ()
                return self.list;
        end

        return {
                ['insert']              = insert,
                ['getMedian']   = getMedian,
                ['size']                = size,
                ['get']                 = get,
                ['clear']               = clear,
                ['getMaxSize']  = getMaxSize,
                ['setList']             = setList,
                ['getList']             = getList
        }
end


Auctioneer.BalancedList = {
        NewBalancedList = newBalancedList,
}

---

Generated by GNU Enscript 1.6.5.90.