Working with Generics

Question

First, the task:

Create a new Map class, now using the name Sortedmap. It should have the same methods as the Map class of the previous task, and accept as type Key a type K that implements the Comparable interface. The array Key pairs, Value must be kept ordered. For this, each insert the correct position to insert and move all later elements of the array a position.

The find method can now perform a binary search (call the method binary search given in the laboratory).

This is a lab job, so I’ve already implemented the Map class and made some changes to implement Sortedmap. I switched types to 'K' and 'V'. I will put the following code and it will be easier to view.

Implementation of the Map class:

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;
    }

}

Implementation of Sortedmap (Map class with types changed to use 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;
}

}

The problem occurs when I arrive at the 'Keys() method. I need to create a vector class because there is no way in the Keys() method to return a generic type vector. So from what I understood from the teacher’s explanation, I must create a Vector class (he put one as an example, but I would like to do mine to learn and understand how everything is working). The penultimate is the searchBinary() given in the laboratory and to be implemented in the method find(). The last method is the compareTo, that needs to be implemented but I don’t know how to do it.

If I haven’t been clear on the question, just ask. Thank you! :)

CLASSES FOR PROGRAM TESTING -- TEACHER

Note the fact that some of the teacher’s methods are under different names in my code

Implementation of 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;
        }
    }

}

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;
    }

Implementation of the Vector class: From what I understand, it is not possible to return a generic type vector in the Keys method, and it is necessary 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 searchBinaria() given in the laboratory:

  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 );
    }

Implementation of the Test class: Where the main is located for program execution and testing

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" );
    }
}

Answer 1

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;
    }

Also, you can force the type K 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’t say what the teacher thinks, but by the enunciation and the implementation of Map, my understanding is that the method keys() in SortedMap could have the following signature:

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

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

Comparing

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

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

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