First, the task:
Create a new Map class, now using the name SortedMap. She must have the same methods of the Map class of the previous task, and accept as type Key type K that implements the Comparable interface. The array of key pairs, value must be kept sorted. For this, each insert the correct position to insert and move all the elements of the array a position.
The find method can now perform a binary search (call method binary search given in the lab).
This is a lab job, so I've already done the Map class implementation and have already made some changes to implement SortedMap. I switched the types to 'K' and 'V'. I'll post the following code and it'll be easier to see.
Map class implementation:
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;
}
}
SortedMap implementation (Map class with types changed for Generics usage)
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;
}
}
The problem occurs when I get into the 'keys ()' method. I need to create a Vector class, because there is no way to return a generic type in the keys () method. So from what I understood from the teacher explanation, I should create a Vector class (it put one as an example, but I would like to do mine to learn and understand how everything is working). The penultimate is the searchBinaria () given in the lab and must be implemented in the find () method. The last method is the compareTo , which needs to be implemented but I do not know how to do it.
If I have not been clear in doubt, just ask. Thank you! :)
CLASSES FOR PROGRAM TEST - TEACHER
Consider the fact that some teacher methods have different names in my code
SortedMap implementation:
// 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;
}
}
}
Implementation of the keys () method:
/**
* 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;
}
Vector class implementation: I can not return a generic type vector in the keys method, so I need to create this class
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;
}
}
Implementation of the Binary search () given in the lab:
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 );
}
Test class implementation: Where main is located for running and testing the program
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" );
}
}