Copying and Equality

	copying

Copying

	Suppose we want to make a copy of an object with the following structure: class MyClass { OpenList List1, List2; }

Ways to Copy

	Copy constructor
	static copy method
	clone() method (returns copy)
	Any of these can be defined in terms of the other.

Copy constructor

	Add constructor MyClass(MyClass orig)    {    É       }
	Use constructor MyClass newObj = new MyClass(orig);

static copy method

	Add method static MyClass copy(MyClass orig)    {    É       }
	Use method MyClass newObj = MyClass.copy(orig);

clone() method

	Add method public MyClass clone()    {    É       }
	Use method MyClass newObj = orig.clone();

Body of copy method, etc.

	Various meanings of ÒcopyÓ
	Think of object as a tree
		Deep copy: Copy all the way down to the leaves.
		Shallow copy: Copy references only.
	Illustrate with copy constructors

Shallow Copy

	class MyClass { OpenList List1, List2; MyClass(MyClass orig) { List1 = orig.List1; List2 = orig.List2; } }
	The copy shares the lists with the original.

Deep Copy

	class MyClass { OpenList List1, List2; MyClass(MyClass orig) { List1 = copyOpenList(orig.List1); List2 = copyOpenList(orig.List2); } }
	The copy has copies of the original lists, provided that copyList makes such copies.

copyList, slightly deeper

	static OpenList copyOpenList(OpenList orig) { if( orig.isEmpty() ) { return OpenList.nil; } else { return cons(orig.first(),             copyOpenList(orig.rest())); } }
	Still does not copy individual list elements (which could be lists themselves).

copyList, with copied Elements

	static OpenList copyOpenList(OpenList orig) { if( orig.isEmpty() ) { return OpenList.nil; } else { return cons(copy(orig.first()),             copyOpenList(orig.rest())); } }

Copying elements that are lists recursively

clone()

	clone() is defined for every object.
	It is over-ridable.
	There is an interface Cloneable: to over-ride clone() a class must declare that it implements Cloneable
	To get an Object to clone itself, Java says to return: super.Clone()
	If the Object is not Cloneable, it will throw CloneNotSupportedException

clone() limitations

	You cannot do this: as clone() is not visible for Objects in general.
	I could find no way to implement a general static method that will check dynamically whether an Object implements Cloneable, then call clone(). There may be a kludgy way.

Checking Equality

	Defining equals() is at programmerÕs discretion
	By analogy with copying:
		Equality checking can be deep or shallow.
	Semantic equality may be taken into account:
		e.g. allowing an integer value to be equal to a floating value.

Default equals()

	equals() is defined in the base class Object.
	It may/should be over-ridden.
	The default implementation is that x.equals(y) if, and only if, x and y are the same Object.

Interning principle

	Suppose we could guarantee that two objects are semantically equal only if they are the same object.
	Then computing equals would be very fast: only need to compare references.
	Such a guarantee can be made if we intern all of the objects in the class.

Interning principle

	To intern objects in a class, we need a way to get to all objects in that class that were ever created.
	The client does not use the constructor, but rather uses a factory method that returns objects.
	The factory method checks to see whether the prescribed object has already been created
		If so, it returns the existing objectÕs reference.
		If not, it creates a new object (using the constructor) and returns the reference to that object.

Interning Example: an Interning cons

Implementing find and remember

	We must store every OpenList ever produced (sharing tails, etc.)
	We must be able to find a list with equal firsts and rests.
	A na•ve implementation would store an internal list of all OpenLists (not itself a OpenList) and search the list with find.
	This process can become slow.

Faster Implemention of find and remember

	Use the concept of hashing.
	Hashing computes a numeric signature for the proposed new item.
	It then uses the signature to access an array (called a hash table) of Òequivalence classesÓ of items.
	Each equivalence class ideally has a relatively small number of items in it.
	The only searching needed is that of searching the small equivalence class, not the whole universe.

How Java Helps

	Java provides method hashCode() of Object.
	This gives a (generally large) number for any object.
	By dividing the hash code by the hash table size, equivalence classes are thereby formed.
	All objects with the same hash code modulo the table size are considered equivalent.
	Java also provides a class HashSet that can be used to implement find and remember.

Further Investigation

	Examine these classes/interfaces on the Java API web page:
		Exception
		Object
		Cloneable
		HashSet
		Collection
		HashMap