The program I'm about to do pretends to be a system that counts the passage of cars through porticos, so the program receives several types of commands and does not end until it receives an empty line.
There are three types of commands, which are: PASS 00AA00 I , indicates that the registration vehicle 00AA00 has passed through a portico and that the ticket payment situation is irregular.
If it is PASS 00AA00 R , in this case the car has passed through the portico too, but its ticket payment situation is regular.
o UNFLAG 00AA00 , only changes the ticket payment situation to regulate, that is, if the vehicle with that registration has the irregular situation, passes it to regulate, if it is regular, it is maintained; Finally we have the STATUS 00AA00, this command performs an output, verifying the number of passes of a vehicle with the registration number 00AA00 and its ticket payment situation, if it does not exist, it performs a NO RECORD output.
To solve this problem, I was asked to use the AVL trees and my code is as follows:
import java.util.ArrayList;
import java.util.Scanner;
public class TP2_probB {
static No raiz = null;
static double numRotacoes = 0;
static double numAtravessos = 0;
public static class No {
private String matricula;
private int porticos;
private boolean estadoRegular;
private No pai;
private No filhoEsq;
private No filhoDir;
private int balanceamento;
public No(String matricula, int porticos, boolean estadoRegular) {
this.matricula = matricula;
this.porticos = porticos;
this.estadoRegular = estadoRegular;
this.pai = null;
this.filhoDir = null;
this.filhoEsq = null;
this.balanceamento = 0;
}
public void setEstadoRegular(boolean estadoRegular) {
this.estadoRegular = estadoRegular;
}
public void setPai(No pai) {
this.pai = pai;
}
public void setFilhoEsq(No filhoEsq) {
this.filhoEsq = filhoEsq;
}
public void setFilhoDir(No filhoDir) {
this.filhoDir = filhoDir;
}
public void atribuiNoEsq(No noEsq) {
this.filhoEsq = noEsq;
}
public void atribuiNoDir(No noDir) {
this.filhoDir = noDir;
}
public void atribuiPai(No noPai) {
this.pai = noPai;
}
public void aumentaPortico() {
porticos++;
}
public String getMatricula() {
return matricula;
}
public boolean isEstadoRegular() {
return estadoRegular;
}
public No getPai() {
return pai;
}
public No getFilhoEsq() {
return filhoEsq;
}
public No getFilhoDir() {
return filhoDir;
}
public int getBalanceamento() {
return balanceamento;
}
public void setBalanceamento(int balanceamento) {
this.balanceamento = balanceamento;
}
@Override
public String toString() {
String estado;
if (estadoRegular == true) {
estado = "R";
} else {
estado = "I";
}
return matricula + " " + porticos + " " + estado;
}
}
private static No duplaRotacaoFilhoEsq(No k3)
{
k3.setFilhoEsq(rotacaoFilhoDir(k3));
return rotacaoFilhoEsq(k3);
}
private static No duplaRotacaoFilhoDir(No k3)
{
k3.setFilhoDir(rotacaoFilhoEsq(k3));
return rotacaoFilhoDir(k3);
}
private static No rotacaoFilhoDir(No k1) {
No k2 = k1.getFilhoDir();
k2.setPai(k1.getPai());
k1.setFilhoDir(k2.getFilhoEsq());
if(k1.getFilhoDir()!=null)
{
k1.getFilhoDir().setPai(k1);
}
k2.setFilhoEsq(k1);
k1.setPai(k2);
if(k2.getPai()!=null)
{
if(k2.getPai().getFilhoDir()==k1)
{
k2.getPai().setFilhoDir(k2);
}
else if(k2.getPai().getFilhoEsq()==k1)
{
k2.getPai().setFilhoEsq(k2);
}
}
balanco(k2);
balanco(k1);
return k2;
}
private static No rotacaoFilhoEsq(No k1) {
No k2 = k1.getFilhoEsq();
k2.setPai(k1.getPai());
k1.setFilhoEsq(k2.getFilhoDir());
if(k1.getFilhoEsq()!=null)
{
k1.getFilhoEsq().setPai(k1);
}
k2.setFilhoDir(k1);
k1.setPai(k2);
if(k2.getPai()!=null)
{
if(k2.getPai().getFilhoDir()==k1)
{
k2.getPai().setFilhoDir(k2);
}
else if(k2.getPai().getFilhoEsq()==k1)
{
k2.getPai().setFilhoEsq(k2);
}
}
balanco(k2);
balanco(k1);
return k2;
}
private static int altura(No aux)
{
if(aux == null)
{
return -1;
}
if(aux.getFilhoEsq() == null && aux.getFilhoDir() == null)
{
return 0;
}
else if (aux.getFilhoEsq() == null)
{
return 1 + altura(aux.getFilhoDir());
}
else if (aux.getFilhoDir() == null)
{
return 1 + altura(aux.getFilhoEsq());
}
else
return 1 + Math.max(altura(aux.getFilhoEsq()), altura(aux.getFilhoDir()));
}
private static void balanco(No tmp)
{
tmp.setBalanceamento(altura(tmp.getFilhoDir())-altura(tmp.getFilhoEsq()));
}
public static void main(String args[]) {
Scanner input = new Scanner(System.in);
String linha;
String[] aux;
ArrayList<String> output = new ArrayList<String>();
while (true) {
linha = input.nextLine();
if (linha.isEmpty())
{
break;
}
else
{
aux = linha.split(" ");
if (aux[0].compareTo("PASS") == 0) {
No novo;
if (aux[2].compareTo("R") == 0) {
novo = new No(aux[1], 1, true);
} else {
novo = new No(aux[1], 1, false);
}
if (raiz == null) {
raiz = novo;
balanco(raiz);
} else {
procuraNo(novo);
}
} else if (aux[0].compareTo("UNFLAG") == 0) {
if (raiz != null) {
No no = new No(aux[1], 0, false);
mudaEstado(no);
}
} else if (aux[0].compareTo("STATUS") == 0) {
if (raiz == null) {
output.add(aux[1] + " NO RECORD");
} else {
No no = new No(aux[1], 0, false);
output.add(procuraRegisto(no));
}
}
}
}
for (int i = 0; i < output.size(); i++) {
System.out.println(output.get(i));
}
System.out.println("Número de Rotações: "+numRotacoes+"\nNúmero de atravessias: "+numAtravessos);
}
public static void procuraNo(No novo) {
No aux = raiz;
while (true) {
if (aux.getMatricula().compareTo(novo.getMatricula()) == 0) {
aux.aumentaPortico();
aux.setEstadoRegular(novo.isEstadoRegular());
equilibra(aux);
break;
} else if (aux.getMatricula().compareTo(novo.getMatricula()) < 0) {
if (aux.getFilhoDir() == null) {
novo.setPai(aux);
aux.setFilhoDir(novo);
aux=aux.getFilhoDir();
equilibra(aux);
break;
} else {
aux = aux.getFilhoDir();
numAtravessos++;
}
} else if (aux.getMatricula().compareTo(novo.getMatricula()) > 0) {
if (aux.getFilhoEsq() == null) {
novo.setPai(aux);
aux.setFilhoEsq(novo);
aux=aux.getFilhoEsq();
equilibra(aux);
break;
} else {
aux = aux.getFilhoEsq();
numAtravessos++;
}
}
}
}
public static void equilibra(No tmp) {
balanco(tmp);
int balanco = tmp.getBalanceamento();
if(balanco==-2)
{
if(altura(tmp.getFilhoEsq().getFilhoEsq())>=altura(tmp.getFilhoEsq().getFilhoDir()))
{
tmp = rotacaoFilhoEsq(tmp);
numRotacoes++;
}
else
{
tmp = duplaRotacaoFilhoDir(tmp);
numRotacoes++;
}
}
else if(balanco==2)
{
if(altura(tmp.getFilhoDir().getFilhoDir())>=altura(tmp.getFilhoDir().getFilhoEsq()))
{
tmp = rotacaoFilhoDir(tmp);
numRotacoes++;
}
else
{
tmp = duplaRotacaoFilhoEsq(tmp);
numRotacoes++;
}
}
if(tmp.getPai()!=null)
{
equilibra(tmp.getPai());
}
else
{
raiz = tmp;
}
}
public static void mudaEstado(No novo) {
No aux = raiz;
while (true) {
if (aux.getMatricula().compareTo(novo.getMatricula()) == 0) {
aux.setEstadoRegular(true);
break;
} else if (aux.getMatricula().compareTo(novo.getMatricula()) < 0) {
if (aux.getFilhoDir() == null) {
break;
} else {
aux = aux.getFilhoDir();
numAtravessos++;
}
} else if (aux.getMatricula().compareTo(novo.getMatricula()) > 0) {
if (aux.getFilhoEsq() == null) {
break;
} else {
aux = aux.getFilhoEsq();
numAtravessos++;
}
}
}
}
public static String procuraRegisto(No novo) {
No aux = raiz;
while (true) {
if (aux.getMatricula().compareTo(novo.getMatricula()) == 0) {
return aux.toString();
} else if (aux.getMatricula().compareTo(novo.getMatricula()) < 0) {
if (aux.getFilhoDir() == null) {
return (novo.getMatricula() + " NO RECORD");
} else {
aux = aux.getFilhoDir();
numAtravessos++;
}
} else if (aux.getMatricula().compareTo(novo.getMatricula()) > 0) {
if (aux.getFilhoEsq() == null) {
return (novo.getMatricula() + " NO RECORD");
} else {
aux = aux.getFilhoEsq();
numAtravessos++;
}
}
}
}
}
The error that is occurring to me is StackOverflowError:
Exception in thread "main" java.lang.StackOverflowError
at TP2_probB.altura(TP2_probB.java:179)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
at TP2_probB.altura(TP2_probB.java:186)
I have some test files available at this link link
I hope you can help me because I've tried to solve the problem and without any success, so I'm here to ask for help from the community. Thank you.