Realizando busca em Array

Normalmente nos encontramos em uma situação onde temos um grupo de dados e desejamos verificar se existe um dado em particular neste conjunto. Este tipo de pesquisa é uma atividade corriqueira para programadores. Também não é incomum que estes dados estejam no formato de um array. Em Java, um Array é uma estrutura de dados que armazena elementos (números, strings, objetos) e infelizmente não possui um método para verificar se um elemento pertence a ele ou não. Este tipo de procedimento é encontrado em outras classes Java como em ArrayList e HashSet (são coleções Java).

Como fazemos então para buscar um elemento de um array?

Vou tentar esclarecer algumas formas de realizar busca em um array:

1) Realizar a busca convertendo o Array em um ArrayList
A classe ArrayList possui um método denominado contains() que retorna true se o objeto passado para ele estiver contido no ArrayList. Desta forma realizando a conversão com Array.asList() é possível realizar a busca.

2) Realizar a busca convertendo o Array em um HashSet
Da mesma forma que em ArrayList, podemos utilizar HashSet que apresenta o método contains(). Este método apresenta tempo de busca O(1), isto é, a busca tem tempo constante.

3) Realizar a busca utilizando Arrays.binarySearch()
A busca binária também é um método rápido de pesquisa mas os dados precisam estar ordenados, por isto temos que utilizar o método java.util.Arrays.sort() antes de fazer a busca. Precisamos notar que sort() ordena o próprio array e binarySearch() retorna a posição do array que foi encontrado ou um número negativo caso não tenha achado.

4) método da força bruta
Fazemos uma varredura nos elementos do array utilizam algum tipo de loop. NO nosso caso, preferi utilizar o foreach que provê um Iterator. A pesquisa é O(n) e por isto é o pior método dos relacionados acima.

Vamos ver nosso exemplo:

Veja que para imprimirmos o Array foi necessário convertê-lo em String. Isto foi facilmente realizado utilizando Arrays.toString().

Para converter o Array em uma lista também foi fácil. Bastou utilizar Arrays.asList(). E para conseguirmos o HashSet, converti o List do exemplo 1 utilizando HashSet<E>( List<E> ).

Para obtermos o array ordenado fiz um processo de duas etapas. Primeiro, copiei o array original para um novo array utilizando Arrays.copyOf( array, array.length). array.length está sendo utilizando para dizer a copyOf() que deve copiar todos os elementos. A etapa final foi ordenar que foi conseguido usando Arrays.sort(). Note que passamos como parâmetro o array a ser ordenado.

Tendo o array ordenado, a busca binária foi fácil.


A saída do programa é:

Ainda podemos utilizar a classe org.apache.commons.lang.ArrayUtils para realizar buscas em arrays. Podemos utilizar ArrayUtils.contains() e ArrayUtils.indexOf() para localizar um valor em arrays dos tipos primitivos do Java. Para que funcione é necessário que você baixe a biblioteca, inclua no seu arquivo .java com import e altere seu classpath para o local onde a biblioteca está.

Vamos alterar nosso programa um pouco para verificar esta opção também.

Criamos uma classe adicional com métodos estáticos para realizar o trabalho. Na classe original, adicionamos as chamadas para o exemplo 5 e 6.

Na primeira opção (exemplo 5) utilizei o ArrayUtils.contains() e no outro ArrayUtils.indexOf(). Notem que tive que realizar o import da classe para que o funcionasse e como estou no ambiente do NetBeans, acrescentei a biblioteca em um diretório denominado lib dentro do meu projeto:

Exemplos de String.replace()

Veremos neste post 4 métodos para substituir conteúdo em uma classe String que permitem trocar um caracter, uma sequência de caracteres, todas as ocorrência de uma padrão ou a primeira ocorrência de um padrão.

1. utilizando o método Replace para trocar um caracter
Este método pega um caracter (primeiro parâmetro da chamada) e troca todas as ocorrências deste pelo novo caracter (segundo parâmetro de passagem). O formato da chamada é:

String.replace(char caracterAntigo, char caracterNovo)

Este método retorna uma nova String com os caracteres substituídos. A troca é sensível ao caso, portanto uma chamada com "r" não irá trocar as ocorrências de "R". Se não for encontrado o caracter, a String será retornada como foi passada.


String exemplo = "O rato roeu a roupa do rei de Roma.";
String nova = exemplo.replace('r', 't');

Saída:
O tato toeu a toupa do tei de Roma.


2. utilizando o método Replace para trocar uma sequência de caracteres
Este método troca uma sequência de caracteres pela outra. As sequências não podem ser nulas. Caso alguma seja, será gerado um erro do tipo NullPointerException. A troca é feita do início para o final, assim se temos uma String originalmente igual a "ccc" e realizamos um replace("cc", "d"), o resultado final será "dc". O formato do método é:

String replace(CharSequence aSerTrocado, CharSequence trocarPor)

String exemplo = "String de exemplo para procedimento de troca de caracteres.";
String nova = exemplo.replace("ro", "RO");

Saída:
String de exemplo para pROcedimento de tROca de caracteres.



3. utilizando o método ReplaceAll com expressões regulares
Se você vem do ambiente Windows ou de programação em linguagem como Delphi ou VB provavelmente não está acostumado com as regex. Estas expressões permitem que realizemos operações de busca e substituição bastante complexas em String. O formato do método é:

replaceAll(String regex, String sequenciaSubstituta)

Uma boa fonte de consulta são alguns posts que já coloquei no blog a algum tempo. Dê uma olhada nos posts denominados Expressões Regulares.

String exemplo = "Exemplo de troca de caracteres utilizando expressões regulares.";
String novo = exemplo.replaceAll("^r","S");

Output:
Exemplo de troca de caracteres utilizando expressões Segulares.

A expressão ^r indica que o programa irá procurar as palavras iniciadas com "r". O método irá localizar estes casos e trocar a letra "r" por "S" como vimos no resultado apresentado.

Se a expressão regular não for válida, o método replaceAll() irá gerar uma exceção do tipo PatternSyntaxException.



4. utilizando o método ReplaceFirst
Funciona com no exemplo 3, porém somente realiza a troca da primeira ocorrência da sequência de caracteres.

replaceFirst(String regex, String sequenciaSubstituta)

String exemplo = "Exemplo de troca de caracteres utilizando expressões regulares com replaceFirst";
String novo = exemplo.replaceFirst("re","SE");

Output:
Exemplo de troca de caracteSEs utilizando expressões regulares com replaceFirst

A segunda ocorrência de "re" não é trocada.

Trabalhando com XML e DOM Parser - Parte II

Para que nosso programa funcionasse lançamos mão de diversas classes e métodos. Vamos ver os principais:

1) javax.xml.parsers.DocumentBuilderFactory

Esta classe permite que a aplicação obtenha um parser que produz árvores DOM a partir de objetos XML. Esta classe possui um construtor protegido que impede que um objeto seja instanciado, assim chamamos diretamente a classe estática gerada por DocumentBuilderFactory.newInstance().

2) javax.xml.parsers.DocumentBuilder

Com a nova instância criada podemos chamar o método newDocumentBuilder() para obtermos um novo DocumentBuilder. Esta é a forma de obtermos um Document a partir de um arquivo XML. De posse do objeto desta classe, podemos ler (parse) o documento XML de diversas fontes de entrada: InputStreams, arquivos, URLs e fontes SAX. No nosso caso iremos ler um arquivo utilizando Document.parse( File f ).

3) Document.getElementsByTagName( String nomeDaTag )

Este método convenientemente retorna para nós a lista de elementos de uma tag contida no documento. Esta lista é um objeto da classe NodeList. O nosso exemplo estamos procurando os registros dos deuses que está sob a tag <deus>. Com esta lista podemos fazer um loop varrendo cada entrada e a partir daí processar as demais tags filhas.

Notem que o procedimento é igual para as tags filhas.
Temos que tomar algumas precauções adicionais que consistem em verificar se alguma coisa está sendo retornada da nossa pesquisa, pois senão ao tentarmos acessar .item(0) obtemos um erro.

Espero que a lógica do programa tenha ficado clara. Senão postem os comentários, que tento esclarecer melhor.