Supporto del contenitore per oggetti in Java 1.0.2

Herbert Spencer ha scritto: "La scienza è conoscenza organizzata". Il corollario potrebbe essere che le applicazioni sono oggetti organizzati. Prendiamo un momento per passare ad alcuni aspetti di Java che sono fondamentali per lo sviluppo di applicazioni piuttosto che di applet.

Di coloro che hanno sentito parlare di Java, la maggior parte ha imparato a conoscere la lingua attraverso la stampa popolare. L'affermazione che emerge molto è che Java è per "programmare piccole applicazioni, o applet, che possono essere incorporate in una pagina Web". Sebbene corretta, questa definizione trasmette solo un aspetto della nuova lingua; non descrive l'intera immagine. Forse Java può essere meglio descritto come un linguaggio progettato per costruire sistemi - grandi sistemi - di pezzi di codice eseguibile portatili ben compresi che possono essere combinati, in tutto o in parte, per produrre un insieme desiderabile.

In questa colonna inizierò a esaminare i vari strumenti che puoi utilizzare per creare in Java. Dimostrerò come questi strumenti possono essere combinati per creare un'applicazione più grande e come, una volta che hai un'applicazione, puoi aggregare ulteriormente l'applicazione in sistemi ancora più grandi - tutto possibile perché in Java non c'è distinzione tra un'applicazione completa e una semplice subroutine.

Per fornire il foraggio del codice sorgente per questa e le colonne precedenti, ho scelto di creare un interprete BASIC. "Perché BASIC?" potresti chiedere, pensando che nessuno usi più il BASIC. Questo non è del tutto vero. BASIC vive in Visual Basic e in altri linguaggi di scripting. Ma ancora più importante, molte persone ne sono state esposte e possono fare il seguente salto concettuale: se le "applicazioni" sono programmate in BASIC e BASIC può essere scritto in Java, allora le applicazioni possono essere scritte in Java. BASIC è solo un altro linguaggio interpretato; gli strumenti che costruiremo possono essere modificati per utilizzare qualsiasi sintassi del linguaggio, quindi i concetti fondamentali sono al centro di questi articoli. Pertanto, ciò che inizia come un'applicazione diventa un componente di altre applicazioni, forse anche applet.

Classi e contenitori generici

La creazione di classi generiche è particolarmente importante quando si creano applicazioni perché il riutilizzo delle classi fornisce un'enorme leva per ridurre sia la complessità che il time to market. In un'applet, il valore di una classe generica è mitigato dalla necessità di caricarlo sulla rete. L'impatto negativo del caricamento di classi generiche sulla rete è dimostrato dal Java Workshop (JWS) di Sun. JWS potenzia la versione standard dell'Astratto Windowing Toolkit (AWT) utilizzando alcune classi "ombra" molto eleganti. Il vantaggio è che le applet sono facili da sviluppare e ricche di funzionalità; lo svantaggio è che il caricamento di queste classi può richiedere molto tempo su un collegamento di rete lento. Anche se questo svantaggio alla fine scomparirà, ciò che troviamo è che spesso è necessaria una prospettiva di sistema sullo sviluppo delle classi per ottenere la soluzione migliore.

Dato che stiamo iniziando a guardare un po 'più seriamente allo sviluppo di applicazioni, assumeremo di aver già determinato che le classi generiche sono una soluzione valida.

Java, come molti linguaggi generici, fornisce diversi strumenti per la creazione di classi generiche. Requisiti diversi richiederanno l'utilizzo

strumenti diversi. In questa colonna userò lo sviluppo di una containerclasse come esempio poiché può ospitare quasi tutti gli strumenti che un utente potrebbe desiderare di utilizzare.

Contenitori: una definizione

Per quelli di voi che non hanno ancora familiarità con le cose orientate agli oggetti, un contenitore è una classe che organizza altri oggetti. I contenitori comuni sono alberi binari, code, elenchi e stack. Java fornisce tre classi contenitore con la versione JDK 1.0.2: java.util.Hashtable, java.util.Stack e java.util.Vector.

I contenitori hanno sia un principio di organizzazione che un'interfaccia. Gli stack, ad esempio, possono essere organizzati come "first in, last out" (FILO) e la loro interfaccia può essere definita per avere due metodi: push () e pop () . Si può pensare che i contenitori semplici abbiano i metodi standard di aggiunta e rimozione . Inoltre, avranno un mezzo per enumerare l'intero contenitore, per verificare se un oggetto candidato è già nel contenitore e per testare il numero di elementi contenuti nel contenitore.

Le classi di contenitori Java dimostrano alcuni dei problemi con i contenitori, in particolare i contenitori con chiave (quei contenitori che utilizzano una chiave per individuare un oggetto). I contenitori senza chiave come Stack e Vector semplicemente inseriscono gli oggetti e ne estraggono gli oggetti. Il contenitore con chiave Hashtable utilizza un oggetto chiave per individuare un oggetto dati. Affinché la funzione di codifica funzioni, l'oggetto chiave deve supportare un metodo HashCode che restituisce un codice hash univoco per ogni oggetto. Questa capacità di digitazione funziona perché ilObjectclass definisce un metodo HashCode e quindi viene ereditato da tutti gli oggetti, ma non è sempre quello che vuoi. Ad esempio, se si inseriscono oggetti nel contenitore della tabella hash e li si indicizza con oggetti String, il metodo HashCode predefinito restituisce semplicemente un numero intero univoco basato sul valore di riferimento dell'oggetto. Per le stringhe, vuoi davvero che il codice hash sia una funzione del valore della stringa, quindi String sovrascrive HashCode e fornisce la sua versione. Ciò significa che per qualsiasi oggetto che sviluppi e desideri memorizzare in una tabella hash utilizzando un'istanza dell'oggetto come chiave, devi sovrascrivere il metodo HashCode. Ciò assicura che gli oggetti costruiti in modo identico abbiano lo stesso codice.

Ma per quanto riguarda i contenitori ordinati? L'unica interfaccia di ordinamento fornita nella Objectclasse è equals () ed è vincolata a equiparare due oggetti come aventi lo stesso riferimento, non aventi lo stesso valore. Questo è il motivo per cui, in Java, non puoi scrivere il seguente codice:

 if (someStringObject == "this") then {... do something ...} 

Il codice precedente confronta i riferimenti agli oggetti, rileva che qui sono presenti due oggetti diversi e restituisce false. Devi scrivere il codice come segue:

 if (someStringObject.compareTo ("this") == 0) then {... do something ...} 

Quest'ultimo test utilizza la conoscenza incapsulata nel metodo compareTo di String per confrontare due oggetti stringa e restituire un'indicazione di uguaglianza.

Utilizzando gli strumenti nella confezione

Come accennato in precedenza, gli sviluppatori di programmi generici hanno a disposizione due strumenti principali: ereditarietà dell'implementazione (estensione) ed ereditarietà comportamentale (implementazione).

Per utilizzare l'ereditarietà dell'implementazione, estendi (sottoclasse) una classe esistente. Per estensione, tutte le sottoclassi della classe base hanno le stesse capacità della classe radice. Questa è la base per il HashCodemetodo nella Objectclasse. Poiché tutti gli oggetti ereditano dalla java.lang.Objectclasse, tutti gli oggetti hanno un metodo HashCodeche restituisce un hash univoco per quell'oggetto. Se desideri utilizzare i tuoi oggetti come chiavi, tuttavia, tieni presente l'avvertenza menzionata in precedenza sull'override HashCode.

Oltre all'ereditarietà dell'implementazione, esiste l'ereditarietà comportamentale (implementazione), che si ottiene specificando che un oggetto implementa una particolare interfaccia Java. Un oggetto che implementa un'interfaccia può essere sottoposto a cast a un riferimento a un oggetto di quel tipo di interfaccia. Quindi quel riferimento può essere utilizzato per richiamare i metodi specificati da quell'interfaccia. In genere, le interfacce vengono utilizzate quando una classe potrebbe dover elaborare diversi oggetti di tipi diversi in modo comune. Ad esempio, Java definisce l'interfaccia Runnable utilizzata dalle classi thread per lavorare con le classi nel proprio thread.

Costruire un container

Per dimostrare i compromessi nella scrittura di codice generico, ti guiderò attraverso la progettazione e l'implementazione di una classe contenitore ordinata.

Come ho accennato in precedenza, nello sviluppo di applicazioni generiche, in molti casi sarebbe utile un buon contenitore. Nella mia applicazione di esempio avevo bisogno di un contenitore con chiave , il che significa che volevo recuperare gli oggetti contenuti utilizzando una chiave semplice e ordinati in modo da poter recuperare gli oggetti contenuti in un ordine specifico basato sui valori della chiave.

Quando si progettano sistemi, è importante tenere presente quali parti del sistema utilizzano una particolare interfaccia. Nel caso dei contenitori, ci sono due interfacce critiche: il contenitore stesso e le chiavi che indicizzano il contenitore. I programmi utente utilizzano il contenitore per archiviare e organizzare gli oggetti; i contenitori stessi utilizzano le interfacce chiave per aiutarli a organizzarsi. Quando progettiamo i contenitori, ci sforziamo di renderli facili da usare e di immagazzinare un'ampia varietà di oggetti (aumentando così la loro utilità). Progettiamo le chiavi in ​​modo che siano flessibili in modo che un'ampia varietà di implementazioni di container possa utilizzare le stesse strutture chiave.

To solve my behavioral requirements, keying and sorting, I turn to a useful tree data structure called a binary search tree (BST). Binary trees have the useful property of being sorted, so they can be efficiently searched and can be dumped out in sorted order. The actual BST code is an implementation of the algorithms published in the book Introduction to Algorithms, by Thomas Cormen, Charles Leiserson, and Ron Rivest.

java.util.Dictionary

The Java standard classes have taken a first step toward generic keyed containers with the definition of an abstract class named java.util.Dictionary. If you look at the source code that comes with the JDK, you will see that Hashtable is a subclass of Dictionary.

The Dictionary class attempts to define the methods common to all keyed containers. Technically, what is being described could more properly be called a store as there is no required binding between the key and the object it indexes. However, the name is appropriate as nearly everyone understands the basic operation of a dictionary. An alternative name might be KeyedContainer, but that title gets tedious pretty quickly. The point is that the common superclass of a set of generic classes should express the core behavior being factored out by that class. The Dictionary methods are as follows:

size( )

This method returns the number of objects currently being held by the container.
isEmpty( ) This method returns true if the container has no elements.
keys( ) Return the list of keys in the table as an Enumeration.
elements( ) Return the list of contained objects as an Enumeration.
get(Objectk) Get an object, given a particular key k.
put(Objectk,Objecto) Store an object o using key k.
remove(Objectk) Remove an object that is indexed by key k.

By subclassing Dictionary, we use the tool of implementation inheritance to create an object that can be used by a wide variety of clients. These clients need know only how to use a Dictionary, and we can then substitute our new BST or a Hashtable without the client noticing. It is this property of abstracting out the core interface into the superclass that is crucial to reusability, general-purpose function, expressed cleanly.

Basically, Dictionary gives us two groups of behavior, accounting and administration -- accounting in the form of how many objects we've stored and bulk reading of the store, and administration in the form of get, put, and remove.

If you look at the Hashtable class source (it is included with all versions of the JDK in a file named src.zip), you will see that this class extends Dictionary and has two private internal classes, one named HashtableEntry and one named HashtableEnumerator. The implementation is straightforward. When put is called, objects are placed into a HashtableEntry object and stored into a hash table. When get is called, the key passed is hashed and the hashcode is used to locate the desired object in the hash table. These methods keep track of how many objects have been added or removed, and this information is returned in response to a size request. The HashtableEnumerator class is used to return results of the elements method or keys method.

First cut at a generic keyed container

The BinarySearchTree class is an example of a generic container that subclasses Dictionary but uses a different organizing principle. As in the Hashtable class, I've added a couple of classes to support holding the stored objects and keys and for enumerating the table.

The first is BSTNode, which is equivalent to a HashtableEntry. It is defined as shown in the code outline below. You can also look at the source.

class BSTNode { protected BSTNode parent; protected BSTNode left; protected BSTNode right; protected String key; protected Object payload; public BSTNode(String k, Object p) { key = k; payload = p; } protected BSTNode() { super(); } BSTNode successor() { return successor(this); } BSTNode precessor() { return predecessor(this); } BSTNode min() { return min(this); } BSTNode max() { return max(this); } void print(PrintStream p) { print(this, p); } private static BSTNode successor(BSTNode n) { ... } private static BSTNode predecessor(BSTNode n) { ... } private static BSTNode min(BSTNode n) { ... } private static BSTNode max(BSTNode n) { ... } private static void print(BSTNode n, PrintStream p) { ... } } 

Diamo un'occhiata a questo codice per chiarire due cose. Innanzitutto, c'è il costruttore protetto da null, che è presente in modo che le sottoclassi di questa classe non debbano dichiarare un costruttore che sovrascrive uno dei costruttori di questa classe. In secondo luogo, i metodi successor , predecessor , min , max e print sono molto brevi e chiamano semplicemente lo stesso equivalente privato in modo da risparmiare spazio di memoria.