Working with Generics

1

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" );
    }
}
    
asked by anonymous 19.04.2017 / 19:48

1 answer

0

Using More Generic Types

Here, you could use K and V as key and value types, respectively:

public class SortedMap<K, V> implements Comparable<K> {

    public static class Pair {
        Object key, value;
    }

In addition, you can force type K to be something that implements Comparable .

Example:

public class SortedMap<K extends Comparable<K>, V> implements Comparable<K> {

    public static class Pair {
        K key;
        V value;
    }

Method keys()

I can not say what the teacher thinks, but by the statement and the implementation of Map , my understanding is that the keys() method in SortedMap could have the following signature:

public K[] keys() { ... }

You could choose to abstract the array in a class as Vector , but this would be nothing more than an object containing an inner array and some access methods like size() and get() . If you have time, you can do this, but I do not see it as essential.

Comparing

In fact, the SortedMap class does not have to compare anything. Who implements Comparable and consequently the compareTo method is the type that is used as a map key.

For example, if you use String or Integer or any basic type of Java, this method is already implemented and you do not have to do anything.

The idea of the Comparable interface is that you can implement the interface arbitrarily on any class by comparing any attributes it has to set the sort.

    
21.04.2017 / 04:01