Ordinare Hashtable o TreeMap per valore

[erpupone10]

Ciao a tutti,
ho un problema..sto realizzando un progettino per la compressione di file in formato GIF e voglio creare una tavolozza di colori in base al numero di pixel che hanno un determinato colore nell'immagine che processo. In pratica analizzo tutti i pixel e conto i pixel con una certa tonalità. salvo tutti questi dati in una TreeMap con indice il colore e valore il numero di pixel con quel colore (entrambi i valori sono interi). C'è un modo per ordinare questa lista in base al valore e non alla chiave..oppure c'è un altro oggetto diverso da quello che sto usando che permette questo cioè che abbia un entry univoca a cui è associato un valore che posso ordinare.
Questo è il codice che ho creato e che ordina la TreeMap in base alla key..

public static ImageProcessor CompressRGBAdaptive(ImageProcessor ip,int nx,int ny,int pal,int numCol)
  {      
    int i,numPixel;
    int array[] = new int[4];
    TreeMap<Integer,Integer> palette = new TreeMap<Integer,Integer>();
    for(int x = 0;x<nx;x++) {
      for(int y=0;y<ny;y++) {
        array = ip.getPixel(x,y,array);        
        i=(array[0] << 16)+(array[1] << 8)+(array[2]);
        if(palette.containsKey(i)) {
          numPixel = palette.get(i);
          numPixel++;
          palette.put(i,numPixel);
        }
        else palette.put(i,1);
      }
    }
    IJ.write("Dimensione palette: "+palette.size());
    int cont=0,numPix = nx*ny;
    IJ.write("numPix: "+numPix);
    Vector<Integer> v = new Vector<Integer>(palette.keySet());           
        // Display (sorted) TreeMap.
        for (ListIterator<Integer> e = v.listIterator(); e.hasNext();) {
            Integer key = e.next();
            Integer val = palette.get(key);
            IJ.write("Colore: " + key + "     Numero Pixel: " + val);
        }
    return ip;
  }

Dimenticavo di dire che uso ImageJ...

ciao e grazie..

[andbin]

Originariamente inviato da erpupone10
In pratica analizzo tutti i pixel e conto i pixel con una certa tonalità. salvo tutti questi dati in una TreeMap con indice il colore e valore il numero di pixel con quel colore (entrambi i valori sono interi).

A dire il vero non ti conviene affatto usare TreeMap. Usa HashMap.
Il perché te lo spiego subito. Se poi tanto dopo dovrai fare un ordinamento sui valori, allora non ti serve tenere la collezione ordinata secondo le chiavi!
E per dirla tutta, TreeMap è più lento di HashMap. Anche questo è presto spiegato: TreeMap è organizzato internamente come un "albero" binario e per tale motivo le principali operazioni come put/get/remove/containsKey hanno una complessità O(log n). Invece HashMap ha una complessità O(1), cioè in teoria tempo costante, dovuto al fatto che usa una hash-table.
Visto che potenzialmente hai moltissimi colori, è chiaro che è meglio HashMap.

Originariamente inviato da erpupone10
C'è un modo per ordinare questa lista in base al valore e non alla chiave

L'avevo già spiegato in un'altra discussione (ora non ricordo se era un tuo thread ... forse sì). Non si può ordinare (o tenere ordinata) una Map secondo i valori.

Originariamente inviato da erpupone10
oppure c'è un altro oggetto diverso da quello che sto usando che permette questo cioè che abbia un entry univoca a cui è associato un valore che posso ordinare.

Ci sarebbero diverse strade per fare quello che vorresti fare.

Potresti creare una tua classe es. ColorCounter che contiene colore e contatore. Con i dati della HashMap crei un ArrayList<ColorCounter> che poi ordinerai tranquillamente tramite sort() di Collections specificando ad esempio un Comparator che compara il solo campo contatore.

Ma ci sarebbe anche un'altra soluzione più azzardata: usare un HashSet<ColorCounter>. Naturalmente ColorCounter avrà equals()/hashCode() che si baseranno solo sul colore, non sul contatore.
Alla fine devi ancora sempre ottenere un ArrayList<ColorCounter> da ordinare come detto sopra. Ma così almeno ti risparmi boxing/unboxing come invece stai facendo ora che usi la Map con <Integer,Integer>. Sì ... proprio così: quando incrementi il contatore fai un unboxing e poi dopo un boxing.

[andbin]

Dimentica la storia del HashSet. In effetti ragionandoci "a freddo" non può funzionare. Non va bene quando l'oggetto ha dello stato che non viene usato per definire la "identità" dell'oggetto tramite equals().

Rimane la strada della HashMap.

[erpupone10]

Ciao,
grazie ancora per tutti i tuoi consigli, questa parte che hai scritto mi sembra particolarmente interessante:

Potresti creare una tua classe es. ColorCounter che contiene colore e contatore. Con i dati della HashMap crei un ArrayList<ColorCounter> che poi ordinerai tranquillamente tramite sort() di Collections specificando ad esempio un Comparator che compara il solo campo contatore.

Riusciresti a farmene un breve esempio?

Grazie

Giovanni

[andbin]

Originariamente inviato da erpupone10
Riusciresti a farmene un breve esempio?

Certo, un esempio posso farlo sempre volentieri (e rimedio alla fesseria che ho detto circa la soluzione con HashSet).

Faccio un esempio in cui cambia solo il tipo di dato da conteggiare. Si vuole ad esempio ottenere una statistica dei caratteri in una stringa:

import java.util.*;

public class Prova
{
    public static void main (String[] args)
    {
        String str = "java programming language";

        // crea mappa
        HashMap<Character,CharCounter> map = new HashMap<Character,CharCounter> ();

        for (int i = 0; i < str.length (); i++)
        {
            char c = str.charAt (i);

            CharCounter cc = map.get (c);

            if (cc == null)
            {
                cc = new CharCounter (c);
                map.put (c, cc);
            }

            cc.increment ();
        }

        // crea lista
        ArrayList<CharCounter> list = new ArrayList<CharCounter> (map.size ());

        for (Character c : map.keySet ())
            list.add (map.get (c));

        // ordina lista
        Collections.sort (list, new CounterComparator ());

        // stampa lista
        for (CharCounter cc : list)
            System.out.println ("'" + cc.getCharacter () + "' -> " + cc.getCounter ());
    }
}

class CharCounter
{
    private char ch;
    private int counter;

    public CharCounter (char ch)
    {
        this.ch = ch;
    }

    public void increment ()
    {
        counter++;
    }

    public char getCharacter ()
    {
        return ch;
    }

    public int getCounter ()
    {
        return counter;
    }
}

class CounterComparator implements Comparator<CharCounter>
{
    public int compare (CharCounter o1, CharCounter o2)
    {
        int c1 = o1.getCounter ();
        int c2 = o2.getCounter ();

        // compara i due contatori
        return c1 > c2 ? +1 : c1 < c2 ? -1 : 0;
    }
}

Notare che in CharCounter non ho implementato (anche per brevità) equals/hashCode. Nel programma di esempio non vengono usati. È chiaro che se un CharCounter dovesse essere usato come elemento di ricerca nella lista o dovesse essere usato come chiave in un set/map, allora ovviamente i due metodi vanno implementati.

L'output del programma è:

'e' -> 1
'o' -> 1
'l' -> 1
'j' -> 1
'i' -> 1
'v' -> 1
'u' -> 1
'p' -> 1
' ' -> 2
'n' -> 2
'm' -> 2
'r' -> 2
'g' -> 4
'a' -> 5

Se si vuole ordinarlo al contrario (il conteggio più alto all'inizio), basta cambiare la sola riga di comparazione in compare().

[erpupone10]

Ciao,

ti ringrazio infinitamente..
ho realizzato un programma utilizzando praticamente il tuo codice, (Ho solo sostituito con un Integer il Char che usavi tu). Ora però il compilatore mi da questo errore:

File: C:\Programmi\ImageJ\plugins\GIF\Gif.java [line: 66]
Error: C:\Programmi\ImageJ\plugins\GIF\Gif.java:66: non-static variable this cannot be referenced from a static context
File: C:\Programmi\ImageJ\plugins\GIF\Gif.java [line: 91]
Error: C:\Programmi\ImageJ\plugins\GIF\Gif.java:91: non-static variable this cannot be referenced from a static context
--------------[line: 66]

Ti posto il codice:

public static ImageProcessor CompressRGBAdaptive(ImageProcessor ip,int nx,int ny,int pal,int numCol)
  {      
    
    int array[] = new int[4];    
    HashMap<Integer,ColorCounter> map = new HashMap<Integer,ColorCounter> ();
    for(int x = 0;x<nx;x++) {
      for(int y=0;y<ny;y++) {
        array = ip.getPixel(x,y,array);        
        Integer i = (array[0] << 16)+(array[1] << 8)+(array[2]);  
        ColorCounter cc = map.get(i);
        if (cc == null)
            {
                cc = new ColorCounter (i); 
                map.put (i, cc);
            }
            cc.increment ();        
      }
    }
    
     // crea lista
        ArrayList<ColorCounter> list = new ArrayList<ColorCounter> (map.size ());

        for (Integer c : map.keySet ())
            list.add (map.get (c));

        // ordina lista
        Collections.sort (list, new CounterComparator ());

        // stampa lista
        for (ColorCounter cc : list)
            IJ.write("'" + cc.getColor () + "' -> " + cc.getPixel ());
    
    return ip;
  }
 
  class CounterComparator implements Comparator<ColorCounter>
{
    public int compare (ColorCounter o1, ColorCounter o2)
    {
        int c1 = o1.getPixel();
        int c2 = o2.getPixel();

        // compara i due contatori
        return c1 < c2 ? +1 : c1 > c2 ? -1 : 0;
    }
}


  class ColorCounter {
    private int numPixel,color;
    public ColorCounter(int color){
      this.color=color;      
    }
    public int getPixel() {
      return this.numPixel;
    }
    public int getColor() {
      return this.color;
    }
    public void increment() {
      numPixel++;
    }
  }

Che tipo di errore ho commesso?
Gli errori sono sulle righe che ho messo in grassetto che comunque riporto:

cc = new ColorCounter (i);
Collections.sort (list, new CounterComparator ());

Grazie

Giovanni

[andbin]

Originariamente inviato da erpupone10
Che tipo di errore ho commesso?

Le classi CounterComparator e ColorCounter le hai definite allo stesso livello dei metodi, quindi dentro la classe. Sono in pratica delle "inner class".

Per istanziare una inner class è necessario avere una istanza della classe contenitore (e nei metodi statici non il 'this'). Non sto adesso a fare disquisizioni su come/perché vada fatta la istanziazione di una inner class.
Semplicemente nel tuo caso non ti serve averle come inner class. Dichiarale come classi top-level.

[erpupone10]

Ora funziona!!!
Ti ringrazio davvero!

A presto per altri eventuali suggerimenti e dubbi

Ciao

Giovanni