1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using FluentAssertions;
  5 using Xunit;
  6 using Xunit.Abstractions;
  7 
  8 namespace Try_More_On_IEnumerable
  9 {
 10     public class EnumerableTests2
 11     {
 12         private readonly ITestOutputHelper _testOutputHelper;
 13 
 14         public EnumerableTests2(
 15             ITestOutputHelper testOutputHelper)
 16         {
 17             _testOutputHelper = testOutputHelper;
 18         }
 19 
 20         [Fact]
 21         public void T11分组合并()
 22         {
 23             var array1 = new[] {0, 1, 2, 3, 4};
 24             var array2 = new[] {5, 6, 7, 8, 9};
 25 
 26             // 通过本地方法合并两个数组为一个数据
 27             var result1 = ConcatArray(array1, array2).ToArray();
 28 
 29             // 使用 Linq 中的 Concat 来合并两个 IEnumerable 对象
 30             var result2 = array1.Concat(array2).ToArray();
 31 
 32             // 使用 Linq 中的 SelectMany 将 “二维数据” 拉平合并为一个数组
 33             var result3 = new[] {array1, array2}.SelectMany(x => x).ToArray();
 34 
 35             /**
 36              *  使用 Enumerable.Range 生成一个数组，这个数据的结果为
 37              *  0,1,2,3,4,5,6,7,8,9
 38              */
 39             var result = Enumerable.Range(0, 10).ToArray();
 40 
 41             // 通过以上三种方式合并的结果时相同的
 42             result1.Should().Equal(result);
 43             result2.Should().Equal(result);
 44             result3.Should().Equal(result);
 45 
 46             IEnumerable<T> ConcatArray<T>(IEnumerable<T> source1, IEnumerable<T> source2)
 47             {
 48                 foreach (var item in source1)
 49                 {
 50                     yield return item;
 51                 }
 52 
 53                 foreach (var item in source2)
 54                 {
 55                     yield return item;
 56                 }
 57             }
 58         }
 59 
 60         [Fact]
 61         public void T12拉平三重循环()
 62         {
 63             /**
 64              * 通过本地函数获取 0-999 共 1000 个数字。
 65              * 在 GetSomeData 通过三重循环构造这些数据
 66              * 值得注意的是 GetSomeData 隐藏了三重循环的细节
 67              */
 68             var result1 = GetSomeData(10, 10, 10)
 69                 .ToArray();
 70 
 71             /**
 72              * 与 GetSomeData 方法对比，将“遍历”和“处理”两个逻辑进行了分离。
 73              * “遍历”指的是三重循环本身。
 74              * “处理”指的是三重循环最内部的加法过程。
 75              * 这里通过 Select 方法，将“处理”过程抽离了出来。
 76              * 这其实和 “T03分离条件”中使用 Where 使用的是相同的思想。
 77              */
 78             var result2 = GetSomeData2(10, 10, 10)
 79                 .Select(tuple => tuple.i * 100 + tuple.j * 10 + tuple.k)
 80                 .ToArray();
 81 
 82             // 生成一个 0-999 的数组。
 83             var result = Enumerable.Range(0, 1000).ToArray();
 84 
 85             result1.Should().Equal(result);
 86             result2.Should().Equal(result);
 87 
 88             IEnumerable<int> GetSomeData(int maxI, int maxJ, int maxK)
 89             {
 90                 for (var i = 0; i < maxI; i++)
 91                 {
 92                     for (var j = 0; j < maxJ; j++)
 93                     {
 94                         for (var k = 0; k < maxK; k++)
 95                         {
 96                             yield return i * 100 + j * 10 + k;
 97                         }
 98                     }
 99                 }
100             }
101 
102             IEnumerable<(int i, int j, int k)> GetSomeData2(int maxI, int maxJ, int maxK)
103             {
104                 for (var i = 0; i < maxI; i++)
105                 {
106                     for (var j = 0; j < maxJ; j++)
107                     {
108                         for (var k = 0; k < maxK; k++)
109                         {
110                             yield return (i, j, k);
111                         }
112                     }
113                 }
114             }
115         }
116 
117         private class TreeNode
118         {
119             public TreeNode()
120             {
121                 Children = Enumerable.Empty<TreeNode>();
122             }
123 
124             /// <summary>
125             /// 当前节点的值
126             /// </summary>
127             public int Value { get; set; }
128             
129             /// <summary>
130             /// 当前节点的子节点列表
131             /// </summary>
132             public IEnumerable<TreeNode> Children { get; set; }
133         }
134 
135         [Fact]
136         public void T13遍历树()
137         {
138             /**
139              * 树结构如下：
140              * └─0
141              *   ├─1
142              *   │ └─3
143              *   └─2
144              */
145             var tree = new TreeNode
146             {
147                 Value = 0,
148                 Children = new[]
149                 {
150                     new TreeNode
151                     {
152                         Value = 1,
153                         Children = new[]
154                         {
155                             new TreeNode
156                             {
157                                 Value = 3
158                             },
159                         }
160                     },
161                     new TreeNode
162                     {
163                         Value = 2
164                     },
165                 }
166             };
167 
168             // 深度优先遍历的结果
169             var dftResult = new[] {0, 1, 3, 2};
170 
171             // 通过迭代器实现深度优先遍历
172             var dft = DFTByEnumerable(tree).ToArray();
173             dft.Should().Equal(dftResult);
174 
175             // 使用堆栈配合循环算法实现深度优先遍历
176             var dftList = DFTByStack(tree).ToArray();
177             dftList.Should().Equal(dftResult);
178 
179             // 递归算法实现深度优先遍历
180             var dftByRecursion = DFTByRecursion(tree).ToArray();
181             dftByRecursion.Should().Equal(dftResult);
182 
183             // 广度优先遍历的结果
184             var bdfResult = new[] {0, 1, 2, 3};
185 
186             /**
187              * 通过迭代器实现广度优先遍历
188              * 此处未提供“通过队列配合循环算法”和“递归算法”实现广度优先遍历的两种算法进行对比。读者可以自行尝试。
189              */
190             var bft = BFT(tree).ToArray();
191             bft.Should().Equal(bdfResult);
192 
193             /**
194              * 迭代器深度优先遍历
195              * depth-first traversal
196              */
197             IEnumerable<int> DFTByEnumerable(TreeNode root)
198             {
199                 yield return root.Value;
200                 foreach (var child in root.Children)
201                 {
202                     foreach (var item in DFTByEnumerable(child))
203                     {
204                         yield return item;
205                     }
206                 }
207             }
208 
209             // 使用堆栈配合循环算法实现深度优先遍历
210             IEnumerable<int> DFTByStack(TreeNode root)
211             {
212                 var result = new List<int>();
213                 var stack = new Stack<TreeNode>();
214                 stack.Push(root);
215                 while (stack.TryPop(out var node))
216                 {
217                     result.Add(node.Value);
218                     foreach (var nodeChild in node.Children.Reverse())
219                     {
220                         stack.Push(nodeChild);
221                     }
222                 }
223 
224                 return result;
225             }
226 
227             // 递归算法实现深度优先遍历
228             IEnumerable<int> DFTByRecursion(TreeNode root)
229             {
230                 var list = new List<int> {root.Value};
231                 foreach (var rootChild in root.Children)
232                 {
233                     list.AddRange(DFTByRecursion(rootChild));
234                 }
235 
236                 return list;
237             }
238 
239             // 通过迭代器实现广度优先遍历
240             IEnumerable<int> BFT(TreeNode root)
241             {
242                 yield return root.Value;
243 
244                 foreach (var bftChild in BFTChildren(root.Children))
245                 {
246                     yield return bftChild;
247                 }
248 
249                 IEnumerable<int> BFTChildren(IEnumerable<TreeNode> children)
250                 {
251                     var tempList = new List<TreeNode>();
252                     foreach (var treeNode in children)
253                     {
254                         tempList.Add(treeNode);
255                         yield return treeNode.Value;
256                     }
257 
258                     foreach (var bftChild in tempList.SelectMany(treeNode => BFTChildren(treeNode.Children)))
259                     {
260                         yield return bftChild;
261                     }
262                 }
263             }
264         }
265 
266         [Fact]
267         public void T14搜索树()
268         {
269             /**
270              * 此处所指的搜索树是指在遍历树的基础上增加终结遍历的条件。
271              * 因为一般构建搜索树是为了找到第一个满足条件的数据，因此与单纯的遍历存在不同。
272              * 树结构如下：
273              * └─0
274              *   ├─1
275              *   │ └─3
276              *   └─5
277              *     └─2
278              */
279 
280             var tree = new TreeNode
281             {
282                 Value = 0,
283                 Children = new[]
284                 {
285                     new TreeNode
286                     {
287                         Value = 1,
288                         Children = new[]
289                         {
290                             new TreeNode
291                             {
292                                 Value = 3
293                             },
294                         }
295                     },
296                     new TreeNode
297                     {
298                         Value = 5,
299                         Children = new[]
300                         {
301                             new TreeNode
302                             {
303                                 Value = 2
304                             },
305                         }
306                     },
307                 }
308             };
309 
310             /**
311              * 有了深度优先遍历算法的情况下，再增加一个条件判断，便可以实现深度优先的搜索
312              * 搜索树中第一个大于等于 3 并且是奇数的数字
313              */
314             var result = DFS(tree, x => x >= 3 && x % 2 == 1);
315 
316             /**
317              * 搜索到的结果是3。
318              * 特别提出，如果使用广度优先搜索，结果应该是5。
319              * 读者可以通过 T13遍历树 中的广度优先遍历算法配合 FirstOrDefault 中相同的条件实现。
320              * 建议读者尝试以上代码尝试一下。
321              */
322             result.Should().Be(3);
323 
324             int DFS(TreeNode root, Func<int, bool> predicate)
325             {
326                 var re = DFTByEnumerable(root)
327                     .FirstOrDefault(predicate);
328                 return re;
329             }
330 
331             // 迭代器深度优先遍历
332             IEnumerable<int> DFTByEnumerable(TreeNode root)
333             {
334                 yield return root.Value;
335                 foreach (var child in root.Children)
336                 {
337                     foreach (var item in DFTByEnumerable(child))
338                     {
339                         yield return item;
340                     }
341                 }
342             }
343         }
344 
345         [Fact]
346         public void T15分页()
347         {
348             var arraySource = new[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
349 
350             // 使用迭代器进行分页，每 3 个一页
351             var enumerablePagedResult = PageByEnumerable(arraySource, 3).ToArray();
352 
353             // 结果一共 4 页
354             enumerablePagedResult.Should().HaveCount(4);
355             // 最后一页只有一个数字，为 9 
356             enumerablePagedResult.Last().Should().Equal(9);
357 
358 
359             // 通过常规的 Skip 和 Take 来分页是最为常见的办法。结果应该与上面的分页结果一样
360             var result3 = NormalPage(arraySource, 3).ToArray();
361 
362             result3.Should().HaveCount(4);
363             result3.Last().Should().Equal(9);
364 
365             IEnumerable<IEnumerable<int>> PageByEnumerable(IEnumerable<int> source, int pageSize)
366             {
367                 var onePage = new LinkedList<int>();
368                 foreach (var i in source)
369                 {
370                     onePage.AddLast(i);
371                     if (onePage.Count != pageSize)
372                     {
373                         continue;
374                     }
375 
376                     yield return onePage;
377                     onePage = new LinkedList<int>();
378                 }
379 
380                 // 最后一页如果数据不足一页，也应该返回该页
381                 if (onePage.Count > 0)
382                 {
383                     yield return onePage;
384                 }
385             }
386 
387             IEnumerable<IEnumerable<int>> NormalPage(IReadOnlyCollection<int> source, int pageSize)
388             {
389                 var pageCount = Math.Ceiling(1.0 * source.Count / pageSize);
390                 for (var i = 0; i < pageCount; i++)
391                 {
392                     var offset = i * pageSize;
393                     var onePage = source
394                         .Skip(offset)
395                         .Take(pageSize);
396                     yield return onePage;
397                 }
398             }
399 
400             /**
401              * 从写法逻辑上来看，显然 NormalPage 的写法更容易让大众接受
402              * PageByEnumerable 写法在仅仅只有在一些特殊的情况下才能体现性能上的优势，可读性上却不如 NormalPage
403              */
404         }
405 
406         [Fact]
407         public void T16分页与多级缓存()
408         {
409             /**
410              * 获取 5 页数据，每页 2 个。
411              * 依次从 内存、Redis、ElasticSearch和数据库中获取数据。
412              * 先从内存中获取数据，如果内存中数据不足页，则从 Redis 中获取。
413              * 若 Redis 获取后还是不足页，进而从 ElasticSearch 中获取。依次类推，直到足页或者再无数据
414              */
415             const int pageSize = 2;
416             const int pageCount = 5;
417             var emptyData = Enumerable.Empty<int>().ToArray();
418 
419             /**
420              * 初始化各数据源的数据，除了内存有数据外，其他数据源均没有数据
421              */
422             var memoryData = new[] {0, 1, 2};
423             var redisData = emptyData;
424             var elasticSearchData = emptyData;
425             var databaseData = emptyData;
426 
427             var result = GetSourceData()
428                 // ToPagination 是一个扩展方法。此处是为了体现链式调用的可读性，转而使用扩展方法，没有使用本地函数
429                 .ToPagination(pageCount, pageSize)
430                 .ToArray();
431 
432             result.Should().HaveCount(2);
433             result[0].Should().Equal(0, 1);
434             result[1].Should().Equal(2);
435 
436             /**
437              * 初始化各数据源数据，各个数据源均有一些数据
438              */
439             memoryData = new[] {0, 1, 2};
440             redisData = new[] {3, 4, 5};
441             elasticSearchData = new[] {6, 7, 8};
442             databaseData = Enumerable.Range(9, 100).ToArray();
443 
444             var result2 = GetSourceData()
445                 .ToPagination(pageCount, pageSize)
446                 .ToArray();
447 
448             result2.Should().HaveCount(5);
449             result2[0].Should().Equal(0, 1);
450             result2[1].Should().Equal(2, 3);
451             result2[2].Should().Equal(4, 5);
452             result2[3].Should().Equal(6, 7);
453             result2[4].Should().Equal(8, 9);
454 
455             IEnumerable<int> GetSourceData()
456             {
457                 // 将多数据源的数据连接在一起
458                 var data = GetDataSource()
459                     .SelectMany(x => x);
460                 return data;
461 
462                 // 获取数据源
463                 IEnumerable<IEnumerable<int>> GetDataSource()
464                 {
465                     // 将数据源依次返回
466                     yield return GetFromMemory();
467                     yield return GetFromRedis();
468                     yield return GetFromElasticSearch();
469                     yield return GetFromDatabase();
470                 }
471 
472                 IEnumerable<int> GetFromMemory()
473                 {
474                     _testOutputHelper.WriteLine("正在从内存中获取数据");
475                     return memoryData;
476                 }
477 
478                 IEnumerable<int> GetFromRedis()
479                 {
480                     _testOutputHelper.WriteLine("正在从Redis中获取数据");
481                     return redisData;
482                 }
483 
484                 IEnumerable<int> GetFromElasticSearch()
485                 {
486                     _testOutputHelper.WriteLine("正在从ElasticSearch中获取数据");
487                     return elasticSearchData;
488                 }
489 
490                 IEnumerable<int> GetFromDatabase()
491                 {
492                     _testOutputHelper.WriteLine("正在从数据库中获取数据");
493                     return databaseData;
494                 }
495             }
496 
497             /**
498              * 值得注意的是：
499              * 由于 Enumerable 按需迭代的特性，如果将 result2 的所属页数改为只获取 1 页。
500              * 则在执行数据获取时，将不会再控制台中输出从 Redis、ElasticSearch和数据库中获取数据。
501              * 也就是说，并没有执行这些操作。读者可以自行修改以上代码，加深印象。
502              */
503         }
504     }
505 
506     public static class EnumerableExtensions
507     {
508         /// <summary>
509         /// 将原数据分页
510         /// </summary>
511         /// <param name="source">数据源</param>
512         /// <param name="pageCount">页数</param>
513         /// <param name="pageSize">页大小</param>
514         /// <returns></returns>
515         public static IEnumerable<IEnumerable<int>> ToPagination(this IEnumerable<int> source,
516             int pageCount,
517             int pageSize)
518         {
519             var maxCount = pageCount * pageSize;
520             var countNow = 0;
521             var onePage = new LinkedList<int>();
522             foreach (var i in source)
523             {
524                 onePage.AddLast(i);
525                 countNow++;
526 
527                 // 如果获取的数量已经达到了分页所需要的总数，则停止进一步迭代
528                 if (countNow == maxCount)
529                 {
530                     break;
531                 }
532 
533                 if (onePage.Count != pageSize)
534                 {
535                     continue;
536                 }
537 
538                 yield return onePage;
539                 onePage = new LinkedList<int>();
540             }
541 
542             // 最后一页如果数据不足一页，也应该返回该页
543             if (onePage.Count > 0)
544             {
545                 yield return onePage;
546             }
547         }
548     }
549 }