Map & Prioritary queue

BlitzMax Forums/BlitzMax Programming/Map & Prioritary queue

Paposo

(Posted 2006) [#1]

Gello guys.
Sorry my bad english.
I offer free modules for your use.
This are implementations of Maps and prioritary queues baseds on a tree red-black. Same implementation used by java for the trees.

Base code for tree manegement

SuperStrict

Rem
bbdoc: Arbol Rojo-Negro
End Rem
Module rvm.arbolbin

ModuleInfo "Version: 1.01"
ModuleInfo "Author: Ramon Vidal"
ModuleInfo "License: Public"


Private
Const NODONEGRO:Byte=False
Const NODOROJO:Byte=True
Const ARBOLASCENDENTE:Byte=True
Const ARBOLDESCENDENTE:Byte=False
Public

'	******************************************************************************************************************
'	Nodo binario con balanceo ROJO-NEGRO
'	Es la base para cualquier tipo de nodo balanceado ROJO-NEGRO
'	******************************************************************************************************************

Rem
bbdoc: Implementacion de nodo de arbol binario con balanceo Rojo-Negro
about:
Representa un nodo generico. Normalmente no sera usado por el usuario final <br>
Existen muchos metodos no documentados pero que se pueden usar para nuevas implementaciones de usuario. Consulte el fuente.
End Rem
Type TNodoRN 
	Field izq:TNodoRN=Null
	Field der:TNodoRN=Null
	Field padre:TNodoRN=Null
	Field color:Byte=NODONEGRO
	Field dato:TDatoNodo=Null
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Crea un nuevo nodo

	Function create:TNodoRN(dato:TDatoNodo, padre:TNodoRN)
		Local nodo:TNodoRN= New TNodoRN
		nodo.dato=dato
		nodo.padre=padre
		Return nodo
	EndFunction

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el nodo raiz

	Method getRaiz:TNodoRN()
		Local p:TNodoRN=Self
		While(p.padre)
			p=p.padre
		Wend
		Return p
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Borra todos los datos de un nodo y elimina sus descendientes

	Method clear()
		If(izq) 
			izq.clear()
		EndIf
		If(der)
			der.clear()
		EndIf
		izq=Null
		der=Null
		padre=Null
		dato=Null
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Actualiza el dato asociado al nodo, devolviendo el dato anteriormente asociado

	Method setDato:TDatoNodo(dato:TDatoNodo)
		Local ant:TDatoNodo=self.dato
		self.dato=dato
		Return ant
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Actualiza el dato asociado al nodo, devolviendo el dato anteriormente asociado

	Method getDato:TDatoNodo()
		Return dato
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el primer nodo segun orden ARBOLASCENDENTE o ARBOLDESCENDENTE

	Method getFirstNodo:TNodoRN(orden:Byte)
		Local retorno:TNodoRN=getRaiz()
		If(orden=ARBOLASCENDENTE)
			While(retorno.izq)
				retorno=retorno.izq
			Wend
		Else
			While(retorno.der)
				retorno=retorno.der
			Wend
		EndIf
		Return retorno
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el ultimo nodo segun orden ARBOLASCENDENTE o ARBOLDESCENDENTE

	Method getLastNodo:TNodoRN(orden:Byte)
		Return getFirstNodo(Not orden)
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el siguiente nodo al actual segun orden ARBOLASCENDENTE o ARBOLDESCENDENTE

	Method getNextNodo:TNodoRN(orden:Byte)
		Local retorno:TNodoRN
		
		If(orden=ARBOLASCENDENTE)
			If(self.der)						'	Si el nodo actual tiene rama derecha descendemos por ella
				retorno=Self.der
				While(retorno.izq)			'	Nos movemos hacia el mas pequeño
					retorno=retorno.izq
				Wend
			Else								'	Si no tiene ramas a la derecha hay que volver atras
			
				'	Hay que subir hacia atras hasta que el nodo actual sea un hijo izquierdo o sea raiz
				retorno=Self
				While(retorno)And(retorno.esRamaDer())
					retorno=retorno.padre
				Wend
				If(retorno)
					retorno=retorno.padre
				EndIf
			
			EndIf		
		Else
			If(self.izq)						'	Si el nodo actual tiene rama izquierda descendemos por ella
				retorno=self.izq
				While(retorno.der)			'	Nos movemos hacia el mas grande
					retorno=retorno.der
				Wend
			Else								'	Si no tiene ramas a la izquierda hay que volver atras
			
				'	Hay que subir hacia atras hasta que el nodo actual sea un hijo derecho o sea raiz
				retorno=Self
				While((retorno)And(retorno.esRamaIzq()))
					retorno=retorno.padre
				Wend
				If(retorno)
					retorno=retorno.padre
				EndIf
			
			EndIf		

		EndIf
		Return retorno
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	¿Este nodo es una rama izquierda?

	Method esRamaIzq:Byte()
		If(padre) And (padre.izq=Self)
			Return True
		Else
			Return False
		EndIf
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	¿Este nodo es una rama derecha?

	Method esRamaDer:Byte()
		If(padre) And (padre.der=Self)
			Return True
		Else
			Return False
		EndIf
	EndMethod

EndType

'	******************************************************************************************************************
'	Contenido estandar para cualquier TNodoRN
'	Es la base para implementar el contenido de los nodos
'	******************************************************************************************************************

Rem
bbdoc: Contenedor abstracto estandar de informacion asociada a un nodo
about:
Se usa para dar consistencia a la comparacion con independencia de los datos asociados al nodo <br>
El usuario solo necesitara esta informacion si decide crear una implementacion nueva a partir de TArbolRN
End Rem
Type TDatoNodo Abstract
Rem
bbdoc: Obtiene el objeto a comparar
returns:
Un objeto asociado al nodo
about:
Este metodo es usado por las funciones de comparacion para obtener el dato a comparar
End Rem
	Method getComparable:Object() Abstract
Rem
bbdoc: Obtiene el objeto que representa los datos contenidos en el nodo
returns:
Un objeto asociado al nodo
about:
Este metodo es usado por las funciones de recorrido
End Rem
	Method toObject:Object() Abstract
	
	Method getPair:Object()
		Return [getComparable(),toObject()]
	EndMethod
	
End Type

'	******************************************************************************************************************
'	Arbol binario abstracto
'	Es la base para cualquier tipo de arbol binario rojo-negro
'	******************************************************************************************************************

Rem
bbdoc: Clase abstracta base para el desarrollo de arboles binarios rojo-negro concretos
about:
Proporciona la gestion basica del arbol y funcionalidades de usuario <br>
En esta documentacion solo se incluiran los metodos de usuario final. <br>
Si se desea extender el arbol para crear una implementacion concreta propia debera consultarse el fuente, donde si estan
documentadas todas las funciones. <br>
No deben usarse directamente las variables.
End Rem
Type TArbolRN Abstract

	Field orden:Byte=ARBOLASCENDENTE
	Field raiz:TNodoRN=Null
	Field size:Int=0
	
	Field comparar:Int(dato1:TDatoNodo, dato2:TDatoNodo)
	Field recorrido:Byte(dato:Object)

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Inicializador: Una clase heredada puede sobreescribirlo para adaptar la comparacion. Ojo realmente no se sobreescribe
	'	El metodo new se llama para cada una de las clases superiores
	
	Method New()
		comparar=comparacionEstandar
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Accesorio: funcion de comparacion estandar. Una clase heredada puede sobreescribirlo para adaptar la comparacion
	
	Function comparacionEstandar:Int(dato1:TDatoNodo, dato2:TDatoNodo)
		Return dato1.getComparable().compare(dato2.getComparable())
	EndFunction

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Accesorio: Obtiene el color de un nodo	

	Function colorOf:Byte(nodo:TNodoRN)
		If(nodo=Null)
			Return NODONEGRO
		Else
			Return nodo.color
		EndIf
	EndFunction

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Accesorio: Obtiene el hijo izquierdo de un nodo

	Function leftOf:TNodoRN(nodo:TNodoRN)
		If(nodo=Null)
			Return Null
		Else
			Return nodo.izq
		EndIf
	EndFunction
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Accesorio: Obtiene el hijo derecho de un nodo

	Function rightOf:TNodoRN(nodo:TNodoRN)
		If(nodo=Null)
			Return Null
		Else
			Return nodo.der
		EndIf
	EndFunction
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Accesorio: Obtiene el padre de un nodo

	Function parentOf:TNodoRN(nodo:TNodoRN)
		If(nodo=Null)
			Return Null
		Else
			Return nodo.padre
		EndIf
	EndFunction

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Accesorio: Actualiza el color de un nodo

	Function updateColor(nodo:TNodoRN, color:Byte)
		If(nodo) 
			nodo.color=color
		EndIf
	EndFunction

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Comprueba si el arbol esta vacio

	Rem
	bbdoc: ¿Esta vacio el arbol?
	returns: True si esta vacio, false si contiene algun elemento
	about:
	Eficiencia constante O(k) 
	End Rem
	Method isEmpty:Byte()
		If(size=0)
			Return True
		Else
			Return False
		EndIf
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el numero de elementos del arbol

	Rem
	bbdoc: Obtiene el numero de elementos que contiene el arbol
	returns: Devuelve un Int con el numero de elementos
	about:
	Eficiencia constante O(k)
	End Rem
	Method getSize:Int()
		Return size
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Marca el arbol como ascendente. Por defecto

	Rem
	bbdoc: Activa el orden ascendente del arbol
	about:
	Eficiencia constante O(k)
	End Rem
	Method setAscendente()
		orden=ARBOLASCENDENTE
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Marca el arbol como descendente	

	Rem
	bbdoc: Activa el orden descendente del arbol
	about:
	Eficiencia constante O(k)
	End Rem
	Method setDescendente()
		orden=ARBOLDESCENDENTE
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	¿Es el arbol ascendente?

	Rem
	bbdoc: Comprueba si el arbol se vera en orden ascendente
	returns: True si el arbol es ascendente o false en caso contrario
	about:
	Eficiencia constante O(k)
	End Rem
	Method isAscendente:Byte()
		Return orden
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el primer dato segun orden establecido

	Method getFirstDato:Object()
		If(raiz)
			Local nodo:TNodoRN=raiz.getFirstNodo(orden)
			Return nodo.dato.toObject()
		Else
			RuntimeError "No hay elementos"
		EndIf
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el ultimo dato segun orden establecido

	Method getLastDato:Object()
		If(raiz)
			Local nodo:TNodoRN=raiz.getLastNodo(orden)
			Return nodo.dato.toObject()
		Else
			RuntimeError "No hay elementos"
		EndIf
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene la primera clave segun orden establecido

	Method getFirstKey:Object()
		If(raiz)
			Local nodo:TNodoRN=raiz.getFirstNodo(orden)
			Return nodo.dato.getComparable()
		Else
			RuntimeError "No hay elementos"
		EndIf
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene la ultima clave segun orden establecido

	Method getLastKey:Object()
		If(raiz)
			Local nodo:TNodoRN=raiz.getLastNodo(orden)
			Return nodo.dato.getComparable()
		Else
			RuntimeError "No hay elementos"
		EndIf
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtener array

	Rem
	bbdoc: Obtiene un array con los elementos del arbol
	returns: Un array de objetos
	about:
	Eficiencia lineal O(n)
	End Rem
	Method toArray:Object[]()
		Local arr:Object[]=New Object[size]
		Local nn:Int=0
		For Local datos:Object=EachIn Self
			arr[nn]=datos
			nn:+1
		Next
		Return arr
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Reduce el numero de elementos en 1

	Method decrementSize()
		size:-1
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Incrementa el numero de elementos en 1

	Method incrementSize()
		size:+1
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el menor nodo mayor o el mayor nodo menor

	Method sucesor:TNodoRN(t:TNodoRN)
		Local p:TNodoRN
		If(t=Null)
			Return Null
		ElseIf(t.der)
			p=t.der
			While(p.izq)
				p=p.izq
			Wend
			Return p
		Else
			p=t.padre
			Local ch:TNodoRN=t
			While( p And ch=p.der)
				ch=p
				p=p.padre
			Wend
			Return p
		EndIf
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el nodo que contiene una determinada clave

	Method getNodo:TNodoRN(dato:TDatoNodo)
		Local p:TNodoRN=raiz
		While(p)
			Local cmp:Int=comparar(dato,p.dato)
			If(cmp=0)
				Return p
			ElseIf(cmp<0)
				p=p.izq
			Else
				p=p.der
			EndIf
		Wend
		Return Null	
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el dato asociado a una clave

	Method getDato:TDatoNodo(dato:TDatoNodo)
		Local p:TNodoRN=getNodo(dato)
		If(p)
			Return p.dato
		Else
			Return Null
		EndIf
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Inicia un recorrido recursivo

	Rem
	bbdoc: Recorre recursivamente todo el arbol segun orden establecido
	returns: True si la funcion ha detenido el recorrido, false en caso contrario
	about:
	Requiere un puntero a una funcion de recorrido con la siguiente firma: <br>
		funcionrecorrido:byte(dato:Object) <br>
		El valor dato se obtiene del metodo getPair() de TDatoNodo que devuelve un array [clave, valor]
	Si la funcion devuelve true el recorrido se detendra, si devuelve false continua el recorrido con el siguiente nodo. <br>
	Eficiencia lineal O(n)
	End Rem
	Method recorrer:Byte(recorre:Byte Ptr)
		Local retorno:Byte=False
		If(raiz)
			recorrido=recorre
			If(isAscendente())
				retorno=recorrerNodosAsc(raiz)
			Else
				retorno=recorrerNodosDes(raiz)
			EndIf
			recorrido=Null
		EndIf
		Return retorno
	EndMethod
	
'	------------------------------------------------------------------------------------------------------------------
'	Obtiene un enumeradores para poder usarse como colecciones

	Rem
	bbdoc: Obtiene un enumerador de los valores del arbol
	returns: Un enumerador estandar
	about:
	Este metodo lo llama automaticamente la sentencia FOR ... EACHIN .. NEXT para recorridos <br>
	Los datos siempre se obtienen ordenados segun el orden establecido en el arbol <br>
	Eficiencia lineal O(n)
	End Rem

	Method ObjectEnumerator:EnumeradorAbstractoArbol()
		Return EnumeradorArbolBin.create(Self)
	End Method

	Rem
	bbdoc: Obtiene un enumerador de las claves del arbol
	returns: Un enumerador estandar
	about:
	Los datos siempre se obtienen ordenados segun el orden establecido en el arbol <br>
	Eficiencia lineal O(n)
	End Rem
	Method KeysEnumerator:EnumeradorAbstractoArbol()
		Return EnumeradorKeysArbolBin.create(Self)
	EndMethod
	
	Rem
	bbdoc: Obtiene un enumerador de las parejas claves-valor del arbol en formato array de 2 elementos
	returns: Un enumerador estandar
	about:
	Los datos siempre se obtienen ordenados segun el orden establecido en el arbol <br>
	Eficiencia lineal O(n)
	End Rem
	Method PairsEnumerator:EnumeradorAbstractoArbol()
		Return EnumeradorPairsArbolBin.create(Self)
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el primer nodo segun orden establecido

	Method getFirstNodo:TNodoRN()
		If(raiz=Null) 
			Return Null
		Else
			Return raiz.getFirstNodo(orden)
		EndIf		
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el ultimo nodo segun orden establecido

	Method getLastNodo:TNodoRN()
		If(raiz=Null) 
			Return Null
		Else
			Return raiz.getLastNodo(orden)
		EndIf		
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el siguiente nodo al actual segun orden establecido

	Method getNextNodo:TNodoRN(nodoActual:TNodoRN)
		If(nodoActual=Null)
			Return Null
		Else
			Return nodoActual.getNextNodo(orden)
		EndIf
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Obtiene el nodo que ocupa una determinada posicion segun orden establecido
	'	La posicion a buscar empieza con 0 hasta getSize()-1
	'	Este metodo tiene una eficiencia lineal O(n). No es practico usarlo

	Method getNodoAt:TNodoRN(posicion:Int)
		If(size=0)
			RuntimeError "El arbol esta vacio"
		ElseIf ((size<=posicion) Or (posicion<0))
			RuntimeError "Posicion fuera de rango"
		EndIf
		Local nodo:TNodoRN=getFirstNodo()
		Local cta:Int=0
		While(nodo)
			If(cta=posicion)
				Return nodo
			EndIf
			nodo=getNextNodo(nodo)
			cta:+1
		Wend
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Efectua una rotacion a la izquierda del nodo

	Method rotarIzq(p:TNodoRN)
		Local x:TNodoRN=p.der
		p.der=x.izq
		If(x.izq)
			x.izq.padre=p
		EndIf
		x.padre=p.padre
		If(p.padre=Null)
			raiz=x
		ElseIf(p.padre.izq=p)
			p.padre.izq=x
		Else
			p.padre.der=x
		EndIf
		x.izq=p
		p.padre=x
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Efectua una rotacion a la derecha del nodo

	Method rotarDer(p:TNodoRN)
		Local x:TNodoRN=p.izq
		p.izq=x.der
		If(x.der)
			x.der.padre=p
		EndIf
		x.padre=p.padre
		If(p.padre=Null)
			raiz=x
		ElseIf(p.padre.der=p)
			p.padre.der=x
		Else
			p.padre.izq=x
		EndIf
		x.der=p
		p.padre=x
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Balancea el arbol despues de una insercion

	Method corregirInsercion(x:TNodoRN)
		Local y:TNodoRN
		x.color=NODOROJO
		While(x And x<>raiz And x.padre.color=NODOROJO)
			If(parentOf(x)=leftOf(parentOf(parentOf(x))))
				y=rightOf(parentOf(parentOf(x)))
				If(colorOf(y)=NODOROJO)
					updateColor(parentOf(x),NODONEGRO)
					updateColor(y,NODONEGRO)
					updateColor(parentOf(parentOf(x)),NODOROJO)
					x=parentOf(parentOf(x))
				Else
					If(x=rightOf(parentOf(x)))
						x=parentOf(x)
						rotarIzq(x)
					EndIf
					updateColor(parentOf(x),NODONEGRO)
					updateColor(parentOf(parentOf(x)), NODOROJO)
					If(parentOf(parentOf(x)))
						rotarDer(parentOf(parentOf(x)))
					EndIf
				EndIf
			Else
				y=leftOf(parentOf(parentOf(x)))
				If(colorOf(y)=NODOROJO)
					updateColor(parentOf(x),NODONEGRO)
					updateColor(y,NODONEGRO)
					updateColor(parentOf(parentOf(x)),NODOROJO)
					x=parentOf(parentOf(x))
				Else
					If(x=leftOf(parentOf(x)))
						x=parentOf(x)
						rotarDer(x)
					EndIf
					updateColor(parentOf(x),NODONEGRO)
					updateColor(parentOf(parentOf(x)), NODOROJO)
					If(parentOf(parentOf(x)))
						rotarIzq(parentOf(parentOf(x)))
					EndIf
				EndIf
			EndIf
			raiz.color=NODONEGRO
		Wend
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Balancea el arbol despues de una eliminacion

	Method corregirBorrado(x:TNodoRN)
		Local sib:TNodoRN
		While(x<>raiz And colorOf(x)=NODONEGRO)
			If(x=leftOf(parentOf(x)))
				sib=rightOf(parentOf(x))
				If(colorOf(sib)=NODOROJO)
					updateColor(sib,NODONEGRO)
					updateColor(parentOf(x),NODOROJO)
					rotarIzq(parentOf(x))
					sib=rightOf(parentOf(x))
				EndIf
				If(colorOf(leftOf(sib))=NODONEGRO And colorOf(rightOf(sib))=NODONEGRO)
					updateColor(sib, NODOROJO)
					x=parentOf(x)
				Else
					If(colorOf(rightOf(sib))=NODONEGRO)
						updateColor(leftOf(sib),NODONEGRO)
						updateColor(sib,NODOROJO)
						rotarDer(sib)
						sib=rightOf(parentOf(x))
					EndIf
					updateColor(sib, colorOf(parentOf(x)))
					updateColor(parentOf(x), NODONEGRO)
					updateColor(rightOf(sib), NODONEGRO)
					rotarIzq(parentOf(x))
					x=raiz
				EndIf
			Else
				sib=leftOf(parentOf(x))
				If(colorOf(sib)=NODOROJO)
					updateColor(sib,NODONEGRO)
					updateColor(parentOf(x),NODOROJO)
					rotarDer(parentOf(x))
					sib=leftOf(parentOf(x))
				EndIf
				If(colorOf(leftOf(sib))=NODONEGRO And colorOf(rightOf(sib))=NODONEGRO)
					updateColor(sib, NODOROJO)
					x=parentOf(x)
				Else
					If(colorOf(leftOf(sib))=NODONEGRO)
						updateColor(rightOf(sib),NODONEGRO)
						updateColor(sib,NODOROJO)
						rotarIzq(sib)
						sib=leftOf(parentOf(x))
					EndIf
					updateColor(sib, colorOf(parentOf(x)))
					updateColor(parentOf(x), NODONEGRO)
					updateColor(leftOf(sib), NODONEGRO)
					rotarDer(parentOf(x))
					x=raiz
				EndIf			
			EndIf
		Wend
		updateColor(x,NODONEGRO)
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Inserta un nuevo dato en el arbol y balancea si es necesario

	Method putDato:TDatoNodo(datoNodo:TDatoNodo)
		Local t:TNodoRN=raiz
		Local cmp:Int
		
		If(t=Null)
			incrementSize()
			raiz=TNodoRN.create(datoNodo,Null)
			Return Null
		EndIf
		
		Repeat
			cmp=comparar(datoNodo,t.dato)
			If(cmp=0)
				Return setDatoExistente(t, datoNodo)
			ElseIf(cmp<0)
				If(t.izq)
					t=t.izq
				Else
					incrementSize()
					t.izq=TNodoRN.create(datoNodo, t)
					corregirInsercion(t.izq)
					Return Null
				EndIf
			Else
				If(t.der)
					t=t.der
				Else
					incrementSize()
					t.der=TNodoRN.create(datoNodo, t)
					corregirInsercion(t.der)
					Return Null
				EndIf
			EndIf
		Forever
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Este metodo se ejecuta cuando ya existe el dato que queremos insertar. 
	'	Por defecto se sustituye el dato, pero una clase heredada de TArbolRN puede sobreescribirlo
	
	Method setDatoExistente:TDatoNodo(nodo:TNodoRN, dato:TDatoNodo)
		Return nodo.setDato(dato)
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Elimina un dato del arbol
	'	No es necesario que el DatoNodo que se le pasa sea el original. Basta con que se pueda comparar
	'	Devuelve el DatoNodo original contenido en el arbol
	
	Method removeDato:TDatoNodo(dato:TDatoNodo)
		Local p:TNodoRN=getNodo(dato)
		If(p=Null)
			Return Null
		EndIf
		Local ant:TDatoNodo=p.dato
		removeNodo(p)
		Return ant
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Elimina un nodo del arbol y balancea si es necesario

	Method removeNodo(p:TNodoRN)
		Local s:TNodoRN
		Local rep:TNodoRN
		decrementSize()
		
		If(p.izq And p.der)
			s=sucesor(p)
			p.dato=s.dato
			p=s
		EndIf
		
		If(p.izq)
			rep=p.izq
		Else
			rep=p.der
		EndIf
		
		If(rep)
			rep.padre=p.padre
			If(p.padre=Null)
				raiz=rep
			ElseIf(p.padre.izq=p)
				p.padre.izq=rep
			Else
				p.padre.der=rep
			EndIf
			p.izq=Null 
			p.der=Null
			p.padre=Null
			If(p.color=NODONEGRO)
				corregirBorrado(rep)
			EndIf
		ElseIf(p.padre=Null)
			raiz=Null
		Else
			If(p.color=NODONEGRO)
				corregirBorrado(p)
			EndIf
			If(p.padre)
				If(p=p.padre.izq)
					p.padre.izq=Null
				ElseIf(p=p.padre.der)
					p.padre.der=Null
				EndIf
				p.padre=Null
			EndIf
		EndIf
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Borra todos los elementos del arbol
	Method clear()
		If(raiz)
			raiz.clear()
			size=0
		EndIf
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Comprueba la existencia de un dato. Realmente comprueba solo la existencia de la clave del dato
	Method existDato:Byte(dato:TDatoNodo)
		If(getNodo(dato))
			Return True
		Else
			Return False
		EndIf
	EndMethod

'	------------------------------------------------------------------------------------------------------------------
'	Auxiliar para recorridos Ascendente

	Method recorrerNodosAsc:Byte(Nodo:TNodoRN)
		
		If(nodo.izq)
			If(recorrerNodosAsc(nodo.izq))
				Return True
			EndIf
		EndIf
		If(recorrido(nodo.dato.getPair()))
			Return True
		EndIf
		If(nodo.der)
			If(recorrerNodosAsc(nodo.der))
				Return True
			EndIf
		EndIf
		Return False
		
	EndMethod

'	------------------------------------------------------------------------------------------------------------------
'	Auxiliar para recorridos Descendente

	Method recorrerNodosDes:Byte(Nodo:TNodoRN)
		
		If(nodo.der)
			If(recorrerNodosDes(nodo.der))
				Return True
			EndIf
		EndIf
		If(recorrido(nodo.dato.getPair()))
			Return True
		EndIf
		If(nodo.izq)
			If(recorrerNodosDes(nodo.izq))
				Return True
			EndIf
		EndIf		
		Return False
		
	EndMethod


EndType

'	******************************************************************************************************************
'	Enumerador de nodos
'	Es la base para cualquier tipo de enumerador de elementos de un arbol balanceado
'	******************************************************************************************************************

Type EnumeradorAbstractoArbol Abstract
	Method HasNext:Byte() Abstract
	Method NextObject:Object() Abstract
EndType
	
Type EnumeradorNodos Extends EnumeradorAbstractoArbol
	Field nodo:TNodoRN
	Field orden:Byte
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	¿Hay mas nodos?
	
	Method HasNext:Byte()
		Return (nodo<>Null)
	EndMethod

	'---------------------------------------------------------------------------------------------------------------------------------
	'	Devuelve el siguiente nodo

	Method NextObject:Object()
		If(nodo=Null) 
			RuntimeError "No hay mas elementos"
		EndIf
		Local obj:TNodoRN=nodo
		nodo=nodo.getNextNodo(orden)
		Return obj
	EndMethod

EndType	

Type EnumeradorArbolBin Extends EnumeradorNodos
	Method NextObject:Object()
		Local obj:TNodoRN=TNodoRN(super.NextObject())
		Local dn:TDatoNodo=obj.dato
		Return dn.toObject()
	EndMethod

	Function create:EnumeradorArbolBin(mapa:TArbolRN)
		Local enum:EnumeradorArbolBin=New EnumeradorArbolBin
		enum.orden=mapa.orden
		If(mapa.raiz)
			enum.nodo=mapa.raiz.getFirstNodo(enum.orden)
		EndIf
		Return enum
	EndFunction

EndType

Type EnumeradorKeysArbolBin Extends EnumeradorNodos
	Method nextObject:Object()
		Local obj:TNodoRN=TNodoRN(super.NextObject())
		Local dn:TDatoNodo=obj.dato
		Return dn.getComparable()
	EndMethod

	Function create:EnumeradorKeysArbolBin(mapa:TArbolRN)
		Local enum:EnumeradorKeysArbolBin=New EnumeradorKeysArbolBin
		enum.orden=mapa.orden
		If(mapa.raiz)
			enum.nodo=mapa.raiz.getFirstNodo(enum.orden)
		EndIf
		Return enum
	EndFunction

EndType

Type EnumeradorPairsArbolBin Extends EnumeradorNodos
	Method nextObject:Object()
		Local obj:TNodoRN=TNodoRN(super.NextObject())
		Local dn:TDatoNodo=obj.dato
		Return dn.getPair()
	EndMethod

	Function create:EnumeradorPairsArbolBin(mapa:TArbolRN)
		Local enum:EnumeradorPairsArbolBin=New EnumeradorPairsArbolBin
		enum.orden=mapa.orden
		If(mapa.raiz)
			enum.nodo=mapa.raiz.getFirstNodo(enum.orden)
		EndIf
		Return enum
	EndFunction

EndType

Code for Map

SuperStrict

Rem
bbdoc: Mapa balanceado
End Rem
Module rvm.treemap

ModuleInfo "Version: 1.01"
ModuleInfo "Author: Ramon Vidal"
ModuleInfo "License: Public"

Import rvm.arbolbin

'	******************************************************************************************************************
Rem
bbdoc: Implementacion del contenedor de los datos que forman un Mapa
about:
Se usa para dar consistencia a la comparacion con independencia de los datos asociados al nodo <br>
Tambien ofrece consistencia para la obtencion del objeto asociado a una clave <br>
Esta clase no es utilizada por el usuario del mapa. Solo se requerira si se extiende la clase.
End Rem
Type TDatoMap Extends TDatoNodo
	Field clave:Object
	Field dato:Object
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Method getComparable:Object()
		Return clave
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Method toObject:Object()
		Return dato
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Function create:TDatoMap(clave:Object, dato:Object)
		Local retorno:TDatoMap=New TDatoMap
		retorno.dato=dato
		retorno.clave=clave
		Return retorno
	EndFunction
	
End Type

'	******************************************************************************************************************
Rem
bbdoc: Implementacion de un mapa basado en un arbol,binario balanceado
about:
No permite claves duplicadas. <br>
Eficiencia O(log(n)) para las principales operaciones <br>
vease #rvm.arbolbin.TArbolRN para informacion sobre mas metodos disponibles
End Rem
Type TTreeMap Extends TArbolRN

	'---------------------------------------------------------------------------------------------------------------------------------
	Rem
	bbdoc: Crea un Mapa con una version personalizada de la funcion de comparacion
	returns: Un nuevo TTreeMap
	End Rem
	Function create:TTreeMap(funcionComparacion:Byte Ptr)
		Local tree:TTreeMap=New TTreeMap
		tree.comparar=funcionComparacion
		Return tree
	EndFunction
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Rem
	bbdoc: Añade un nuevo objeto asociado a una clave al mapa
	returns: El dato insertado o null si no ha sido posible insertarlo
	about:
	Eficiencia O(log(n))
	End Rem
	Method put:Object(clave:Object, dato:Object)
		Local dat:TDatoMap=TdatoMap.create(clave, dato)
		Return putDato(dat)
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Rem
	bbdoc: Elimina una clave y el valor asociado del mapa
	returns: El objeto eliminado o null si no existe
	about:
	Eficiencia O(log(n))
	End Rem
	Method remove:Object(clave:Object)
		Local dat:TDatoMap=TdatoMap.create(clave, Null)
		Return removeDato(dat)
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Rem
	bbdoc: Obtiene el objeo asociado a una determinada clave
	returns: El objeto asociado o null si no existe
	about:
	Eficiencia O(log(n)) 
	End Rem
	Method get:Object(clave:Object)
		Local dat:TDatoMap=TdatoMap.create(clave, Null)
		Local dato:TDatoNodo=getDato(dat)
		If(dato)
			Return dato.toObject()
		Else
			Return Null
		EndIf
	EndMethod	

EndType

Code for Prioritary queue:

SuperStrict

Rem
bbdoc: Cola Prioritaria
End Rem
Module rvm.colap

ModuleInfo "Version: 1.01"
ModuleInfo "Author: Ramon Vidal"
ModuleInfo "License: Public"

Import rvm.arbolbin
Import rvm.treemap
Import brl.linkedlist

Rem
bbdoc: Wraper para encanpsular un entero
about:
Se utiliza para uniformizar el funcionamiento del arbol, ya que las claves siempre son objetos, no tipos simples
End Rem
Type TInteger
	Field entero:Int
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Rem
	bbdoc: Comparador utilizado por la clase TInteger
	returns:
	Un entero que indica el resultado de la comparacion. Valores: -1, 0, 1 si es menor, igual o mayor
	about:
	El usuario final no necesita usarlo
	End Rem
	Method compare:Int(dato:Object)
		Local dat:TInteger=TInteger(dato)
		If(dat)
			If(entero>dat.entero)
				Return 1
			ElseIf(entero<dat.entero)
				Return -1
			Else
				Return 0
			EndIf
		Else
			RuntimeError "Tipos no comparables"
		EndIf
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Rem
	bbdoc: Devuelve el entero encapsulado
	returns:
	Un entero
	about:
	El usuario final podra usarlo en algun enumerador a fin de obtener el entero encapsulado
	End Rem
	Method getInt:Int()
		Return entero
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Rem
	bbdoc: Crea un objeto TInteger a partir de un entero
	returns:
	Un objeto TInteger que encapsula un entero
	End Rem
	Function create:TInteger(entero:Int)
		Local retorno:TInteger=New TInteger
		retorno.entero=entero
		Return retorno
	EndFunction
	
EndType

Rem
bbdoc: Contenedor de informacion asociada a un nodo
about:
Se usa para dar consistencia a la comparacion con independencia de los datos asociados al nodo <br>
El usuario solo necesitara esta informacion si decide crear una implementacion nueva a partir de TColaP
End Rem
Type TDatoColaP Extends TDatoNodo
	Field prioridad:TInteger
	Field dato:TList
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Method New()
		dato=New TList
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Method getComparable:Object()
		Return prioridad
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Method toObject:Object()
		Return dato
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	Function create:TDatoColaP(dato:Object, prioridad:Int)
		Local retorno:TDatoColaP=New TDatoColaP
		retorno.dato.addfirst(dato)
		retorno.prioridad=TInteger.create(prioridad)
		Return retorno
	EndFunction
	
End Type

Rem
bbdoc: Implementacion de una cola prioritaria
about:
Representa una cola con la particularidad de que los elementos salen segun la prioridad establecida para ellos. <br>
Es posible recorrer la cola sin necesidad de extraer los elementos e incluso modificar la prioridad de cualquier
elemento previamente introducido. <br>
Veanse mas metodos disponibles en #rvm.arbolbin.TArbolRN
End Rem
Type TColaP Extends TArbolRN

	Field datos:TTreeMap=New TTreeMap	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Añade un elemento en la cola con una prioridad especifica
	
	Rem
	bbdoc: Añade un objeto a la cola con una determinada prioridad de salida
	End Rem
	Method encolar(dato:Object, prioridad:Int)
		Local dat:TDatoColaP=TDatoColaP.create(dato,prioridad)
		putDato(dat)
		datos.put(dato, getNodo(dat))
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Extrae el siguiente elemento de la cola segun su prioridad

	Rem
	bbdoc: Extrae el siguiente elemento de la cola
	returns:
	Un objeto previamente introducido en la cola
	about:
	Los objetos se extraen segun su prioridad. Es posible alterar el orden general usando SetAscendente() o SetDescendente() <br>
	Vease la documentacion de la clase padre.
	End Rem
	Method desencolar:Object()
		Local nodo:TNodoRN=getLastNodo()
		Local datAct:TDatoColaP=TDatoColaP(nodo.getDato())
		Local retorno:Object=datAct.dato.removeLast()
		datos.remove(retorno)
		If(datAct.dato.isEmpty())
			removeNodo(nodo)
		EndIf
		Return retorno
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Cambia la prioridad de un determinado elemento

	Rem
	bbdoc: Cambia la prioridad de un determinado elemento
	End Rem
	Method setPrioridad(dato:Object, newPrioridad:Int)
		eliminar(dato);
		encolar(dato, newPrioridad)
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Elimina un elemento de la cola

	Rem
	bbdoc: Elimina un elemento de la cola
	End Rem
	Method eliminar(dato:Object)
		Local datMap:TDatoMap=TDatoMap(datos.remove(dato))
		If(datMap=Null)
			RuntimeError "No existe el elemento"
		EndIf
		Local datNod:TNodoRN=TNodoRN(datMap.toObject())
		Local datAct:TDatoColaP=TDatoColaP(datNod.getDato())
		datAct.dato.remove(dato)
		If(datAct.dato.isEmpty())
			removeDato(datAct)
		EndIf
	EndMethod
	
	'---------------------------------------------------------------------------------------------------------------------------------
	'	Este metodo se ejecuta cuando ya existe el dato que queremos insertar. 
	'	Sobreescribe el methodo de la clase base
	
	Method setDatoExistente:TDatoNodo(nodo:TNodoRN, dato:TDatoNodo)
		Local datAct:TDatoColaP=TDatoColaP(nodo.getDato())
		datAct.dato.addFirst(TDatoColaP(dato).dato.first())
		Return Null		'	encolar no utiliza el valor de retorno
	EndMethod

'	------------------------------------------------------------------------------------------------------------------
'	Obtiene un enumerador para poder usarse como colecciones

	Rem
	bbdoc: Obtiene un enumerador de los elementos del arbol
	returns: Un enumerador estandar que devuelve valores
	about:
	Sobreescribe el metodo estandar. <br>
	Este metodo lo llama automaticamente la sentencia FOR ... EACHIN .. NEXT para recorridos <br>
	Los datos siempre se obtienen ordenados segun el orden establecido en el arbol <br>
	Eficiencia lineal O(n)
	End Rem
	Method ObjectEnumerator:EnumeradorAbstractoArbol()
		Return EnumeradorCola.Create(Self)
	End Method

	'---------------------------------------------------------------------------------------------------------------------------------
'	Obtiene un enumerador para poder usarse como colecciones

	Rem
	bbdoc: Obtiene un enumerador de las parejas claves-valor del arbol en formato array de 2 elementos [TInteger, Object]
	returns: Un enumerador estandar que devuelve parejas [prioridad, valor]
	about:
	Sobreescribe el metodo estandar. <br>
	Los datos siempre se obtienen ordenados segun el orden establecido en el arbol <br>
	El elemento clave es un TInteger. Se puede obtener el entero con el metodo toInt()
	Eficiencia lineal O(n)
	End Rem
	Method PairsEnumerator:EnumeradorAbstractoArbol()
		Return EnumeradorPairsCola.create(Self)
	EndMethod

EndType

Type EnumeradorCola Extends EnumeradorNodos
	Field enumLista:TListEnum
	
	Method NextObject:Object()
		If(nodo=Null) 
			RuntimeError "No hay mas elementos"
		EndIf

		Local retorno:Object=enumLista.nextObject()
		If(Not enumLista.hasNext())
			nodo=nodo.getNextNodo(orden)
			If(nodo)
				enumLista=TList(nodo.dato.toObject()).ObjectEnumerator()
			EndIf
		EndIf
		Return retorno
	EndMethod
	
	Function create:EnumeradorCola(cola:TColaP)
		Local enum:EnumeradorCola=New EnumeradorCola
		enum.orden=cola.orden
		If(cola.raiz)
			enum.nodo=cola.raiz.getFirstNodo(enum.orden)
			enum.enumLista=TList(enum.nodo.dato.toObject()).ObjectEnumerator()
		EndIf
		Return enum
	EndFunction
	
EndType
	
Type EnumeradorPairsCola Extends EnumeradorNodos
	Field enumLista:TListEnum

	Method NextObject:Object()
		If(nodo=Null) 
			RuntimeError "No hay mas elementos"
		EndIf

		Local retorno:Object[]=[nodo.dato.getComparable(),eNumLista.nextObject()]
		If(Not enumLista.hasNext())
			nodo=nodo.getNextNodo(orden)
			If(nodo)
				enumLista=TList(nodo.dato.toObject()).ObjectEnumerator()
			EndIf
		EndIf
		Return retorno
	EndMethod
	
	Function create:EnumeradorPairsCola(cola:TColaP)
		Local enum:EnumeradorPairsCola=New EnumeradorPairsCola
		enum.orden=cola.orden
		If(cola.raiz)
			enum.nodo=cola.raiz.getFirstNodo(enum.orden)
			enum.enumLista=TList(enum.nodo.dato.toObject()).ObjectEnumerator()
		EndIf
		Return enum
	EndFunction
	
EndType

Please, if you enconter any bug comment this.

Bye,
Paposo

Dreamora

(Posted 2006) [#2]

Isn't a priority queue basing on a self restructuring tree a little over the top? (thinking that heap delivers the same runtime without the need of averaging it and with far less overhead due to simple array implementation)

Oh and just to mention: brl.map is red-black based ... Where is the actual use of yours? (not that I have anything against new datastructures, they are always welcome :) )

Paposo

(Posted 2006) [#3]

Hello Dremora.
The tree is used for for simple ordering the prioritys. In each node use a LinkedList. This is very eficient, the search for next priority is O(log(n) ) eficient and the extraction for linkedList is O(k) constant eficiency for use only the last and the first elements.
If you use a big number of elements the implementation look very eficient.
The method setPrioridad() not is O(log(n)) eficient. It search object in linked list.
I use the priority queue for painting the sprites in my prefered order. I not use desencolar. i use and enumerator and if ne sprite is moved to front i use setPrioridad() for repriorice it. This is very fast that sort entire queue.

Ahhh! brl.map is not balanced. not is one good implementation of red-black three. Test it! Use a set of preordered keys in brl.map. The eficiency is O(n). Very, very bad. Use the same set in TTreeMap. Get times and compare. 20000 elements need 200 millisec in Ttreemap and 40000 millisec in brl.map

The brl.map is only eficient with random ordered keys.

Bye,
paposo

Dreamora

(Posted 2006) [#4]

Erm brl.map got an update a few days ago after the new implementation was posted on the Module Tweaks board 3 weeks ago by mark. So sadly, it is balanced now :-)

But you are right, the old implementation was quite critical, as ordered data ended with a linear linked list which made it pointless.

On PriorityQueue: With stack you could do everything on O(log(n)) base.
If you were a little freaky, even O(log(log(n))) is possible ... but I would never try to implement a Fibonacci Heap once again
And without a really large amount of objects, O(log(n)) isn't really slower than O(log(log(n))) as the whole relinking etc takes time as well that is not counted in O() time

Paposo

(Posted 2006) [#5]

Thanks Dreamora.

I updated de brl mods and look at TMap. Very well. This is a good implementation.

I look for your technic in priorityQueue. Thanks

Bye,
Paposo