Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös

TYPES ABSTRAITS (DE DONNÉES)

Abstraction de données

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös ii

Déf. Un type est un ensemble (possiblement infini) de valeurs et d’opérations surcelles-ci.

�type = domaine + opérations

Déf. Un type abstrait (TA) est un type accessible uniquement à travers une in-terface.

�TA = type + interface

client : le programme qui utilise le TAinterface : contrat entre client et l’implémentationimplémentation : le programmme qui spécifie le TA

? fondations : nombres, caractères, chaînes, . . .? objets : temps, fichier, forme géométrique, . . .? collections d’éléments � étudier les structures de données pour les implémenter

? graphes, réseaux � choisir la bonne structure pour son algorithme

Java et Type Abstrait

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös iii

� la philosophie orientée objet de Java est proche de notre abstraction� avec quelques différences

abstraction programmation OO (Java)

client code qui utilise le type (classe ou interface)

interface (contrat)

méthodes visibles (public/protected/) + variables (de classe et d'instance) visibles+ contrat dans la documentation (p.e., restrictions sur les arguments)

typevaleuropération

classe ou interfaceinstance (objet)méthode

implémentation classe

Java et Type Abstrait

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös iv

� la philosophie orientée objet de Java est proche de notre abstraction� avec quelques différences

? Java impose des contraintes de syntaxe sur la spécification de l’interface duTA (API = interface de programmation)

? clients avec droits différentspublic class C{

public void yksi (C arg){...} // tous les clientsprotected void kaksi(C arg){...} // sous-classes et même package

void kolme(C arg){...} // même package...

}

? l’interface abstrait du Java n’est pas l’interface (du TA) de notre défini-tion(p.e. il ne définit pas le syntaxe des constructeurs)

? implémentation et interface souvent dans le même fichier(la classe qui déclare et définit une méthode)

Structure de données

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös v

si on veut implanter un type abstrait :? il faut décider comment stocker la valeur

(pour une collection, «valeur» = ensemble d’éléments dans la collection),? il faut décider sur les algorithmes pour les opérations spécifiées par l’inter-

face,? et encoder l’atout (dans ce cours, en Java)� objet avec variables privées pour stocker la valeur� méthodes d’instance et de classe pour implanter les algorithmes

structure de données

= implémentation d’un type abstrait (collection)= spécification du stockage des données et des algorithmes qui performent les opé-rations

File

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös vi

File généralisée (TA) = collection d’éléments avec deux opérations :

1. injection d’un élément : ajouter / insérer / enfiler / empiler / . . .

2. éjection d’un élément : retirer / supprimer / défiler / dépiler / . . .

il existe beaucoup de variantes selon la politique d’injection/éjection, ainsi quel’interface pour le TA (= comment spécifie-t-on l’«élément» ?)

Pile — abstraction

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös vii

Le type abstrait pile (stack ) :abstraction d’une pile d’objets : empilés l’un sur l’autre, on ne peut accéder qu’àl’élément le plus récemment empilé

opérations du TA : «empiler» (push) et «dépiler» (pop)

push("premier"),push("2e"),push("dernier")pop() → dernier

pop() → 2e

pop() → premier

� la structure de données doit assurer la logique LIFO (last-in first-out) de push/pop

� on a le droit de stocker les éléments comme on veut car il n’y a pas d’autre opération d’accès

Queue — abstraction

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös viii

Le type abstrait queue ou file FIFO (queue en anglais) :abstraction de file d’attente : objets rangés un après l’autre, on peut enfiler à la finou défiler au début

opérations du TA : «enfiler» (enqueue) et «défiler» (dequeue)

enqueue("premier"), enqueue("2e"), enqueue("dernier")dequeue() → premier

dequeue() → 2e

dequeue() → dernier

� la structure de données doit assurer la logique FIFO (first-in first-out) de enqueue/dequeue

� on a le droit de stocker les éléments comme on veut car il n’y a pas d’autre opération d’accès

Pile et queue

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös ix

importance fondamentale en informatique

pile : permet de sauvegarder et rétablir l’état? exécution d’appel de procédures, récursivité (variables locales stockées sur

la pile)? analyse syntaxique, compilation (appariement d’éléments syntaxiques t.q.

parèntheses ouvrante et fermante)� syntaxe = grammaire hors-contexte = reconnu par automate à pile

queue : permet de syncroniser production et consommation en respectant l’ordre? lecture et écriture de fichiers, streaming? requête et exécution de tâches : serveur Web, print queue, ordonnancement

des processus

TAs classiques

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös x

opérations principales

sac (bag)

pile (stack)

queue

files

vide?

+

parcourir

+

-

ajouter retirer

add

push

enqueue

rechercher

-pop

dequeue

dictionnaire ordonné(sorted dictionary)

min

-

ensemble (set)

+

-

add

deleteou -

+file à priorités(priority queue) deleteMin

+

contains

getdeletetable de symboles

(symbol table / map)

TAs

+/- addou -

add

-

structurestypiques

tableau ou liste chaînée

tas (heap)

tableau de hachage

arbre binaire de recherche

- -

Types en Java

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös xi

Java est un langage fortement typé (toute variable a un type déclaré)? types primitifs (int, double, boolean, . . . )? types agrégés (tableaux, et ceux définis par les classes et les interfaces)

Déf. variable = abstraction d’un emplacement en mémoire (von Neumann)

composants d’une variable :

1. nom

2. adresse (lvalue)

3. valeur (rvalue)

4. type

5. portée / visibilité

? En Java, la valeur d’une variable de type agrégé est une référence.? Une référence (ou pointeur) est soit null soit l’adresse d’un emplacement

mémoire contentant une valeur typée.

Mémoire en Java

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös xii

overhead (info sur classe, syncronisation,

ramasse-miette)

variables d'instance

arrondi à 8k octets

int n=1000;Object x = new MonObjet(); int[] T = new int[n];

x référence

boolean

byte

char

int

long

float

doubleréférence

Object

Integer

short

Node<Object>taille en octets

(Java SE 1.6.0_51, 64 bits, MacOS)

24–40

24

24

8 (adresse mémoire sur 64 bits)

8

4

8

4

2

2

1

1

T référenceen-tète

16 octets

16-24 octets

n×t octets

n valeur

Tas (heap) d'allocation d'objets

Pile (stack) de variables locales

padding

Java Collections

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös xiii

Interfaces fondamentales dans le package java.util :

java.util.List : accès par indice d’élémentjava.util.Map =table de symboles = dictionnaire : recherche par cléjava.util.Deque : file avec accès aux deux extrémités

Multiples implémentations

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös xiv

1/12/19, 5:17 PMCollections Framework Overview

Page 3 of 4https://docs.oracle.com/javase/10/docs/api/java/util/doc-files/coll-overview.html

can result in an exception. Some restricted collections permit this usage.

Collection ImplementationsClasses that implement the collection interfaces typically have names in the form of <Implementation-style><Interface>. The general purpose implementations are summarized in the following table:

General purpose implementations

Interface HashTable

ResizableArray

BalancedTree

LinkedList

Hash Table + LinkedList

Set HashSet TreeSet LinkedHashSetList ArrayList LinkedList Deque ArrayDeque LinkedList Map HashMap TreeMap LinkedHashMap

The general-purpose implementations support all of the optional operations in the collection interfacesand have no restrictions on the elements they may contain. They are unsynchronized, but theCollections class contains static factories called synchronization wrappers that can be used to addsynchronization to many unsynchronized collections. All of the new implementations have fail-fastiterators, which detect invalid concurrent modification, and fail quickly and cleanly (rather than behavingerratically).

The AbstractCollection, AbstractSet, AbstractList, AbstractSequentialList and AbstractMapclasses provide basic implementations of the core collection interfaces, to minimize the effort required toimplement them. The API documentation for these classes describes precisely how each method isimplemented so the implementer knows which methods must be overridden, given the performance of thebasic operations of a specific implementation.

Concurrent CollectionsApplications that use collections from more than one thread must be carefully programmed. In general,this is known as concurrent programming. The Java platform includes extensive support for concurrentprogramming. See Java Concurrency Utilities for details.

Collections are so frequently used that various concurrent friendly interfaces and implementations ofcollections are included in the APIs. These types go beyond the synchronization wrappers discussedpreviously to provide features that are frequently needed in concurrent programming.

These concurrent-aware interfaces are available:

BlockingQueueTransferQueueBlockingDequeConcurrentMapConcurrentNavigableMap

déclarer le type des variables par l’interface et initialiser par l’implantation choisie

Map<Long,String> M = new HashMap<>();// tableau de hachageSet<Number> S = new TreeSet<>();// arbre binaire de recherche

(types paramétrisés !)

java.util.Collection

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös xv

public interface Collection<E> extends Iterable<E>// contient des éléments de type E

{// opérations de baseint size();boolean isEmpty();boolean contains(Object element);boolean add(E element); //optionnelleboolean remove(Object element); //optionnelleIterator<E> iterator();

// opérations de masseboolean containsAll(Collection<?> c);boolean addAll(Collection<? extends E> c); //optionnelleboolean removeAll(Collection<?> c); //optionnelleboolean retainAll(Collection<?> c); //optionnellevoid clear(); //optionnelle

// opérations de tableauxObject[] toArray();<T> T[] toArray(T[] a);

}

java.util.AbstractCollection

Types abstraits ? IFT2015 H2020 ? UdeM ? Miklós Csűrös xvi

génie logiciel économique : afin d’implémenter Collection, il suffit de définirune sous-classe de AbstractCollection— il ne reste que deux méthodes à coder !

public abstract class AbstractCollection<E>implements Collection<E>

{public abstract Iterator<E> iterator(); // à implémenterpublic abstract int size(); // à implémenter

public boolean isEmpty(){ return size()==0;} // par défaut

public boolean contains(Object obj){

Iterator iter = iterator();// parcours de la collection, comparer avec obj

}...

� l’implémentation par défaut est non-fonctionnelle (UnsupportedOperationException)

ou inefficace pour toute méthode intéressante