1# -*- coding: utf-8 -*- 

2""" 

3@file 

4@brief Simple *mapper* and *reducer* implemented in :epkg:`Python` 

5""" 

6from itertools import groupby 

7 

8 

9def mapper(fct, gen): 

10 """ 

11 Applies function *fct* to a generator. 

12 

13 @param fct function 

14 @param gen generator 

15 @return generator 

16 

17 .. exref:: 

18 :title: mapper 

19 :tag: progfonc 

20 

21 .. runpython:: 

22 :showcode: 

23 

24 from sparkouille.fctmr import mapper 

25 res = mapper(lambda x: x + 1, [4, 5]) 

26 print(list(res)) 

27 

28 .. faqref:: 

29 :title: Différence entre un itérateur et un générateur ? 

30 :tag: faqprogfonc 

31 

32 Un :epkg:`itérateur` et un :epkg:`générateur` produisent 

33 tous deux des éléments issus d'un ensemble. La différence 

34 vient du fait que qu'un :epkg:`itérateur` parcourt les 

35 éléments d'un ensemble qui existe en mémoire. Un :epkg:`générateur` 

36 produit ou calcule des éléments d'un ensemble qui n'existe 

37 pas en mémoire. Par conséquent, parcourir deux fois un ensemble 

38 avec un itérateur a un coût en :math:`O(n)` alors que pour 

39 un générateur, il faut ajouter le calcul de l'élément une 

40 seconde fois. Le coût est imprévisible et parfois il est 

41 préférable de :epkg:`cacher` les éléments pour le parcourir 

42 plusieurs fois : cela revient à transformer un :epkg:`générateur` 

43 en :epkg:`itérateur`. Un générateur est souvent défini comme suit 

44 en :epkg:`Python` : 

45 

46 .. runpython:: 

47 :showcode: 

48 

49 def generate(some_iterator): 

50 for el in some_iterator: 

51 yield el 

52 

53 g = generate([4, 5]) 

54 print(list(g)) 

55 print(g.__class__.__name__) 

56 """ 

57 return map(fct, gen) 

58 

59 

60def take(gen, count=5, skip=0): 

61 """ 

62 Skips and takes elements from a generator. 

63 

64 @param gen generator 

65 @param count number of elements to consider 

66 @param skip skip the first elements 

67 @return generator 

68 

69 .. exref:: 

70 :title: take 

71 :tag: progfonc 

72 

73 .. runpython:: 

74 :showcode: 

75 

76 from sparkouille.fctmr import take 

77 res = take([4, 5, 6, 7, 8, 9], 2, 2) 

78 print(list(res)) 

79 """ 

80 took = 0 

81 for i, el in enumerate(gen): 

82 if i < skip: 

83 continue 

84 if took >= count: 

85 break 

86 yield el 

87 took += 1 

88 

89 

90def ffilter(fct, gen): 

91 """ 

92 Filters out elements from a generator. 

93 

94 @param fct function 

95 @param gen generator 

96 @return generator 

97 

98 .. exref:: 

99 :title: filter 

100 :tag: progfonc 

101 

102 .. runpython:: 

103 :showcode: 

104 

105 from sparkouille.fctmr import ffilter 

106 res = ffilter(lambda x: x % 2 == 0, [4, 5]) 

107 print(list(res)) 

108 """ 

109 return filter(fct, gen) 

110 

111 

112def reducer(fctkey, gen, asiter=True, sort=True): 

113 """ 

114 Implements a reducer. 

115 

116 @param fctkey function which returns the key 

117 @param gen generator 

118 @param asiter returns an iterator on each element of the group 

119 of the group itself 

120 @param sort sort elements by key before grouping 

121 @return generator 

122 

123 .. exref:: 

124 :title: reducer 

125 :tag: progfonc 

126 

127 .. runpython:: 

128 :showcode: 

129 

130 from sparkouille.fctmr import reducer 

131 res = reducer(lambda x: x[0], [ 

132 ('a', 1), ('b', 2), ('a', 3)], asiter=False) 

133 print(list(res)) 

134 """ 

135 if sort: 

136 new_gen = map(lambda x: x[1], sorted( 

137 map(lambda el: (fctkey(el), el), gen))) 

138 gr = groupby(new_gen, fctkey) 

139 else: 

140 gr = groupby(gen, fctkey) 

141 if asiter: 

142 # Cannot return gr. Python is confused when yield and return 

143 # are used in the same function. 

144 for _ in gr: 

145 yield _ 

146 else: 

147 for key, it in gr: 

148 yield key, list(it) 

149 

150 

151def combiner(fctkey1, gen1, fctkey2, gen2, how='inner'): 

152 """ 

153 Joins (or combines) two generators. 

154 The function is written based on two reducers. 

155 The function is more efficient if the groups 

156 of the second ensemble *gen2* are shorter 

157 as each of them will be held in memory. 

158 

159 @param fctkey1 function which returns the key for gen1 

160 @param gen1 generator for the first element 

161 @param fctkey2 function which returns the key for gen2 

162 @param gen2 generator for the second element 

163 @param how *inner*, *outer*, *left*, right* 

164 @return generator 

165 

166 .. exref:: 

167 :title: combiner or join 

168 :tag: progfonc 

169 

170 .. runpython:: 

171 :showcode: 

172 

173 from sparkouille.fctmr import combiner 

174 

175 def c0(el): 

176 return el[0] 

177 

178 ens1 = [('a', 1), ('b', 2), ('a', 3)] 

179 ens2 = [('a', 10), ('b', 20), ('a', 30)] 

180 res = combiner(c0, ens1, c0, ens2) 

181 print(list(res)) 

182 """ 

183 gr1 = reducer(fctkey1, gen1, asiter=True, sort=True) 

184 gr2 = reducer(fctkey2, gen2, asiter=False, sort=True) 

185 

186 def fetch_next(it): 

187 "local function" 

188 try: 

189 return next(it) 

190 except StopIteration: 

191 return None, None 

192 

193 k1, g1 = fetch_next(gr1) 

194 k2, g2 = fetch_next(gr2) 

195 while k1 is not None or k2 is not None: 

196 if k1 is None or (k2 is not None and k2 < k1): 

197 if how in ('outer', 'right'): 

198 for el in g2: 

199 yield None, el 

200 k2, g2 = fetch_next(gr2) 

201 else: 

202 break 

203 elif k2 is None or k1 < k2: 

204 if how in ('outer', 'left'): 

205 for el in g1: 

206 yield el, None 

207 k1, g1 = fetch_next(gr1) 

208 else: 

209 break 

210 elif k1 == k2: 

211 for el1 in g1: 

212 for el2 in g2: 

213 yield el1, el2 

214 k1, g1 = fetch_next(gr1) 

215 k2, g2 = fetch_next(gr2)