#!/usr/bin/env python

import Grafo
import GrafoUtils


class HeapIndireto:
	""" Heap Indireto.
	
	Acessos ao vetor interno são sempre feitos levando em conta que o
	início dele é o elemento 1"""
	def __init__(self, v=[],p={}):
		"""v é a lista de elementos a serem colocados na heap
		p é a lista de 'pesos' de cada elemento de v, endereçada
		de forma p[i], onde i é um elemento de p"""
		self.__heap=[None]+v	# Colocamos um elemento na posição 0
		self.__p=p.copy()	# Lista dos pesos

		# Iniciando a lista de posições
		self.__pos={}
		for i in range(1,len(self.__heap)):
			self.pos[ self.__heap[i] ]=i

	# funcções de controle da representação interna
	def __getPos(self, v):
		"""Retorna a posição de um item dentro da heap.
		
		v é um elemento da heap (não o indice desse elemento na heap, mas seu valor)"""
		return self.__pos[v]
	
	def __getValor(self,i):
		"""Retorna o valor de um no na heap.
		
		i é o índice desse no na heap"""
		if i < 1:
			raise IndexError
		return self.__p[self.__heap[i]]
	
	def __setValor(self,i,val):
		"""Modifica o valor de um nó da heap.
		
		i é o indice desse no na heap"""
		if i < 1:
			raise IndexError
		self.__p[self.__heap[i]]=val
		
	def __troca(self, i,j):
		if (i < 1) or (j < 1):
			raise IndexError("Indices inválidos para heap")
		# Atualiza a troca no vertor pos
		tmp = self.__pos[ self.__heap[i] ]
		self.__pos[ self.__heap[i] ]= self.__pos[ self.__heap[j] ]
		self.__pos[ self.__heap[j] ]= tmp
		# Troca as posições no heap
		tmp = self.__heap[i]
		self.__heap[i]=self.__heap[j]
		self.__heap[j]=tmp

	def __pop(self):
		"""Remove e retorna o elemento final do heap"""
		v = self.__heap.pop()
		self.__pos[v]=0
		return v
	
	def __append(self,v,val):
		self.__p[v]=val
		self.__heap.append(v)
		self.__pos[v]=self.tamanho()
	
	# Funções de manipulação da heap

	def pai(self,i):
		return int(i/2)
		
	def esquerdo(self,pai):
		return pai*2
	
	def direito(self,pai):
		return pai*2 + 1
	
	def tamanho(self):
		return len(self.__heap) - 1
	
	def subir(self, i):
		pai = self.pai(i)
		if pai >= 1:
			if self.__getValor(pai) > self.__getValor(i):
				self.__troca(pai,i)
				self.subir(pai)
	
	def descer(self,pai):
		n = self.tamanho()
		esquerdo=self.esquerdo(pai)
		direito=self.direito(pai)
		menor=esquerdo
		
		if esquerdo <= n:
			if direito <= n:
				if self.__getValor(direito) < self.__getValor(esquerdo):
					menor=direito
			if self.__getValor(pai) > self.__getValor(menor):
				self.__troca(pai,menor)
				self.descer(menor)
				
	def constroi(self):
		n = self.tamanho()
		for i in range((n/2)-1, 0, -1): # (n/2 -1)...1
			self.descer(i)

	# Funções da Lista de Prioridades...
	def retiraMin(self):
		self.__troca(1,self.tamanho())
		val=self.__pop()
		self.descer(1)
		return val
	
	def insere(self,i, val):
		self.__append(i,val)
		self.subir(self.tamanho())
	
	def diminuiValor(self, v, val):
		"""Diminui o valor da chave do elemento 'v' para 'val'
		
		V é um elemento pertencente ao heap (não seu indice nele)"""
		i = self.__getPos(v)
		if val > self.__getValor(i):
			raise ValueError("O valor atual é menor que o valor fornecido.")
		self.__setValor(i, val)
		self.subir(i)
	
	# Funções para lidar com a lista de valores / indireção
	def getValor(self,v):
		"""Retorna o peso/valor de um item v.
		
		v é um elemento do do heap, não o seu índice"""
		return self.__getValor(self.__getPos(v)) # avi.. pq n pegar direto de self.__p?!
	
	def contem(self,v):
		"""Verifica se um elemento está contido no heap ou não"""
		if self.__getPos(v) == 0:
			# Lembrando 0 é indice invalido dentro do heap...
			return 0
		else:
			return 1


def AGMPrim(g,raiz=0,inf=100000):
	"""Algoritmo de Prim para a AGM do grafo g
	
	Retorna uma "lista de paternidade". O valor de um item 'i' nessa
	lista é o rotulo do vértice pai desse item 'i' na AGM
	
	inf, argumento opcional, é o valor numero usado para representar infinito."""
	pai=[None]*g.numeroVertices()
	
	q=HeapIndireto()
	for u in g.listaVertices():
		q.insere(u,inf)
	q.diminuiValor(raiz,0)
	pai[raiz]=None
	while q.tamanho() > 1 :
		u = q.retiraMin()
		for v in g.listaAdjacencia(u):
			if q.contem(v) and g.obtemAresta(u,v) < q.getValor(v):
				pai[v]=u
				q.diminuiValor(v, g.obtemAresta(u,v))
	
	return pai

if __name__=='__main__':
	g=GrafoUtils.TSPLIB2Grafo('../brazil58.tsp')
	pai=AGMPrim(g)
	print "A AGM desse grafo custa", GrafoUtils.custo_lista_paternidade(pai,g)