##language:zh


-- 60.7.17.34 [<<DateTime(2004-10-15T03:29:39Z)>>]
<<TableOfContents>>
== 描述 ==

<<Text processing in python>>开始部分函数编程里面几个 lambda，开始看起来有点晕呢！

自己写了几个，但是c++ stl里面的 not1,not2,bind1st,bind2nd自己写不出来,或者不方便. 

-------
{{{
#!python
not1 = lambda f:lambda x,f=f :not f(x)  
not2 = lambda f:lambda x,y,f=f:not f(x,y)
bind1st = lambda f,x:lambda:y,p=f:p(x,y) #??
bind2nd = lambda f,x:lambda:y,p=f:p(y,x) #??
}}}

会了哈. 不过看起来不如类和函数清晰，(这就是传说中的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 
{{{
#!python
def ifthenelse(a, b, c):
	if a: return b
	else: return c

def is_ver(major,minor):
	from sys import version_info
	ver=version_info
	return ifthenelse(ver[0]>major or (ver[0]==major and ver[1]>=minor), True,False)

def is_ver_23():
	return is_ver(2,3)	
}}}

minifunction.py

{{{
#!python
import operator
import types
from miniutil import ifthenelse

class unary_function:    
	def __init__(self,arg,result):
		if type(arg) is not  types.TypeType:
			self.argument_type=type(arg)
		else:
			self.argument_type=arg
		if type(result) is not types.TypeType:
			self.result_type=type(result)
		else:
			self.result_type=result

class binary_function:
	def __init__(self,arg1,arg2,result):
		if type(arg1) is not types.TypeType:
			self.first_argument_type=type(arg1)
		else:
			self.first_argument_type=arg1
		if type(arg2) is not types.TypeType:
			self.second_argument_type=type(arg2)
		else:
			self.second_argument_type=arg2
		if type(result) is not types.TypeType:
			self.result_type=type(result)
		else:
			self.result_type = result
		
class plus(binary_function):
	def __init__(self,Tp):
		binary_function.__init__(self,Tp,Tp,Tp)
	def __call__(self,a,b):
		return a+b
	
class minus(binary_function):
	def __init__(self,Tp):
		binary_function.__init__(self,Tp,Tp,Tp)
	def __call__(self,a,b):
		return a-b
	
class multiplies(binary_function):
	def __init__(self,Tp):
		binary_function.__init__(self,Tp,Tp,Tp)
	def __call__(self,a,b):
		return a*b;
	

class divides(binary_function):
	def __init__(self,Tp):
		binary_function.__init__(self,Tp,Tp,Tp)
	def __call__(self,a,b):
		return a/b;

class floordivides(binary_function):
	def __init__(self,Tp):
		binary_function.__init__(self,Tp,Tp,Tp)
	def __call__(self,a,b):
		return a//b;
	

class modulus(binary_function):
	def __init__(self,Tp):
		binary_function.__init__(self,Tp,Tp,Tp)
	def __call__(self,a,b):
		return a%b;

class negate(unary_function):
	def __init__(self,Tp):
		unary_function.__init__(self,Tp,Tp)
	def __call__(self, a): return -a


class equal_to(binary_function):
	def __init__(self,Tp):
		#binary_function.__init__(self,Tp,Tp,True)
		pass
	def __call__(self,a,b):
		return a==b

class not_equal_to(binary_function):
	def __init__(self,Tp):
		#binary_function.__init__(self,Tp,Tp,True)
		pass
	def __call__(self,a,b):
		return not a==b

class greater(binary_function):
	def __init__(self,Tp):
		#binary_function.__init__(self,Tp,Tp,True)
		pass
	def __call__(self,a,b):
		return a>b

class less(binary_function):
	def __init__(self,Tp):
		#binary_function.__init__(self,Tp,Tp,True)
		pass
	def __call__(self,a,b):
		return a<b

class greater_equal(binary_function):
	def __init__(self,Tp):
		#binary_function.__init__(self,Tp,Tp,True)
		pass
	def __call__(self,a,b):
		return a>=b

class less_equal(binary_function):
	def __init__(self,Tp):
		#binary_function.__init__(self,Tp,Tp,True)
		pass
	def __call__(self,a,b):
		return a<=b

class logical_or(binary_function):
	def __init__(self,Tp):
		#binary_function.__init__(self,Tp,Tp,True)
		pass
	def __call__(self,a,b):
		return bool(a) or bool(b)
	
class logical_and(binary_function):
	def __init__(self,Tp):
		#binary_function.__init__(self,Tp,Tp,True)
		pass
	def __call__(self,a,b):
		return bool(a) and bool(b)
	
class logical_not(unary_function):
	def __init__(self,Tp):
		#unary_function.__init__(self,Tp,True)
		pass
	def __call__(self,a):
		return not bool(a)
class logical_xor(binary_function):
	def __init__(self,Tp):
		#binary_function.__init__(self,Tp,Tp,Tp)
		pass
	def __call__(self,a,b):
		return (bool(a) and not bool(b)) or (bool(b) and not bool(a))

class unary_negate(unary_function):
	def __init__(self,Tp):
		#unary_function.__init__(self,Tp.argument_type,Tp.result_type)
		self.pred = Tp
	def __call__(self,a):
		return not self.pred(a)
	
class binary_negate(binary_function):
	def __init__(self,Tp):
		#binary_function.__init__(self,Tp.first_argument_type,Tp.second_argument_type,Tp.result_type)
		self.pred = Tp.__call__
	def __call__(self,a,b):
		return not self.pred(a,b)
	
def not1(unary_pred):
	return unary_negate(unary_pred)

def not2(binary_pred):
	return binary_negate(binary_pred)

class binder1st(unary_function):
	def __init__(self,bop,bv):
		self.bindvalue=bv
		self.bindfunction=bop
	def __call__(self,value):
		return  self.bindfunction(self.bindvalue,value)

def bind1st(_fn,_x):
	return binder1st(_fn,_x)

class binder2nd(unary_function):
	def __init__(self,bop,bv):
		self.bindvalue=bv
		self.bindfunction=bop
	def __call__(self,value):
		return  self.bindfunction(value, self.bindvalue)

def bind2nd(_fn,_x):
	return binder2nd(_fn,_x)

if __name__=="__main__":
    print less(int)(4,5)
    print bind2nd(less(int),5)(4)==True
    print bind2nd(less(int),5)(6)==False
    print "ok"


}}}

minialgo.py

{{{
#!python
"""py implementation of part of c++ stl algorithm"""

from miniutil import ifthenelse
import copy


__about__=r"""py implementation of part of c++ stl"""
__all__=["max","min","set_union","etc"]
version_info = "0.1.1"
author="v_gyc"


def max(a,b):
	return ifthenelse(a>=b,a,b)


def min(a,b):
	return ifthenelse(a<=b,a,b)
	

def median(a,b,c):
	if a <b and a <c:
		return min(b,c)
	if a>b and a>c :
		return max(b,c)
	return a

def find(lst,value):
	index = 0
	for x in lst:
		if x==value :
			return index
		index +=1
	return -1	

def find_if(lst,pred):
	index = 0
	for x in lst:
		if pred(lst[index]):
			return index
		index +=1
	return -1	
	

def adjacent_find(lst):
	lstb=lst[1:]
	for i in range(len(lst)-2):
		if(lst[i]==lstb[i]):
			return i
	return -1

def adjacent_find_if(lst,pred):
	lstb=lst[1:]
	for i in range(len(lst)-2):
		if pred(lst[i],lstb[i]):
			return i
	return -1

def count(lst,value):
	return lst.count(value)

def count_if(lst,pred):
	result =0
	for x in lst:
		if pred(x):
			result += 1
	return result

def search(lst1,lst2):
	len1 = len(lst1)
	len2 = len(lst2)
	if len1<len2:
		return -1
	if len1==0:
		return -1
	if len2==0:
		return 0
	if len2 == 1:
		return find(lst1,lst2[0])

	i1=i2=0
	partial = False
	
	while(i1<len1 and i2<len2):
		if lst1[i1]!=lst2[i2]:
			if not partial:
				i1+=1
			else:
				partial=False
				i1 -=(i2-1)
				i2=0
		else:
			partial = True
			i1+=1
			i2+=1
			
	if(i2==len2):
		return i1-len2
	else:
		return -1;

def search_if(lst1,lst2,pred):
	len1 = len(lst1)
	len2 = len(lst2)
	if len1<len2:
		return -1
	if len1==0:
		return -1
	if len2==0:
		return 0
	if len2 == 1:
		return find(lst1,lst2[0])

	i1=i2=0
	partial = False
	
	while(i1<len1 and i2<len2):
		if not pred(lst1[i1], lst2[i2]):
			if not partial:
				i1+=1
			else:
				partial=False
				i1 -=(i2-1)
				i2=0
		else:
			partial = True
			i1+=1
			i2+=1
			
	if(i2==len2):
		return i1-len2
	else:
		return -1;

def transfrom(lst,uop):
	'''tranform =lambda uop,lst=[] : map(uop,lst)'''
	return map(uop,lst)
	
def transfrom2(lst1,lst2,bop):
	'''tranform2 =lambda uop,lst1=[],lst2=[] : map(bop,lst1,lst2)'''
	return map(bop,lst1,lst2) 

def replace(lst,old,new):
	index = 0
	for x in lst:
		if x==old:
			lst[index]=new
		index += 1
	#return lst

def replace_if(lst,pred,new):
	index = 0
	for x in lst:
		if pred(x):
			lst[index]=new
		index += 1
	#return lst

def replace_copy(lst,old,new):
	result = copy.deepcopy(lst)
	replace(result,old,new)
	return result

def replace_copy_if(lst,pred,new):
	result = copy.deepcopy(lst)
	replace_if(result,pred,new)
	return result

def generate(lst,generator):
	index=0
	for x in lst:
		lst[index]=g().next()
		index += 1
		
	#return lst

def generate_n(lst,n,generator):
	index=0
	for x in lst:
		lst[index]=g().next()
		index += 1
		if(index>=n):
			break
	#return lst

def remove(lst,value):
	lst.remove(value)
	#return lst

def remove_if(lst,pred):
	""""""
	result = []
	for x in lst:
		if pred(x):
			pass
		else:
			result.append(x)
	lst = result[:]
	return lst
	
def remove_copy(lst,value):
	result = lst[:]
	result.remove(value)
	return result

def remove_copy_if(lst,pred):
	result = lst[:]
	remove_if(result,pred)
	return result
			
def unique(lst):
	"""Remove consecutive duplicate values from a sequence"""	
	while(True):
		index = adjacent_find(lst)
		if index==-1:
			break
		del lst[index]
	#return lst

def unique_if(lst,pred):
	"""Remove consecutive predicating duplicate values from a sequence"""
	while(True):
		index = adjacent_find_if(lst,pred)
		if index ==-1:
			break
		del lst[index]
	#return lst

def reverse_copy(lst):
	"""given the reverse of the original list"""
	result = lst[:]
	result.reverse()
	return result

def rotate(lst,middle):
	"""	Rotates the elements of the list  by @p (middle-first)
	positions so that the element at @p middle is moved to @p first, the
	element at @p middle+1 is moved to @first+1 and so on for each element
	in the range @p [first,last).    """
	
	front = lst[:middle]
	back = lst[middle:]
	front.reverse()
	back.reverse()
	lst=[]
	lst.extend(back)
	lst.extend(front)
	#return lst

def rotate_copy(lst,middle):
	front = lst[:middle]
	back = lst[middle:]
	front.reverse()
	back.reverse()
	result=[]
	result.extend(back)
	result.extend(front)
	return result

def random_shuffle(lst):
	import random
	random.shuffle(lst)
	#return lst


def partition(lst,value):
	'''Move elements and return an index @pindex
	so that each elements in [:pindex] is less than value
	and elemnet in [pindex:] is no less than value  '''
	
	length=len(lst)
	
	index=0
	backindex=length
	
	while(True):
		while(True):
			if(index==backindex):
				return index
			elif lst[index]<value :
				index += 1
			else:
				break
		backindex -= 1		
		while(True):
			if index==backindex :
				return index
			elif not lst[backindex]<value:
				backindex -= 1
			else:
				break
		t=lst[index]
		lst[index]=lst[backindex]
		lst[backindex]=t
		index += 1

def partition_if(lst,pred):
	
	'''Move elements and return an index @pindex
	so that pred(el) for elements el in [:pindex] is true
	and pred(el) for elemnet in [pindex:] if false  '''

	length=len(lst)
	
	index=0
	backindex=length
	
	while(True):
		while(True):
			if(index==backindex):
				return index
			elif pred(lst[index]) :
				index += 1
			else:
				break
		backindex -= 1		
		while(True):
			if index==backindex :
				return index
			elif not pred(lst[backindex]):
				backindex -= 1
			else:
				break
		t=lst[index]
		lst[index]=lst[backindex]
		lst[backindex]=t
		index += 1
	
def partition_copy(lst,value):
	result = lst[:]
	partition(result,value)
	return result

def partion_copy_if(lst,pred):
	result = lst[:]
	partition_if(result,pred)
	return result

sort_threshold = 16


def replace_list(lst1,lst2,index=0):
	''' replace the contents of lst1 from index to index+length with lst2,
	return the result list '''
	
	len1 = len(lst1)
	length = len(lst2)
	if length<=0: return
	
	for x in range(length):
		try:
			lst1[index+x] = lst2[x]
		except IndexError:
			lst1.append(lst2[x])
			
		

def replace_list_copy(lst1,lst2,index):
	tmp = lst1[:]
	replace_list(tmp,lst2,index)
	return tmp





def bisect_left_if(slt,value,cmp) :
	"""return the index  @pindex for which the element at pindex
	is greater than value and when insert value before pindex
	the sorted nature of the list will be hold"""
	
	# bisect_left is in module bisect,
	#but waht is the list is sorted by other comaparing functions,
	#e.g, list.sort(cot2(cmp))
	# this function is for that.
	
	it = 0
	ti = len(slt)-1
	
	if(value<slt[0]): return 0
	if(value>slt[-1]): return len(slt)
	
	middle_if = (it+ti)/2
	
	while(it<middle_if):			
		test = cmp(slt[middle_if],value)
		if test>0:
			ti = middle_if
			middle_if = (it + ti)//2
		elif test == 0:
			return middle_if
		else:
			it = middle_if
			middle_if = (it+ti)//2
			
	return it-cmp(slt[it],value)

def partial_sort(lst,middle):
	'''@TODO implement:
	Sorts the smallest middle elements in the range [:] and
	moves them to the range [:middle]. The order of the remaining elements
	in the range @p [middle:] is undefined. implementation eh?'''
	
	from bisect import bisect_left
	if middle <=0 : return lst
	front = lst[:middle]
	back = lst[middle:]
	ext=[]	
	front.sort()	
	for x in back:
		index = bisect_left(front,x)
		if (index<middle):
			front.insert(index,x)
			ext.append(front.pop())
		else:
			ext.append(x)
	
	replace_list(lst,front)
	replace_list(lst,ext,len(front))
	#return lst	


def partial_sort_if(lst,middle,cmpfunc):
	''''''	
	if middle <=0 : return lst	
	front = lst[:middle]
	back = lst[middle:]
	ext=[]	
	front.sort(cmpfunc)	
	for x in back:
		index = bisect_left_if(front,x,cmpfunc)		
		if index<middle :
			front.insert(index,x)
			ext.append(front.pop())
		else:
			ext.append(x)			
	replace_list(lst,front)
	replace_list(lst,ext,len(front))
	
	#return lst

def nth_element(lst,nth):
	
	"""  Rearranges the elements in the lst so that the nth element
	*  is the same element that would have been in that position had the
	*  whole sequence been sorted.  The elements on either side of @p nth are
	*  not completely sorted, but for any element @i in the range
	*  [first,nth) and any element j in the range [nth,last) it
	*  holds that j<i is false.	"""
	"""@TODO implement"""
	
	index = 0
	length = len(lst)
	
	#if nth is outofindex
	if nth >= length or nth<0 :
		return
	
	#empty lst or has only one element	
	if length == 1 or length ==0:	return
	
	#	use a random value to partition	
	middle = (index + length)//2 	
	value = lst[middle]	
	pindex = partition(lst,value)
	
	#may be implemented incursively	
	if pindex>nth:
		partial_sort(lst,pindex)
		return
	if pindex <= nth:
		tmp=lst[pindex:]
		tmp.sort()		
		for x in tmp:
			lst[pindex]=x
			pindex +=1
		return 	
	#return 

def binary_search(sortedlist,value):
	if (value < sortedlist[0])or (sortedlist[-1]<value):
		return False
	if(sortedlist[-1]==value)or(sortedlist[0]==value):
		return True
	
	index=0
	backindex = len(sortedlist)-1
	middle = backindex//2
	
	if middle == index:
		return False		
	else:
		return binary_search(sortedlist[:middle],value) or binary_search(sortedlist[middle:],value)
	
def merge(sortedlist1,sortedlist2):	
	result = []
	len1 = len(sortedlist1)
	len2 = len(sortedlist2)	
	i=j=0	
	while(i<len1 and j<len2):
		first = sortedlist1[i]
		second = sortedlist2[j]
		
		result.append(min(first,second))
		
		if first < second:			i += 1
		elif first == second:
			result.append(first)
			i += 1
			j += 1
		else:			j += 1
	
	result.extend(sortedlist1[i:])
	result.extend(sortedlist2[j:])
	return result

def merge_if(sortedlist1,sortedlist2,cmpfunc=cmp):	
	result = []
	len1 = len(sortedlist1)
	len2 = len(sortedlist2)	
	i=j=0	
	while(i<len1 and j<len2):
		first = sortedlist1[i]
		second = sortedlist2[j]
		
		cmpresult = cmpfunc(first,second)
		
		if cmpresult <0:
			result.append(first)
			i += 1			
		elif cmpresult==0:
			result.append(first)
			result.append(second)
			i += 1
			j += 1
		else:
			result.append(second)
			j += 1
	
	result.extend(sortedlist1[i:])
	result.extend(sortedlist2[j:])
	return result
			
def _appendIfNotExists(sortedlist,value):
	"""for sorted list"""
	
	if(sortedlist == []):
		sortedlist.append(value)
		return
	
	if sortedlist[-1]!=value:
		sortedlist.append(value)

def _extendIfNotExists(sortedlist,sortedlist2):
	"""for sorted list"""
	
	if sortedlist == [] or sortedlist2==[]:
		sortedlist.extend(sortedlist2)
	else:
		index =0
		while(sortedlist[-1]==sortedlist2[index]):
			index += 1
		sortedlist.extend(sortedlist2[index:])
	
def set_union(sortedlist1,sortedlist2):
	result = []
	len1 = len(sortedlist1)
	len2 = len(sortedlist2)	
	i=j=0	
	while(i<len1 and j<len2):
		first = sortedlist1[i]
		second = sortedlist2[j]
		
		_appendIfNotExists(result,(min(first,second)))
		
		if first < second:
			i += 1
		elif first == second:
			i += 1
			j += 1
		else:
			j += 1
	_extendIfNotExists(result,sortedlist1[i:])
	_extendIfNotExists(result,sortedlist2[j:])
	return result


def set_intersection(sortedlist1,sortedlist2):
	result = []
	len1 = len(sortedlist1)
	len2 = len(sortedlist2)
	i=j=0
	
	while(i<len1 and j<len2):
		first = sortedlist1[i]
		second = sortedlist2[j]
		
		if first < second:
			i += 1
		elif first == second:
			_appendIfNotExists(result,first)
			i += 1
			j += 1
		else:
			j += 1
	return result

		
def set_difference(lst1,lst2):
	result = []
	len1 = len(lst1)
	len2 = len(lst2)
	i=j=0
	
	while(i<len1 and j<len2):
		first = sortedlist1[i]
		second = sortedlist2[j]
		
		if first < second:
			_appendIfNotExists(result,first)
			i += 1			
		elif first == second:
			i += 1
			j += 1
		else:
			_appendIfNotExists(result,first)
			j += 1
			
	_extendIfNotExists(result,sortedlist1[i:])
	return result

def set_symmetric_difference(lst1,lst2):
	result = []
	len1 = len(lst1)
	len2 = len(lst2)
	i=j=0
	
	while(i<len1 and j<len2):
		first = sortedlist1[i]
		second = sortedlist2[j]
		
		if first < second:
			_appendIfNotExists(result,first)
			_appendIfNotExists(result,second)			
			i += 1			
		elif first == second:
			i += 1
			j += 1
		else:
			_appendIfNotExists(result,first)			
			_appendIfNotExists(result,second)
			j += 1
	_extendIfNotExists(result,sortedlist1[i:])
	_extendIfNotExists(result,sortedlist2[j:])	
	return result

def max_element(lst):
	"""return the index of the max element"""
	vlen = len(lst)
	if vlen ==0:  return -1
	if vlen ==1: return 0
	
	tmp=lst[0]
	result=index=0
	
	for x in lst:
		if x >= tmp:
			tmp == x
			result = index
		index += 1		
	return result

	
"""contents below are from <Text processing in python> """
apply_each = lambda fns, args=[] : map(apply, fns, [args]*len(fns))
bools = lambda lst: map(truth, lst)
bool_each = lambda fns, args=[] : bools(apply_each(fns, args))
conjoin = lambda fns, args=[] : reduce(mul, bool_each(fns, args))
all = lambda fns: lambda arg, fns=fns : conjoin(fns, (arg,))
both = lambda f,g: all((f,g))
all3 = lambda f,g,h: all((f,g,h))
and_ = lambda f,g: lambda x, f=f, g=g: f(x) and g(x)
disjoin = lambda fns, args=[]: reduce(add, bool_each(fns, args))
some = lambda fns: lambda arg, fns=fns: disjoin(fns, (arg,))
either = lambda f,g: some((f,g))
anyof3 = lambda f,g,h: some((f,g,h))
compose = lambda f,g: lambda x, f=f, g=g: f(g(x))
compose3 = lambda f,g,h: lambda x, f=f, g=g, h=h: f(g(h(x)))
ident = lambda x: x

}}}


== 测试 unittest ==

minitest.py

{{{
#!python
import miniutil
import minifunction
import minialgo
import unittest
import types


class testMini(unittest.TestCase):
    def setUp(self):
        self.listSimple = [1,2,3,4,5]
        self.listMod = [3,6,9,2,4,8,1,4,7]
        self.listEmpty=[]
        self.listOne=[1]
        
    def testMinifunction(self):
        eq = self.assertEqual
        
        up = minifunction.unary_function("123",False)
        self.assertEqual(up.argument_type,types.StringType)
        self.assertEqual(up.result_type,type(True))
        
        bp=minifunction.binary_function(1,"234",2.34)
        self.assertEqual(bp.first_argument_type, type(23))
        self.assertEqual(bp.second_argument_type,type("hahaha"))
        self.assertEqual(bp.result_type,type(3.45))
        
        """test minifunction.less"""
        self.assertEqual(minifunction.less(int)(4,5),True)
        self.assertEqual(minifunction.less("a")("a","b"),True)
        self.assertEqual(minifunction.less([])([2],[4]),True)
        self.assertEqual(minifunction.less([])([4,5],[4,5,6]),True)
        self.assertEqual(minifunction.less(())((5),(6)),True)
        self.assertEqual(minifunction.less(())((4,5),(4,5,6)),True)
        
        
        """test minifunction.greater"""
        self.assertEqual(minifunction.greater(int)(4,5),False)
        self.assertEqual(minifunction.greater("a")("a","b"),False)
        self.assertEqual(minifunction.greater([])([2],[4]),False)
        self.assertEqual(minifunction.greater([])([4,5],[4,5,6]),False)
        self.assertEqual(minifunction.greater(())((5),(6)),False)
        self.assertEqual(minifunction.greater(())((4,5),(4,5,6)),False)
        
        '''test minifunction.plus, minus,divides,multiplies'''
        mnf = minifunction        
        self.assertEqual(mnf.plus(int)(4,5),9)
        self.assertEqual(mnf.plus(types.StringType)("a","b"),"ab")
        self.assertEqual(mnf.plus([])([],[]),[])
        self.assertEqual(mnf.plus([])([1],[2]),[1,2])
        self.assertEqual(mnf.plus(())((),()),())
        self.assertEqual(mnf.plus(())((1,2),(3,4)),(1,2,3,4))
        self.assertEqual(mnf.plus(())((1,2),(2,4)),(1,2,2,4))
        
        
        self.assertEqual(mnf.minus(int)(4,5),-1)
        self.assertEqual(mnf.minus(int)(4.4,5.5),4.4-5.5)
        
        self.assertEqual(mnf.multiplies(5)(5,6),30)
        self.assertEqual(mnf.multiplies("a")("",4),"")
        self.assertEqual(mnf.multiplies("a")(" ",4),"    ")                
        self.assertEqual(mnf.multiplies("a")("a",4),"aaaa")
        self.assertEqual(mnf.multiplies("a")("ab",4),"abababab")
        
        self.assertEqual(mnf.multiplies(5)([],4),[])
        self.assertEqual(mnf.multiplies(5)([1],4),[1,1,1,1])
        
        '''test minifunction logial operations'''
        self.assertEqual(mnf.logical_and(None)(1>2,2>1),False)
        self.assertEqual(mnf.logical_or(None)(1>2,2>1),True)
        self.assertEqual(mnf.logical_or(None)(1>2,2>3),False)        
        self.assertEqual(mnf.logical_xor(None)(1>2,2>1),True)
        self.assertEqual(mnf.logical_xor(None)(1>2,1>2),False)        
        self.assertEqual(mnf.logical_xor(None)([],"a"),True)
        self.assertEqual(mnf.logical_xor(None)([],""),False)
        
        '''test minifunction binder1st ,binder2nd, bind1st, bind2nd,not1,not2'''
        self.assertEqual(mnf.bind1st(mnf.less(int),10)(9),False)
        self.assertEqual(mnf.bind1st(mnf.less(int),10)(11),True)        
        self.assertEqual(mnf.bind2nd(mnf.less(int),10)(9),True)
        self.assertEqual(mnf.bind2nd(mnf.less(int),10)(11),False)
        
        self.assertEqual(mnf.bind1st(mnf.plus(int),10)(11),21)
        self.assertEqual(mnf.bind1st(mnf.plus(None),"a")("b"),"ab")        
        self.assertEqual(mnf.bind2nd(mnf.plus(int),"")(""),"")
        self.assertEqual(mnf.bind2nd(mnf.plus(int),"a")("b"),"ba")
        self.assertEqual(mnf.bind2nd(mnf.plus(int),"a")(""),"a")
        
        
        self.assertEqual(mnf.not1(mnf.logical_not(None))(True),True)
        self.assertEqual(mnf.not1(mnf.logical_not(None))(False),False)
        self.assertEqual(mnf.not1(mnf.not1(mnf.logical_not(None)))(False),True)
        
        self.assertEqual(mnf.not2(mnf.logical_and(None))(1,2),False)
        self.assertEqual(mnf.not2(mnf.logical_and(None))(0,"a"),True)
        self.assertEqual(mnf.not2(mnf.logical_or(None))(1,0),False)
        self.assertEqual(mnf.not2(mnf.logical_or(None))(0,""),True)
    
    def testMaxMinMedian(self):
        alg = minialgo
        self.assertEqual(minialgo.max(4,5),5)
        self.assertEqual(alg.max("a","b"),"b")
        self.assertEqual(alg.max([],[]),[])
        self.assertEqual(alg.max([],[1]),[1])
        self.assertEqual(alg.max([1,2],[1]),[1,2])
        self.assertEqual(alg.max([1,2],[1,2,3]),[1,2,3])
        self.assertEqual(alg.max([2,3],[2,4]),[2,4])
        self.assertEqual(alg.max([2,3,2],[2,4]),[2,4])
        
        self.assertEqual(alg.max((),()),())
        
        #odd 
        self.assertEqual(alg.max((),(1)),())
        self.assertEqual(alg.max((),(1,2)),(1,2))
        self.assertEqual(alg.max((),([1])),())        
        self.assertEqual(alg.max((),([1,2])),())
        self.assertEqual(alg.max((),([1,2,3])),())                
        self.assertEqual(alg.max((1,2),(1,3)),(1,3))                        
        self.assertEqual(alg.max((4,5,6,7),(3,4,5,5,8)),(4,5,6,7))
        self.assertEqual(alg.max((-2,3),([1])),(-2,3))                      

    
    def testFindandFind_if(self):
    
        alg = minialgo
        lst = self.listMod
        """self.listMod = [3,6,9,2,4,8,1,4,7]"""
        self.assertEqual(alg.find(lst,6),1)
        self.assertEqual(alg.find(lst,3),0)
        self.assertEqual(alg.find(lst,4),4)
        

        def predodd(a):
            if a%2==0 and a%3==0:
                return True
            else:
                return False
            
        '''index of 6 which is a common multiplier? of 2 and 3'''    
        self.assertEqual(alg.find_if(lst,predodd),1)
        
        '''contents below is only to show the usage of bind2nd and bind1st'''        
    
        class findpred(minifunction.binary_function):
            def __init__(self,tp,modr):
                minifunction.binary_function.__init__(self,tp,tp,tp)
                self.mod_result=modr
            def __call__(self,a,b):
                """@TODO doc """
                if (a%b) == self.mod_result:
                    return True
                else:
                    return False
                
        """index of element 9"""                        
        pred = minifunction.bind2nd(findpred(int,9),10)        
    
        self.assertEqual(alg.find_if(lst,pred), 2)        
        """index of element 8 """                
        pred = minifunction.bind2nd(findpred(int,8),10)        
        self.assertEqual(alg.find_if(lst,pred), 5)        
        
        """index of 7 using bind1st"""    
        pred = minifunction.bind1st(findpred(int,3),10)        
        self.assertEqual(alg.find_if(lst,pred), 8)
    
    def testAdjacent_find(self):
        lst = [2,3,4,5,5,7,6,6]
        alg = minialgo
        self.assertEqual(alg.adjacent_find(lst),3)
        lst.reverse()
        self.assertEqual(alg.adjacent_find(lst),0)        
    
    def testCount_if(self):
        lst = [2,3,13,33,34,46,1003,2,1004,2005,2007]
        pred = lambda a: miniutil.ifthenelse(a%10==3,True,False)        
        self.assertEqual(minialgo.count_if(lst,pred),4)
    
        pred = lambda a: miniutil.ifthenelse(a%10==3 or a>2000,True,False)        
        self.assertEqual(minialgo.count_if(lst,pred),6)
    
    def testSearch(self):
        alg = minialgo
        mnf = minifunction
        
        self.assertEqual(alg.search(self.listEmpty,self.listMod),-1)
        self.assertEqual(alg.search(self.listMod,self.listEmpty),0)
        
        self.assertEqual(alg.search(self.listMod,self.listOne),6)
        
        lst = [2,3,4]
        llst = [4,5,6,2,3,2,3,4,2,3,4,5,]
        self.assertEqual(alg.search(llst,lst),5)
        self.assertEqual(alg.search(llst[5:],lst),0)
        self.assertEqual(alg.search(llst[6:],lst),2)
        self.assertEqual(alg.search([2,3,4],lst),0)
        self.assertEqual(alg.search([1,2,3,4],lst),1)
        
    
    def testSearch_if(self)    :
        """@TODO implement"""
        pass

    def testTransform(self):
        lst = range(5) #[0,1,2,3,4]
        trans = lambda a : -a
        lst = minialgo.transfrom(lst,trans)  #[0,-1,-2,-3,-4]
        self.assertEqual(lst, range(0,-5,-1))
        
        lst = minialgo.transfrom(lst,trans) #back
        self.assertEqual(lst,range(5))
        
    def testTransform2(self):
        lst = range(5)
        tsl = range(0,-5,-1)  #[0,-1,-2,-3,-4]        
        bop = lambda a,b : a+b
        
        tmp = minialgo.transfrom2(lst, tsl, bop)        
        self.assertEqual(tmp,[0]*5)
        
    def testReplace(self):
        alg = minialgo
        
        lst = range(5)  #0 1 2 3 4
        alg.replace(lst, 4,99)
        self.assertEqual(alg.find(lst,4),-1)
        self.assertEqual(alg.find(lst,99),4)
        
    def testReplace_if(self):
        alg = minialgo        
        lst = range(5)
        from miniutil import ifthenelse        
        pred = lambda x: ifthenelse(x%4==0,True,False)        
        alg.replace_if(lst,pred,8)
        self.assertEqual(lst[4],8)
        
        alg.replace_if(lst,pred,"aa")
        self.assertEqual(lst[4],"aa")
        
    def testPartition(self):
        alg = minialgo
        
        lst = self.listEmpty
        self.assertEqual(alg.partition(lst,-1),0)
        self.assertEqual(alg.partition(lst,4),0)
        self.assertEqual(alg.partition(lst,5),0)
        
        lst = self.listOne
        self.assertEqual(alg.partition(lst,-1),0)
        self.assertEqual(alg.partition(lst,1),0)        
        self.assertEqual(alg.partition(lst,2),1)
        
        tmp  = [5,4,3,2,1]       
        lst = tmp[:]
        self.assertEqual(alg.partition(lst,-99),0)
        #print -99 ,lst        
        lst = tmp[:]
        self.assertEqual(alg.partition(lst,-1),0)
        #print -1,lst
        lst = tmp[:]
        self.assertEqual(alg.partition(lst,1),0)
        #print 1,lst        
        lst = tmp[:]
        self.assertEqual(alg.partition(lst,2),1)
        #print 2,lst        
        lst = tmp[:]
        self.assertEqual(alg.partition(lst,3),2)
        #print 3, lst        
        lst = tmp[:]
        self.assertEqual(alg.partition(lst,4),3)
        #print 4, lst        
        lst = tmp[:]
        self.assertEqual(alg.partition(lst,5),4)
        #print 5, lst
        lst = tmp[:]
        self.assertEqual(alg.partition(lst,6),5)
        #print 6,lst
        lst = tmp[:]
        self.assertEqual(alg.partition(lst,999),5)
        #print 999, lst
        
    def testReplaceList(self)    :
        alg = minialgo
        lst1 = [1,2,3,4,5]
        lst2 = [5,4,3,2,1]
        
        tmp=lst1[:]
        alg.replace_list(tmp,lst2,0)
        self.assertEqual(tmp,[5,4,3,2,1])
        
        tmp=lst1[:]
        alg.replace_list(tmp,lst2,5)
        self.assertEqual(tmp,[1,2,3,4,5,  5,4,3,2,1])
        
        tmp=lst1[:]
        alg.replace_list(tmp,lst2,2)
        self.assertEqual(tmp,[1,2,  5,4,3,2,1])
        
    def testPartialsort(self):        
        lst = [9,6,3,8,5,2,7,4,1]
        alg = minialgo


        tmp=lst[:]
        alg.partial_sort(tmp,-3)
        self.assertEqual(tmp,lst)
        
        tmp=lst[:]
        alg.partial_sort(tmp,0)
        self.assertEqual(tmp,lst)
        
        tmp=lst[:]
        alg.partial_sort(tmp,1)
        self.assertEqual(tmp[0],1)
        
        tmp=lst[:]
        alg.partial_sort(tmp,2)
        self.assertEqual(tmp[0],1)
        self.assertEqual(tmp[1],2)        
        
        tmp=lst[:]
        alg.partial_sort(tmp,5)
        self.assertEqual(tmp[0],1)
        self.assertEqual(tmp[4],5)        
        
        tmp=lst[:]
        alg.partial_sort(tmp,8)
        self.assertEqual(tmp,range(1,10))
        
        
        tmp=lst[:]
        alg.partial_sort(tmp,222)
        self.assertEqual(tmp,range(1,10))
        
        
        lst= "gdahebifc"        
        tmp=list(lst)[:]
        alg.partial_sort(tmp,0)
        self.assertEqual("".join(tmp),lst)
        
        tmp=list(lst)[:]
        alg.partial_sort(tmp,1)
        self.assertEqual("".join(tmp)[0],"a")
        
        tmp=list(lst)[:]
        alg.partial_sort(tmp,4)
        self.assertEqual("".join(tmp)[0],"a")
        self.assertEqual("".join(tmp)[1],"b")
        self.assertEqual("".join(tmp)[2],"c")
        self.assertEqual("".join(tmp)[3],"d")
        
        tmp=list(lst)[:]
        alg.partial_sort(tmp,22)
        self.assertEqual("".join(tmp),"abcdefghi")
        
    def testBisect_Left_if(self):
        from bisect import bisect_left
        lst = self.listSimple
        for i in range(-len(lst),len(lst)):
            ifindex = minialgo.bisect_left_if(lst,i,cmp)
            index = bisect_left(lst,i)
            self.assertEqual(ifindex,index )
        
    def testNth_element(self):
        lst = [3,6,9,2,1,4,8,5,7,0]              
        for i in range(10):
            tmp=lst[:]
            minialgo.random_shuffle(tmp)
            #print "original ",tmp
            minialgo.nth_element(tmp,i)
            #print "index",i,":", tmp
            self.assertEqual(tmp[i],i)
            
        lst = "abcdefghij"        
        for i in range(10):
            tmp=list(lst)[:]
            minialgo.random_shuffle(tmp)
            #print "original ","".join(tmp)
            minialgo.nth_element(tmp,i)
            #print "index",i,":", "".join(tmp)
            self.assertEqual(tmp[i],chr(ord("a")+i))
            
        lst = ['m','a','x','p']
        
        tmp=lst[:]        
        minialgo.random_shuffle(lst)
        minialgo.nth_element(tmp,0)
        self.assertEqual(tmp[0],'a')
        #print tmp
        
        tmp=lst[:]        
        minialgo.random_shuffle(lst)
        minialgo.nth_element(tmp,1)
        self.assertEqual(tmp[0],'a')        
        self.assertEqual(tmp[1],'m')
        #print tmp
        
        tmp=lst[:]        
        minialgo.random_shuffle(lst)
        minialgo.nth_element(tmp,2)
        self.assertEqual(tmp[2],'p')
        #print tmp
        
        tmp=lst[:]        
        minialgo.random_shuffle(lst)
        minialgo.nth_element(tmp,3)
        self.assertEqual(tmp[3],'x')
        #print tmp        
        
    def testBinary_Search(self):
        lst=[1,3,5,7,9]
        
        for i in range(-10,20):
            if i%2 ==0 or i<1 or i>9:
                self.assertEqual(minialgo.binary_search(lst,i),False)
            else:
                self.assertEqual(minialgo.binary_search(lst,i),True)
    
    def testMerge(self):
        alg = minialgo
        
        lst1=lst2=[]

        result = alg.merge(lst1,lst2)
        self.assertEqual(result,[])

        lst1=[]
        lst2=[1]
        result = alg.merge(lst1,lst2)
        self.assertEqual(result,[1])
        
        lst1=[]
        lst2=[1,2]
        result = alg.merge(lst1,lst2)
        self.assertEqual(result,[1,2])
        
        lst1=[1,2]
        lst2=[1,2]
        result = alg.merge(lst1,lst2)
        self.assertEqual(result,[1,1,2,2])

        lst1=[1,2,3]
        lst2=[2,4,6]
        result = alg.merge(lst1,lst2)
        self.assertEqual(result,[1,2,2,3,4,6])
        
    
        
    def testSet_Union(self):
        alg = minialgo
        
        lst1=lst2=[]

        result = alg.set_union(lst1,lst2)
        
        self.assertEqual(result,[])

        lst1=[]
        lst2=[1]
        result = alg.set_union(lst1,lst2)
        self.assertEqual(result,[1])
        
        lst1=[]
        lst2=[1,2]
        result = alg.set_union(lst1,lst2)
        self.assertEqual(result,[1,2])
        
        lst1=[1,2]
        lst2=[1,2]
        result = alg.set_union(lst1,lst2)
        self.assertEqual(result,[1,2])

        lst1=[1,2,3]
        lst2=[2,4,6]
        result = alg.set_union(lst1,lst2)
        self.assertEqual(result,[1,2,3,4,6])
    
    def testdir(self):
        print dir(minialgo)

    
if __name__ == '__main__':
    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实现起来也蛮困难的 :(

________________________________________

"小提琴砸钉子"
________________________________________

== 参考 See Also ==