看到哪里排序到哪里的ListView-控件新闻-慧都网

看到哪里排序到哪里的ListView

原创|其它|编辑：郝浩|2009-12-17 11:03:29.000|阅读 551 次

概述：这个Demo窗口上的ListView有一百万个项目，点了“Sort”之后就会开始排序。但这个排序跟以往的不同，你看到哪里它排到哪里，但这个排序不仅仅是在窗口内部排，而是你看到的内容都是正确的。

#慧都22周年庆大促·界面/图表报表/文档/IDE/IOT/测试等千款热门软控件火热促销中>>

这个做了两天的小demo（）主要是为了解决如何在ListView上排序大量数据的问题。

这个Demo窗口上的ListView有一百万个项目，点了“Sort”之后就会开始排序。但这个排序跟以往的不同，你看到哪里它排到哪里，但这个排序不仅仅是在窗口内部排，而是你看到的内容都是正确的。

举个例子，你在浏览1000-1020条的时候，我会开始排序（当然有一点点延迟，不过不会卡窗口），然后确保1000-1020一定是【全局中的】第1000小到第1020小的，就如同全部排过序一样。而且还有一个副作用，就是小于1000的全部比1000小，大于1020的全部比1020大（这可以让你继续浏览的时候排序迅速收敛，而且这听起来应该很熟悉，嘿嘿）。

很明显，算法是一个线程+消息队列的快速排序变形。

欢迎下载并试用。

------------------------------------------------------------------------------------------

下面是代码（如果不想下载可以直接看，不过强烈建议亲身体验）

------------------------------------------------------------------------------------------

  1 using System;
  2 using System.Collections.Generic;
  3 using System.ComponentModel;
  4 using System.Data;
  5 using System.Drawing;
  6 using System.Linq;
  7 using System.Text;
  8 using System.Windows.Forms;
  9 using System.Reflection;
10 using System.Threading;
11
12 namespace PartialSort
13 {
14     public partial class Form1 : Form
15     {
16         private DataManager manager = null;
17         private bool sorted = false;
18
19         public Form1()
20         {
21             InitializeComponent();
22             PropertyInfo prop = listViewData.GetType().GetProperty("DoubleBuffered", BindingFlags.Instance | BindingFlags.NonPublic);
23             prop.SetValue(listViewData, true, new object[] { });
24             manager = new DataManager();
25             listViewData.VirtualListSize = manager.Count;
26         }
27
28         private void Form1_Load(object sender, EventArgs e)
29         {
30         }
31
32         private void listViewData_RetrieveVirtualItem(object sender, RetrieveVirtualItemEventArgs e)
33         {
34             if (sorted)
35             {
36                 manager.WantToBeSorted(e.ItemIndex);
37             }
38             DataItem item = manager[e.ItemIndex];
39             e.Item = new ListViewItem(new string[]
40             {
41                 e.ItemIndex.ToString(),
42                 item.id.ToString(),
43                 item.content.ToString(),
44                 manager.IsHit(e.ItemIndex) ? "YES" : ""
45             });
46         }
47
48         private void button1_Click(object sender, EventArgs e)
49         {
50             sorted = true;
51             timerRefresh.Enabled = true;
52             listViewData.Refresh();
53         }
54
55         private void timerRefresh_Tick(object sender, EventArgs e)
56         {
57             if (manager.Sorting)
58             {
59                 int count = listViewData.Height / listViewData.TopItem.Bounds.Height;
60      ;           for (int i = 0; i < count; i++)
61                 {
62                     int index = listViewData.TopItem.Index + i;
63                     if (manager.IsHit(count))
64                     {
65                         break;
66                     }
67                 }
68             }
69             else
70             {
71                 ;timerRefresh.Enabled = false;
72             }
73             listViewData.Refresh();
74         }
75
76         private void Form1_FormClosed(object sender, FormClosedEventArgs e)
77         {
78             manager.Close();
79         }
80     }
81
82     public struct DataItem
83     {
84         public int id;
85         public double content;
86     }
87
88     public struct Pair
89     {
90         public int first;
91         public int second;
92     }
93
94     public class DataManager
95     {
96         private DataItem[] items = null;
97         private int[] indices = null;
98         private bool[] hits = null;
99         private List<Pair> ranges = new List<Pair>();
100
101         private List<int> request = new List<int>();
102         private Thread sorter = null;
103         private int sorted = 0;
104
105         private int SearchRange(int index)
106         {
107      ;       int firstLarger = ranges.Count;
108             int start = 0;
109             int end = ranges.Count - 1;
110   ;          while (start <= end)
111             {
112                 int mid = (start + end) / 2;
113                 Pair ;p = ranges[mid];
114                 if (p.second < index)
115                 {
116                     start = mid + 1;
117                 }
118        ;         else if (index < p.first)
119                 {
120                     end = mid - 1;
121                     firstLarger = mid;
122                 }
123                 else
124                 {
125      ;               return firstLarger;
126                 }
127             }
128         ;    return firstLarger;
129         }
130
131         private void TryMerge(int firstIndex)
132         {
133             if (firstIndex >= 0 && firstIndex < ranges.Count - 1)
134             {
135                 Pair p1 = ranges[firstIndex];
136                 Pair p2 = ranges[firstIndex + 1];
137                 if (p1.second == p2.first - 1)
138                 {
139                     p1.second = p2.second;
140                     ranges[firstIndex] = p1;
141                     ranges.RemoveAt(firstIndex + 1);
142                 }
143             }
144         }
145
146         private void InsertSortedIndex(int index, int firstLarger)
147         {
148             Pair newPair = new Pair();
149             newPair.first = index;
150             newPair.second = index;
151             ranges.Insert(firstLarger, newPair);
152             TryMerge(firstLarger);
153             TryMerge(firstLarger - 1);
154         }
155
156         private void GetUnsortedRange(int firstLarger, out int start, out int end)
157         {
158             ;start = 0;
159      ;       end = items.Length - 1;
160             if (ranges.Count > 0)
161             {
162                 if (firstLarger == ranges.Count)
163                 {
164                   ;  start = ranges[firstLarger - 1].second + 1;
165                 }
166                 else if (firstLarger == 0)
167                 {
168                     end = ranges[0].first - 1;
169                 }
170                 else
171                 {
172                     start = ranges[firstLarger - 1].second + 1;
173                     end = ranges[firstLarger].first - 1;
174                 }
175             }
176         }
177
178         private int Reorder(int start, int end, int index)
179         {
180           ;  int current = start;
181             int target = end;
182             ;int offset = -1;
183             if (end - index < index - start)
184             {
185                 current = end;
186                 target = start;
187                 offset = 1;
188             }
189             int t = indices[index];
190             indices[index] = indices[current];
191    ;         indices[current] = t;
192
193             while (current != target)
194             {
195                 int result = items[indices[current]].content.CompareTo(items[indices[target]].content);
196      ;           if (result * offset < 0)
197                 {
198               ;      t = indices[current];
199                     indices[current] = indices[target];
200                     indices[target] = t;
201
202          ;           t = current;
203                     current = target;
204                     target = t;
205
206                     offset *= -1;
207                 }
208                 target += offset;
209             }
210             sorted++;
211            return current;
212         }
213
214         private void SorterFunction()
215         {
216             while (Sorting)
217             {
218              ;   int index = -1;
219                 lock (request)
220                 {
221                     if (request.Count > 0)
222                     {
223    ;                     index = request[request.Count - 1];
224                         request.RemoveAt(request.Count - 1);
225                         if (hits[index])
226                         {
227                             index = -1;
228                         }
229                     }
230                 }
231                 if (index != -1)
232                 {
233              ;       int firstLarger = SearchRange(index);
234  ;                   int start = 0;
235                     int end = 0;
236   ;                  GetUnsortedRange(firstLarger, out start, out end);
237                     while (true)
238                     {
239                         int result = Reorder(start, end, index);
240                         InsertSortedIndex(result, firstLarger);
241                         hits[result] = true;
242                         if (result < index)
243                         {
244                             start = result + 1;
245                         }
246                         else if (result > index)
247                         {
248                             end = result - 1;
249                         }
250                         else
251                         {
252                             break;
253                         }
254                     }
255                 }
256                 Thread.Sleep(1);
257             }
258         }
259
260         public DataManager()
261         {
262             items = new DataItem[10000000];
263  ;           indices = new int[items.Length];
264             hits = new bool[items.Length];
265             Random random = new Random((int)DateTime.Now.Ticks);
266             for (int i = 0; i < items.Length; i++)
267             {
268                 items[i] = new DataItem();
269                 items[i].id = i;
270                 items[i].content = random.NextDouble();
271                 indices[i] = i;
272                 hits[i] = false;
273             }
274             sorter = new Thread(SorterFunction);
275             sorter.Start();
276         }
277
278         public void WantToBeSorted(int index)
279         {
280             if (hits[index]) return;
281             lock (request)
282             {
283                 request.Add(index);
284             }
285         }
286
287         public int Count
288         {
289             get
290             {
291                 return items.Length;
292             }
293         }
294
295         public DataItem this[int index]
296         {
297             get
298             {
299                 return items[indices[index]];
300             }
301         }
302
303         public bool IsHit(int index)
304         {
305             return hits[index];
306         }
307
308         public void Close()
309         {
310             sorter.Abort();
311         }
312
313         public bool Sorting
314         {
315             get
316             {
317                 return items.Length > sorted;
318             }
319         }
320     }
321 }
322

标签：

本站文章除注明转载外，均为本站原创或翻译。欢迎任何形式的转载，但请务必注明出处、不得修改原文相关链接，如果存在内容上的异议请邮件反馈至chenjj@hmdbvip.cn

文章转载自：博客园

上一篇：ASP中的EVAL函数下一篇：Infragistics第三方控件 Web控件使用技巧