vanilla-wow-addons – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 --[[
2 Version: 3.9.0.1000 (Kangaroo)
3 Revision: $Id: BalancedList.lua 958 2006-08-16 04:21:17Z mentalpower $
4  
5 License:
6 This program is free software; you can redistribute it and/or
7 modify it under the terms of the GNU General Public License
8 as published by the Free Software Foundation; either version 2
9 of the License, or (at your option) any later version.
10  
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15  
16 You should have received a copy of the GNU General Public License
17 along with this program(see GPL.txt); if not, write to the Free Software
18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 ]]
20 -----------------------------------------------------------------------------
21 -- A balanced list object that always does ordered inserts and pushes off the end
22 -- values in the correct direction to keep the list balanced and median values
23 -- in the center
24 -----------------------------------------------------------------------------
25 local function newBalancedList(paramSize)
26 local self = {maxSize = paramSize, list = {}};
27  
28 -- Does an ordered insert and pushes the an end value off if maxsize
29 -- is exceeded. The end value that is pushed of depends on the location in
30 -- the list that the value was inserted. If it is inserted on the left half
31 -- of the list then the right end value will be pushed off and vise versa.
32 -- This is what keeps the list balanced. For example if your list is {1,2,3,4}
33 -- and you insert(2) then your list would become {1,2,2,3}.
34 local insert = function (value)
35 if (not value) then return; end
36 local val = tonumber(value) or 0;
37  
38 local insertPos = 0
39 local left = 1
40 local right = table.getn(self.list)
41 local middleVal
42 local middle
43 -- insert in sorted order
44 if (right) then
45 while (left <= right) do
46 middle = math.floor((right-left) / 2) + left
47 middleVal = tonumber(self.list[middle]) or 0
48 if (val < middleVal) then
49 right = middle - 1
50 elseif (val > middleVal) then
51 left = middle + 1
52 else
53 insertPos = middle
54 break
55 end
56 end
57 end
58 -- TODO: Check how to optimize that too
59 if (insertPos == 0) then
60 insertPos = left;
61 end
62  
63 table.insert(self.list, insertPos, val);
64  
65 -- see if we need to balance the list
66 if (self.maxSize ~= nil and table.getn(self.list) > self.maxSize) then
67 if (insertPos <= math.floor(self.maxSize / 2) + 1) then
68 table.remove(self.list); -- remove from the right side
69 else
70 table.remove(self.list, 1); -- remove from the left side
71 end
72 end
73 end
74  
75 local clear = function()
76 self.list = {};
77 end
78  
79 -- set the list from a list, if the size exeeds maxSize it it truncated
80 local setList = function(externalList)
81 clear();
82 if (externalList ~= nil) then
83 for i,v in pairs(externalList) do
84 insert(v);
85 end
86 end
87 end
88  
89 -- returns the median value of the list
90 local getMedian = function()
91 return getMedian(self.list);
92 end
93  
94 -- returns the current size of the list
95 local size = function()
96 return table.getn(self.list);
97 end
98  
99 -- retrieves the value in the list at this position
100 local get = function(pos)
101 return tonumber(self.list[pos]);
102 end
103  
104 local getMaxSize = function()
105 return self.maxSize;
106 end
107  
108 local getList = function ()
109 return self.list;
110 end
111  
112 return {
113 ['insert'] = insert,
114 ['getMedian'] = getMedian,
115 ['size'] = size,
116 ['get'] = get,
117 ['clear'] = clear,
118 ['getMaxSize'] = getMaxSize,
119 ['setList'] = setList,
120 ['getList'] = getList
121 }
122 end
123  
124  
125 Auctioneer.BalancedList = {
126 NewBalancedList = newBalancedList,
127 }