-- 60.7.17.34 [DateTime(2004-10-15T03:29:39Z)] TableOfContents
描述
<<Text processing in python>>开始部分函数编程里面几个 lambda，开始看起来有点晕呢！
自己写了几个，但是c++ stl里面的 not1,not2,bind1st,bind2nd自己写不出来,或者不方便.
会了哈. 不过看起来不如类和函数清晰，(这就是传说中的python sytle吧？)
这样调用
>>>fa = not1(bool) >>>fa(123) False >>>tmp =lambda x: a%10==3 >>>nottmp = not1(tmp) >>>nottmp(3) True >>> nottmp(4) False
因此把stl中的 function, algorithm, 使用python 类 写了一遍(有现成的模块?)
代码 script
miniutil.py
minifunction.py
1 import operator
2 import types
3 from miniutil import ifthenelse
4
5 class unary_function:
6 def __init__(self,arg,result):
7 if type(arg) is not types.TypeType:
8 self.argument_type=type(arg)
9 else:
10 self.argument_type=arg
11 if type(result) is not types.TypeType:
12 self.result_type=type(result)
13 else:
14 self.result_type=result
15
16 class binary_function:
17 def __init__(self,arg1,arg2,result):
18 if type(arg1) is not types.TypeType:
19 self.first_argument_type=type(arg1)
20 else:
21 self.first_argument_type=arg1
22 if type(arg2) is not types.TypeType:
23 self.second_argument_type=type(arg2)
24 else:
25 self.second_argument_type=arg2
26 if type(result) is not types.TypeType:
27 self.result_type=type(result)
28 else:
29 self.result_type = result
30
31 class plus(binary_function):
32 def __init__(self,Tp):
33 binary_function.__init__(self,Tp,Tp,Tp)
34 def __call__(self,a,b):
35 return a+b
36
37 class minus(binary_function):
38 def __init__(self,Tp):
39 binary_function.__init__(self,Tp,Tp,Tp)
40 def __call__(self,a,b):
41 return a-b
42
43 class multiplies(binary_function):
44 def __init__(self,Tp):
45 binary_function.__init__(self,Tp,Tp,Tp)
46 def __call__(self,a,b):
47 return a*b;
48
49
50 class divides(binary_function):
51 def __init__(self,Tp):
52 binary_function.__init__(self,Tp,Tp,Tp)
53 def __call__(self,a,b):
54 return a/b;
55
56 class floordivides(binary_function):
57 def __init__(self,Tp):
58 binary_function.__init__(self,Tp,Tp,Tp)
59 def __call__(self,a,b):
60 return a//b;
61
62
63 class modulus(binary_function):
64 def __init__(self,Tp):
65 binary_function.__init__(self,Tp,Tp,Tp)
66 def __call__(self,a,b):
67 return a%b;
68
69 class negate(unary_function):
70 def __init__(self,Tp):
71 unary_function.__init__(self,Tp,Tp)
72 def __call__(self, a): return -a
73
74
75 class equal_to(binary_function):
76 def __init__(self,Tp):
77 #binary_function.__init__(self,Tp,Tp,True)
78 pass
79 def __call__(self,a,b):
80 return a==b
81
82 class not_equal_to(binary_function):
83 def __init__(self,Tp):
84 #binary_function.__init__(self,Tp,Tp,True)
85 pass
86 def __call__(self,a,b):
87 return not a==b
88
89 class greater(binary_function):
90 def __init__(self,Tp):
91 #binary_function.__init__(self,Tp,Tp,True)
92 pass
93 def __call__(self,a,b):
94 return a>b
95
96 class less(binary_function):
97 def __init__(self,Tp):
98 #binary_function.__init__(self,Tp,Tp,True)
99 pass
100 def __call__(self,a,b):
101 return a<b
102
103 class greater_equal(binary_function):
104 def __init__(self,Tp):
105 #binary_function.__init__(self,Tp,Tp,True)
106 pass
107 def __call__(self,a,b):
108 return a>=b
109
110 class less_equal(binary_function):
111 def __init__(self,Tp):
112 #binary_function.__init__(self,Tp,Tp,True)
113 pass
114 def __call__(self,a,b):
115 return a<=b
116
117 class logical_or(binary_function):
118 def __init__(self,Tp):
119 #binary_function.__init__(self,Tp,Tp,True)
120 pass
121 def __call__(self,a,b):
122 return bool(a) or bool(b)
123
124 class logical_and(binary_function):
125 def __init__(self,Tp):
126 #binary_function.__init__(self,Tp,Tp,True)
127 pass
128 def __call__(self,a,b):
129 return bool(a) and bool(b)
130
131 class logical_not(unary_function):
132 def __init__(self,Tp):
133 #unary_function.__init__(self,Tp,True)
134 pass
135 def __call__(self,a):
136 return not bool(a)
137 class logical_xor(binary_function):
138 def __init__(self,Tp):
139 #binary_function.__init__(self,Tp,Tp,Tp)
140 pass
141 def __call__(self,a,b):
142 return (bool(a) and not bool(b)) or (bool(b) and not bool(a))
143
144 class unary_negate(unary_function):
145 def __init__(self,Tp):
146 #unary_function.__init__(self,Tp.argument_type,Tp.result_type)
147 self.pred = Tp
148 def __call__(self,a):
149 return not self.pred(a)
150
151 class binary_negate(binary_function):
152 def __init__(self,Tp):
153 #binary_function.__init__(self,Tp.first_argument_type,Tp.second_argument_type,Tp.result_type)
154 self.pred = Tp.__call__
155 def __call__(self,a,b):
156 return not self.pred(a,b)
157
158 def not1(unary_pred):
159 return unary_negate(unary_pred)
160
161 def not2(binary_pred):
162 return binary_negate(binary_pred)
163
164 class binder1st(unary_function):
165 def __init__(self,bop,bv):
166 self.bindvalue=bv
167 self.bindfunction=bop
168 def __call__(self,value):
169 return self.bindfunction(self.bindvalue,value)
170
171 def bind1st(_fn,_x):
172 return binder1st(_fn,_x)
173
174 class binder2nd(unary_function):
175 def __init__(self,bop,bv):
176 self.bindvalue=bv
177 self.bindfunction=bop
178 def __call__(self,value):
179 return self.bindfunction(value, self.bindvalue)
180
181 def bind2nd(_fn,_x):
182 return binder2nd(_fn,_x)
183
184 if __name__=="__main__":
185 print less(int)(4,5)
186 print bind2nd(less(int),5)(4)==True
187 print bind2nd(less(int),5)(6)==False
188 print "ok"
minialgo.py
1 """py implementation of part of c++ stl algorithm"""
2
3 from miniutil import ifthenelse
4 import copy
5
6
7 __about__=r"""py implementation of part of c++ stl"""
8 __all__=["max","min","set_union","etc"]
9 version_info = "0.1.1"
10 author="v_gyc"
11
12
13 def max(a,b):
14 return ifthenelse(a>=b,a,b)
15
16
17 def min(a,b):
18 return ifthenelse(a<=b,a,b)
19
20
21 def median(a,b,c):
22 if a <b and a <c:
23 return min(b,c)
24 if a>b and a>c :
25 return max(b,c)
26 return a
27
28 def find(lst,value):
29 index = 0
30 for x in lst:
31 if x==value :
32 return index
33 index +=1
34 return -1
35
36 def find_if(lst,pred):
37 index = 0
38 for x in lst:
39 if pred(lst[index]):
40 return index
41 index +=1
42 return -1
43
44
45 def adjacent_find(lst):
46 lstb=lst[1:]
47 for i in range(len(lst)-2):
48 if(lst[i]==lstb[i]):
49 return i
50 return -1
51
52 def adjacent_find_if(lst,pred):
53 lstb=lst[1:]
54 for i in range(len(lst)-2):
55 if pred(lst[i],lstb[i]):
56 return i
57 return -1
58
59 def count(lst,value):
60 return lst.count(value)
61
62 def count_if(lst,pred):
63 result =0
64 for x in lst:
65 if pred(x):
66 result += 1
67 return result
68
69 def search(lst1,lst2):
70 len1 = len(lst1)
71 len2 = len(lst2)
72 if len1<len2:
73 return -1
74 if len1==0:
75 return -1
76 if len2==0:
77 return 0
78 if len2 == 1:
79 return find(lst1,lst2[0])
80
81 i1=i2=0
82 partial = False
83
84 while(i1<len1 and i2<len2):
85 if lst1[i1]!=lst2[i2]:
86 if not partial:
87 i1+=1
88 else:
89 partial=False
90 i1 -=(i2-1)
91 i2=0
92 else:
93 partial = True
94 i1+=1
95 i2+=1
96
97 if(i2==len2):
98 return i1-len2
99 else:
100 return -1;
101
102 def search_if(lst1,lst2,pred):
103 len1 = len(lst1)
104 len2 = len(lst2)
105 if len1<len2:
106 return -1
107 if len1==0:
108 return -1
109 if len2==0:
110 return 0
111 if len2 == 1:
112 return find(lst1,lst2[0])
113
114 i1=i2=0
115 partial = False
116
117 while(i1<len1 and i2<len2):
118 if not pred(lst1[i1], lst2[i2]):
119 if not partial:
120 i1+=1
121 else:
122 partial=False
123 i1 -=(i2-1)
124 i2=0
125 else:
126 partial = True
127 i1+=1
128 i2+=1
129
130 if(i2==len2):
131 return i1-len2
132 else:
133 return -1;
134
135 def transfrom(lst,uop):
136 '''tranform =lambda uop,lst=[] : map(uop,lst)'''
137 return map(uop,lst)
138
139 def transfrom2(lst1,lst2,bop):
140 '''tranform2 =lambda uop,lst1=[],lst2=[] : map(bop,lst1,lst2)'''
141 return map(bop,lst1,lst2)
142
143 def replace(lst,old,new):
144 index = 0
145 for x in lst:
146 if x==old:
147 lst[index]=new
148 index += 1
149 #return lst
150
151 def replace_if(lst,pred,new):
152 index = 0
153 for x in lst:
154 if pred(x):
155 lst[index]=new
156 index += 1
157 #return lst
158
159 def replace_copy(lst,old,new):
160 result = copy.deepcopy(lst)
161 replace(result,old,new)
162 return result
163
164 def replace_copy_if(lst,pred,new):
165 result = copy.deepcopy(lst)
166 replace_if(result,pred,new)
167 return result
168
169 def generate(lst,generator):
170 index=0
171 for x in lst:
172 lst[index]=g().next()
173 index += 1
174
175 #return lst
176
177 def generate_n(lst,n,generator):
178 index=0
179 for x in lst:
180 lst[index]=g().next()
181 index += 1
182 if(index>=n):
183 break
184 #return lst
185
186 def remove(lst,value):
187 lst.remove(value)
188 #return lst
189
190 def remove_if(lst,pred):
191 """"""
192 result = []
193 for x in lst:
194 if pred(x):
195 pass
196 else:
197 result.append(x)
198 lst = result[:]
199 return lst
200
201 def remove_copy(lst,value):
202 result = lst[:]
203 result.remove(value)
204 return result
205
206 def remove_copy_if(lst,pred):
207 result = lst[:]
208 remove_if(result,pred)
209 return result
210
211 def unique(lst):
212 """Remove consecutive duplicate values from a sequence"""
213 while(True):
214 index = adjacent_find(lst)
215 if index==-1:
216 break
217 del lst[index]
218 #return lst
219
220 def unique_if(lst,pred):
221 """Remove consecutive predicating duplicate values from a sequence"""
222 while(True):
223 index = adjacent_find_if(lst,pred)
224 if index ==-1:
225 break
226 del lst[index]
227 #return lst
228
229 def reverse_copy(lst):
230 """given the reverse of the original list"""
231 result = lst[:]
232 result.reverse()
233 return result
234
235 def rotate(lst,middle):
236 """ Rotates the elements of the list by @p (middle-first)
237 positions so that the element at @p middle is moved to @p first, the
238 element at @p middle+1 is moved to @first+1 and so on for each element
239 in the range @p [first,last). """
240
241 front = lst[:middle]
242 back = lst[middle:]
243 front.reverse()
244 back.reverse()
245 lst=[]
246 lst.extend(back)
247 lst.extend(front)
248 #return lst
249
250 def rotate_copy(lst,middle):
251 front = lst[:middle]
252 back = lst[middle:]
253 front.reverse()
254 back.reverse()
255 result=[]
256 result.extend(back)
257 result.extend(front)
258 return result
259
260 def random_shuffle(lst):
261 import random
262 random.shuffle(lst)
263 #return lst
264
265
266 def partition(lst,value):
267 '''Move elements and return an index @pindex
268 so that each elements in [:pindex] is less than value
269 and elemnet in [pindex:] is no less than value '''
270
271 length=len(lst)
272
273 index=0
274 backindex=length
275
276 while(True):
277 while(True):
278 if(index==backindex):
279 return index
280 elif lst[index]<value :
281 index += 1
282 else:
283 break
284 backindex -= 1
285 while(True):
286 if index==backindex :
287 return index
288 elif not lst[backindex]<value:
289 backindex -= 1
290 else:
291 break
292 t=lst[index]
293 lst[index]=lst[backindex]
294 lst[backindex]=t
295 index += 1
296
297 def partition_if(lst,pred):
298
299 '''Move elements and return an index @pindex
300 so that pred(el) for elements el in [:pindex] is true
301 and pred(el) for elemnet in [pindex:] if false '''
302
303 length=len(lst)
304
305 index=0
306 backindex=length
307
308 while(True):
309 while(True):
310 if(index==backindex):
311 return index
312 elif pred(lst[index]) :
313 index += 1
314 else:
315 break
316 backindex -= 1
317 while(True):
318 if index==backindex :
319 return index
320 elif not pred(lst[backindex]):
321 backindex -= 1
322 else:
323 break
324 t=lst[index]
325 lst[index]=lst[backindex]
326 lst[backindex]=t
327 index += 1
328
329 def partition_copy(lst,value):
330 result = lst[:]
331 partition(result,value)
332 return result
333
334 def partion_copy_if(lst,pred):
335 result = lst[:]
336 partition_if(result,pred)
337 return result
338
339 sort_threshold = 16
340
341
342 def replace_list(lst1,lst2,index=0):
343 ''' replace the contents of lst1 from index to index+length with lst2,
344 return the result list '''
345
346 len1 = len(lst1)
347 length = len(lst2)
348 if length<=0: return
349
350 for x in range(length):
351 try:
352 lst1[index+x] = lst2[x]
353 except IndexError:
354 lst1.append(lst2[x])
355
356
357
358 def replace_list_copy(lst1,lst2,index):
359 tmp = lst1[:]
360 replace_list(tmp,lst2,index)
361 return tmp
362
363
364
365
366
367 def bisect_left_if(slt,value,cmp) :
368 """return the index @pindex for which the element at pindex
369 is greater than value and when insert value before pindex
370 the sorted nature of the list will be hold"""
371
372 # bisect_left is in module bisect,
373 #but waht is the list is sorted by other comaparing functions,
374 #e.g, list.sort(cot2(cmp))
375 # this function is for that.
376
377 it = 0
378 ti = len(slt)-1
379
380 if(value<slt[0]): return 0
381 if(value>slt[-1]): return len(slt)
382
383 middle_if = (it+ti)/2
384
385 while(it<middle_if):
386 test = cmp(slt[middle_if],value)
387 if test>0:
388 ti = middle_if
389 middle_if = (it + ti)//2
390 elif test == 0:
391 return middle_if
392 else:
393 it = middle_if
394 middle_if = (it+ti)//2
395
396 return it-cmp(slt[it],value)
397
398 def partial_sort(lst,middle):
399 '''@TODO implement:
400 Sorts the smallest middle elements in the range [:] and
401 moves them to the range [:middle]. The order of the remaining elements
402 in the range @p [middle:] is undefined. implementation eh?'''
403
404 from bisect import bisect_left
405 if middle <=0 : return lst
406 front = lst[:middle]
407 back = lst[middle:]
408 ext=[]
409 front.sort()
410 for x in back:
411 index = bisect_left(front,x)
412 if (index<middle):
413 front.insert(index,x)
414 ext.append(front.pop())
415 else:
416 ext.append(x)
417
418 replace_list(lst,front)
419 replace_list(lst,ext,len(front))
420 #return lst
421
422
423 def partial_sort_if(lst,middle,cmpfunc):
424 ''''''
425 if middle <=0 : return lst
426 front = lst[:middle]
427 back = lst[middle:]
428 ext=[]
429 front.sort(cmpfunc)
430 for x in back:
431 index = bisect_left_if(front,x,cmpfunc)
432 if index<middle :
433 front.insert(index,x)
434 ext.append(front.pop())
435 else:
436 ext.append(x)
437 replace_list(lst,front)
438 replace_list(lst,ext,len(front))
439
440 #return lst
441
442 def nth_element(lst,nth):
443
444 """ Rearranges the elements in the lst so that the nth element
445 * is the same element that would have been in that position had the
446 * whole sequence been sorted. The elements on either side of @p nth are
447 * not completely sorted, but for any element @i in the range
448 * [first,nth) and any element j in the range [nth,last) it
449 * holds that j<i is false. """
450 """@TODO implement"""
451
452 index = 0
453 length = len(lst)
454
455 #if nth is outofindex
456 if nth >= length or nth<0 :
457 return
458
459 #empty lst or has only one element
460 if length == 1 or length ==0: return
461
462 # use a random value to partition
463 middle = (index + length)//2
464 value = lst[middle]
465 pindex = partition(lst,value)
466
467 #may be implemented incursively
468 if pindex>nth:
469 partial_sort(lst,pindex)
470 return
471 if pindex <= nth:
472 tmp=lst[pindex:]
473 tmp.sort()
474 for x in tmp:
475 lst[pindex]=x
476 pindex +=1
477 return
478 #return
479
480 def binary_search(sortedlist,value):
481 if (value < sortedlist[0])or (sortedlist[-1]<value):
482 return False
483 if(sortedlist[-1]==value)or(sortedlist[0]==value):
484 return True
485
486 index=0
487 backindex = len(sortedlist)-1
488 middle = backindex//2
489
490 if middle == index:
491 return False
492 else:
493 return binary_search(sortedlist[:middle],value) or binary_search(sortedlist[middle:],value)
494
495 def merge(sortedlist1,sortedlist2):
496 result = []
497 len1 = len(sortedlist1)
498 len2 = len(sortedlist2)
499 i=j=0
500 while(i<len1 and j<len2):
501 first = sortedlist1[i]
502 second = sortedlist2[j]
503
504 result.append(min(first,second))
505
506 if first < second: i += 1
507 elif first == second:
508 result.append(first)
509 i += 1
510 j += 1
511 else: j += 1
512
513 result.extend(sortedlist1[i:])
514 result.extend(sortedlist2[j:])
515 return result
516
517 def merge_if(sortedlist1,sortedlist2,cmpfunc=cmp):
518 result = []
519 len1 = len(sortedlist1)
520 len2 = len(sortedlist2)
521 i=j=0
522 while(i<len1 and j<len2):
523 first = sortedlist1[i]
524 second = sortedlist2[j]
525
526 cmpresult = cmpfunc(first,second)
527
528 if cmpresult <0:
529 result.append(first)
530 i += 1
531 elif cmpresult==0:
532 result.append(first)
533 result.append(second)
534 i += 1
535 j += 1
536 else:
537 result.append(second)
538 j += 1
539
540 result.extend(sortedlist1[i:])
541 result.extend(sortedlist2[j:])
542 return result
543
544 def _appendIfNotExists(sortedlist,value):
545 """for sorted list"""
546
547 if(sortedlist == []):
548 sortedlist.append(value)
549 return
550
551 if sortedlist[-1]!=value:
552 sortedlist.append(value)
553
554 def _extendIfNotExists(sortedlist,sortedlist2):
555 """for sorted list"""
556
557 if sortedlist == [] or sortedlist2==[]:
558 sortedlist.extend(sortedlist2)
559 else:
560 index =0
561 while(sortedlist[-1]==sortedlist2[index]):
562 index += 1
563 sortedlist.extend(sortedlist2[index:])
564
565 def set_union(sortedlist1,sortedlist2):
566 result = []
567 len1 = len(sortedlist1)
568 len2 = len(sortedlist2)
569 i=j=0
570 while(i<len1 and j<len2):
571 first = sortedlist1[i]
572 second = sortedlist2[j]
573
574 _appendIfNotExists(result,(min(first,second)))
575
576 if first < second:
577 i += 1
578 elif first == second:
579 i += 1
580 j += 1
581 else:
582 j += 1
583 _extendIfNotExists(result,sortedlist1[i:])
584 _extendIfNotExists(result,sortedlist2[j:])
585 return result
586
587
588 def set_intersection(sortedlist1,sortedlist2):
589 result = []
590 len1 = len(sortedlist1)
591 len2 = len(sortedlist2)
592 i=j=0
593
594 while(i<len1 and j<len2):
595 first = sortedlist1[i]
596 second = sortedlist2[j]
597
598 if first < second:
599 i += 1
600 elif first == second:
601 _appendIfNotExists(result,first)
602 i += 1
603 j += 1
604 else:
605 j += 1
606 return result
607
608
609 def set_difference(lst1,lst2):
610 result = []
611 len1 = len(lst1)
612 len2 = len(lst2)
613 i=j=0
614
615 while(i<len1 and j<len2):
616 first = sortedlist1[i]
617 second = sortedlist2[j]
618
619 if first < second:
620 _appendIfNotExists(result,first)
621 i += 1
622 elif first == second:
623 i += 1
624 j += 1
625 else:
626 _appendIfNotExists(result,first)
627 j += 1
628
629 _extendIfNotExists(result,sortedlist1[i:])
630 return result
631
632 def set_symmetric_difference(lst1,lst2):
633 result = []
634 len1 = len(lst1)
635 len2 = len(lst2)
636 i=j=0
637
638 while(i<len1 and j<len2):
639 first = sortedlist1[i]
640 second = sortedlist2[j]
641
642 if first < second:
643 _appendIfNotExists(result,first)
644 _appendIfNotExists(result,second)
645 i += 1
646 elif first == second:
647 i += 1
648 j += 1
649 else:
650 _appendIfNotExists(result,first)
651 _appendIfNotExists(result,second)
652 j += 1
653 _extendIfNotExists(result,sortedlist1[i:])
654 _extendIfNotExists(result,sortedlist2[j:])
655 return result
656
657 def max_element(lst):
658 """return the index of the max element"""
659 vlen = len(lst)
660 if vlen ==0: return -1
661 if vlen ==1: return 0
662
663 tmp=lst[0]
664 result=index=0
665
666 for x in lst:
667 if x >= tmp:
668 tmp == x
669 result = index
670 index += 1
671 return result
672
673
674 """contents below are from <Text processing in python> """
675 apply_each = lambda fns, args=[] : map(apply, fns, [args]*len(fns))
676 bools = lambda lst: map(truth, lst)
677 bool_each = lambda fns, args=[] : bools(apply_each(fns, args))
678 conjoin = lambda fns, args=[] : reduce(mul, bool_each(fns, args))
679 all = lambda fns: lambda arg, fns=fns : conjoin(fns, (arg,))
680 both = lambda f,g: all((f,g))
681 all3 = lambda f,g,h: all((f,g,h))
682 and_ = lambda f,g: lambda x, f=f, g=g: f(x) and g(x)
683 disjoin = lambda fns, args=[]: reduce(add, bool_each(fns, args))
684 some = lambda fns: lambda arg, fns=fns: disjoin(fns, (arg,))
685 either = lambda f,g: some((f,g))
686 anyof3 = lambda f,g,h: some((f,g,h))
687 compose = lambda f,g: lambda x, f=f, g=g: f(g(x))
688 compose3 = lambda f,g,h: lambda x, f=f, g=g, h=h: f(g(h(x)))
689 ident = lambda x: x
测试 unittest
minitest.py
1 import miniutil
2 import minifunction
3 import minialgo
4 import unittest
5 import types
6
7
8 class testMini(unittest.TestCase):
9 def setUp(self):
10 self.listSimple = [1,2,3,4,5]
11 self.listMod = [3,6,9,2,4,8,1,4,7]
12 self.listEmpty=[]
13 self.listOne=[1]
14
15 def testMinifunction(self):
16 eq = self.assertEqual
17
18 up = minifunction.unary_function("123",False)
19 self.assertEqual(up.argument_type,types.StringType)
20 self.assertEqual(up.result_type,type(True))
21
22 bp=minifunction.binary_function(1,"234",2.34)
23 self.assertEqual(bp.first_argument_type, type(23))
24 self.assertEqual(bp.second_argument_type,type("hahaha"))
25 self.assertEqual(bp.result_type,type(3.45))
26
27 """test minifunction.less"""
28 self.assertEqual(minifunction.less(int)(4,5),True)
29 self.assertEqual(minifunction.less("a")("a","b"),True)
30 self.assertEqual(minifunction.less([])([2],[4]),True)
31 self.assertEqual(minifunction.less([])([4,5],[4,5,6]),True)
32 self.assertEqual(minifunction.less(())((5),(6)),True)
33 self.assertEqual(minifunction.less(())((4,5),(4,5,6)),True)
34
35
36 """test minifunction.greater"""
37 self.assertEqual(minifunction.greater(int)(4,5),False)
38 self.assertEqual(minifunction.greater("a")("a","b"),False)
39 self.assertEqual(minifunction.greater([])([2],[4]),False)
40 self.assertEqual(minifunction.greater([])([4,5],[4,5,6]),False)
41 self.assertEqual(minifunction.greater(())((5),(6)),False)
42 self.assertEqual(minifunction.greater(())((4,5),(4,5,6)),False)
43
44 '''test minifunction.plus, minus,divides,multiplies'''
45 mnf = minifunction
46 self.assertEqual(mnf.plus(int)(4,5),9)
47 self.assertEqual(mnf.plus(types.StringType)("a","b"),"ab")
48 self.assertEqual(mnf.plus([])([],[]),[])
49 self.assertEqual(mnf.plus([])([1],[2]),[1,2])
50 self.assertEqual(mnf.plus(())((),()),())
51 self.assertEqual(mnf.plus(())((1,2),(3,4)),(1,2,3,4))
52 self.assertEqual(mnf.plus(())((1,2),(2,4)),(1,2,2,4))
53
54
55 self.assertEqual(mnf.minus(int)(4,5),-1)
56 self.assertEqual(mnf.minus(int)(4.4,5.5),4.4-5.5)
57
58 self.assertEqual(mnf.multiplies(5)(5,6),30)
59 self.assertEqual(mnf.multiplies("a")("",4),"")
60 self.assertEqual(mnf.multiplies("a")(" ",4)," ")
61 self.assertEqual(mnf.multiplies("a")("a",4),"aaaa")
62 self.assertEqual(mnf.multiplies("a")("ab",4),"abababab")
63
64 self.assertEqual(mnf.multiplies(5)([],4),[])
65 self.assertEqual(mnf.multiplies(5)([1],4),[1,1,1,1])
66
67 '''test minifunction logial operations'''
68 self.assertEqual(mnf.logical_and(None)(1>2,2>1),False)
69 self.assertEqual(mnf.logical_or(None)(1>2,2>1),True)
70 self.assertEqual(mnf.logical_or(None)(1>2,2>3),False)
71 self.assertEqual(mnf.logical_xor(None)(1>2,2>1),True)
72 self.assertEqual(mnf.logical_xor(None)(1>2,1>2),False)
73 self.assertEqual(mnf.logical_xor(None)([],"a"),True)
74 self.assertEqual(mnf.logical_xor(None)([],""),False)
75
76 '''test minifunction binder1st ,binder2nd, bind1st, bind2nd,not1,not2'''
77 self.assertEqual(mnf.bind1st(mnf.less(int),10)(9),False)
78 self.assertEqual(mnf.bind1st(mnf.less(int),10)(11),True)
79 self.assertEqual(mnf.bind2nd(mnf.less(int),10)(9),True)
80 self.assertEqual(mnf.bind2nd(mnf.less(int),10)(11),False)
81
82 self.assertEqual(mnf.bind1st(mnf.plus(int),10)(11),21)
83 self.assertEqual(mnf.bind1st(mnf.plus(None),"a")("b"),"ab")
84 self.assertEqual(mnf.bind2nd(mnf.plus(int),"")(""),"")
85 self.assertEqual(mnf.bind2nd(mnf.plus(int),"a")("b"),"ba")
86 self.assertEqual(mnf.bind2nd(mnf.plus(int),"a")(""),"a")
87
88
89 self.assertEqual(mnf.not1(mnf.logical_not(None))(True),True)
90 self.assertEqual(mnf.not1(mnf.logical_not(None))(False),False)
91 self.assertEqual(mnf.not1(mnf.not1(mnf.logical_not(None)))(False),True)
92
93 self.assertEqual(mnf.not2(mnf.logical_and(None))(1,2),False)
94 self.assertEqual(mnf.not2(mnf.logical_and(None))(0,"a"),True)
95 self.assertEqual(mnf.not2(mnf.logical_or(None))(1,0),False)
96 self.assertEqual(mnf.not2(mnf.logical_or(None))(0,""),True)
97
98 def testMaxMinMedian(self):
99 alg = minialgo
100 self.assertEqual(minialgo.max(4,5),5)
101 self.assertEqual(alg.max("a","b"),"b")
102 self.assertEqual(alg.max([],[]),[])
103 self.assertEqual(alg.max([],[1]),[1])
104 self.assertEqual(alg.max([1,2],[1]),[1,2])
105 self.assertEqual(alg.max([1,2],[1,2,3]),[1,2,3])
106 self.assertEqual(alg.max([2,3],[2,4]),[2,4])
107 self.assertEqual(alg.max([2,3,2],[2,4]),[2,4])
108
109 self.assertEqual(alg.max((),()),())
110
111 #odd
112 self.assertEqual(alg.max((),(1)),())
113 self.assertEqual(alg.max((),(1,2)),(1,2))
114 self.assertEqual(alg.max((),([1])),())
115 self.assertEqual(alg.max((),([1,2])),())
116 self.assertEqual(alg.max((),([1,2,3])),())
117 self.assertEqual(alg.max((1,2),(1,3)),(1,3))
118 self.assertEqual(alg.max((4,5,6,7),(3,4,5,5,8)),(4,5,6,7))
119 self.assertEqual(alg.max((-2,3),([1])),(-2,3))
120
121
122 def testFindandFind_if(self):
123
124 alg = minialgo
125 lst = self.listMod
126 """self.listMod = [3,6,9,2,4,8,1,4,7]"""
127 self.assertEqual(alg.find(lst,6),1)
128 self.assertEqual(alg.find(lst,3),0)
129 self.assertEqual(alg.find(lst,4),4)
130
131
132 def predodd(a):
133 if a%2==0 and a%3==0:
134 return True
135 else:
136 return False
137
138 '''index of 6 which is a common multiplier? of 2 and 3'''
139 self.assertEqual(alg.find_if(lst,predodd),1)
140
141 '''contents below is only to show the usage of bind2nd and bind1st'''
142
143 class findpred(minifunction.binary_function):
144 def __init__(self,tp,modr):
145 minifunction.binary_function.__init__(self,tp,tp,tp)
146 self.mod_result=modr
147 def __call__(self,a,b):
148 """@TODO doc """
149 if (a%b) == self.mod_result:
150 return True
151 else:
152 return False
153
154 """index of element 9"""
155 pred = minifunction.bind2nd(findpred(int,9),10)
156
157 self.assertEqual(alg.find_if(lst,pred), 2)
158 """index of element 8 """
159 pred = minifunction.bind2nd(findpred(int,8),10)
160 self.assertEqual(alg.find_if(lst,pred), 5)
161
162 """index of 7 using bind1st"""
163 pred = minifunction.bind1st(findpred(int,3),10)
164 self.assertEqual(alg.find_if(lst,pred), 8)
165
166 def testAdjacent_find(self):
167 lst = [2,3,4,5,5,7,6,6]
168 alg = minialgo
169 self.assertEqual(alg.adjacent_find(lst),3)
170 lst.reverse()
171 self.assertEqual(alg.adjacent_find(lst),0)
172
173 def testCount_if(self):
174 lst = [2,3,13,33,34,46,1003,2,1004,2005,2007]
175 pred = lambda a: miniutil.ifthenelse(a%10==3,True,False)
176 self.assertEqual(minialgo.count_if(lst,pred),4)
177
178 pred = lambda a: miniutil.ifthenelse(a%10==3 or a>2000,True,False)
179 self.assertEqual(minialgo.count_if(lst,pred),6)
180
181 def testSearch(self):
182 alg = minialgo
183 mnf = minifunction
184
185 self.assertEqual(alg.search(self.listEmpty,self.listMod),-1)
186 self.assertEqual(alg.search(self.listMod,self.listEmpty),0)
187
188 self.assertEqual(alg.search(self.listMod,self.listOne),6)
189
190 lst = [2,3,4]
191 llst = [4,5,6,2,3,2,3,4,2,3,4,5,]
192 self.assertEqual(alg.search(llst,lst),5)
193 self.assertEqual(alg.search(llst[5:],lst),0)
194 self.assertEqual(alg.search(llst[6:],lst),2)
195 self.assertEqual(alg.search([2,3,4],lst),0)
196 self.assertEqual(alg.search([1,2,3,4],lst),1)
197
198
199 def testSearch_if(self) :
200 """@TODO implement"""
201 pass
202
203 def testTransform(self):
204 lst = range(5) #[0,1,2,3,4]
205 trans = lambda a : -a
206 lst = minialgo.transfrom(lst,trans) #[0,-1,-2,-3,-4]
207 self.assertEqual(lst, range(0,-5,-1))
208
209 lst = minialgo.transfrom(lst,trans) #back
210 self.assertEqual(lst,range(5))
211
212 def testTransform2(self):
213 lst = range(5)
214 tsl = range(0,-5,-1) #[0,-1,-2,-3,-4]
215 bop = lambda a,b : a+b
216
217 tmp = minialgo.transfrom2(lst, tsl, bop)
218 self.assertEqual(tmp,[0]*5)
219
220 def testReplace(self):
221 alg = minialgo
222
223 lst = range(5) #0 1 2 3 4
224 alg.replace(lst, 4,99)
225 self.assertEqual(alg.find(lst,4),-1)
226 self.assertEqual(alg.find(lst,99),4)
227
228 def testReplace_if(self):
229 alg = minialgo
230 lst = range(5)
231 from miniutil import ifthenelse
232 pred = lambda x: ifthenelse(x%4==0,True,False)
233 alg.replace_if(lst,pred,8)
234 self.assertEqual(lst[4],8)
235
236 alg.replace_if(lst,pred,"aa")
237 self.assertEqual(lst[4],"aa")
238
239 def testPartition(self):
240 alg = minialgo
241
242 lst = self.listEmpty
243 self.assertEqual(alg.partition(lst,-1),0)
244 self.assertEqual(alg.partition(lst,4),0)
245 self.assertEqual(alg.partition(lst,5),0)
246
247 lst = self.listOne
248 self.assertEqual(alg.partition(lst,-1),0)
249 self.assertEqual(alg.partition(lst,1),0)
250 self.assertEqual(alg.partition(lst,2),1)
251
252 tmp = [5,4,3,2,1]
253 lst = tmp[:]
254 self.assertEqual(alg.partition(lst,-99),0)
255 #print -99 ,lst
256 lst = tmp[:]
257 self.assertEqual(alg.partition(lst,-1),0)
258 #print -1,lst
259 lst = tmp[:]
260 self.assertEqual(alg.partition(lst,1),0)
261 #print 1,lst
262 lst = tmp[:]
263 self.assertEqual(alg.partition(lst,2),1)
264 #print 2,lst
265 lst = tmp[:]
266 self.assertEqual(alg.partition(lst,3),2)
267 #print 3, lst
268 lst = tmp[:]
269 self.assertEqual(alg.partition(lst,4),3)
270 #print 4, lst
271 lst = tmp[:]
272 self.assertEqual(alg.partition(lst,5),4)
273 #print 5, lst
274 lst = tmp[:]
275 self.assertEqual(alg.partition(lst,6),5)
276 #print 6,lst
277 lst = tmp[:]
278 self.assertEqual(alg.partition(lst,999),5)
279 #print 999, lst
280
281 def testReplaceList(self) :
282 alg = minialgo
283 lst1 = [1,2,3,4,5]
284 lst2 = [5,4,3,2,1]
285
286 tmp=lst1[:]
287 alg.replace_list(tmp,lst2,0)
288 self.assertEqual(tmp,[5,4,3,2,1])
289
290 tmp=lst1[:]
291 alg.replace_list(tmp,lst2,5)
292 self.assertEqual(tmp,[1,2,3,4,5, 5,4,3,2,1])
293
294 tmp=lst1[:]
295 alg.replace_list(tmp,lst2,2)
296 self.assertEqual(tmp,[1,2, 5,4,3,2,1])
297
298 def testPartialsort(self):
299 lst = [9,6,3,8,5,2,7,4,1]
300 alg = minialgo
301
302
303 tmp=lst[:]
304 alg.partial_sort(tmp,-3)
305 self.assertEqual(tmp,lst)
306
307 tmp=lst[:]
308 alg.partial_sort(tmp,0)
309 self.assertEqual(tmp,lst)
310
311 tmp=lst[:]
312 alg.partial_sort(tmp,1)
313 self.assertEqual(tmp[0],1)
314
315 tmp=lst[:]
316 alg.partial_sort(tmp,2)
317 self.assertEqual(tmp[0],1)
318 self.assertEqual(tmp[1],2)
319
320 tmp=lst[:]
321 alg.partial_sort(tmp,5)
322 self.assertEqual(tmp[0],1)
323 self.assertEqual(tmp[4],5)
324
325 tmp=lst[:]
326 alg.partial_sort(tmp,8)
327 self.assertEqual(tmp,range(1,10))
328
329
330 tmp=lst[:]
331 alg.partial_sort(tmp,222)
332 self.assertEqual(tmp,range(1,10))
333
334
335 lst= "gdahebifc"
336 tmp=list(lst)[:]
337 alg.partial_sort(tmp,0)
338 self.assertEqual("".join(tmp),lst)
339
340 tmp=list(lst)[:]
341 alg.partial_sort(tmp,1)
342 self.assertEqual("".join(tmp)[0],"a")
343
344 tmp=list(lst)[:]
345 alg.partial_sort(tmp,4)
346 self.assertEqual("".join(tmp)[0],"a")
347 self.assertEqual("".join(tmp)[1],"b")
348 self.assertEqual("".join(tmp)[2],"c")
349 self.assertEqual("".join(tmp)[3],"d")
350
351 tmp=list(lst)[:]
352 alg.partial_sort(tmp,22)
353 self.assertEqual("".join(tmp),"abcdefghi")
354
355 def testBisect_Left_if(self):
356 from bisect import bisect_left
357 lst = self.listSimple
358 for i in range(-len(lst),len(lst)):
359 ifindex = minialgo.bisect_left_if(lst,i,cmp)
360 index = bisect_left(lst,i)
361 self.assertEqual(ifindex,index )
362
363 def testNth_element(self):
364 lst = [3,6,9,2,1,4,8,5,7,0]
365 for i in range(10):
366 tmp=lst[:]
367 minialgo.random_shuffle(tmp)
368 #print "original ",tmp
369 minialgo.nth_element(tmp,i)
370 #print "index",i,":", tmp
371 self.assertEqual(tmp[i],i)
372
373 lst = "abcdefghij"
374 for i in range(10):
375 tmp=list(lst)[:]
376 minialgo.random_shuffle(tmp)
377 #print "original ","".join(tmp)
378 minialgo.nth_element(tmp,i)
379 #print "index",i,":", "".join(tmp)
380 self.assertEqual(tmp[i],chr(ord("a")+i))
381
382 lst = ['m','a','x','p']
383
384 tmp=lst[:]
385 minialgo.random_shuffle(lst)
386 minialgo.nth_element(tmp,0)
387 self.assertEqual(tmp[0],'a')
388 #print tmp
389
390 tmp=lst[:]
391 minialgo.random_shuffle(lst)
392 minialgo.nth_element(tmp,1)
393 self.assertEqual(tmp[0],'a')
394 self.assertEqual(tmp[1],'m')
395 #print tmp
396
397 tmp=lst[:]
398 minialgo.random_shuffle(lst)
399 minialgo.nth_element(tmp,2)
400 self.assertEqual(tmp[2],'p')
401 #print tmp
402
403 tmp=lst[:]
404 minialgo.random_shuffle(lst)
405 minialgo.nth_element(tmp,3)
406 self.assertEqual(tmp[3],'x')
407 #print tmp
408
409 def testBinary_Search(self):
410 lst=[1,3,5,7,9]
411
412 for i in range(-10,20):
413 if i%2 ==0 or i<1 or i>9:
414 self.assertEqual(minialgo.binary_search(lst,i),False)
415 else:
416 self.assertEqual(minialgo.binary_search(lst,i),True)
417
418 def testMerge(self):
419 alg = minialgo
420
421 lst1=lst2=[]
422
423 result = alg.merge(lst1,lst2)
424 self.assertEqual(result,[])
425
426 lst1=[]
427 lst2=[1]
428 result = alg.merge(lst1,lst2)
429 self.assertEqual(result,[1])
430
431 lst1=[]
432 lst2=[1,2]
433 result = alg.merge(lst1,lst2)
434 self.assertEqual(result,[1,2])
435
436 lst1=[1,2]
437 lst2=[1,2]
438 result = alg.merge(lst1,lst2)
439 self.assertEqual(result,[1,1,2,2])
440
441 lst1=[1,2,3]
442 lst2=[2,4,6]
443 result = alg.merge(lst1,lst2)
444 self.assertEqual(result,[1,2,2,3,4,6])
445
446
447
448 def testSet_Union(self):
449 alg = minialgo
450
451 lst1=lst2=[]
452
453 result = alg.set_union(lst1,lst2)
454
455 self.assertEqual(result,[])
456
457 lst1=[]
458 lst2=[1]
459 result = alg.set_union(lst1,lst2)
460 self.assertEqual(result,[1])
461
462 lst1=[]
463 lst2=[1,2]
464 result = alg.set_union(lst1,lst2)
465 self.assertEqual(result,[1,2])
466
467 lst1=[1,2]
468 lst2=[1,2]
469 result = alg.set_union(lst1,lst2)
470 self.assertEqual(result,[1,2])
471
472 lst1=[1,2,3]
473 lst2=[2,4,6]
474 result = alg.set_union(lst1,lst2)
475 self.assertEqual(result,[1,2,3,4,6])
476
477 def testdir(self):
478 print dir(minialgo)
479
480
481 if __name__ == '__main__':
482 unittest.main()
讨论 Discussion
一开始写了很多, 不知道有 _ _call _ _，以为没有重载的operator ()运算符， 而是用了一个函数 function
def function(args):
pass呵呵,还好,改动起来比较方便! 不然,基础知识不熟练的cost也太大了.
python的堆模块heapq, 仅仅提供了默认语义. list.sort(cmp),可以提供一个cmp函数,但是在heapq(其他模块中)并没有提供对应的处理函数. 如果想更generic,可能有两种方法(未实现):
1 封装对象,提供 < 操作符号 2 写一个通用的 heap实现,处理提供的compare function参数
嘿嘿,数据结构不精通, 即使看了c++ stl 的排序代码, 用Python实现起来也蛮困难的 