[Algoritmos] - Intervalos - Avaliação e ordenação

Olá pessoal…
Estou trabalhando com intervalos em uma aplicação de ordenamento espaço-temporal…Estou comeando a fazer uns testes com manipulação de intervalos. Inicialmente estou trabalhando com geração, avaliação e ordenamento de intervalos, para depois aplicar alguns desses conceitos.

Seguem duas classes que fiz:

public class Intervalo implements Comparable
{
    private float limiteinferior;
    private float limiteSuperior;

    public Intervalo( float limiteinferior,float limiteSuperior)
    {
        this.limiteinferior = limiteinferior;
        this.limiteSuperior = limiteSuperior;
    }

    public float getLimiteInferior()
    {
        return this.limiteinferior;
    }

    public float getLimiteSuperior()
    {
        return this.limiteSuperior;
    }

    public int compareTo(Object intervalo)
    {
        Intervalo outro = (Intervalo)intervalo;
        if(this.limiteinferior<outro.getLimiteInferior() &&
           this.limiteSuperior<=outro.getLimiteSuperior())
        {
            return -1;
        }
        else if(this.limiteinferior>=outro.getLimiteSuperior() &&
                this.limiteSuperior>outro.getLimiteInferior())
        {
            return 1;
        }

        return 0;
    }

    public String toString()
    {
        return "["+this.limiteinferior+","+this.limiteSuperior+"]";
    }
}

Esta classe representa um intervalo com limites reais. entre outras coisas, ela também implementar um critério de comparação entre intervalos, a partir do qual eu consigo verificar qual vem antes de qual.

import java.util.ArrayList;
import java.util.Collections;

public class OrdenaIntervalo
{

    public OrdenaIntervalo(){}

    public ArrayList<Intervalo> ordenaintervalo(ArrayList<Intervalo> intervalos)
    {
        Collections.sort(intervalos);
        return intervalos;
    }

    public ArrayList<Intervalo> geraIntervalos(float inicio, float fim, int quantidade,int maxDistanciaIntervalo)
    {
        ArrayList<Intervalo> intervalos = new ArrayList();

        for(int i=0;i<quantidade;i++)
        {
            float limInferior = 0;
            float limSuperior = 0;
            do
            {
                limInferior = (float)((Math.random()*(fim-inicio))+inicio);
                limSuperior = limInferior+(float)(Math.random()*maxDistanciaIntervalo);
            }
            while(!ehIntervaloValido(limInferior,limSuperior,intervalos));

            intervalos.add(new Intervalo(limInferior,limSuperior));
        }

        return intervalos;
    }

    public boolean ehIntervaloValido(float limInferior, float limSuperior, ArrayList<Intervalo> intervalos)
    {
        /*
        Deve verificar se o intervalo não é sub-intervalo e se não é uma sobreposição
        Exemplo de sub-intervalo: [2,3] é sub-intervalo de [1,4]
        Exemplo de sobreposição: [1,3] sobrepõe [2,4]
        */
        if(!ehSubIntervalo(limInferior,limSuperior, intervalos) &&
           !ehSobreposicao(limInferior,limSuperior,intervalos))
        {
            return true;
        }

        return false;
    }

    public boolean ehSubIntervalo(float limInferior, float limSuperior, ArrayList<Intervalo> intervalos)
    {
        if(!intervalos.isEmpty())
        {
            Intervalo intervalo;
            for(int i=0;i<intervalos.size();i++)
            {
                intervalo = intervalos.get(i);
                if(limInferior>=intervalo.getLimiteInferior() && limSuperior<=intervalo.getLimiteSuperior())
                {
                    return true;
                }

                if(limInferior<=intervalo.getLimiteInferior() && limSuperior>=intervalo.getLimiteSuperior())
                {
                    return true;
                }
            }

            return false;
        }
        else
        {
            return false;
        }
    }

    public boolean ehSobreposicao(float limInferior, float limSuperior, ArrayList<Intervalo> intervalos)
    {
        if(!intervalos.isEmpty())
        {
            Intervalo intervalo;
            for(int i=0;i<intervalos.size();i++)
            {
                intervalo = intervalos.get(i);
                if(limInferior<intervalo.getLimiteInferior() &&
                   limSuperior>intervalo.getLimiteInferior() &&
                   limSuperior<intervalo.getLimiteSuperior())
                {
                    return true;
                }

                if(limInferior>intervalo.getLimiteInferior() &&
                   limInferior<intervalo.getLimiteSuperior() &&
                   limSuperior>intervalo.getLimiteSuperior())
                {
                    return true;
                }
            }

            return false;
        }
        else
        {
            return false;
        }
    }

    public void escreveIntervalos(ArrayList<Intervalo> intervalos)
    {
        for(int i=0;i<intervalos.size();i++)
        {
            System.out.println(intervalos.get(i).toString());
        }
    }

    public static void main(String[] s)
    {
        OrdenaIntervalo ordena = new OrdenaIntervalo();
        System.out.println("Gerando intervalos");
        ArrayList<Intervalo> intervalos = ordena.geraIntervalos(0, 1000, 300,10);
        ordena.escreveIntervalos(intervalos);
        System.out.println("\nOrdenando intervalos");
        intervalos = ordena.ordenaintervalo(intervalos);
        ordena.escreveIntervalos(intervalos);
    }
}

Esta classe oferece métodos para comparar, gerar e verificar se é um intervalo válido. Na aplicação que estou desenvolvendo, um intervalo não pode ser sub-intervalo de outro e não pode sobrepor outro intervalo em algum dos seus limites. O método para gerar intervalos leva em conta o método que avalia se é um intervalo válido e gera N intervalos válidos.

Eu queria saber se alguém consegue propor uma solução melhor que essa para avaliação da validade dos intervalos. Ou seja, tendo um conjunto C com n intervalos, eu preciso avaliar se um dado intervalo i é válido, em função dos n intervalos já definidos em C, respeitando os critérios (não ser sub-intervalo de um intervalo já definido e não sobrepor um intervalo já definido)…

Uso essa classe simples nos meus trabalhos de processamento de imagens. Posso saber quando os intervalos estão em intersecção, ou fazer qualquer operação com eles. Útil para trabalhar em espaço de cores.

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package janvil.core;

/**
 *
 * @author Julio Brito
 */
public class IntRange {

    private int min;

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getMin() {
        return min;
    }

    public void setMin(int min) {
        this.min = min;
    }
    private int max;

    public IntRange(int min, int max) {
        this.min = min;
        this.max = max;
    }
    
    public int getLength(){
        return this.max - this.min;
    }

    public boolean isInside(int x) {
        return ((x >= min) && (x <= max));
    }

    public boolean isInside(IntRange range) {
        return ((isInside(range.getMin)) && (isInside(range.getMax)));
    }

    public boolean isOverlapping(IntRange range) {
        return ((isInside(range.getMin)) || (isInside(range.getMax)));
    }
}

2 Respostas

Topicos relacionados