------------------
--- suportadas na nova versao do terrahs

module TerraHS.Algebras.Base.Tree where
-- módulo para definição operações e do formato geral da árvore
-- para um tipo t qualquer

-- definição das operações
class SimpleTree t where
	leaf                :: a -> t a
	tnull               :: t a
	branch              :: a -> t a -> t a -> t a
	getData             :: t a -> a
	setData             :: t a -> a -> t a
	left, right         :: t a -> t a
	allLeaves 			:: t a -> [t a]
	allBranches 			:: t a -> [t a]
	allObjects			:: t a -> [t a]
	isLeaf              :: t a -> Bool
	
-- definição de uma estrutura de árvore de um tipo a qualquer
-- a árvore pode ser uma folha tipo a, um nó interno tip a com duas sub-árvores tipo a ou um valor nulo
-- Tree: type constructor
-- Leaf and Branch: data constructors
data Tree a  = Leaf a | Branch  a (Tree a) (Tree a) | NULL  deriving (Show, Eq)

-- definição dos axiomas (implementação das operações com suas restrições)
instance SimpleTree Tree  where	
	leaf                  		= Leaf				-- retorna uma folha tipo t com o objeto a
	tnull						= NULL				-- retorna nulo para ser colocado na árvore
	branch   					= Branch			-- retorna um nó interno 3 componentes tipo t para o objeto a
	getData  (Leaf a)       	= a					-- recupera o objeto na folha da árvore
	getData  (Branch a l r) 	= a					-- recupera o objeto no nó interno da árvore
	setData  (Leaf _) a         = (Leaf a)			-- define um objeto a de entrada para uma folha
	setData  (Branch _ l r) a   = (Branch a l r)	-- define um objeto tipo a para um nó da árvore com as subárvores da direita e da esquerda
	left  (Branch a l r)    	= l					-- recupera a subárvore da esquerda
	right (Branch a l r)    	= r					-- recupera a subárvore da direita
	isLeaf   (Leaf _)       	= True				-- testa se um objeto é uma folha
	isLeaf   _              	= False			
	allBranches tr								-- recupera todos os nós internos sem as folhas
		| not (isLeaf tr ) = tr : (allBranches (left tr))  ++ (allBranches (right tr))  
		| (isLeaf tr) = []
		
	allLeaves tr									-- recupera todas as folhas que compõe a árvore 
		| not (isLeaf tr ) = (allLeaves (left tr)) ++ (allLeaves (right tr))  
		| (isLeaf tr) = [tr]
		
	allObjects tr									-- recupera todas as folhas que compõe a árvore 
		| not (isLeaf tr ) = tr : (allObjects (left tr))  ++ (allObjects (right tr))  
		| (isLeaf tr) = [tr]
		

fringe :: Tree a -> [a]   -- A different definition of fringe
fringe (Leaf x) = [x]
fringe (Branch o x y) = fringe x