Package ldc

DIU EIL 2020/2022

BLOC3 - Liste Doublement Chainée

Project Status: Inactive – The project has reached a stable, usable state but is no longer being actively developed; support/maintenance will be provided as time allows.

The project has reached a stable, usable state but is no longer being actively developed;

Support/maintenance will be provided as time allows.

Logo

About The Project

L’objectif de ce projet est de développer le type de données Liste Doublement Chaînée (LDC). Il s’agit d’un enrichissement du type Liste Chainée vu pendant le cours.

Pour une LDC, un nœud est constitué :

  • d’une valeur,
  • d’une référence sur le nœud suivant,
  • et d’une référence sur le nœud précédent.

Remarques :

  • Pour le premier nœud, le nœud précédent est None.
  • Pour le dernier nœud, le nœud suivant est None.
  • On considérera des nœuds contenant des entiers.
  • De même qu’en cours, un nœud sera défini par une liste (tableau) Python.
  • Le type LDC sera confondu avec le type nœud (NoeudLDC) de cette liste.
  • Une liste vide vaudra donc None.

Partie 1

  • Créer la fonction CreerNoeudLDC(val,precedent,suivant) : NoeudLDC
  • val (entier) : la valeur contenue dans le noeud
  • precedent (NoeudLDC) : le nœud précédent. Vaut None pour un nœud en début de liste
  • suivant (NoeudLDC) : le nœud suivant. Vaut None pour un nœud en fin de liste
  • Créer la fonction EstNoeudLDC(n : NoeudLDC) : booleen : qui vérifie que n est bien un nœud de liste doublement chainée, c’est-à-dire que :
  • n vaut None ou :
  • n est une liste de 3 éléments (la fonction native isinstance sera utile)
    • n[0] est un entier
    • n[1] et n[2] sont aussi des NoeudLDC (fonction récursive)
  • Créer les fonctions d’accès aux données, et de modifications de ces données :
  • GetValLDC(n : NoeudLDC) : entier
  • GetPrecedentLDC(n : NoeudLDC) : NoeudLDC
  • GetSuivantLDC(n : NoeudLDC) : NoeudLDC
  • Créez les fonctions suivantes :
  • LongueurLDC(l) : entier (renvoie la longueur de la liste)
  • InsererDebutLDC(l,val) : NoeudLDC (insère un nœud au début de la liste)
  • InsererFinLDC(l,val) : NoeudLDC (insère un nœud à la fin de la liste)
  • SupprimerDebutLDC(l) : NoeudLDC (supprime le premier nœud de la liste)
  • SupprimerFinLDC(l) : NoeudLDC (supprime le dernier nœud de la liste)
  • AccesLDC(l,p) : NoeudLDC (renvoie le nœud d’indice p dans la liste. Le premier nœud a pour indice 0)
  • InsererPlaceLDC(l,val,p) : NoeudLDC (insère le nœud contenant val juste après le nœud d’indice p ; le premier nœud a pour indice 0)
  • SupprimerPlaceLDC(l,p) : NoeudLDC (supprime de l le nœud d’indice p ; le premier nœud a pour indice 0)
  • SupprimerValLDC(l,val) : NoeudLDC (supprime de l le premier nœud contenant val ; premier car en effet, rien n’interdit que la liste contienne des doublons)
  • LDC2List(l) : tableau (renvoie la liste Python (tableau) contenant les éléments de l ; renvoie [] si l vaut None)
  • List2LDC(l) : NoeudLDC (renvoie la liste doublement chainée contenant dans le même ordre les éléments de la liste Python (tableau) l ; renvoie None si l vaut [])
  • Pour chaque fonction, vous chercherez à quelles conditions la fonction peut être appelée (par exemple, on ne peut pas supprimer le premier élément d’une liste vide ; ou encore, on peut vérifier le type des arguments, via l’utilisation de isinstance et EstNoeudLDC). Vous rédigerez alors une condition assert pour chacune de ces conditions, comme vu en cours, dans l’exemple de la liste simplement chainée.

Dans une partie python if __name__ == "__main__", vous rédigerez un jeu de test vous convainquant que votre programme ne comporte pas de bug. Chaque fonction doit donc être testée.

Partie 2

Créez un nouveau fichier qui importe le précédent.

Ce fichier va définir les fonctionnalités pour faire en sorte que la liste soit triée dans l’ordre croissant

  • Créer la fonction EstOrdonneeLDC(l) : booleen, qui renvoie True si la liste est croissante (doublons possibles)
  • Créer la fonction TriLDC(l) : NoeudLDC qui renvoie la liste doublement chainée triée des entiers de la liste doublement chainée l. On utilisera LDC2List, puis la fonction sort de Python, puis List2LDC
  • Créer la fonction InsereOrdreLDC(l,val) qui insère val à sa place dans la liste doublement chainée croissante l, de manière que l reste croissante

De même, il faudra rédiger une partie main pour tester ces deux nouvelles fonctions.

Conseils

Pensez à bien commenter vos fonctions. Pour cela, suivez les normes décrites dans les documents suivants :

Getting Started

To get a local copy up and running follow these simple steps.

Prerequisites

None

Installation

Cloner le dépot

git clone https://framagit.org/slozano54/listedoublementchainee

Ou télécharger l'archive zip.

Pour générer la documentation il faut installer le paquet python pdoc3

pip3 install pdoc

Les fichiers de la documentation sont générés dans le dossier ./docs/ldc

Usage

À la racine du projet, lancer le script python programmePrincipal.py

python3 programmePrincipal.py
  • Choisir la partie à tester en tapant 1 ou 2 :

https://framagit.org/slozano54/listedoublementchainee

  • Partie 1, choisir les tests à lancer en tapant 1, 2, 3 ou 4 :

https://framagit.org/slozano54/listedoublementchainee

Par exemple, les tests pour les définitions :

https://framagit.org/slozano54/listedoublementchainee

  • Pour la partie 1, il y a un sous menu pour tester les fonctions indépendamment :

https://framagit.org/slozano54/listedoublementchainee

  • Partie 2, choisir les tests à lancer en tapant 1, 2, 3 ou 4 :

https://framagit.org/slozano54/listedoublementchainee

Roadmap

See the open issues for a list of proposed features (and known issues).

Contributing

Contributions are what make the open source community such an amazing place to be learn, inspire, and create. Any contributions you make are greatly appreciated.

  1. Fork the Project
  2. Create your Feature Branch (git checkout -b feature/AmazingFeature)
  3. Commit your Changes (git commit -m 'Add some AmazingFeature')
  4. Push to the Branch (git push origin feature/AmazingFeature)
  5. Open a Pull Request

License

MIT

Contact

Sébastien LOZANO - Write me on gitlab

Project Link: https://framagit.org/slozano54/listedoublementchainee

Expand source code
#!/usr/bin/python3
#-*- coding: utf8 -*-

# @author : Sébastien LOZANO

# Source pour l'écriture d'un REAMDE en mardown : https://www.makeareadme.com/ 
# Génère la page d'accueil de la documentation pdoc3

"""
# DIU EIL 2020/2022 
## BLOC3 - Liste Doublement Chainée

<!-- ![Work in progress](http://www.repostatus.org/badges/latest/wip.svg) -->
![Project Status: Inactive – The project has reached a stable, usable state but is no longer being actively developed; support/maintenance will be provided as time allows.](https://www.repostatus.org/badges/latest/inactive.svg)

_The project has reached a stable, usable state but is no longer being actively developed;_

_Support/maintenance will be provided as time allows._

<a href="https://framagit.org/slozano54/listedoublementchainee">
  <img src="https://framagit.org/slozano54/listedoublementchainee/-/raw/master/images/logo.png" alt="Logo" width="80" height="80">
</a>

<!-- ABOUT THE PROJECT -->
## About The Project
L’objectif de ce projet est de développer le type de données **Liste Doublement Chaînée (LDC)**. Il s’agit
d’un enrichissement du type Liste Chainée vu pendant le cours.

Pour une LDC, un nœud est constitué :

- d’une valeur,
- d’une référence sur le nœud suivant,
- et d’une référence sur le nœud précédent.

Remarques :

- Pour le premier nœud, le nœud précédent est None.
- Pour le dernier nœud, le nœud suivant est None.
- On considérera des nœuds contenant des entiers.
- De même qu’en cours, un nœud sera défini par une liste (tableau) Python.
- Le type LDC sera confondu avec le type nœud (NoeudLDC) de cette liste.
- Une liste vide vaudra donc None.

### Partie 1

- Créer la fonction **CreerNoeudLDC(val,precedent,suivant) : NoeudLDC**
  - **val (entier)** : la valeur contenue dans le noeud
  - **precedent (NoeudLDC)** : le nœud précédent. Vaut None pour un nœud en début de liste
  - **suivant (NoeudLDC)** : le nœud suivant. Vaut None pour un nœud en fin de liste
- Créer la fonction **EstNoeudLDC(n : NoeudLDC) : booleen** : qui vérifie que n est bien un nœud de liste doublement chainée, c’est-à-dire que :
  - n vaut None ou :
  - n est une liste de 3 éléments (la fonction native isinstance sera utile)
    - n[0] est un entier
    - n[1] et n[2] sont aussi des NoeudLDC (fonction récursive)
- Créer les fonctions d’accès aux données, et de modifications de ces données :
  - **GetValLDC(n : NoeudLDC) : entier**
  - **GetPrecedentLDC(n : NoeudLDC) : NoeudLDC**
  - **GetSuivantLDC(n : NoeudLDC) : NoeudLDC**
- Créez les fonctions suivantes :
  - **LongueurLDC(l) : entier** (renvoie la longueur de la liste)
  - **InsererDebutLDC(l,val) : NoeudLDC** (insère un nœud au début de la liste)
  - **InsererFinLDC(l,val) : NoeudLDC** (insère un nœud à la fin de la liste)
  - **SupprimerDebutLDC(l) : NoeudLDC** (supprime le premier nœud de la liste)
  - **SupprimerFinLDC(l) : NoeudLDC** (supprime le dernier nœud de la liste)
  - **AccesLDC(l,p) : NoeudLDC** (renvoie le nœud d’indice p dans la liste. Le premier nœud a pour indice 0)
  - **InsererPlaceLDC(l,val,p) : NoeudLDC** (insère le nœud contenant val juste après le nœud d’indice p ; le premier nœud a pour indice 0)
  - **SupprimerPlaceLDC(l,p) : NoeudLDC** (supprime de l le nœud d’indice p ; le premier nœud a pour indice 0)
  - **SupprimerValLDC(l,val) : NoeudLDC** (supprime de l le premier nœud contenant val ; premier car en effet, rien n’interdit que la liste contienne des doublons)
  - **LDC2List(l) : tableau** (renvoie la liste Python (tableau) contenant les éléments de l ; renvoie [] si l vaut None)
  - **List2LDC(l) : NoeudLDC** (renvoie la liste doublement chainée contenant dans le même ordre les éléments de la liste Python (tableau) l ; renvoie None si l vaut [])
- Pour chaque fonction, vous chercherez à quelles conditions la fonction peut être appelée (par exemple, on ne peut pas supprimer le premier élément d’une liste vide ; ou encore, on peut vérifier le type des arguments, via l’utilisation de isinstance et EstNoeudLDC). Vous rédigerez alors une condition assert pour chacune de ces conditions, comme vu en cours, dans l’exemple de la liste simplement chainée.

> Dans une partie ```python if __name__ == "__main__"```, vous rédigerez un jeu de test vous convainquant que votre programme ne comporte pas de bug. Chaque fonction doit donc être testée.

### Partie 2

Créez un nouveau fichier qui importe le précédent.

Ce fichier va définir les fonctionnalités pour faire en sorte que la liste soit triée dans l’ordre croissant

- Créer la fonction **EstOrdonneeLDC(l) : booleen**, qui renvoie True si la liste est croissante (doublons possibles)
- Créer la fonction **TriLDC(l) : NoeudLDC** qui renvoie la liste doublement chainée triée des entiers de la liste doublement chainée l. On utilisera LDC2List, puis la fonction sort de Python, puis List2LDC
- Créer la fonction **InsereOrdreLDC(l,val)** qui insère val à sa place dans la liste doublement chainée croissante l, de manière que l reste croissante

> De même, il faudra rédiger une partie main pour tester ces deux nouvelles fonctions.

### Conseils
Pensez à bien commenter vos fonctions. Pour cela, suivez les normes décrites dans les documents suivants :

- https://www.python.org/dev/peps/pep-0008/#comments
- https://www.python.org/dev/peps/pep-0257/

<!-- [![Product Name Screen Shot][product-screenshot]](https://example.com) -->

<!-- GETTING STARTED -->
## Getting Started

To get a local copy up and running follow these simple steps.

### Prerequisites

None

### Installation

Cloner [le dépot](https://framagit.org/slozano54/listedoublementchainee)

```shell
git clone https://framagit.org/slozano54/listedoublementchainee
```

Ou télécharger l'[archive zip](https://framagit.org/slozano54/listedoublementchainee/-/archive/master/listedoublementchainee-master.zip).

Pour générer la documentation il faut installer le paquet python [pdoc3](https://pdoc3.github.io/pdoc/)

```shell
pip3 install pdoc
```

Les fichiers de la documentation sont générés dans le dossier **./docs/ldc**

<!-- USAGE EXAMPLES -->

<!-- _For more examples, please refer to the [Documentation](https://framagit.org/slozano54/listedoublementchainee)_ -->

<!-- USAGE -->
## Usage

À la racine du projet, lancer le script python **programmePrincipal.py**

```shell
python3 programmePrincipal.py
```

- Choisir la partie à tester en tapant 1 ou 2 :

![https://framagit.org/slozano54/listedoublementchainee](https://framagit.org/slozano54/listedoublementchainee/-/raw/master/images/screenShot_1.png)

- **Partie 1**, choisir les tests à lancer en tapant 1, 2, 3 ou 4 :

![https://framagit.org/slozano54/listedoublementchainee](https://framagit.org/slozano54/listedoublementchainee/-/raw/master/images/screenShot_3.png)

Par exemple, les tests pour les définitions :

![https://framagit.org/slozano54/listedoublementchainee](https://framagit.org/slozano54/listedoublementchainee/-/raw/master/images/screenShot_4.png)

- Pour la **partie 1**, il y a un sous menu pour tester les fonctions indépendamment :

![https://framagit.org/slozano54/listedoublementchainee](https://framagit.org/slozano54/listedoublementchainee/-/raw/master/images/screenShot_5.png)

- **Partie 2**, choisir les tests à lancer en tapant 1, 2, 3 ou 4 :

![https://framagit.org/slozano54/listedoublementchainee](https://framagit.org/slozano54/listedoublementchainee/-/raw/master/images/screenShot_2.png)

<!-- ROADMAP -->
## Roadmap

See the [open issues](https://framagit.org/slozano54/listedoublementchainee/issues) for a list of proposed features (and known issues).

<!-- CONTRIBUTING -->
## Contributing

Contributions are what make the open source community such an amazing place to be learn, inspire, and create. Any contributions you make are **greatly appreciated**.

1. Fork the Project
2. Create your Feature Branch (`git checkout -b feature/AmazingFeature`)
3. Commit your Changes (`git commit -m 'Add some AmazingFeature'`)
4. Push to the Branch (`git push origin feature/AmazingFeature`)
5. Open a Pull Request



<!-- LICENSE -->
## License

[MIT](https://choosealicense.com/licenses/mit/)

<!-- CONTACT -->
## Contact

Sébastien LOZANO - Write me on gitlab

Project Link: [https://framagit.org/slozano54/listedoublementchainee](https://framagit.org/slozano54/listedoublementchainee)
"""
pass

# Pour gérer les imports relatifs 
import os, sys; sys.path.append(os.path.dirname(os.path.realpath(__file__)))

Sub-modules

ldc.partie1

Toutes les méthodes permettant de travailler sur les listes doublement chainées

ldc.partie2

Toutes les méthodes permettant de travailler sur l'ordre des listes doublement chainées

ldc.tools

Des outils pour des trucs et des machins made in home.