'''
Input for the base algorithms:
- M is a matroid.
- T_0 is an initial base of M
'''
def greedy_base_closest(M,T_0):
	# Greedy-base with closest tiebreak.
	# We begin by imposing a linear order on the elements
	E = sorted(M.groundset())
	m = len(E)
	# Setting initial states
	active = E
	T = set(T_0)
	# Visiting first base
	yield(T)
	while True:
		visited = False
		# We check all pairs e,f such that e is active, and take the smallest possible e.
		for i in range(1,m,1):
			e = E[i]
			if e in active:
				for j in range(i-1,-1,-1):
					f = E[j]
					if M.is_basis(T.symmetric_difference({e,f})) and not visited:
						T = T.symmetric_difference({e,f})
						active = [a for a in E if a<e] + [a for a in active if a>e]
						yield(T)
						visited = True
		if not visited:
			break


def greedy_base_furthest(M,T_0):
	# Greedy-base with furthest tiebreak.
	# We begin by imposing a linear order on the elements
	E = sorted(M.groundset())
	m = len(E)
	# Initializing variables
	T = set(T_0)
	T_star = {e for e in E if e not in T_0}
	stack = []
	visit = []
	# Initialization of the stack:
	# add elements f whose f-prefix minor has a branching in the colexico tree.
	for i in range(m-1,-1,-1):
		e=E[i]
		partial_T = [g for g in E if g in T and g>e]
		partial_T_star = [g for g in E if g in T_star and g>e]
		if M.is_independent(partial_T+[e]) and M.is_coindependent(partial_T_star+[e]):
			stack.append(e)
	# Output first basis
	yield T
	# Loop while stack is nonempty
	while stack:
		e = stack.pop()
		j = E.index(e)
		T = T.symmetric_difference({e})
		T_star = T_star.symmetric_difference({e})
		# We descend to respect the furthest tie breaker rule by delaying and to add into the stack
		for i in range(j-1,-1,-1):
			f = E[i]
			partial_T = [g for g in E if g in T and g>f]
			partial_T_star = [g for g in E if g in T_star and g>f]
			# If there is a branching add to the stack
			if M.is_independent(partial_T+[f]) and M.is_coindependent(partial_T_star+[f]):
				stack.append(f)
			# Otherwise, choose f if we are forced to
			elif (M.is_independent(partial_T+[f]) and f not in T) or (M.is_coindependent(partial_T_star+[f]) and f in T):
				T = T.symmetric_difference({f})
				T_star = T_star.symmetric_difference({f})
		yield T