Cours Java
Correction du TD3

Alain Plantec

1 La classe HashDict


/* Aux quelques bogues pres, merci a MM. Demurget et Leroux (IUP3, 2001-2002) */

import java.util.*;

public class HashDict implements Map {
    protected LinkedList[] table;
    protected int height;
    Set keysCache;
    Collection valuesCache;
    Set entriesCache;
    boolean keyModified;
    boolean valueModified;

    public class Couple implements Map.Entry {
	private Object key;
	private Object value;
	public Couple (Object k, Object v) {
	    key = k;
	    value = v;
	}
	public Object getKey () { return key; }
	public Object getValue () { return value; }
	public Object setValue (Object v) {
	    Object oldValue = value;
	    value = v;
	    return oldValue;
	}
	public String toString () {
	    return "[" + key + "] => [" + value + "]";
	}
    }

    public HashDict (int s) {
	table = new LinkedList[s];
	height = s;
	keyModified = false;
	valueModified = false;
    }

    protected Couple coupleFromKey (Object k) {
	// Note: le hashcode peut etre negatif, donc sans valeur absolue
	//       l'index du tableau risque d'etre tres malsain
	int p = Math.abs (k.hashCode () % height);
	if (table[p] == null)
	    return null;
	List v = table[p];
	for (Iterator i = v.iterator (); i.hasNext (); ) {
	    Couple c = (Couple) i.next ();
	    if (c.getKey ().equals (k))
		return c;
	}
	return null;
    }

    public Object put (Object k, Object v) {
	Couple c = coupleFromKey (k);
	if (c != null) {
	    valueModified = true;
	    return c.setValue (v);
	}
	int p = Math.abs (k.hashCode () % height);
	if (table[p] == null)
	    table[p] = new LinkedList ();
	table[p].add (new Couple (k, v));
	keyModified = true;
	return null;
    }

    public Object get (Object k) {
	Couple c = coupleFromKey (k);
	if (c == null)
	    return null;
	return c.getValue ();
    }

    public Object remove (Object k) {
	Couple c = coupleFromKey (k);
	if (c == null)
	    return null;
	Object oldValue = c.getValue ();
	int p = Math.abs (k.hashCode () % height);
	table[p].remove (c);
	keyModified = true;
	valueModified = true;
	if (table[p].size() == 0)
	    table[p] = null;
	return oldValue;
    }

    public boolean containsKey (Object k) {
	return coupleFromKey (k) != null;
    }

    public boolean containsValue (Object v) {
	for (int n = 0; n < height; n++)
	    if (table[n] != null) {
		for (Iterator i = table[n].iterator (); i.hasNext (); ) {
		    Couple c = (Couple) i.next ();
		    if (c.getValue ().equals (v))
			return true;
		}
	    }
	return false;
    }

    public int size () {
	int s = 0;
	for (int n = 0; n < height; n++)
	    if (table[n] != null)
		s += table[n].size ();
	return s;
    }

    public boolean isEmpty () {
	for (int n = 0; n < height; n++)
	    if (table[n] != null)
		return false;
	return true;
    }

    public void clear () {
	for (int n = 0; n < height; n++)
	    table[n] = null;
	keyModified = true;
	valueModified = true;
    }

    public void putAll (Map t) {
	Set s = t.entrySet ();
	for (Iterator i = s.iterator (); i.hasNext (); ) {
	    Couple c = (Couple) i.next ();
	    put (c.getKey (), c.getValue ());
	}
	if (s.size () > 0) {
	    keyModified = true;
	    valueModified = true;
	}
    }

    public Set keySet () {
	if (keyModified) {
	    keysCache = new HashSet ();
	    for (int n = 0; n < height; n++)
		if (table[n] != null)
		    for (Iterator i = table[n].iterator (); i.hasNext (); )
			keysCache.add (((Couple) i.next ()).getKey ());
	}
	return keysCache;
    }

    public Collection values () {
	if (valueModified) {
	    valuesCache = new ArrayList ();
	    for (int n = 0; n < height; n++)
		if (table[n] != null)
		    for (Iterator i = table[n].iterator (); i.hasNext (); )
			valuesCache.add (((Couple) i.next ()).getValue ());
	}
	return valuesCache;
    }

    public Set entrySet () {
	if (keyModified || valueModified) {
	    entriesCache = new HashSet ();
	    for (int n = 0; n < height; n++)
		if (table[n] != null)
		    for (Iterator i = table[n].iterator (); i.hasNext (); )
			entriesCache.add (i.next ());
	}
	return entriesCache;
    }

    public String toString () {
	StringBuffer strBuf = new StringBuffer ();
	for (int n = 0; n < height; n++)
	    if (table[n] != null)
		strBuf.append ("(" + n + "): " + table[n] + "\n");
	return strBuf.toString ();
    }

    public static void main (String[] args) {
	HashDict hd = new HashDict (256);

	Object keys[] = { new Integer (12), "tralili", new Float (5.2f), "une cle" };
	Object values[] = {"salut", new String ("lalere"), "ceci est un test", new Float (2.0f) };

	for (int i = 0; i < keys.length; i++)
	    hd.put (keys[i], values[i]);

	System.out.println (hd);
	hd.put (keys[1], "valeur remplacee");
	System.out.println (hd);

	System.out.println ("> cles:    " + hd.keySet ());
	System.out.println ("> valeurs: " + hd.values ());
	System.out.println ("> couples: " + hd.entrySet ());

	// a vous de tester le reste =)
    }
}




Plantec Alain
2002-02-21