Prise en charge des conteneurs pour les objets dans Java 1.0.2

Herbert Spencer a écrit: «La science est une connaissance organisée». Le corollaire pourrait être que les applications sont des objets organisés. Prenons un moment pour passer à certains aspects de Java qui sont essentiels pour développer des applications plutôt que des applets.

Parmi ceux qui ont entendu parler de Java, la majorité a appris la langue à travers la presse populaire. L'affirmation qui revient souvent est que Java sert à «programmer de petites applications, ou applets, qui peuvent être intégrées à une page Web». Bien que correcte, cette définition ne transmet qu'un seul aspect de la nouvelle langue; cela ne décrit pas la situation dans son ensemble. Peut-être que Java peut être mieux décrit comme un langage conçu pour construire des systèmes - de grands systèmes - de morceaux de code exécutable portables bien compris qui peuvent être combinés, en tout ou en partie, pour produire un tout souhaitable.

Dans cette colonne, je commencerai à examiner les différents outils que vous pouvez utiliser pour créer en Java. Je vais montrer comment ces outils peuvent être combinés pour créer une application plus grande, et comment, une fois que vous avez une application, vous pouvez l'agréger davantage dans des systèmes encore plus grands - tout cela est possible car en Java, il n'y a pas de distinction entre une application complète et un sous-programme simple.

Pour fournir du code source pour cette colonne et les colonnes précédentes, j'ai choisi de créer un interpréteur BASIC. "Pourquoi BASIC?" vous pourriez demander, pensant que plus personne n'utilise BASIC. Ce n'est pas tout à fait vrai. BASIC vit dans Visual Basic et dans d'autres langages de script. Mais plus important encore, de nombreuses personnes y ont été exposées et peuvent faire le saut conceptuel suivant: si les «applications» sont programmées en BASIC et que BASIC peut être écrit en Java, alors les applications peuvent être écrites en Java. BASIC est juste un autre langage interprété; les outils que nous allons construire peuvent être modifiés pour utiliser n'importe quelle syntaxe de langage, ainsi les concepts de base sont au centre de ces articles. Par conséquent, ce qui commence comme une application devient un composant d'autres applications - même des applets peut-être.

Classes et conteneurs génériques

La création de classes génériques est particulièrement pertinente lors de la création d'applications, car la réutilisation des classes offre un énorme levier pour réduire à la fois la complexité et le temps de mise sur le marché. Dans une applet, la valeur d'une classe générique est atténuée par la nécessité de la charger sur le réseau. L'impact négatif du chargement de classes génériques sur le réseau est démontré par Sun's Java Workshop (JWS). JWS enrichit la version standard de la boîte à outils de fenêtrage abstrait (AWT) en utilisant des classes "shadow" très élégantes. L'avantage est que les applets sont faciles à développer et riches en fonctionnalités; l'inconvénient est que le chargement de ces classes peut prendre beaucoup de temps sur une liaison réseau lente. Bien que cet inconvénient finisse par disparaître, nous constatons qu'une perspective système sur le développement de classes est souvent nécessaire pour parvenir à la meilleure solution.

Puisque nous commençons à examiner un peu plus sérieusement le développement d'applications, nous supposerons que nous avons déjà déterminé que les classes génériques sont une solution valide.

Java, comme de nombreux langages à usage général, fournit plusieurs outils pour créer des classes génériques. Des exigences différentes nécessiteront l'utilisation

différents outils. Dans cette colonne, je vais utiliser le développement d'une containerclasse comme exemple car elle peut accueillir presque tous les outils qu'un utilisateur pourrait souhaiter utiliser.

Conteneurs: une définition

Pour ceux d'entre vous qui ne sont pas encore familiarisés avec les objets orientés objet, un conteneur est une classe qui organise d'autres objets. Les conteneurs courants sont les arborescences binaires, les files d'attente, les listes et les piles. Java fournit trois classes de conteneur avec la version JDK 1.0.2: java.util.Hashtable, java.util.Stack et java.util.Vector.

Les conteneurs ont à la fois un principe d'organisation et une interface. Les piles, par exemple, peuvent être organisées comme "premier entré, dernier sorti" (FILO), et leur interface peut être définie pour avoir deux méthodes - push () et pop () . Les conteneurs simples peuvent être considérés comme ayant les méthodes standard d' ajout et de suppression . En outre, ils auront un moyen d'énumérer le conteneur entier, de vérifier si un objet candidat est déjà dans le conteneur et de tester le nombre d'éléments détenus par le conteneur.

Les classes de conteneur Java illustrent certains des problèmes avec les conteneurs, en particulier les conteneurs à clé (ces conteneurs qui utilisent une clé pour localiser un objet). Les conteneurs sans clé comme Stack et Vector remplissent simplement des objets et en retirent des objets. Le conteneur à clé Hashtable utilise un objet clé pour localiser un objet de données. Pour que la fonction de saisie fonctionne, l'objet clé doit prendre en charge une méthode HashCode qui renvoie un code de hachage unique pour chaque objet. Cette capacité de saisie fonctionne car leObjectclass définit une méthode HashCode et est donc héritée par tous les objets, mais ce n'est pas toujours ce que vous voulez. Par exemple, si vous placez des objets dans votre conteneur de table de hachage et que vous les indexez avec des objets String, la méthode HashCode par défaut renvoie simplement un entier unique basé sur la valeur de référence de l'objet. Pour les chaînes, vous voulez vraiment que le code de hachage soit une fonction de la valeur de chaîne, donc String remplace HashCode et fournit sa propre version. Cela signifie que pour tout objet que vous développez et que vous souhaitez stocker dans une table de hachage en utilisant une instance de l'objet comme clé, vous devez remplacer la méthode HashCode. Cela garantit que les objets construits de manière identique utilisent le même code.

Mais qu'en est-il des conteneurs triés? La seule interface de tri fournie dans la Objectclasse est equals () , et elle est contrainte d'assimiler deux objets comme ayant la même référence, n'ayant pas la même valeur. C'est pourquoi, en Java, vous ne pouvez pas écrire le code suivant:

 if (someStringObject == "this") then {... faire quelque chose ...} 

Le code ci-dessus compare les références d'objet, note qu'il y a deux objets différents ici et renvoie false. Vous devez écrire le code comme suit:

 if (someStringObject.compareTo ("this") == 0) alors {... faire quelque chose ...} 

Ce dernier test utilise des connaissances encapsulées dans la méthode compareTo de String pour comparer deux objets chaîne et renvoyer une indication d'égalité.

Utiliser les outils de la boîte

Comme je l'ai mentionné précédemment, les développeurs de programmes génériques disposent de deux outils principaux: l'héritage d'implémentation (extension) et l'héritage comportemental (implémentation).

Pour utiliser l'héritage d'implémentation, vous étendez (sous-classe) une classe existante. Par extension, toutes les sous-classes de la classe de base ont les mêmes capacités que la classe racine. C'est la base de la HashCodeméthode dans la Objectclasse. Comme tous les objets héritent de la java.lang.Objectclasse, tous les objets ont une méthode HashCodequi renvoie un hachage unique pour cet objet. Cependant, si vous souhaitez utiliser vos objets comme clés, gardez à l'esprit la mise en garde mentionnée précédemment concernant le remplacement HashCode.

En plus de l'héritage d'implémentation, il existe l'héritage comportemental (implémentation), qui est obtenu en spécifiant qu'un objet implémente une interface Java particulière. Un objet qui implémente une interface peut être converti en une référence d'objet de ce type d'interface. Ensuite, cette référence peut être utilisée pour appeler les méthodes spécifiées par cette interface. En règle générale, les interfaces sont utilisées lorsqu'une classe peut avoir besoin de traiter plusieurs objets de types différents d'une manière commune. Par exemple, Java définit l'interface Runnable qui est utilisée par les classes de thread pour travailler avec des classes dans leur propre thread.

Construire un conteneur

Pour démontrer les compromis lors de l'écriture de code générique, je vais vous guider à travers la conception et l'implémentation d'une classe de conteneur triée.

Comme je l'ai mentionné plus tôt, dans le développement d'applications à usage général, dans de nombreux cas, un bon conteneur serait utile. Dans mon exemple d'application, j'avais besoin d'un conteneur qui était à la fois clé , ce qui signifie que je voulais récupérer des objets contenus à l'aide d'une clé simple, et triés afin de pouvoir récupérer les objets contenus dans un ordre spécifique basé sur les valeurs de clé.

Lors de la conception de systèmes, il est important de garder à l'esprit quelles parties du système utilisent une interface particulière. Dans le cas des conteneurs, il existe deux interfaces critiques: le conteneur lui-même et les clés qui indexent le conteneur. Les programmes utilisateur utilisent le conteneur pour stocker et organiser des objets; les conteneurs eux-mêmes utilisent les interfaces clés pour les aider à s'organiser. Lors de la conception des conteneurs, nous nous efforçons de les rendre faciles à utiliser et de stocker une grande variété d'objets (augmentant ainsi leur utilité). Nous concevons les clés pour qu'elles soient flexibles afin qu'une grande variété d'implémentations de conteneurs puisse utiliser les mêmes structures de clés.

Pour résoudre mes exigences comportementales, la saisie et le tri, je me tourne vers une structure de données arborescente utile appelée arbre de recherche binaire (BST). Les arbres binaires ont la propriété utile d'être triés, de sorte qu'ils peuvent être recherchés efficacement et peuvent être vidés dans un ordre trié. Le code BST actuel est une implémentation des algorithmes publiés dans le livre Introduction to Algorithms , de Thomas Cormen, Charles Leiserson et Ron Rivest.

java.util.Dictionary

Les classes standard Java ont fait un premier pas vers des conteneurs à clé génériques avec la définition d'une classe abstraite nommée java.util.Dictionary. Si vous regardez le code source fourni avec le JDK, vous verrez qu'il Hashtables'agit d'une sous-classe de Dictionary.

La Dictionaryclasse tente de définir les méthodes communes à tous les conteneurs à clé. Techniquement, ce qui est décrit pourrait plus correctement être appelé un magasin car il n'y a pas de liaison requise entre la clé et l'objet qu'elle indexe. Cependant, le nom est approprié car presque tout le monde comprend le fonctionnement de base d'un dictionnaire. Un autre nom pourrait être KeyedContainer, mais ce titre devient fastidieux assez rapidement. Le fait est que la superclasse commune d'un ensemble de classes génériques devrait exprimer le comportement de base pris en compte par cette classe. Les Dictionaryméthodes sont les suivantes:

Taille( )

Cette méthode renvoie le nombre d'objets actuellement détenus par le conteneur.
est vide( ) Cette méthode retourne true si le conteneur ne contient aucun élément.
clés( ) Renvoie la liste des clés du tableau sous forme d'énumération.
éléments( ) 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) { ... } } 

Jetons un coup d'œil à ce code afin de clarifier deux choses. Tout d'abord, il y a le constructeur protégé par null, qui est présent pour que les sous-classes de cette classe n'aient pas à déclarer un constructeur qui remplace l'un des constructeurs de cette classe. Deuxièmement, les méthodes successor , predecessor , min , max et print sont très courtes et appellent simplement le même équivalent privé afin de conserver de l'espace mémoire.