Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A general solution to Cedric' School Challenge. Also the particular one that I did initially. http://beust.com/weblog/2013/02/13/coding-challenge-light-edition/
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
// Here's a generalized answer to Cedric's School Challenge.
// Object identity is the transitive closure of all objects where any key is equal.
// http://beust.com/weblog/2013/02/13/coding-challenge-light-edition/
public class MultiKeyObject {
// If which objects have are equal (equality of any key) can change after they are created then
// the hashCode can change. That means you can't put them into a collection that cares about
// the hashCode until after all of the objects that might be equal are created.
// OTOH, if you want to rely on the hashCode not changing, then what objects are equal can
// become dependent on the order they are created. Takes your pick.
public final static boolean HAS_INVARIANT_HASHCODE = false;
private static final Map<Map.Entry, Set<MultiKeyObject>> byKeyValuePair = new HashMap<Map.Entry, Set<MultiKeyObject>>();
// If we don't want the (final) identities to be dependent on the order they are created then we have to allow them to change.
// That also means hashCode can change when new objects are created because the identity is a set.
private Set<MultiKeyObject> identity;
public MultiKeyObject(Map<Object, Object> keys) {
identity = uniqueIdentity(Collections.unmodifiableMap(keys));
identity.add(this);
}
@Override
public int hashCode() {
return identity.hashCode();
}
@Override
public boolean equals(Object obj) {
return obj instanceof MultiKeyObject && identity.contains(obj);
}
private static Set<MultiKeyObject> uniqueIdentity(Map<Object, Object> keys) {
Set<MultiKeyObject> id = null;
for (Map.Entry key_value : keys.entrySet()) {
Set<MultiKeyObject> id_for_kvp = byKeyValuePair.get(key_value);
if (id_for_kvp != null) {
if (id == null) {
id = id_for_kvp;
} else if (id_for_kvp != id) {
// If you want hashCode to be invariant for an object (and thus not like a set), then you have to fail here:
if (HAS_INVARIANT_HASHCODE) {
throw new IllegalArgumentException("Attempt to use key with same value for more than one MultiKeyObject.");
} else {
// Otherwise this object is in the intersection of two previously disjoint identity sets.
// We need to merge them into one big happy identity.
for (MultiKeyObject oid : id_for_kvp) {
oid.changeIdentity(id);
}
}
}
}
}
if (id == null) {
id = HAS_INVARIANT_HASHCODE ? new UniqueIdentityHashSet<MultiKeyObject>() : new IdentityHashSet<MultiKeyObject>();
}
for (Map.Entry key_value : keys.entrySet()) {
Set<MultiKeyObject> old_id = byKeyValuePair.put(key_value, id);
assert((old_id == null) || (old_id == id));
}
return id;
}
protected void changeIdentity(Set<MultiKeyObject> id) {
// This is an ugly hack. A more realistic way to do this is to keep the key map in the object.
for (Map.Entry<Map.Entry, Set<MultiKeyObject>> okvp : byKeyValuePair.entrySet()) {
if (okvp.getValue() == identity) {
okvp.setValue(id);
}
}
identity = id;
id.add(this);
}
private static class IdentityHashSet<T> extends UniqueIdentityHashSet<T> {
@Override
public int hashCode() {
return map.keySet().hashCode();
}
@Override
public boolean equals(Object obj) {
return ((obj instanceof IdentityHashSet) && map.keySet().equals(((IdentityHashSet)obj).map.keySet()));
}
}
private static class UniqueIdentityHashSet<T> implements Set<T> {
protected Map<T, T> map = new IdentityHashMap<T, T>();
@Override
public int size() {
return map.size();
}
@Override
public boolean isEmpty() {
return map.isEmpty();
}
@Override
public boolean contains(Object o) {
return map.containsKey(o);
}
@Override
public Iterator<T> iterator() {
return map.keySet().iterator();
}
@Override
public Object[] toArray() {
return map.keySet().toArray();
}
@Override
public <T> T[] toArray(T[] a) {
return map.keySet().toArray(a);
}
@Override
public boolean add(T o) {
map.put(o, o);
return true;
}
@Override
public boolean remove(Object o) {
map.remove(o);
return true;
}
@Override
public boolean containsAll(Collection<?> c) {
return map.keySet().containsAll(c);
}
@Override
public boolean addAll(Collection<? extends T> c) {
for (T s : c) {
map.put(s, s);
}
return true;
}
@Override
public boolean retainAll(Collection<?> c) {
for (T s : map.keySet()) {
if (!c.contains(s)) map.remove(s);
}
return true;
}
@Override
public boolean removeAll(Collection<?> c) {
for (T s : map.keySet()) {
if (c.contains(s)) map.remove(s);
}
return true;
}
@Override
public void clear() {
map.clear();
}
}
}
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
// Here's a correct answer to Cedric's School Challenge.
// School identity is the set of all schools where either name or nickname are equal.
// http://beust.com/weblog/2013/02/13/coding-challenge-light-edition/
public class NewSchool extends MultiKeyObject {
static enum KeyName { NAME, NICKNAME }
private final String name;
private final String nickname; // Nicks are not really unique. How many Aggies are there?
public NewSchool(String name, String nick)
{
super(newKey(name, nick));
this.name = name;
this.nickname = nick;
}
private static Map<Object, Object> newKey(final String name, final String nick) {
return new HashMap<Object, Object>() {
{
put(KeyName.NAME, name);
put(KeyName.NICKNAME, nick);
}
};
}
@Override
public String toString() {
return name + " (aka " + nickname + ") #" + Integer.toHexString(hashCode());
}
public static void main(String[] args)
{
NewSchool school1 = new NewSchool("University of Pennsylvania", "upenn");
System.out.println("school1: " + school1);
NewSchool school2 = new NewSchool("University of Pennsylvania", "Penn State");
NewSchool school3 = new NewSchool("university of pennsylvania", "Penn State");
NewSchool school4 = new NewSchool("UNIVERSITY OF PENNSYLVANIA", "PENN STATE");
System.out.println("school1: " + school1);
System.out.println("school2: " + school2);
System.out.println("school3: " + school3);
System.out.println("school4: " + school4);
System.out.println("Equals 1 == 2: " + school1.equals(school2));
System.out.println("Equals 1 == 3: " + school1.equals(school3));
System.out.println("Equals 2 == 3: " + school2.equals(school3));
System.out.println("Equals 1 == 4: " + school1.equals(school4));
{
Set<NewSchool> schools = new HashSet<NewSchool>();
schools.add(school1);
schools.add(school2);
schools.add(school3);
schools.add(school4);
System.out.println("Set: " + schools);
}
// If MultiKeyObject.HAS_INVARIANT_HASHCODE is true then this will fail.
try {
NewSchool school5 = new NewSchool("UNIVERSITY OF PENNSYLVANIA", "Penn State");
System.out.println("school5: " + school5);
System.out.println("Equals 1 == 4: " + school1.equals(school4));
System.out.println("Equals 1 == 5: " + school1.equals(school5));
{
Set<NewSchool> schools = new HashSet<NewSchool>();
schools.add(school1);
schools.add(school2);
schools.add(school3);
schools.add(school4);
schools.add(school5);
System.out.println("Set: " + schools);
}
} catch (IllegalArgumentException ex) {
System.out.println("Can't create school5: " + ex.getMessage());
}
}
}
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
// Here's a correct answer to Cedric's School Challenge.
// School identity is the set of all schools where either name or nickname are equal.
// http://beust.com/weblog/2013/02/13/coding-challenge-light-edition/
public class School {
private static final Map<String, Set<School>> byName = new HashMap<String, Set<School>>();
private static final Map<String, Set<School>> byNickname = new HashMap<String, Set<School>>();
private final String name;
private final String nickname; // Nicks are not really unique. How many Aggies are there?
private final Set<School> identity;
public School(String name, String nickname) {
this.name = name;
this.nickname = nickname;
identity = uniqueId(name, nickname);
identity.add(this);
}
private static Set<School> uniqueId(String name, String nickname) {
Set<School> id = byName.get(name);
if (id == null) {
id = byNickname.get(nickname);
if (id == null) {
id = new IdentityHashSet<School>();
byNickname.put(nickname, id);
}
byName.put(name, id);
} else {
if (byNickname.containsKey(nickname)) {
assert (byNickname.get(nickname) == id);
} else {
byNickname.put(nickname, id);
}
}
return id;
}
@Override
public int hashCode() {
// Note that the IdentityHashSet.hashCode (and IdentityHashSet.equals) that I'm using
// here does *not* follow the Set contract but instead relies on Object.hashCode (and Object.equals).
// If we were to use a Set that implemented equals for its contents then we'd need another Object somewhere.
return identity.hashCode();
}
@Override
public boolean equals(Object obj) {
return obj instanceof School && identity.contains(obj);
}
public boolean equalsFuzzily(Object obj) {
return ((obj instanceof School)) && (name.equalsIgnoreCase(((School) obj).name) || nickname.equalsIgnoreCase(((School) obj).nickname));
}
@Override
public String toString() {
return name + " (aka " + nickname + ")";
}
public Set<String> allNames() {
Set<String> names = new HashSet<String>();
for (School s : identity) {
names.add(s.name);
}
return names;
}
public Set<String> allNicknames() {
Set<String> names = new HashSet<String>();
for (School s : identity) {
names.add(s.nickname);
}
return names;
}
public static void main(String[] args)
{
School school1 = new School("University of Pennsylvania", "upenn");
School school2 = new School("University of Pennsylvania", "Penn State");
School school3 = new School("university of pennsylvania", "Penn State");
System.out.println("school1: " + school1);
System.out.println("school2: " + school2);
System.out.println("school3: " + school3);
System.out.println("Equals 1 == 2: " + school1.equals(school2));
System.out.println("Equals 1 == 3: " + school1.equals(school3));
System.out.println("Equals 2 == 3: " + school2.equals(school3));
System.out.println("EqualsFuzzily 1 ~ 2: " + school1.equalsFuzzily(school2));
System.out.println("EqualsFuzzily 1 ~ 3: " + school1.equalsFuzzily(school3));
System.out.println("EqualsFuzzily 2 ~ 3: " + school2.equalsFuzzily(school3));
Set<School> schools = new HashSet<School>();
schools.add(school1);
schools.add(school2);
schools.add(school3);
System.out.println("Set: " + schools);
for (String name : school1.allNames()) {
System.out.println(name);
}
for (String nick : school1.allNicknames()) {
System.out.println(nick);
}
}
private static class IdentityHashSet<T> implements Set<School> {
private Map<School, School> map = new IdentityHashMap<School, School>();
@Override
public int size() {
return map.size();
}
@Override
public boolean isEmpty() {
return map.isEmpty();
}
@Override
public boolean contains(Object o) {
return map.containsKey(o);
}
@Override
public Iterator<School> iterator() {
return map.keySet().iterator();
}
@Override
public Object[] toArray() {
return map.keySet().toArray();
}
@Override
public <T> T[] toArray(T[] a) {
return map.keySet().toArray(a);
}
@Override
public boolean add(School school) {
map.put(school, school);
return true;
}
@Override
public boolean remove(Object o) {
map.remove(o);
return true;
}
@Override
public boolean containsAll(Collection<?> c) {
return map.keySet().containsAll(c);
}
@Override
public boolean addAll(Collection<? extends School> c) {
for (School s : c) {
map.put(s, s);
}
return true;
}
@Override
public boolean retainAll(Collection<?> c) {
for (School s : map.keySet()) {
if (!c.contains(s)) map.remove(s);
}
return true;
}
@Override
public boolean removeAll(Collection<?> c) {
for (School s : map.keySet()) {
if (c.contains(s)) map.remove(s);
}
return true;
}
@Override
public void clear() {
map.clear();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.