Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros

TYPES ABSTRAITS (DE DONNEES)

Abstraction de donnees

Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros ii

Def. Un type est un ensemble (possiblement infini) de valeurs et d’operations surcelles-ci.

�type = domaine + operations

Def. Un type abstrait (TA) est un type accessible uniquement a travers une in-terface.

�TA = type + interface

client : le programme qui utilise le TAinterface : contrat entre client et l’implementationimplementation : le programmme qui specifie le TA

? fondations : nombres, caracteres, chaınes, . . .? objets : temps, fichier, forme geometrique, . . .? collections d’elements � etudier les structures de donnees pour les implementer

? graphes, reseaux � choisir la bonne structure pour son algorithme

Java et Type Abstrait

Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros iii

� la philosophie orientee objet de Java est proche de notre abstraction� avec quelques differences

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 H2019 ? UdeM ? Miklos Csuros iv

� la philosophie orientee objet de Java est proche de notre abstraction� avec quelques differences

? Java impose des contraintes de syntaxe sur la specification de l’interface du TA? clients avec droits differents

public class C{

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

void kolme(C arg){...} // meme package...

}

? interface de Java n’est pas exactement l’interface de notre definition(ne definit pas le syntaxe des constructeurs)

? implementation et interface souvent dans le meme fichier(la classe qui declare et definit une methode)

Structure de donnees

Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros v

si on veut implanter un type abstrait :? il faut decider comment stocker la valeur

(pour une collection, «valeur» = ensemble d’elements dans la collection),? il faut decider sur les algorithmes pour les operations specifiees par l’interface,? et encoder l’atout (dans ce cours, en Java)� objet avec variables privees pour stocker la valeur� methodes d’instance et de classe pour implanter les algorithmes

structure de donnees

= implementation d’un type abstrait (collection)= specification du stockage des donnees et des algorithmes qui performent lesoperations

File

Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros vi

File generalisee (TA) = collection d’elements avec deux operations :

1. injection d’un element : ajouter / inserer / enfiler / empiler / . . .

2. ejection d’un element : retirer / supprimer / defiler / depiler / . . .

il existe beaucoup de variantes selon la politique d’injection/ejection, ainsi quel’interface pour le TA (= comment specifie-t-on l’«element» ?)

Pile — abstraction

Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros vii

Le type abstrait pile (stack ) :abstraction d’une pile d’objets : empiles l’un sur l’autre, on ne peut acceder qu’al’element le plus recemment empile

operations du TA : «empiler» (push) et «depiler» (pop)

pop

pop

pushpop

push

push

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

� on a le droit de stocker les elements comme on veut car il n’y a pas d’autre operation d’acces

Queue — abstraction

Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros viii

Le type abstrait queue ou file FIFO (queue en anglais) :abstraction de file d’attente : objets ranges un apres l’autre, on peut enfiler a la finou defiler au debut

operations du TA : «enfiler» (enqueue) et «defiler» (dequeue)

dequeue

dequeue

enqueue

dequeue

enqueue

enqueue

� la structure de donnees doit assurer la logique FIFO (first-in first-out) de push/pop

� on a le droit de stocker les elements comme on veut car il n’y a pas d’autre operation d’acces

Pile et queue

Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros ix

importance fondamentale en informatique

pile : permet de sauvegarder et retablir l’etat? execution d’appel de procedures, recursivite (variables locales stockees sur la pile)? analyse syntaxique, compilation (appariement d’elements syntaxiques t.q. { . . .})

� syntaxe = grammaire hors-contexte = reconnu par automate a pile

queue : permet de syncroniser production et consommation en respectant l’ordre? lecture et ecriture de fichiers, streaming? requete et execution de taches : serveur Web, print queue, ordonnancement des

processus

TAs classiques

Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros 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 H2019 ? UdeM ? Miklos Csuros xi

Java est un langage fortement type (toute variable a un type declare)? types primitifs (int, double, boolean, . . . )? types agreges (tableaux, et ceux definis par les classes et les interfaces)Def. variable = abstraction d’un emplacement en memoire (von Neumann)

composants d’une variable :

1. nom

2. adresse (lvalue)

3. valeur (rvalue)

4. type

5. portee / visibilite

? En Java, la valeur d’une variable de type agrege est une reference.? Une reference (ou pointeur) est soit null soit l’adresse d’un emplacement memoire

contentant une valeur typee.

Memoire en Java

Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros 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 H2019 ? UdeM ? Miklos Csuros xiii

Interfaces fondamentales dans le package java.util :

java.util.List : acces par indice d’elementjava.util.Map =table de symboles = dictionnaire : recherche par clejava.util.Deque : file avec acces aux deux extremites

Multiples implementations

Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros 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

declarer 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 parametrises !)

java.util.Collection

Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros xv

public interface Collection<E> extends Iterable<E>// contient des elements de type E

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

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

// operations de tableauxObject[] toArray();<T> T[] toArray(T[] a);

}

java.util.AbstractCollection

Types abstraits ? IFT2015 H2019 ? UdeM ? Miklos Csuros xvi

genie logiciel economique : afin d’implementer Collection, il suffit de definirune sous-classe de AbstractCollection— il ne reste que deux methodes a coder !

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

{public abstract Iterator<E> iterator(); // a implementerpublic abstract int size(); // a implementer

public boolean isEmpty(){ return size()==0;} // par defaut

public boolean contains(Object obj){

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

}...

� l’implementation par defaut est non-fonctionnelle (UnsupportedOperationException)

ou inefficace pour toute methode interessante