Procedimiento para la regulación de una asociación de planetas
Enunciado
Procedimientos para la Regulación de una Asociación de Planetas
La Federación Interplanetaria del Sistema Solar Alpha-112 acaba de definir una
normativa de asociación entre sus miembros y desea informatizar alguno de sus
procedimientos. Por el momento, dicha normativa sólo regulará dos cuestiones:
las altas y bajas de planetas en la asociación y el diseño de su red de
comunicaciones.Supondremos que en todo momento habrá M planetas en el sistema, con
identificadores numéricos naturales, pero los valores de dichos identificadores
no estarán acotados. Por otra parte, en todo momento habrá exactamente una
asociación funcionando en el sistema, que puede estar vacía, contener a todos
los planetas o cualquier situación intermedia.Cada planeta del sistema, pertenezca o no a la asociación, es evaluado
periódicamente según N criterios (geográficos, económicos, sociales ...) de
forma que para cada criterio el planeta recibe una puntuación numérica natural.
Los criterios se identifican mediante los valores del intervalo 1..N. Por
último, se considera como criterio adicional que el planeta tenga agua.Paralelamente, la asociación establece un valor mínimo para cada uno de los N
criterios anteriormente mencionados, que han ser alcanzados por los planetas que
deseen entrar en la asociación. Los umbrales mínimos establecidos por la
asociación son actualizables.RED DE COMUNICACIONES
Todos los mensajes de la asociación parten de un planeta especial de la misma,
llamado "emisor" que se encarga de transmitírselos al resto de los planetas
miembros, por medio de la red de la asociación.La red de la asociación funciona de la siguiente manera: si un mensaje llega a
un planeta P cualquiera, éste puede enviárselo a un máximo de dos planetas
predeterminados, llamados los "continuadores" del planeta P. De este modo, el
emisor envía los mensajes a sus continuadores, éstos a los suyos y así
sucesivamente hasta que la información llegue a todos los planetas de la
asociación. Si un planeta tiene dos continuadores, ha de haber una manera de
distinguir entre el primer continuador y el segundo.La red de la asociación ha de cumplir que todos sus miembros estén conectados de
la manera descrita (todos los planetas, salvo el emisor, son continuadores de
algún otro, así no habrá ningún planeta al que no llegue la información).
Obviamente, en el caso de una asociación uniplanetaria, el emisor es el único
planeta que hay. Por otra parte, un planeta no puede ser continuador de sí
mismo, ni de sus continuadores, ni de los continuadores de éstos, etc. Por
último, la red de comunicaciones de la asociación sólo puede cambiar en caso de
altas o bajas de planetas.ALTAS Y BAJAS
* Alta normal:
Cuando un planeta pide ingresar en la asociación, se comprueba si para todos los
criterios, su puntuación es igual o mayor que la pedida por la asociación. En
caso afirmativo, el planeta se convierte en continuador del planeta más cercano
al emisor de la asociación que tenga menos de dos continuadores (de momento, los
casos de empate se pueden resolver de cualquier manera, pero se publicará un
criterio preciso más adelante). Si dicho planeta no tiene continuadores, el
nuevo pasa a ser su primer continuador y, en caso contrario, pasará a ser el
segundo.La distancia entre el emisor y un planeta cualquiera se define como el número de
planetas por los que ha de pasar un mensaje para llegar del uno al otro. La
distancia del emisor a sí mismo es 0. La del emisor a sus continuadores es 1 y
así sucesivamente.* Alta por compensación (sólo se aplica si falla la anterior):
En caso de que el método anterior dé un resultado negativo, un planeta P aún
puede entrar en la asociación con la ayuda de otro planeta Q que ya sea miembro
de la misma, si se cumplen la siguientes condiciones al mismo tiempo:a) Q no tiene agua y P si,
b) está libre la otra posición de continuador del mismo planeta del que Q es
continuador,c) para cada criterio tal que la puntuación de P no llegue al valor mínimo
pedido por la asociación, la suma de la puntuación de P más la puntuación que le
sobre a Q en dicho criterio (la diferencia entre su puntuación y el mínimo),
iguala o supera el valor mínimo definido por la asociación.Si se dan las tres condiciones mencionadas, el planeta P se coloca como
continuador del mismo planeta que Q, que tiene una plaza libre por la condición
b). En caso de que haya varias opciones que permitan entrar a P de esta manera,
se elige la que lo coloque más cerca del emisor, como en el caso anterior.* Baja:
Un planeta puede darse de baja de la asociación sólo si no tiene continuadores.Los requisitos de entrada no se aplican retroactivamente, es decir, si un
planeta ya está en la asociación no le puede expulsar, aunque bajen sus
puntuaciones o suban los requisitos de la asociación.SE PIDE
Diseñar un programa modular razonablemente eficiente que gestione los
procedimientos arriba descritos. En primer lugar, deberá leer la situación
inicial: los datos de todos los planetas y una primera asociación, que podrá ser
cualquiera. Después tendrá que ir procesando las diversas tareas que se le
pidan. Estas podrán ser las siguientes:1) Añadir un planeta a la asociación. Informar de si se ha podido hacer o no.
2) Quitar un planeta de la asociación. Informar de si se ha podido hacer o no.
3) Escribir los identificadores de los planetas de la asociación en orden
creciente.4) Escribir los identificadores de los planetas de la asociación, reflejando la
estructura de la red de comunicaciones.5) Obtener cuál es el mejor planeta para un criterio concreto, de entre los que
no pertenecen a la asociación.6) Modificar las puntuaciones de un planeta cualquiera.
7) Modificar los valores de los requisitos mínimos establecidos por la
asociación.La forma de comunicarse con el programa para que realice dichas tareas será
parecida a la de los casos de estudio de teoría: "Cubeta", "PseudoTetris", etc.
Podéis diseñar un esquema provisional que ya refinaréis cuando conozcáis el
juego de pruebas público.En días sucesivos se publicarán ejemplos gráficos de las situaciones que lo
requieran y se completarán los detalles que se han pasado por alto en este
enunciado.La sintaxis *exacta* de los datos y resultados, acompañada del juego de pruebas
público, se conocerá dos semanas antes del día de la entrega del programa
Java. Hasta entonces no podréis implementar de forma definitiva las operaciones
de lectura y escritura necesarias para los tipos que utilicéis, aunque sí
podréis especificarlas. Podéis consultar el ejemplo del cuatrimestre anterior
para tener una idea aproximada.
PRÁCTICA DE PRAP - JUEGO DE PRUEBAS PÚBLICO Esquema del documento: 0. Observaciones previas. 1. Composición de los juegos de pruebas. 2. Entrada y salida de las operaciones. 3. Juego de pruebas público. -------------------------------------------------- 0. OBSERVACIONES PREVIAS -------------------------------------------------- * El número de planetas será M = 10. De todas formas, el programa debería funcionar (con juegos de pruebas convenientemente adaptados) si M fuera cualquier otro valor mayor que cero. El número de criterios será N = 8. Los identificadores de planetas son números naturales entre 1 y el mayor valor permitido por java para el tipo int. Los identificadores de criterios son los valores 1..N. * Salvo excepciones, los datos de operaciones diferentes se leerán en líneas diferentes y los resultados de operaciones diferentes se escribirán en líneas diferentes. * Los ficheros de entrada de los juegos de pruebas tendrán líneas de menos de 80 caracteres. ------------------------------------------------------------------------------- 1. COMPOSICIÓN DE LOS JUEGOS DE PRUEBAS ------------------------------------------------------------------------------- La primera acción es leer un conjunto de M planetas del siguiente modo: por cada planeta, se lee su id, luego sus N criterios empezando por el primero hasta el octavo y, por último, un booleano que indica si contiene agua. Seguidamente viene la lectura de los miembros de la asociación. Por último, la lectura de los N criterios mínimos de la asociación, en forma de pares <id_criterio, valor>. La asociación se presenta como un árbol binario de enteros (identificadores) recorrido en PREORDEN: primero el emisor, después los continuadores por la izquierda, también en preorden y, por último, los continuadores por la derecha, asimismo en preorden. Notad que identificamos el primer continuador de un planeta con la raíz del subárbol izquierdo que cuelga de él y el segundo continuador con la raíz del subárbol derecho que cuelga de él. Cuando se pida escribir los miembros de la asociación, reflejando la estructura de la red, se hará en INORDEN: primero los continuadores por la izquierda del emisor, también en inorden, después el emisor y, por último, los continuadores por la derecha del emisor, también en inorden. Para más información, consultad el módulo ArbInOutint de la sesión 6 de laboratorio. ------------------------------------------------------------------------------- 2. ENTRADA Y SALIDA DE LAS OPERACIONES ------------------------------------------------------------------------------- Cada operación se identifica mediante un código numérico, que será un entero negativo entre -1 y -8 (esto se ha elegido simplemente para favorecer la legibilidad de los juegos de pruebas). Cada operación comenzará con su código y a éste le seguirán los datos de la misma, si es que necesita alguno. A continuación, detallamos las diferentes operaciones. Para ver ejemplos concretos de la sintaxis de sus entradas y salidas, ir al apartado 3. * AÑADIR UN PLANETA A LA ASOCIACIÓN Identificación: -1 Datos: el id de un planeta del sistema. Se garantiza que el planeta *NO* está en la asociación. Salida: 0 si no se puede añadir, 1 si se añade por el primer método y 2 si es por el segundo. Efectos secundarios: se añade el planeta a la asociación, si se cumplen las condiciones para ello. * QUITAR UN PLANETA DE LA ASOCIACIÓN Identificación: -2 Datos: el id de un planeta del sistema. No se garantiza que el planeta esté en la asociación. Salida: 1 si se puede eliminar, 0 en caso contrario. Efectos secundarios: se elimina el planeta de la asociación, si está en ella y no tiene continuadores. * ESCRIBIR LOS ID'S DE LOS PLANETAS DE LA ASOCIACIÓN EN ORDEN CRECIENTE Identificación: -3 Datos: no tiene Salida: los id's de los planetas de la asociación en orden ascendente. Si la asociación está vacía, no hay salida. Efectos secundarios: no tiene. * ESCRIBIR LOS ID'S DE LOS PLANETAS DE LA ASOCIACIÓN REFLEJANDO LA RED DE COMUNICACIONES DE LA ASOCIACIÓN. Identificación: -4 Datos: no tiene. Salida: los id's de los planetas de la asociación en INORDEN. Si la asociación está vacía, no hay salida. Efectos secundarios: no tiene. * BUSCAR EL MEJOR PLANETA, QUE NO ESTE EN LA ASOCIACIÓN, PARA UN CRITERIO Identificación: -5 Datos: el id del criterio (un valor entre 1 y N). Salida: el id del planeta con mejor puntuación en el criterio dado que no pertenezca a la asociación o 0 si no hay ningún planeta que no esté en la asociación. Si la mejor puntuación es compartida por más de un planeta, se devolverá el que tenga el identificador más pequeño. Efectos secundarios: no tiene. * MODIFICAR LAS PUNTUACIONES DE UN PLANETA CUALQUIERA Identificación: -6 Datos: el id de un planeta del sistema, el número de criterios que se van a leer (un valor entre 1 y N) y, por cada uno de estos, un par <id_criterio, valor> Salida: no tiene. Efectos secundarios: cambian los valores de los criterios leídos del planeta correspondiente. * MODIFICAR LOS REQUISITOS MÍNIMOS DE LA ASOCIACIÓN Identificación: -7 Datos: el número de criterios que se van a modificar (un valor entre 1 y N) y, por cada uno de estos, un par <id_criterio, valor> Salida: no tiene Efectos secundarios: cambian los valores de los requisitos leídos de la asociación. * SALIR DEL PROGRAMA: Identificación: -8 ------------------------------------------------------ 3. JUEGO DE PRUEBAS PÚBLICO ------------------------------------------------------ Entrada comentada: ------------------ 10 2 4 5 6 7 5 3 7 false // Datos de los M planetas: 23 3 4 6 3 2 6 7 4 true // para cada planeta se lee el id, 54 6 6 3 6 9 8 6 7 false // seguido de los N criterios y por último 89 1 3 4 5 3 2 5 6 true // un booleano que indica si tiene agua 79 2 4 2 5 2 7 5 3 true 11 2 4 5 2 2 7 4 3 true 91 4 2 1 5 1 3 6 7 false 51 4 8 6 5 1 2 4 6 true 45 1 5 2 2 4 6 5 5 true 73 6 5 8 7 6 6 5 5 false 23 79 10 0 0 91 0 0 89 54 0 0 0 // Planetas de la asoc. en preorden 1 5 // Requisitos mínimos de la asoc.: 2 5 // el ident. de cada requisito 3 5 // seguido de su valor, en este ejemplo 4 5 // todos los valores son 5 5 5 7 5 6 5 8 5 -4 // escribe la red en inorden -1 // añade un planeta 45 // el id del nuevo planeta es 45 -4 // escribe la red en inorden -1 // añade un planeta 51 // el id del nuevo planeta es 51 -4 // escribe la red en inorden -1 // añade un planeta 73 // el id del nuevo planeta es 73 -4 // escribe la red en inorden -6 // modifica las puntuaciones de un planeta 73 // id del planeta 4 // total de criterios a alterar 5 0 // pares <id_criterio, valor> 2 0 7 0 1 0 -7 // modifica los requisitos mínimos 2 // total de requisitos a modificar 2 1 // id de cada requisito seguido de su valor 6 1 -2 // elimina un planeta de la asoc. 73 // id del planeta a eliminar -4 // escribe la red en inorden -5 // busca el mejor planeta para un criterio 1 // criterio 1 -3 // escribe los ids de los planetas de la asoc. -8 // fin del programa Salida comentada: ----------------- 10 79 91 23 54 89 // red de comunicaciones 0 // el planeta no se puede añadir a la asoc. 10 79 91 23 54 89 // red de comunicaciones 2 // el nuevo planeta se añade por compensación 10 79 91 23 54 89 51 // red de comunicaciones 1 // el nuevo planeta se añade por alta normal 73 10 79 91 23 54 89 51 // red de comunicaciones 1 // el planeta se ha podido quitar 10 79 91 23 54 89 51 // red de comunicaciones 11 // mejor planeta para el criterio 1 que no pertenece a la asoc. 10 23 51 54 79 89 91 // ids de los planetas de la asoc. en orden asc. Al final puede haber una línea en blanco o más. ------------------------------------------------------------------------------- Entrada sin comentar: cortadla y pegadla en un fichero para usarla como entrada a vuestro programa mediante la redirección <. ------------------------------------------------------------------------------- 10 2 4 5 6 7 5 3 7 false 23 3 4 6 3 2 6 7 4 true 54 6 6 3 6 9 8 6 7 false 89 1 3 4 5 3 2 5 6 true 79 2 4 2 5 2 7 5 3 true 11 2 4 5 2 2 7 4 3 true 91 4 2 1 5 1 3 6 7 false 51 4 8 6 5 1 2 4 6 true 45 1 5 2 2 4 6 5 5 true 73 6 5 8 7 6 6 5 5 false 23 79 10 0 0 91 0 0 89 54 0 0 0 1 5 2 5 3 5 4 5 5 5 7 5 6 5 8 5 -4 -1 45 -4 -1 51 -4 -1 73 -4 -6 73 4 5 0 2 0 7 0 1 0 -7 2 2 1 6 1 -2 73 -4 -5 1 -3 -8 ------------------------------------------------------------------------------- Salida sin comentar: vuestro resultado ha de coincidir exactamente con éste (probándolo con el comando diff de unix/linux), salvo las líneas en blanco del final, que pueden variar. ------------------------------------------------------------------------------ 10 79 91 23 54 89 0 10 79 91 23 54 89 2 10 79 91 23 54 89 51 1 73 10 79 91 23 54 89 51 1 10 79 91 23 54 89 51 11 10 23 51 54 79 89 91 ------------------------------------------------------------------------------Joc de proves privat
jp privado 1 10 4 2 5 6 7 5 3 7 false 23 4 3 6 3 2 6 7 4 true 54 6 6 3 6 9 8 6 7 false 89 3 1 4 5 3 2 5 6 true 79 4 2 2 5 2 7 5 3 true 11 4 2 5 2 2 7 4 3 true 91 2 4 1 5 1 3 6 7 false 51 8 4 6 5 1 2 4 6 true 45 5 1 2 2 4 6 5 5 true 73 5 6 8 7 6 6 5 5 false 23 89 10 0 0 91 0 0 79 0 54 0 0 1 5 2 5 3 5 4 5 5 5 7 5 6 5 8 5 -4 -1 51 -4 -1 73 -4 -1 11 -4 -6 73 4 5 0 2 0 7 0 1 0 -7 2 1 1 6 1 -2 54 -4 -5 2 -3 -8 jp privado 2 57 3 4 5 4 3 4 5 4 false 89 4 5 6 4 4 5 6 5 false 33 4 6 4 3 6 7 6 7 true 60 6 7 8 7 8 9 5 7 true 70 3 5 7 8 9 7 4 2 false 91 4 5 3 6 4 6 4 3 true 80 5 6 6 3 5 6 3 2 false 12 5 6 4 7 6 4 6 4 true 13 5 7 5 4 7 4 3 7 false 14 7 6 6 4 7 5 3 7 true 57 89 0 60 0 91 0 0 33 0 70 80 0 0 0 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 -4 -1 12 -4 -1 13 -4 -3 -5 2 -1 14 -4 -3 -5 2 -2 91 -2 91 -2 80 -4 -5 8 -2 14 -2 12 -2 60 -2 89 -2 13 -2 70 -2 33 -4 -3 -2 57 -5 7 -1 14 -4 -3 -8 jp privado 3 57 1 4 5 4 3 4 5 4 false 89 4 1 6 4 4 6 6 9 false 33 4 6 1 3 6 7 6 7 true 60 6 7 8 1 8 9 5 7 true 70 9 9 9 9 1 9 9 9 false 91 9 9 9 9 9 1 9 9 false 80 5 6 6 3 5 6 1 2 true 12 5 6 4 7 6 4 6 1 true 13 1 1 1 1 9 9 1 1 true 14 7 6 6 5 7 3 4 7 true 57 0 89 70 0 33 91 0 0 0 0 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 -4 -1 12 -4 -2 12 -6 12 8 1 1 2 1 3 1 4 1 5 1 6 2 7 2 8 9 -1 12 -1 13 -6 60 1 6 3 -1 60 -4 -1 80 -4 -1 14 -4 -8Solucions als jocs de proves privats
solucion jp privado 1 -- comienza solucion 10 89 91 23 79 54 2 10 89 91 23 51 79 54 1 73 10 89 91 23 51 79 54 0 73 10 89 91 23 51 79 54 1 73 10 89 91 23 51 79 54 10 23 51 73 79 89 91 -- acaba solucion solucion jp privado 2 -- comienza solucion 89 60 91 57 33 80 70 1 12 89 60 91 57 33 80 70 1 12 89 60 91 57 13 33 80 70 12 13 33 57 60 70 80 89 91 14 1 14 12 89 60 91 57 13 33 80 70 12 13 14 33 57 60 70 80 89 91 0 1 0 1 14 12 89 60 57 13 33 70 91 1 1 1 1 1 1 1 57 57 1 12 1 14 14 -- acaba solucion solucion jp privado 3 -- comienza solucion 57 70 91 33 89 2 12 57 70 91 33 89 1 0 2 0 57 70 91 33 89 13 2 57 70 91 33 80 89 13 0 57 70 91 33 80 89 13 -- acaba solucionFitxers: Associacio.java, Planeta.java, Sistema_Solar.java, prap.java
El codi te alguns errors!!
prap.java
import utilsPRAP.InOut;
public class prap{
public static void main (String args[]) throws Exception
{
InOut io = new InOut();
Planeta p = new Planeta();
Sistema_Solar s = new Sistema_Solar();
Associacio a = new Associacio();
s.llegir_sistema_solar(io);
a.llegir_associacio(io,s);
int i = 0;
i = io.readint();
for (;i != -8;)
{
switch (i)
{
case -1:
a.alta_planeta(s,io.readint(),io);
break;
case -2:
a.baixa_planeta(s,io.readint(),io);
break;
case -3:
a.ordena_creixent(io,s);
break;
case -4:
a.ordena_estructura(io);
break;
case -5:
io.write(s.millor_planeta_segons_criteri(io.readint()-1));
io.writeln();
break;
case -6:
p.modificar_criteris_planeta(io.readint(),io,s);
break;
case -7:
a.modificar_requisits_associacio(io);
break;
}
i = io.readint();
}
return;
}
}Sistema_Solar.java
import utilsPRAP.InOut;
public class Sistema_Solar{
private static final int NUM_PLANETES = 10;
private Planeta planetes[];
public void nou_sistema_solar() throws Exception
{
int i=0;
planetes= new Planeta[NUM_PLANETES];
while (i != NUM_PLANETES)
{
planetes[i]= new Planeta();
i++;
}
}
public void llegir_sistema_solar(InOut canal) throws Exception
{
int i=0;
this.nou_sistema_solar();
while (i != NUM_PLANETES)
{
this.planetes[i].llegir_planeta(canal);
i++;
}
}
public int millor_planeta_segons_criteri(int n) throws Exception
{
int id=0;
int i = 0;
int h =0;
boolean trobat = false;
while(!trobat && i != NUM_PLANETES)
{
if (!this.planetes[i].consultar_pertany_associacio())
{
id =this.planetes[i].consultar_identificador();
h=i+1;
trobat = true;
}
else
{
i++;
}
}
if (trobat)
{
while (h < NUM_PLANETES)
{
if (!this.planetes[h].consultar_pertany_associacio())
{
if (this.planetes[h].consultar_criteri_planeta(n) > consulta_planeta(id).consultar_criteri_planeta(n))
{
id = this.planetes[h].consultar_identificador();
}
else if (this.planetes[h].consultar_criteri_planeta(n) == consulta_planeta(id).consultar_criteri_planeta(n))
{
if (this.planetes[h].consultar_identificador() < id)
{
id = this.planetes[h].consultar_identificador();
}
}
}
h++;
}
}
return id;
}
public Planeta consulta_planeta(int id) throws Exception
{
int i=0;
boolean b=false;
while(!b && i != NUM_PLANETES)
{
if (this.planetes[i].consultar_identificador()==id)
{
b=true;
}
else
{
i++;
}
}
return planetes[i];
}
public int[] consulta_planetes_associacio() throws Exception
{
int[] vector= new int[NUM_PLANETES];
int g=0;
while (g != NUM_PLANETES)
{
vector[g]=-1;
g++;
}
int i = 0;
int h=0;
while(i != NUM_PLANETES)
{
if (this.planetes[i].consultar_pertany_associacio())
{
vector[h]=this.planetes[i].consultar_identificador();
h++;
}
i++;
}
return vector;
}
}Planeta.java
import utilsPRAP.InOut;
public class Planeta{
private static final int MAX_CRITERIS = 8;
private int identificador;
private int criteris[];
private boolean pertany_associacio;
private boolean te_aigua;
public void nou_planeta(int id) throws Exception
{
criteris = new int[MAX_CRITERIS];
int i=0;
identificador=id;
while ( i != MAX_CRITERIS)
{
criteris[i]=0;
i++;
}
pertany_associacio= false;
te_aigua= false;
}
public void llegir_planeta(InOut canal) throws Exception
{
this.nou_planeta(canal.readint());
int i = 0;
while(i != MAX_CRITERIS)
{
this.criteris[i]= canal.readint();
i++;
}
this.modifica_aigua(canal.readboolean());
}
public void modificar_criteris_planeta(int id, InOut canal, Sistema_Solar s) throws Exception
{
int i = 0;
int num = canal.readint();
while (i != num)
{
s.consulta_planeta(id).criteris[canal.readint()-1]=canal.readint();
i=i+1;
}
}
public void modifica_pertinenca(boolean b) throws Exception
{
this.pertany_associacio=b;
}
public void modifica_aigua(boolean b) throws Exception
{
this.te_aigua=b;
}
public int consultar_identificador() throws Exception
{
return identificador;
}
public int consultar_criteri_planeta(int i) throws Exception
{
return criteris[i];
}
public boolean consultar_pertany_associacio() throws Exception
{
return pertany_associacio;
}
public boolean consultar_aigua() throws Exception
{
return te_aigua;
}
}
Associacio.java
import utilsPRAP.InOut;
import tadsPRAP.Arbol;
import tadsPRAP.EmptyTreeException;
public class Associacio{
private static final int MAX_REQUISITS = 8;
private Arbol estructura;
private int requisits[];
public void nova_associacio() throws Exception
{
requisits = new int[MAX_REQUISITS];
int i=0;
estructura=null;
while(i != MAX_REQUISITS)
{
requisits[i]=0;
i++;
}
}
public void llegir_associacio(InOut canal, Sistema_Solar s) throws Exception
{
int i=0;
this.nova_associacio();
estructura = llegir_arbre_int(0, canal,s);
while(i != MAX_REQUISITS)
{
requisits[canal.readint()-1]=canal.readint();
i++;
}
}
public Arbol llegir_arbre_int(int marca, InOut canal, Sistema_Solar s) throws Exception
{
Arbol b, c;
int x = canal.readint ();
Integer wx = new Integer (x);
if (x != marca)
{
s.consulta_planeta(x).modifica_pertinenca(true);
b = llegir_arbre_int (marca, canal,s);
c = llegir_arbre_int (marca, canal,s);
b.plantar (wx, c);
}
else
{
b = new Arbol ();
b.a_nulo ();
}
return b;
}
public void alta_planeta(Sistema_Solar s, int id, InOut canal) throws Exception
{
if (comparar_requisits(s,id))
{
if (this.estructura.es_nulo())
{
Arbol aux1 = new Arbol();
Arbol aux3= new Arbol();
aux1.a_nulo();
Integer idx = new Integer(id);
aux3.plantar(idx,aux1,aux1);
this.estructura.copiar_arbol(aux3);
s.consulta_planeta(id).modifica_pertinenca(true);
canal.writeln(1);
}
else
{
int[] vecc = new int[20];
int f=0;
while (f < 20)
{
vecc[f]=-1;
vecc[f+1]=0;
f=f+2;
}
vecc = cerca_planeta_normal(this.estructura,s,id,vecc,0);
int pdd = menor_distancia(vecc);
if (pdd != -1)
{
this.estructura.copiar_arbol(alta_plan(this.estructura,id,pdd,s));
s.consulta_planeta(id).modifica_pertinenca(true);
canal.writeln(1);
}
}
}
else
{
if (s.consulta_planeta(id).consultar_aigua())
{
if (this.estructura.es_nulo())
{
canal.writeln(0);
}
else
{
int[] vec = new int[20];
int i=0;
while (i < 20)
{
vec[i]=-1;
vec[i+1]=0;
i=i+2;
}
vec = cerca_planeta_compens(this.estructura,s,id,vec,0);
int pd = menor_distancia(vec);
if (pd != -1)
{
this.estructura.copiar_arbol(alta_plan(this.estructura,id,pd,s));
s.consulta_planeta(id).modifica_pertinenca(true);
canal.writeln(2);
}
else
{
canal.writeln(0);
}
}
}
else
{
canal.writeln(0);
}
}
}
private int menor_distancia( int[] vector) throws Exception
{
int i =0;
int id=-1;
int prof =12;
while(i < 20)
{
if (vector[i] != -1)
{
if (vector[i+1] < prof)
{
id = vector[i];
prof = vector[i+1];
}
}
i=i+2;
}
return id;
}
private int[] cerca_planeta_normal(Arbol a, Sistema_Solar s, int id, int[] vector, int res) throws Exception
{
Arbol aux1, aux2;
int[] c,d;
if (a.es_nulo())
{
res =0;
}
else
{
aux1 = new Arbol();
aux2 = new Arbol();
c = new int[20];
d = new int[20];
try
{
aux1.hi(a);
aux2.hd(a);
Integer wraiz = (Integer) a.raiz();
c=cerca_planeta_normal(aux1,s,id, vector, res+1);
d=cerca_planeta_normal(aux2,s,id, vector, res+1);
if (aux1.es_nulo())
{
desa(wraiz.intValue(),res, vector);
}
else if (aux2.es_nulo())
{
desa(wraiz.intValue(),res, vector);
}
else if (aux1.es_nulo() && aux2.es_nulo())
{
desa(wraiz.intValue(),res, vector);
}
}
catch (EmptyTreeException e)
{
System.err.println("Error en cerca_planeta_normal");
}
}
return vector;
}
private int[] cerca_planeta_compens(Arbol a, Sistema_Solar s, int id, int[] vector, int res) throws Exception
{
Arbol aux1, aux2;
int[] c,d;
if (a.es_nulo())
{
res =0;
}
else
{
aux1 = new Arbol();
aux2 = new Arbol();
c = new int[20];
d = new int[20];
try
{
aux1.hi(a);
aux2.hd(a);
Integer wraiz = (Integer) a.raiz();
c=cerca_planeta_compens(aux1,s,id, vector, res+1);
d=cerca_planeta_compens(aux2,s,id, vector, res+1);
if (aux1.es_nulo() || aux2.es_nulo())
{
if (!aux1.es_nulo() || !aux2.es_nulo())
{
if ( !aux1.es_nulo())
{
Integer ali = (Integer) aux1.raiz();
if (!s.consulta_planeta(ali.intValue()).consultar_aigua())
{
if (compara_compens(s,id,ali.intValue()))
{
desa(wraiz.intValue(),res, vector);
}
}
}
else
{
Integer adi = (Integer) aux2.raiz();
if (!s.consulta_planeta(adi.intValue()).consultar_aigua())
{
if (compara_compens(s,id,adi.intValue()))
{
desa(wraiz.intValue(),res, vector);
}
}
}
}
}
}
catch (EmptyTreeException e)
{
System.err.println("Error en cerca_planeta_compensa");
}
}
return vector;
}
private void desa(int h, int p, int[] vector) throws Exception
{
int i = 0;
boolean b= false;
while(!b && i < 20)
{
if (vector[i] == -1)
{
vector[i] = h;
vector[i+1] = p;
b=true;
}
i=i+2;
}
}
private Arbol alta_plan(Arbol a, int id, int padre, Sistema_Solar s) throws Exception
{
Arbol aux1, aux2, aux3,c,d;
aux3= new Arbol();
if (!a.es_nulo())
{
aux1 = new Arbol();
aux2 = new Arbol();
c=new Arbol();
d= new Arbol();
try
{
aux1.hi(a);
aux2.hd(a);
Integer wraiz = (Integer) a.raiz();
if (wraiz.intValue()==padre)
{
Integer idx = new Integer(id);
Arbol aux0 = new Arbol();
aux0.a_nulo();
if (aux1.es_nulo())
{
aux1.plantar(idx,aux0, aux0);
aux3.plantar(wraiz,aux1,aux2);
}
else
{
aux2.plantar(idx,aux0, aux0);
aux3.plantar(wraiz,aux1,aux2);
}
}
else
{
c=alta_plan(aux1,id,padre,s);
d=alta_plan(aux2,id,padre,s);
aux3.plantar(wraiz,c,d);
}
}
catch (EmptyTreeException e)
{
System.err.println("Error en alta_plan");
}
}
return aux3;
}
private boolean compara_compens(Sistema_Solar s, int p, int q) throws Exception
{
int i=0;
boolean b = true;
while( b && i != MAX_REQUISITS)
{
int m = s.consulta_planeta(p).consultar_criteri_planeta(i);
if (m < this.requisits[i])
{
int n = s.consulta_planeta(q).consultar_criteri_planeta(i);
if (m + n - this.requisits[i] < this.requisits[i])
{
b=false;
}
}
i++;
}
return b;
}
public void baixa_planeta(Sistema_Solar s, int id, InOut canal) throws Exception
{
if (s.consulta_planeta(id).consultar_pertany_associacio())
{
Arbol dd = new Arbol();
dd.copiar_arbol(intenta_baixa(s,this.estructura,id, canal));
this.estructura.copiar_arbol(dd);
}
else
{
canal.writeln(0);
}
}
public Arbol intenta_baixa(Sistema_Solar s,Arbol a,int id, InOut canal) throws Exception
{
Arbol aux1, aux2, aux3,c,d;
aux3= new Arbol();
if (!a.es_nulo())
{
aux1 = new Arbol();
aux2 = new Arbol();
c=new Arbol();
d= new Arbol();
try
{
aux1.hi(a);
aux2.hd(a);
Integer wraiz = (Integer) a.raiz();
if (wraiz.intValue()==id)
{
if ( aux1.es_nulo() && aux2.es_nulo())
{
a.a_nulo();
s.consulta_planeta(id).modifica_pertinenca(false);
canal.writeln(1);
}
else
{
canal.writeln(0);
aux3.plantar(wraiz,aux1,aux2);
}
}
else
{
c=intenta_baixa(s,aux1,id,canal);
d=intenta_baixa(s,aux2,id,canal);
aux3.plantar(wraiz,c,d);
}
}
catch (EmptyTreeException e)
{
System.err.println("Error en intenta_baixa");
}
}
return aux3;
}
public int[] consultar_requisits_associacio() throws Exception
{
return this.requisits;
}
public void modificar_requisits_associacio(InOut canal) throws Exception
{
int i =0;
int x = canal.readint();
while( i != x)
{
this.requisits[canal.readint()-1] = canal.readint();
i++;
}
}
public boolean comparar_requisits(Sistema_Solar s, int id) throws Exception
{
int i =0;
boolean b =false;
while (!b && i != MAX_REQUISITS)
{
if (this.requisits[i] > s.consulta_planeta(id).consultar_criteri_planeta(i))
{
b= true;
}
i++;
}
return !b;
}
public void ordena_creixent(InOut canal, Sistema_Solar s) throws Exception
{
if (!this.estructura.es_nulo())
{
int h =0;
int[] vector = new int[10];
vector=s.consulta_planetes_associacio();
qsort (vector,0,vector.length-1);
while (h!= vector.length)
{
if (vector[h] != -1)
{
canal.write(vector[h]+" ");
}
h++;
}
canal.writeln();
}
}
private void qsort (int v[], int p, int q) throws Exception
{
if (p < q)
{
int m = particio (v,p,q);
qsort (v,p,m-1);
qsort (v,m+1,q);
}
}
private int particio (int v[], int p, int q) throws Exception
{
int z = v[p];
int f = q;
int m = p+1;
while (m <= f)
{
if (v[f] < z)
{
int aux = v[f]; v[f] = v[m]; v[m] = aux;
m = m+1;
}
else
{
f = f-1;
}
}
m = f; v[p] = v[m]; v[m] = z;
return m;
}
public void ordena_estructura(InOut canal) throws Exception
{
if (!this.estructura.es_nulo())
{
escriure_arbol_int(this.estructura, canal);
canal.writeln();
}
}
public void escriure_arbol_int(Arbol a, InOut io) throws Exception
{
Arbol aux1, aux2;
if (!a.es_nulo())
{
aux1 = new Arbol();
aux2 = new Arbol();
try
{
aux1.hi(a);
aux2.hd(a);
escriure_arbol_int(aux1,io);
Integer wraiz = (Integer) a.raiz();
io.write(wraiz.intValue()+" ");
escriure_arbol_int(aux2,io);
}
catch (EmptyTreeException e)
{
System.err.println("Error en escribir_arbol");
}
}
}
}