# -*- coding: latin-1 -*-
""" 
   Copyright (C) 2003 PimenTech SARL (http://www.pimentech.net)

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public
   License along with this library; see the file COPYING.LIB.  If not,
   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.	
"""

__version__='$Revision: 1.32 $'[11:-2]

from Products.PimenTechLibCommon.object import Object
from Products.PimenTechLibCommon.map import Map
from Products.PimenTechLibCommon.set import Set

try:
	from Globals import HTMLFile
except:
	pass
	
class Vertex(Map):
	"the vertex class"
	
	meta_type = 'Vertex'
	tag = 0
	
	try:
		index_html = HTMLFile('dtml/vertexIndex', globals()) # View Interface
	except:
		pass
	
	def __init__(self, object, title = ''):
		Map.__init__(self, str(object), title)
		self.object = object
		
	def __setitem__(self, label, vertex):
		self.message("%s (Vertex)%s.__setitem__(%s, Vertex %s)" % (self.meta_type, self.getId(),label, vertex))		
		if self.has_key(label):
			set = self[label]
			self.message("set = self[%s]" % label)
		else:
			set = Set(str(label))
			self.message("%s (Vertex)%s.__setitem__(%s, Set %s)" % (self.meta_type, self.getId(),label, set))
			Map.__setitem__(self, label, set)
		set.insert(vertex)

	def __getitem__(self, label):
		return Map.__getitem__(self, label) or Set('')

	def __repr__(self):
		xmlstr = "<%s id='%s' title='%s'>\n" % (self.meta_type, self.getId(), self.title)
		xmlstr = "%s<pair>\n" % xmlstr
		xmlstr = "%s<value>%s</value>\n" % (xmlstr, `self.object`)
		xmlstr = "%s<edges>\n" % xmlstr
		for (label, vertices) in self.items():
			xmlstr = "%s<pair>\n" % xmlstr
			xmlstr = "%s<label>%s</label>\n" % (xmlstr, `label`)
			xmlstr = "%s<vertices>\n" % xmlstr
			for vertex in vertices.values():
				xmlstr = "%s%s\n" % (xmlstr, Object.__repr__(vertex))
			xmlstr = "%s</vertices>\n" % xmlstr			
			xmlstr = "%s</pair>\n" % xmlstr
		xmlstr = "%s</edges>\n" % xmlstr
		xmlstr = "%s</pair>\n" % xmlstr
		return "%s</%s>" % (xmlstr, self.meta_type)
	
	def degre(self):
		"return the degre of a vertex"
		degre = 0
		for vertices in self.values():
			degre = degre + len(vertices.values()) # TODO !!!!
		return degre

	def manage_afterAdd(self, item, container):
		"avoid infinite recursion when added"
		self.message("%s (Vertex)%s.manage_afterAdd(%s,%s)" % (self.meta_type, self.getId(), item, container))
		pass

	def manage_beforeDelete(self, item, container):
		"avoid infinite recursion when deleted"
		self.message("%s (Vertex)%s.manage_beforeDelete(%s,%s)" % (self.meta_type, self.getId(), item, container))
		pass

	def manage_fixupOwnershipAfterAdd(self):
		"avoid infinite recursion when addes"
		self.message("%s (Vertex)%s.manage_fixupOwnershipAfterAdd()" % (self.meta_type, self.getId()))
		pass


class Graph(Set):
	"the graph class, here a set of vertices"

	meta_type = 'Graph'
	directed = 1

	def insert(self, object):
		"return a vertex"
		return Set.insert(self, Vertex(object))
		
	def insert_edge(self, object1, label, object2):
		self.message("%s (Graph)%s.insert_edge(%s,%s,%s)" % (self.meta_type, self.getId(),object1, label, object2))
		vertex1 = self.insert(object1)
		vertex2 = self.insert(object2)
		vertex1[label] = vertex2
		if not self.directed:
			vertex2[label] = vertex1
			
	def clear_tags(self):
		for v in self.values():
			v.tag = 0

	def _get_dfs_path(self, object1, object2):
		v1 = self[object1]
		v2 = self[object2]
		if v1 and v2:
			v1.tag = 1
			for (label, vertices) in v1.items():
				for v in vertices.values():
					if v.tag:
						continue
					if v == v2:
						return [ (v1, label, v) ]
					else:
						subpath = self._get_dfs_path(v, v2)
						if subpath:
							return [ (v1, label, v) ] + subpath
		return []

	def get_dfs_path(self, object1, object2):
		self.clear_tags()
		return self._get_dfs_path(object1, object2)