Primeiro, a tarefa:
Crie uma nova classe Map, agora usando o nome SortedMap. Ela deve ter os mesmos métodos da classe Map da tarefa anterior, e aceitar como tipo Chave um tipo K que implemente a interface Comparable. O array de pares Chave, Valor deve ser mantido ordenado. Para isso, a cada inserção busque a posição correta para inserir e mova todos os elementos posteriores do array uma posição.
O método find pode agora realizar um pesquisa binária (chame o método pesquisa binária dado no laboratório).
Esse é um trabalho de laboratório, portanto eu já realizei a implementação da classe Map e já fiz algumas alterações para implementar a SortedMap. Fiz a troca dos tipos para 'K' e 'V'. Colocarei o código a seguir e será mais fácil de visualizar.
Implementação da classe Map:
public class Map {
public static class Pair {
Object key, value;
}
Pair[] m;
/*
* Construtor da classe Map
* Inicializa um array com tamanho 2 e inicializa cada espaço desse array com os atributos Object key e value
*/
public Map () {
m = new Pair[2];
//Atentar à esse detalhe! Cada espaço do array M ta sendo inicializado com os atributos do tipo Pair
for( int i = 0; i < m.length; i++ )
m[i] = new Pair();
}
/*
* Método put: associa o valor a chave. Se a chave nao existir, encontra um espaço vazio (que se não houver, é aumentado o tamanho do array).
* Caso a chave exista, atualiza-se o valor correspondente
*/
public void put(Object key, Object value) {
int posicao = find(key);
if( posicao == -1 ) {
posicao = makeRoom();
m[posicao].key = key;
}
m[posicao].value = value;
}
/*
* Método expand: dobra o tamanho do array e inicializa todos os espaços gerados com atributos da classe Pair
*/
private void expand () {
Pair[] newVector = new Pair[m.length*2];
for ( int i = 0; i < m.length; i++ )
newVector[i] = m[i];
for( int i = m.length; i < newVector.length; i++ )
newVector[i] = new Pair();
m = newVector;
}
/*
* Método find: localiza uma chave no array, se não encontrar, retorna -1
*/
private int find(Object key) {
for( int i = 0; i < m.length; i++ )
if(key.equals(m[i].key))
return i;
return -1;
}
/*
* Método get: retorna o valor correspondente a chave. Se não encontrar a chave, retorna null
*/
public Object get(Object key) {
int posicao = find(key);
if( posicao == -1 )
return null;
else
return m[posicao].value;
}
/*
* Método remove: remove o valor e a chave passada, caso existam
*/
public void remove (Object key) {
int posicao = find(key);
if( posicao != -1 ) {
m[posicao].key = null;
m[posicao].value = null;
}
}
/*
* Método keys: cria e retorna um array com todas as CHAVES presentes na estrutura
*/
public Object[] keys () {
Object[] allKeys = new Object[numKeys()];
for( int i = 0, j = 0; i < m.length; i++ )
if( m[i].key != null )
allKeys[j++] = m[i].key;
return allKeys;
}
/*
* Método numKeys: Conta quantas chaves foram declaradas na estrutura e retorna o valor
*/
public int numKeys () {
int totalKeys = 0;
for( int i = 0; i < m.length; i++ )
if( m[i].key != null )
totalKeys++;
return totalKeys;
}
/*
* Método makeRoom: busca por espaço null e retorna a posição. Caso não encontre, dobra o tamanho do array e retorna a primeira posição livre do novo array
*/
private int makeRoom() {
for( int i = 0; i < m.length; i++ )
if( m[i].key == null )
return i;
int posicao = m.length;
expand();
return posicao;
}
}
Implementação da SortedMap (classe Map com os tipos alterados para utilização de Generics).
public class SortedMap<K, V> implements Comparable<K> {
public static class Pair {
Object key, value;
}
Pair[] m;
/*
* Construtor da classe Map
* Inicializa um array com tamanho 2 e inicializa cada espaço desse array com os atributos Object key e value
*/
public SortedMap () {
m = new Pair[2];
//Atentar à esse detalhe! Cada espaço do array M ta sendo inicializado com os atributos do tipo Pair
for( int i = 0; i < m.length; i++ )
m[i] = new Pair();
}
/*
* Método put: associa o valor a chave. Se a chave nao existir, encontra um espaço vazio (que se não houver, é aumentado o tamanho do array).
* Caso a chave exista, atualiza-se o valor correspondente
*/
public void put(K key, V value) {
int posicao = find(key);
if( posicao == -1 ) {
posicao = makeRoom();
m[posicao].key = key;
}
m[posicao].value = value;
}
/*
* Método expand: dobra o tamanho do array e inicializa todos os espaços gerados com atributos da classe Pair
*/
private void expand () {
Pair[] newVector = new Pair[m.length*2];
for ( int i = 0; i < m.length; i++ )
newVector[i] = m[i];
for( int i = m.length; i < newVector.length; i++ )
newVector[i] = new Pair();
m = newVector;
}
/*
* Método find: localiza uma chave no array, se não encontrar, retorna -1
*/
private int find(K key) {
pesquisaBinaria(key, m, 0, m.length);
return -1;
}
/*
* Método get: retorna o valor correspondente a chave. Se não encontrar a chave, retorna null
*/
@SuppressWarnings("unchecked")
public V get(K key) {
int posicao = find(key);
if( posicao == -1 )
return null;
else
return (V) m[posicao].value;
}
/*
* Método remove: remove o valor e a chave passada, caso existam
*/
public void remove (K key) {
int posicao = find(key);
if( posicao != -1 ) {
m[posicao].key = null;
m[posicao].value = null;
}
}
/*
* Método keys: cria e retorna um array com todas as CHAVES presentes na estrutura
*/
@SuppressWarnings( "unchecked" )
public Vector<K> keys() {
Vector<K> keySet = new Vector<K>(numKeys());
for( int i = 0, j = 0; i < m.length; i++ )
if( m[i].key != null )
keySet.put(j++, (K) m[i].key );
return keySet;
}
/*
* Método numKeys: Conta quantas chaves foram declaradas na estrutura e retorna o valor
*/
public int numKeys () {
int totalKeys = 0;
for( int i = 0; i < m.length; i++ )
if( m[i].key != null )
totalKeys++;
return totalKeys;
}
/*
* Método makeRoom: busca por espaço null e retorna a posição. Caso não encontre, dobra o tamanho do array e retorna a primeira posição livre do novo array
*/
private int makeRoom() {
for( int i = 0; i < m.length; i++ )
if( m[i].key == null )
return i;
int posicao = m.length;
expand();
return posicao;
}
public static <K extends Comparable<K>> int pesquisaBinaria( K key, K m, int begin, int end ) {
int i = (begin + end) / 2;
if( m[i] == key )
return i;
if( begin >= end )
return -1; // Não foi encontrado
else if( m[i].compareTo( key ) < 0 )
return pesquisaBinaria( key, m, i + 1, end );
else
return pesquisaBinaria( key, m, begin, i - 1 );
}
@Override
public int compareTo(K o) {
return 0;
}
}
O problema ocorre quando eu chego no método 'keys()'. Preciso criar uma classe Vector, porque não há como, no método keys(), retornar um Vetor de tipo genérico. Então pelo que eu entendi da explicação do professor, eu devo criar uma classe Vector (ele colocou uma como exemplo, mas eu gostaria de fazer a minha para aprender e entender como tudo está funcionando). O penúltimo é a buscaBinaria() dada em laboratório e que deve ser implementada no método find(). O último método é o compareTo, que precisa ser implementado mas eu não sei como fazê-lo.
Se eu não tiver sido claro na dúvida, é só perguntar. Obrigado! :)
CLASSES PARA TESTE DO PROGRAMA -- PROFESSOR
Atentar ao fato de que alguns métodos do professor estão com nomes diferentes no meu código
Implementação da SortedMap:
// Generics: construção que permite passar um tipo como parâmetro
// Pode ser usado para Classes e para métodos.
public class Map< Tipo_Key, Tipo_Value > {
public static class Pair {
// Transformando o map em String => Integer
public Object key;
public Object value;
}
Pair[] m;
public Map() {
m = new Pair[2];
for( int i = 0; i < m.length; i++ )
m[i] = new Pair();
}
/**
* Expande o array m.
*/
private void expand() {
Pair[] novo = new Pair[2 * m.length];
for( int i = 0; i < m.length; i++ )
novo[i] = m[i];
for( int i = m.length; i < novo.length; i++ )
novo[i] = new Pair();
m = novo;
}
/**
*
* @param key
* A chave que vai ser inserida. Não pode ser null.
* @param value
* O valor a ser associado a esta chave
*/
public void put( Tipo_Key key, Tipo_Value value ) {
int posicao = find( key );
if( posicao == -1 ) {
posicao = makeRoom();
m[posicao].key = key;
}
m[posicao].value = value;
}
private int find( Tipo_Key key ) {
for( int i = 0; i < m.length; i++ )
if( key.equals( m[i].key ) )
return i;
return -1;
}
/**
* Encontra uma chave null. Se for preciso, expande o array m.
*
* @return
*/
private int makeRoom() {
for( int i = 0; i < m.length; i++ )
if( m[i].key == null )
return i;
int posicao = m.length;
expand();
return posicao;
// ou return m.length - 1;
}
/**
* Retorna o valor associado a uma chave.
*
* @param key
* a chave
* @return o valor associado, ou null.
*/
@SuppressWarnings( "unchecked" )
public Tipo_Value get( Tipo_Key key ) {
int posicao = find( key );
return posicao == -1 ? null : (Tipo_Value) m[posicao].value;
}
/**
* Retorna o número de chaves não nulas no map
*
* @return o número de chaves.
*/
public int getNumKeys() {
int numKeys = 0;
for( int i = 0; i < m.length; i++ )
if( m[i].key != null )
numKeys++;
return numKeys;
}
/**
* Remove uma chave e o seu valor do Map. Se não encontrar, não faz nada.
*
* @param key
* A chave do valor a ser removido
*/
public void remove( Tipo_Key key ) {
int posicao = find( key );
if( posicao != -1 ) {
m[posicao].key = null;
m[posicao].value = null;
}
}
}
Implementação do método keys():
/**
* Retorna um array contendo todas as chaves no map.
*
* @return o array de chaves.
*/
@SuppressWarnings( "unchecked" )
public Vector<Tipo_Key> keys() {
Vector<Tipo_Key> keySet = new Vector<Tipo_Key>(getNumKeys());
for( int i = 0, j = 0; i < m.length; i++ )
if( m[i].key != null )
keySet.put(j++, (Tipo_Key) m[i].key );
return keySet;
}
Implementação da classe Vector: Pelo que eu entendi, não é possível retornar um vetor de tipo genérico no método keys, sendo necessário criar essa classe
public class Vector<T> {
private Object o[];
public Vector( int size ) {
o = new Object[size];
}
public void resize( int newSize ) {
Object novo[] = new Object[newSize];
for( int i = 0; i < o.length; i++ )
novo[i] = o[i];
}
public void put( int i, T value ) {
o[i] = value;
}
@SuppressWarnings( "unchecked" )
public T at( int i ) {
return (T) o[i];
}
public String toString() {
String aux = "[";
for( int i = 0; i < o.length - 1; i++ )
aux += o[i] + ",";
if( o.length > 0 )
aux += o[o.length - 1];
return aux + "]";
}
public int find( T value ) {
for( int i = 0; i < o.length; i++ )
if( o[i].equals( value ) )
return i;
return -1;
}
public int size() {
return o.length;
}
}
Implementação da buscaBinaria() dada em laboratório:
public static <T extends Comparable<T>> int pesquisaBinaria( T key, T v[], int begin, int end ) {
int i = (begin + end) / 2;
if( v[i] == key )
return i;
if( begin >= end )
return -1; // Não foi encontrado
else if( v[i].compareTo( key ) < 0 )
return pesquisaBinaria( key, v, i + 1, end );
else
return pesquisaBinaria( key, v, begin, i - 1 );
}
Implementação da classe Teste: Onde está localizada a main para execução e teste do programa
public class Teste {
public static void main( String[] args ) {
Map<String, Integer> m = new Map<String, Integer>();
Map<Integer, String> nMes = new Map<Integer, String>();
String mes = "Feve", resto = "reiro";
m.put( "Janeiro", 31 );
m.put( "Fevereiro", 28 );
nMes.put( 2, "Fevereiro" );
System.out.println( "FEV: " + m.get( mes + resto ) );
// Imprime 28
m.put( "Fevereiro", 29 );
System.out.println( m.get( "Fevereiro" ) );
// Imprime 29
Vector<String> chave = m.keys();
for( int i = 0; i < chave.size(); i++ )
System.out.println( chave.at( i ) + "=>" + m.get( chave.at( i ) ) );
//for( String k : m.keys() )
// System.out.println( k + " => " + m.get( k );
m.remove( "Janeiro" );
System.out.println( m.get( "Fevereiro" ).getClass().getName() );
int numDias = m.get( "Fevereiro" );
if( numDias < 30 )
System.out.println( "Não tem 30" );
}
}