Source

ArbolPrioridad / src / arbol_prioridad / backend / arbol_prioridad.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
Created on 25/03/2012

@author: asdrubal
'''

from errores import ErrorClave
from nodo import Nodo
from errores import NoEsPunto
import random
from parcond import ParCond
from punto import Punto
from rectangulo import Rectangulo
class ArbolPrioridad(object):
    '''
    classdocs
    '''


    def __init__(self, k):
        '''
        Constructor
        '''
        if k <= 0:
            raise ErrorClave
        self.primera_clave = 0
        self.ultima_clave = k - 1
        self.pr_non_clave = k + 1
        self.raiz = None
    def insertar(self, punto):
        if not isinstance(punto, Nodo):
            raise NoEsPunto
        if self.raiz is None:
            self.raiz = punto
            self.raiz.x_min = self.primera_clave
            self.raiz.x_max = self.pr_non_clave
        else:
            if punto.y < self.raiz.y:
                Nodo.swap(self.raiz, punto)
            self._insertar(punto, self.raiz, self.primera_clave, self.ultima_clave)
    def _insertar(self, punto, nodo, min_x, max_x):
        if nodo is None:
            nodo = punto
        elif nodo.x != punto.x:
            if punto.y < nodo.y:
                Nodo.swap(punto, nodo)
            medio_x = (min_x + max_x) // 2
            if punto.x < medio_x:
                if nodo.izq is None:
                    nodo.izq = punto
                else:
                    self._insertar(punto, nodo.izq, min_x, medio_x)
            else:
                if nodo.der is None:
                    nodo.der = punto
                else:
                    self._insertar(punto, nodo.der, medio_x, max_x)
        return
    def enumerar(self, x0, x1, y0, y1, lista):
        self._enumerar(x0, x1, y0, y1, self.raiz, lista, self.primera_clave, self.pr_non_clave)
    def _enumerar(self, x0, x1, y0, y1, nodo, lista, inferior, superior):
        if nodo is not None:
            if nodo.y <= y1:
                if x0 <= nodo.x and nodo.x <= x1 and nodo.y >= y0:
                    lista.append(nodo)
                medio = (inferior + superior) / 2
                if x0 < medio:
                    self._enumerar(x0, x1, y0, y1, nodo.izq, lista, inferior, medio)
                if medio <= x1:
                    self._enumerar(x0, x1, y0, y1, nodo.der, lista, medio, superior)
        return
    def min_x_rectangulo(self, x0, x1, y0, y1):
        par = ParCond()
        self._min_x_rectangulo(x0, x1, y0, y1, self.raiz, self.primera_clave, self.pr_non_clave, par)
        return Punto(par.x, par.y)
    def _min_x_rectangulo(self, x0, x1, y0, y1, nodo, min_x, max_x, par):
        if nodo is not None:
            if nodo.y > y1:
                print "Test"
                par.valido = False
            else:
                medio_x = (min_x + max_x) / 2
                if x0 < medio_x:
                    self._min_x_rectangulo(x0, x1, y0, y1, nodo.izq, min_x, medio_x, par)
                else:
                    par.valido = False
                if not par.valido and medio_x <= x1:
                    self._min_x_rectangulo(x0, x1, y0, y1, nodo.der, medio_x, max_x, par)
                if (x0 <= nodo.x and nodo.x <= x1 and nodo.y >= y0) and (not par.valido or nodo.x < par.x):
                    par.valido = True
                    par.set_x_y(nodo.x, nodo.y)
    def max_y_rectangulo(self, x0, x1, y0, y1):
        ret_val = ParCond()
        ret_val.valido = False
        self._max_y_rectangulo(x0, x1, y0, y1, self.raiz, self.primera_clave, self.pr_non_clave, ret_val)
        return Punto(ret_val.x, ret_val.y)
    def _max_y_rectangulo(self, x0, x1, y0, y1, nodo, inferior, superior, par):
        if nodo is not None:
            if nodo.y <= y1:
                print nodo.y > 2
                if x0 <= nodo.x and nodo.x <= x1 and nodo.y >= y0:
                    if par.y < nodo.y:
                        par.x = nodo.x
                        par.y = nodo.y
                medio = (inferior + superior) / 2
                if x0 < medio:
                    self._max_y_rectangulo(x0, x1, y0, y1, nodo.izq, inferior, medio, par)
                if medio <= x1:
                    self._max_y_rectangulo(x0, x1, y0, y1, nodo.der, medio, superior, par)
        return 
    def rec_inf(self, lista, imprimir=True):
        if imprimir:
            print "Infijo: "
        self._rec_inf(self.raiz, lista, imprimir)
    def _rec_inf(self, nodo, lista, imprimir):
        if nodo is None:
            return
        self._rec_inf(nodo.izq, lista, imprimir)
        if imprimir:
            print nodo
        lista.append(nodo)
        self._rec_inf(nodo.der, lista, imprimir)
    def rec_pre(self, lista):
        print "Prefijo: "
        self._rec_pre(self.raiz, lista)
    def _rec_pre(self, nodo, lista):
        if nodo is None:
            return
        print nodo
        lista.append(nodo)
        self._rec_pre(nodo.izq, lista)
        self._rec_pre(nodo.der, lista)
    def enum_int(self, rect1, rect2, lista):
        rect = Rectangulo.interseccion(rect1, rect2)
        if rect is not None:
            self.enumerar(rect.punto1.x, rect.punto2.x, rect.punto1.y, rect.punto2.y, lista)
            return True
        return False
def main():
    arbol = ArbolPrioridad(50000)
    random.seed()
    for val in xrange(0, 50000):
        arbol.insertar(Nodo(val, random.randint(0, 3000)))
    lista = []
    arbol.enumerar(110, 20000, 0, 5, lista)
    for val in lista:
        print val
    print "Min X"
    print arbol.min_x_rectangulo(12, 30, 0, 50000)
    lista = []
    arbol.enum_int(Rectangulo(1, 500, 2, 900), Rectangulo(300, 800, 10, 2900), lista)
    for val in lista:
        print val
    
if __name__ == "__main__":
    main()
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.