Managing Objects
(without knowing what they are)
Background: Generic Data
In this section, data structures that hold other data structures will be discussed. A data structure that holds other data structures is considered a container. While a quick search of the Internet will lead to a variety of other definitions (and opinions), the bottom line is that for purposes of studying data structures, and to keep things from getting too complicated, one data structure holding others is called a container. One step beyond that definition is that some programming languages allow for a data structure to hold and manipulate other data structures without knowing anything about the managed data structures. The name for data that is blindly managed by a container is generic data. The container may be able to add, insert, search for, remove, or otherwise manipulate the data but it doesn't have to know anything about the data.
So how does this work? The answer is object orientation. If the container needs to search or sort a given set of data (i.e., an object), it just asks the object how to be sorted or managed. In the previous section, the StudentMgmtClass knew to sort the data by name because it was a data structure that specifically managed StudentClass objects. However, a container doesn't know what it is managing so it must use a tool provided to it by the class it manages. Very commonly, the data to be managed will implement an interface called Comparable.
Using an interface in Java is basically just a promise that you will implement (or code) the methods specified by that interface so that other classes know what they are getting when your class is used. In the case of the Comparable interface, there is only one method promised, and that is compareTo. This is a tool the containers can use to manage the given object. Very specifically, where the previous container class knew how to sort the data with its own method, generic container classes will use the method compareTo for searching, sorting, etc. and trust that it will hold up its end of the task. The updated StudentClass, now called StudentClass_CT will have its own compareTo method so that when a generic class tries to work with the StudentClass_CT, it will know how to conduct comparison operations. The actual compareTo in the new StudentClass_CT is almost exactly the same as the one the StudentMgmtClass used but it is now a local method so it has one parameter. You will see that in action later on.
More Background: Type Parameters
In your work with methods, you use data parameters. You may pass two values into a method to be added, or a data parameter to be inserted into a list, or whatever. Now, as your learning continues, you will be introduced to type parameters. And where you passed the data values into your methods between parentheses previously, you will pass the data types into the generic class using angle brackets. Consider the following example.
public class StudentClass_CT implements Comparable<StudentClass_CT>
The above example shows that when StudentClass_CT is to be compared to something, it will be compared to the data type StudentClass_CT. In other words the data type is used as a parameter so anyone who uses this class knows that the class can be correctly and appropriately compared to itself. Side note: Notice that the above statement indicates that the class implements Comparable. As mentioned previously, that means the required compareTo method has been implemented or coded inside this class.
Now consider another use of type parameters, shown here.
public class GenericMgmtClass<GenericData extends Comparable<GenericData>>
Whoa! Now this is starting to look complicated. But don't worry, it is, but that doesn't mean we have to be afraid of it. This type parameter is telling anyone who uses this class that they must use a data type that has the inherited (or extended) ability to compare to itself. Where the earlier statement for the StudentClass_CT said, "I promise to be able to correctly compare myself to others of my same data type", this statement is saying, "Okay, you can use my class but you must use a data type that can compare to itself". That's a Java requirement.
Now, there is a little secret to using the generic data inside the class. In places where you want the generic data to be used, you will actually use GenericData as a place holder until the class instantiates objects with real data types. Once that happens, every location where the identifier GenericData was placed in the code will be replaced with the data type that was provided as a parameter. You will see more on this later but for the moment, you need to know that in the code you write, you can use the GenericData identifier for declaring variables/references of the parameter data type, and you can use it for casting. On the other hand, since Java doesn't know what GenericData is (again, it's just a place holder), you cannot use it to instantiate arrays or other objects of that type.
Again, just like your data parameters for your methods to do their jobs, these type parameters provide a class with type information that is needed for that class to do its job. One final note before moving on: This reference uses GenericData as the place holder inside class implementations. However, there are others who would rather make you guess at what they are doing. These folks might use K or E or V, or other non-self-documenting quantities. Ignore these folks; they don't know anything about quality programming.
Even More Background: Keys
As discussed in the previous section, heterogenous data can have a variety of different data in one package. However, if the data is to be stored, retrieved, removed, or otherwise managed, some part of the data must be used as a reference to how the data is stored. In the previous section, the data was stored in alphabetical order with respect to the names of the students. However, it could have been stored by student ID, gender, or GPA, since all of those were part of the data structure StudentClass. The designer of the class arbitrarily chose to use the name as the key since the most likely way for which the data might be searched is using the student's name.
Enough with the background. Let's look at some code.
The Class Data
Consider the initial code below.
public class GenericMgmtClass<GenericData extends Comparable<GenericData>>
{
// constants
private static final int DEFAULT_CAPACITY = 10;
// member data
private Object[] genericDataArray;
private int arraySize, arrayCapacity;
*
*
*
This is the beginning. You can see the class header that was provided earlier in this topic. You can also see the constant to be used for creating a default array capacity for the object. You can also see the array size and capacity but before you see those, you see the Object class array. This is a requirement for a generic class but it's also a convenience. Since all classes in Java are derived from the Object class, you can just use the Object class to create your array. It means a little extra management later on, but nothing of significance.
The Class Constructors
There is another small difference related to generic classes when it comes to constructors. Take a look.
/**
* Default constructor, initializes array to default capacity (10)
*
*/
public GenericMgmtClass()
{
genericDataArray = new Object[ DEFAULT_CAPACITY ];
arrayCapacity = DEFAULT_CAPACITY;
arraySize = 0;
}
/**
* Initializing constructor, initializes array to specified capacity
*
* @param capacity integer maximum capacity specification for the array
*
*/
public GenericMgmtClass( int capacity )
{
genericDataArray = new Object[ capacity ];
arrayCapacity = capacity;
arraySize = 0;
}
Notice what's missing? Generic classes cannot use copy constructors because no matter how you code it, there will be aliasing. There is such a thing as a clone operation in Java but pretty much all of the Java community advises against using this. Besides, once you have a generic container that can handle any kind of data, why would you need to copy it?
The Class Methods
Once again, this class has clear, isEmpty, isFull, getCurrentSize and getCurrentCapacity but these are easy to write, and no different from the same code for all the other classes that manage arrays.
So, let's take a look at the insertion operation.
/**
* Description: Inserts item to array by key if array is not full,
* e.g., no more values can be added
*
* Note: Value is inserted at given index,
* all data from that index to the end of the array
* is shifted up by one
*
* @param newStudent value to be inserted into array
*
* @return Boolean success if inserted, or failure if array was full
*/
@SuppressWarnings( "unchecked" )
public boolean insertByKey( GenericData newValue )
{
int workingIndex;
GenericData testValue;
boolean continueLoop = true;
if( !isFull() )
{
workingIndex = arraySize;
while( workingIndex > 0 && continueLoop )
{
testValue = (GenericData)genericDataArray[ workingIndex - 1];
if( newValue.compareTo( testValue ) < 0 )
{
genericDataArray[ workingIndex ]
= genericDataArray[ workingIndex - 1 ];
workingIndex--;
}
else
{
continueLoop = false;
}
}
genericDataArray[ workingIndex ] = newValue;
arraySize++;
return true;
}
return false;
}
Starting at the top, the first thing you notice is the @SuppressWarnings directive. If you pull data out of an Object array, Java wants you to verify that you got the right data. In the case of this class, every data item added to the array is known to be of GenericData type so there is no question what will come out. No harm, no foul. However, the Java compiler is still going to throw a warning if you do pull something out of an array, as you do inside the loop in this example, so you can override the compiler by telling it not to sweat "unchecked" operations. You should only do this at the beginning of methods, and only those methods that need it. Don't do it at the beginning of the class or in individual locations where the issues occur.
Next, the algorithm is the same as was used in the previous topic except that now you are required to use the generic compareTo operation, remembering that the class doesn't know what it is working with. You can place the array access operation in the compareTo method but your code is going to get hard to read very quickly. Your much better bet is to pull the data out of the array in one operation and then use it in the compareTo in the next. Also note that the test for index > 0 and the compareTo test are not both in the loop. Again, for readability purposes, this will save you, and your peer reviewers, many hours trying to chase down bugs introduced by poor readability. For this situation, it means that a Boolean flag must be used to help control the loop but that is not a significant issue.
Next up is the remove method.
/**
* Description: Removes item from array by key
*
* Note: Each data item from the element immediately above
* the remove index to the end of the array
* is moved down by one element
*
* @param key GenericData value to be found
*
* @return removed value if successful, null if not
*/
@SuppressWarnings( "unchecked" )
public GenericData removeByKey( GenericData removeKey )
{
int index = 0;
boolean continueLoop = true;
GenericData testItem, removedItem;
// find element, if it exists
while( index < arraySize && continueLoop )
{
testItem = (GenericData)genericDataArray[ index ];
if( removeKey.compareTo( testItem ) == 0 )
{
continueLoop = false;
}
else
{
index++;
}
}
// check for element found
if( index < arraySize )
{
// set removed item to data found in array
removedItem = (GenericData)genericDataArray[ index ];
// decrement size
arraySize--;
// loop to shift all data down by one
while( index < arraySize )
{
// assign data at current index to next one up
genericDataArray[ index ] = genericDataArray[ index + 1 ];
// increment index
index++;
}
// return removed item
return removedItem;
}
// return failure indication
return null;
}
Again, when it comes time to test for finding the key, the code removeKey.compareTo( testItem ) is used. The generic class has no idea what is being tested and it doesn't care. It simply uses the tool provided by the class being managed, and it can handle its duties.
There is not much new in this method. It has the SuppressWarnings directive because data is removed from the array and cast to GenericData. Note that it does not have to cast the array data to GenericData when it is shifted from one element to the next. That is an Object array to Object array operation so there is no need for casting.
Next up is the retrieve operation.
/**
* Displays sorted list
*/
@SuppressWarnings( "unchecked" )
public void showSortedList()
{
int index;
GenericData item;
if( arraySize > 0 )
{
System.out.println( "\nSorted List:" );
for( index = 0; index < arraySize; index++ )
{
item = (GenericData)genericDataArray[ index ];
System.out.println( item.toString() );
}
}
else
{
System.out.println( "\nList is empty - No Display" );
}
}
This method might or might not be specified in your class requirements but you should write it anyway even if you pull it when you are done. This method shows you what you have in your array and is an excellent way to verify that your programming is correct. This is sometimes also called a diagnosticDisplay or even a diagnosticDump but in any event, it can be very handy for diagnostic purposes.
Generic Data: The Summary
While you are learning a great deal of what is under the hood in this course, you are much more likely to use generics off the shelf in the large-scale development arena. Good programmers develop and test code to verify it has both quality and speed, and you just plug in the data you need to use. There are a lot of versions of this. Java has Maps, Trees, ArrayLists, and lots of others, C++ has the Standard Template Library (STL), Python has a gazillion different libraries, and so on. It is good for you to see how this kind of system works both as a potential user or a developer in the future.