mcs/class/System.Core/System.Linq.Parallel.QueryNodes/QuerySelectManyNode.cs

   1 //
   2 // QueryConcatNode.cs
   3 //
   4 // Author:
   5 //       Jérémie "Garuma" Laval <jeremie.laval@gmail.com>
   6 //
   7 // Copyright (c) 2010 Jérémie "Garuma" Laval
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining a copy
  10 // of this software and associated documentation files (the "Software"), to deal
  11 // in the Software without restriction, including without limitation the rights
  12 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  13 // copies of the Software, and to permit persons to whom the Software is
  14 // furnished to do so, subject to the following conditions:
  15 //
  16 // The above copyright notice and this permission notice shall be included in
  17 // all copies or substantial portions of the Software.
  18 //
  19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  20 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  22 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  23 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  24 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  25 // THE SOFTWARE.
  26
  27 #if NET_4_0
  28 using System;
  29 using System.Threading;
  30 using System.Collections;
  31 using System.Collections.Generic;
  32
  33 namespace System.Linq.Parallel.QueryNodes
  34 {
  35         internal class QuerySelectManyNode<TSource, TCollection, TResult> : QueryStreamNode<TResult, TSource>
  36         {
  37                 Func<TSource, IEnumerable<TCollection>> collectionSelector;
  38                 Func<TSource, int, IEnumerable<TCollection>> collectionSelectorIndexed;
  39                 Func<TSource, TCollection, TResult> resultSelector;
  40
  41                 internal QuerySelectManyNode (QueryBaseNode<TSource> parent,
  42                                               Func<TSource, int, IEnumerable<TCollection>> collectionSelectorIndexed,
  43                                               Func<TSource, TCollection, TResult> resultSelector)
  44                         : base (parent, true)
  45                 {
  46                         this.collectionSelectorIndexed = collectionSelectorIndexed;
  47                         this.resultSelector = resultSelector;
  48                 }
  49
  50                 internal QuerySelectManyNode (QueryBaseNode<TSource> parent,
  51                                               Func<TSource, IEnumerable<TCollection>> collectionSelector,
  52                                               Func<TSource, TCollection, TResult> resultSelector)
  53                         : base (parent, false)
  54                 {
  55                         this.collectionSelector = collectionSelector;
  56                         this.resultSelector = resultSelector;
  57                 }
  58
  59                 internal override IEnumerable<TResult> GetSequential ()
  60                 {
  61                         IEnumerable<TSource> source = Parent.GetSequential ();
  62
  63                         return IsIndexed ?
  64                                 source.SelectMany (collectionSelectorIndexed, resultSelector) :
  65                                 source.SelectMany (collectionSelector, resultSelector);
  66                 }
  67
  68                 internal override IList<IEnumerable<TResult>> GetEnumerablesIndexed (QueryOptions options)
  69                 {
  70                         return Parent.GetOrderedEnumerables (options)
  71                                 .Select ((i) => GetEnumerableInternal (i,
  72                                                                        (kv) => collectionSelectorIndexed (kv.Value, (int)kv.Key),
  73                                                                        (e, c) => resultSelector (e.Value, c)))
  74                                 .ToList ();
  75                 }
  76
  77                 internal override IList<IEnumerable<TResult>> GetEnumerablesNonIndexed (QueryOptions options)
  78                 {
  79                         return Parent.GetEnumerables (options)
  80                                 .Select ((i) => GetEnumerableInternal (i,
  81                                                                        collectionSelector,
  82                                                                        (e, c) => resultSelector (e, c)))
  83                                 .ToList ();
  84                 }
  85
  86                 internal override IList<IEnumerable<KeyValuePair<long, TResult>>> GetOrderedEnumerables (QueryOptions options)
  87                 {
  88                         var source = Parent.GetOrderedEnumerables (options);
  89                         var sizeRequests = new Tuple<long, int, IEnumerable<TCollection>> [options.PartitionCount];
  90                         if (collectionSelectorIndexed == null)
  91                                 collectionSelectorIndexed = (e, i) => collectionSelector (e);
  92                         long deviation = 0;
  93
  94                         Barrier barrier = new Barrier (options.PartitionCount, delegate {
  95                                         Array.Sort (sizeRequests, (e1, e2) => e1.Item1.CompareTo (e2.Item1));
  96                                         long newDeviation = deviation;
  97                                         for (int i = sizeRequests.Length - 1; i >= 0; i--) {
  98                                                 var reqi = sizeRequests[i];
  99                                                 long newIndex = reqi.Item1 + deviation;
 100                                                 newDeviation += reqi.Item2 - 1;
 101                                                 for (int j = i - 1; j >= 0; j--)
 102                                                         newIndex += sizeRequests[j].Item2 - 1;
 103                                                 sizeRequests[i] = Tuple.Create (newIndex, reqi.Item2, reqi.Item3);
 104                                         }
 105                                         deviation = newDeviation;
 106                                 });
 107
 108                         return source
 109                                 .Select ((i, ind) => GetOrderedEnumerableInternal (i, sizeRequests, ind, barrier))
 110                                 .ToList ();
 111                 }
 112
 113                 IEnumerable<TResult> GetEnumerableInternal<T> (IEnumerable<T> source,
 114                                                                Func<T, IEnumerable<TCollection>> collectionner,
 115                                                                Func<T, TCollection, TResult> packer)
 116                 {
 117                         foreach (T element in source)
 118                                 foreach (TCollection item in collectionner (element))
 119                                         yield return packer (element, item);
 120                 }
 121
 122                 IEnumerable<KeyValuePair<long, TResult>> GetOrderedEnumerableInternal (IEnumerable<KeyValuePair<long, TSource>> source,
 123                                                                                        Tuple<long, int, IEnumerable<TCollection>>[] sizeRequests,
 124                                                                                        int index,
 125                                                                                        Barrier barrier)
 126                 {
 127                         try {
 128                                 foreach (KeyValuePair<long, TSource> element in source) {
 129                                         IEnumerable<TCollection> collection = collectionSelectorIndexed (element.Value, (int)element.Key);
 130                                         sizeRequests[index] = Tuple.Create (element.Key, GetCount (ref collection), collection);
 131
 132                                         barrier.SignalAndWait ();
 133
 134                                         long i = sizeRequests[index].Item1;
 135                                         collection = sizeRequests[index].Item3;
 136
 137                                         foreach (TCollection item in collection)
 138                                                 yield return new KeyValuePair<long, TResult> (i++, resultSelector (element.Value, item));
 139                                 }
 140                         } finally {
 141                                 barrier.RemoveParticipant ();
 142                         }
 143                 }
 144
 145                 /* If getting Count is a O(1) operation (i.e. actual is a ICollection) then return it immediatly
 146                  * if not process the IEnumerable into a List and return the Count from that (i.e. enumerable
 147                  * processing will only happen once in case of e.g. a Linq query)
 148                  */
 149                 static int GetCount<T> (ref IEnumerable<T> actual)
 150                 {
 151                         ICollection coll = actual as ICollection;
 152                         if (coll != null)
 153                                 return coll.Count;
 154
 155                         var foo = actual.ToList ();
 156                         actual = foo;
 157
 158                         return foo.Count;
 159                 }
 160         }
 161 }
 162
 163 #endif