M2103-TP9-EXO-1

Créer le projet ReseauSocial.

Depuis C++11, C++ offre une bibliothèque ctime, qui permet de grossièrement gérer l’heure et la date. Cette bibliothèque reprend les structures du C, dans l’espace de nom std. Pour obtenir la date du jour, il faut procéder en 2 étapes. D’abord, récupérer le nombre de secondes écoulées depuis le 01/01/1970, à l’aide de la fonction time() de profil (simplifié)

time (time_t * t);

qui s’utilise comme suit :

time_t t; 
time (&t);

Ensuite,on transforme le time_t en une structure struct tm (rappel: struct classe où tout est publique par défaut) à l’aide de la fonction localtime() de profil

tm * localtime (time_t * t);

qui transforme t, le nombre de secondes écoulées depuis le 01/01/1970, en une tm et s’utilise comme suit :

tm local = * localtime (& t);

nous allons encapsuler cette struct tm dans la classe Date, comme sur le schéma UML suivant, de manière à interdire, à l’utilisateur qui utiliserait cette classe Date, l’accès aux attributs de la struct tm :

On ajoutera à cette classe Date un constructeur par défaut qui construit une Date avec la date du jour.

Travail demandé

Ecrire complètement les fichiers Date.h et Date.cpp qui contiennent respectivement les déclarations et les définitions de la classe Date correspondant au schéma et aux explications, dans l’espace de noms std.
Tester en ajoutant la fonction suivante à l’espace de noms anonyme de votre main.cpp :

    void testDate (void)
    {
        Date date;
        cout << "Aujourd'hui nous sommes le : " 
             << date.getDay () << ' ' << date.getMonth () << ' ' << date.getYear ()
             << " et il est " << date.getHour () << "h " << date.getMinute () 
             << "mn et " <

Petit problème, le mois est le mois dernier et l'année est n'importe quoi. Voici ce que dit le man sur les attributs mis en cause dans le struct tm :

           struct tm {
               int tm_sec;    /* Seconds (0-60) */
               int tm_min;    /* Minutes (0-59) */
               int tm_hour;   /* Hours (0-23) */
               int tm_mday;   /* Day of the month (1-31) */
               int tm_mon;    /* Month (0-11) */
               int tm_year;   /* Year - 1900 */
               int tm_wday;   /* Day of the week (0-6, Sunday = 0) */
               int tm_yday;   /* Day in the year (0-365, 1 Jan = 0) */
               int tm_isdst;  /* Daylight saving time * /
           };

Corriger dans les 2 accesseurs concernés et tester à nouveau.

M2103-TP9-EXO-2

Le but de ce qui suit est de traduire en C++ le schéma UML suivant :

Dans l’espace de noms anonyme du fichier main.cpp déclarer la classe Message, comme elle est décrite sur le schéma UML. Y ajouter un constructeur qui se contente de remplir myContent avec un paramètre correspondant, et myDate, avec la date courante (constructeur par défaut de Date). La fonction displayContent() affiche à l’écran le contenu du message. Vous intégrerez directement les définitions des fonctions dans la classe.
Dans l’espace de noms anonyme, insérer les différentes classes (exercices suivants), de haut en bas, dans l’ordre des exercices. Normalement, seules des déclarations de classes vides seront à ajouter. Lorsque cela sera nécessaire un embryon de classe sera fourni.

Ajouter à la classe l’accesseur à l’attribut myDate.

Dans l’espace de noms anomyme ajouter les fonctions displayDate() suivante :

    void displayDate (const Date & date)
    {
        cout << date.getDay () << ' ' << date.getMonth () << ' ' << date.getYear ();
    
    } // displayDate()

et displayHour() suivante :

    void displayHour (const Date & date)
    {
        cout << date.getHour () << "h " << date.getMinute () 
             << "mn et " <

Tester avec la fonction testMessage() suivante, également à incorporer à l'espace de noms anonyme du fichier main.cpp :

    void testMessage (void)
    {
        Message message ("salut");
        message.displayContent ();
        cout << " posté le : ";
        displayDate (message.getDate ());
        cout << " à ";
        displayHour (message.getDate ());
        cout << endl;

    } // testMessage()}

M2103-TP9-EXO-3

Dans l’espace de noms anonyme du fichier main.cpp déclarer la classe PublicMessage, comme elle est décrite sur le schéma UML.
La fonction add() se contente d’incrémenter de 1 myLikers (nombre de personnes qui aiment ce message).
Ajouter l’accesseur à myNbLikers.
Tester avec la fonction testPublicMessage() suivante, à incorporer également à l’espace de noms anonyme.

    void testPublicMessage (void)
    {
        PublicMessage message ("salut");
        message.displayContent ();
        cout << " posté le : ";
        displayDate (message.getDate ());
        cout << " à ";
        displayHour (message.getDate ());
        cout << endl;
        for (unsigned i(0); i < 5; ++i)
            message.add ();
        cout << "Nb de likers : " << message.getNbLikers (); << endl;

    } // testPublicMessage()

M2103-TP9-EXO-4

Dans l’espace de noms anonyme du fichier main.cpp déclarer la classe PrivateMessage, comme elle est décrite sur le schéma UML. Le constructeur a la tâche supplémentaire d’initialiser le lien avec l’User.
Ajouter l’accesseur à ce lien.

Tester avec la fonction testPrivateMessage() et la classe User provisoire suivantes, à incorporer également à l’espace de noms anonyme.

    class User
    {
       public :
       void sendMessage (const PrivateMessage & message)
       {
           message.displayContent ();
           cout << endl;
       } // sendMessage()
       void addFriend (User * oneFriend) { cout << "ajouté" << endl; }
       User * getFriend (unsigned i) const { cout << i << endl; return new User; }
       System * getSystem (void) const { cout << "système" << endl; return NULL; }
       void addMessage (const PrivateMessage & message) { message.displayContent (); cout << endl; }
       
    }; // User
    
    void testPrivateMessage (void)
    {
        User user;
        PrivateMessage message ("salut", & user);
        message.displayContent ();
        cout << " posté le : ";
        displayDate (message.getDate ());
        cout << " à ";
        displayHour (message.getDate ());
        cout << endl;
        message.getSender ()->getFriend (5);

    } // testPrivateMessage()

M2103-TP9-EXO-5

Dans l’espace de noms anonyme du fichier main.cpp déclarer la classe User, comme elle est décrite sur le schéma UML. Le constructeur initialise les attribut, si nécessaire, aux valeurs des paramètres correspondants. Il ne faut surtout pas que les adresses des messages que génère l’User puissent changer. Il est donc absolument nécessaire de réserver assez de place pour ranger tous les messages (reserve (1000) devrait suffire.
Un utilisateur ne doit pas pouvoir modifier les messages qu’il a reçus, ils sont la propriété de leur émetteur.
La fonction sendMessage() est proposée aux amis de l’User, elle ajoute donc un message à la liste des messages reçus.
La fonction addMessage() sert à ajouter un message dans la liste des messages envoyés, de façon à pouvoir l’envoyer à un ami, par la suite, mais pas forcément maintenant.
Ajouter l’accesseur à l’attribut myName
Ajouter la méthodesgetSentMessage(), pour accéder au ième message envoyé. Attention ! On doit renvoyer le ième message, pas une copie de celui-ci. Attention encore, il est hors de question de pouvoir modifier ce message. C’est une référence sur un objet constant qu’il faut donc retourner.
Ajouter la méthodesgetRecievedMessage(), pour accéder au ième message reçu. Attention à nouveau ! Il est hors de question de pouvoir modifier ce message.

Ajouter les méthodes GetNbSentMessages(), GetNbFriends() et GetNbRecievedMessages().

Tester avec la fonction testUser() suivante :

    void testUser (void)
    {
        System oneSystem;
        User alfred    ("Alfred", NULL);
        User alain     ("Alain", NULL);
        User sophie    ("Sophie", NULL);
        User emmanuel  ("Emmanuel", NULL);
        User christian ("Christian", NULL);
        User petru     ("Petru", NULL);
        User marc      ("Marc", NULL);
        PrivateMessage message ("salut", & alfred);
        message.displayContent ();
        cout << endl;

        alain.addFriend (&sophie);
        alain.addFriend (&emmanuel);
        alain.addFriend (&christian);
        alain.addFriend (&petru);
        alain.addFriend (&marc);

        cout << "Alain a " << alain.getNbFriends () << " amis" << endl;
        cout << "Le troisième ami d'Alain est : " << (alain.getFriend (2))->getName () << endl;

        alfred.addMessage (message);
        alain.sendMessage (&message);
        cout << "Nombre de message envoyés par Alfred : " << alfred.getNbSentMessages ()   << endl;
        cout << "Nombre de message reçus par Alfred : " << alfred.getNbRecievedMessages () << endl;
        cout << "Nombre de message envoyés par Alain : " << alain.getNbSentMessages ()   << endl;
        cout << "Nombre de message reçus par Alain : " << alain.getNbRecievedMessages () << endl;
        alain.getRecievedMessage (0)->displayContent ();
        cout << endl;
        alfred.getSentMessage (0).displayContent ();
        cout << endl;

    } // testUser()

M2103-TP9-EXO-5-Corrigé

    class System;

    class User
    {
        string   myName;
        System * mySystem;
        vector <PrivateMessage>    mySentMessages;
        vector <PrivateMessager *> myRecievedMessages;
        vector <User *>            myFriends;

      public :
        User (const string & name, System * system = NULL) : myName (name), mySystem (system)
        {
            mySentMessages.reserve (20);
        }
        void addFriend (User * aFriend)
        {
           myFriends.push_back (aFriend);

        } // addFriend()

        const string & getName (void) const { return myName; }

        User * getFriend (unsigned i) const { return myFriends [i]; }

        const PrivateMessage & getSentMessage (unsigned i) const { return mySentMessages [i]; }

        const PrivateMessage * getRecievedMessage (unsigned i) const { return myRecievedMessages [i]; }

        System * getSystem (void) const { return mySystem; }

        unsigned getNbFriends        (void) const { return myFriends.size (); }

        unsigned getNbSentMessages   (void) const { return mySentMessages.size (); }

        unsigned getNbRecievedMessages (void) const { return myRecievedMessages.size ();  }

        void sendMessage (const PrivateMessage * message)
        {
            myRecievedMessages.push_back (message);

        } // sendMessage()

        void addMessage (const PrivateMessage & message)
        {
            mySentMessages.push_back (message);
        }

    }; // User

M2103-TP9-EXO-6

Dans l’espace de noms anonyme du fichier main.cpp déclarer la classe System, comme elle est décrite sur le schéma UML. Le constructeur sera utilisé, comme dans le TD3 (TP4) pour tester le programme.
La fonction getUser() renvoie le ième User (pas une copie).
Idem pour getPublicMessage().
Voici le constructeur :

        System (void) : myNbUsers (0), myNbMessages (0)
        {
            myUsers.reserve (1000);
            myPublicMessages.reserve (1000);
            // création des Users
            addUser ("Alfred");
            addUser ("Alain");
            addUser ("Sophie");
            addUser ("Emmanuel");
            addUser ("Christian");
            addUser ("Petru");
            addUser ("Marc");
            /* verification des Users */
            cout << myUsers.size () << endl;
            for (const User & user : myUsers)
            {
                cout << user.getName () << endl;
            }


            /* création de leurs amis * /
            for (unsigned i (0); i < myUsers.size (); ++i)
                for (unsigned j (0); j < myUsers.size () / 2; ++j)
                    myUsers [i].addFriend (&myUsers [(i + ((j * 2) + 1)) % myUsers.size ()]);

            /*  verification des amis  * /
            for (unsigned i (0); i < myUsers.size (); ++i)
            {
                User user = myUsers [i];
                cout << user.getName () << " a " << user.getNbFriends() << " amis : " << endl;
                for (unsigned j (0); j < user.getNbFriends (); ++j)
                    cout << (user.getFriend (j))->getName () << endl;
            }
            /*  création et envoi des messages privés  * /
            for (User & user : myUsers)
            {
                for (unsigned j (0); j < user.getNbFriends (); ++j)
                {
                    string content (string ("salut") + ' ' + (user.getFriend (j))->getName ());
                    PrivateMessage message (content, & user);
                    user.addMessage (message);
                    (user.getFriend (j))->sendMessage (&(user.getSentMessage (user.getNbSentMessages () - 1)));
                }
            }
            /*  vérifications des messages envoyés  * /
            for (unsigned i (0); i < myUsers.size (); ++i)
            {
                User user = myUsers [i];
                cout << user.getName () << " a envoyé " << user.getNbSentMessages() << " messages : " << endl;
                for (unsigned j (0); j < user.getNbSentMessages (); ++j)
                {
                    (user.getSentMessage (j)).displayContent();
                    cout << endl;
                }

            }
            /*  vérifications des messages reçus  * /
            for (unsigned i (0); i < myUsers.size (); ++i)
            {
                User user = myUsers [i];
                cout << user.getName () << " a reçu " << user.getNbRecievedMessages() << " messages : " << endl;
                for (unsigned j (0); j < user.getNbRecievedMessages (); ++j)
                {
                    cout << "de " << (user.getRecievedMessage (j))->getSender ()->getName () << " : ";
                    (user.getRecievedMessage (j))->displayContent();
                    cout << endl;
                }

            }
            /* création et envoie des messages publiques  * /
            string oneMessage ("a");
            for (const User & user : myUsers)
                for (unsigned i (0); i < 5; ++i)
                {
                    oneMessage += 'a';
                    (user.getSystem ())->addPublicMessage (oneMessage);
                }
            /* test de la création des messages * /
            for (const PublicMessage & message : myPublicMessages)
            {
                message.displayContent ();
                cout << endl;
            }
            /*  création des like  * /
            for (User & user : myUsers)
                for (unsigned i (0); i < myNbMessages; ++i)
                    (user.getSystem ())->getPublicMessage (i).add ();

            /*  test des likes * /
            for (const PublicMessage & message : myPublicMessages)
            {
                message.displayContent ();
                cout << " a " << message.getNbLikers () << " likers" << endl;
            }
/*    */

         } // System()

Dans la fonction main() il suffit de déclarer un objet System pour effectuer les tests.
Au fur et à mesure de vos mises au point, déplacer l'espace entre * et / d'un commentaire à l'autre.

M2103-TP9-EXO-6-Corrigé

    class System
    {
        unsigned                 myNbUsers;
        vector             myUsers;
        unsigned                 myNbMessages;
        vector    myPublicMessages;
      public :
        User  & getUser    (unsigned i) { return myUsers [i]; }
        PublicMessage & getPublicMessage (unsigned i) { return myPublicMessages [i]; }

        void addUser (const string & name)
        {
            myUsers.push_back (User (name, this));
            ++myNbUsers;

        } // addUsers()

        void addPublicMessage (const string & message)
        {
            myPublicMessages.push_back (message);
            ++myNbMessages;

        } // addPublicMessage())

        System (void) : myNbUsers (0), myNbMessages (0)
        {
            myUsers.reserve (1000);
            myPublicMessages.reserve (1000);
            // création des Users
            addUser ("Alfred");
            addUser ("Alain");
            addUser ("Sophie");
            addUser ("Emmanuel");
            addUser ("Christian");
            addUser ("Petru");
            addUser ("Marc");
            /* verification des Users */
            cout << myUsers.size () << endl;
            for (const User & user : myUsers)
            {
                cout << user.getName () << endl;
            }


            /* création de leurs amis * /
            for (unsigned i (0); i < myUsers.size (); ++i)
                for (unsigned j (0); j < myUsers.size () / 2; ++j)
                    myUsers [i].addFriend (&myUsers [(i + ((j * 2) + 1)) % myUsers.size ()]);

            /*  verification des amis  * /
            for (unsigned i (0); i < myUsers.size (); ++i)
            {
                User user = myUsers [i];
                cout << user.getName () << " a " << user.getNbFriends() << " amis : " << endl;
                for (unsigned j (0); j < user.getNbFriends (); ++j)
                    cout << (user.getFriend (j))->getName () << endl;
            }
            /*  création et envoi des messages privés  * /
            for (User & user : myUsers)
            {
                for (unsigned j (0); j < user.getNbFriends (); ++j)
                {
                    string content (string ("salut") + ' ' + (user.getFriend (j))->getName ());
                    PrivateMessage message (content, & user);
                    user.addMessage (message);
                    (user.getFriend (j))->sendMessage (&(user.getSentMessage (user.getNbSentMessages () - 1)));
                }
            }
            /*  vérifications des messages envoyés  * /
            for (unsigned i (0); i < myUsers.size (); ++i)
            {
                User user = myUsers [i];
                cout << user.getName () << " a envoyé " << user.getNbSentMessages() << " messages : " << endl;
                for (unsigned j (0); j < user.getNbSentMessages (); ++j)
                {
                    (user.getSentMessage (j)).displayContent();
                    cout << endl;
                }

            }
            /*  vérifications des messages reçus  * /
            for (unsigned i (0); i < myUsers.size (); ++i)
            {
                User user = myUsers [i];
                cout << user.getName () << " a reçu " << user.getNbRecievedMessages() << " messages : " << endl;
                for (unsigned j (0); j < user.getNbRecievedMessages (); ++j)
                {
                    cout << "de " << (user.getRecievedMessage (j))->getSender ()->getName () << " : ";
                    (user.getRecievedMessage (j))->displayContent();
                    cout << endl;
                }

            }
            /* création et envoie des messages publiques  * /
            string oneMessage ("a");
            for (const User & user : myUsers)
                for (unsigned i (0); i < 5; ++i)
                {
                    oneMessage += 'a';
                    (user.getSystem ())->addPublicMessage (oneMessage);
                }
            /* test de la création des messages * /
            for (const PublicMessage & message : myPublicMessages)
            {
                message.displayContent ();
                cout << endl;
            }
            /*  création des like  * /
            for (User & user : myUsers)
                for (unsigned i (0); i < myNbMessages; ++i)
                    (user.getSystem ())->getPublicMessage (i).add ();

            /*  test des likes * /
            for (const PublicMessage & message : myPublicMessages)
            {
                message.displayContent ();
                cout << " a " << message.getNbLikers () << " likers" << endl;
            }
/*    */

         } // System()
     }; // System

M2103-TP8-Exo-1

L’algorithme du quick-sort sera étudié dans le TP de structures de données consacré aux arbres binaires et à la récursivité.

Nous présentons ici un algorithme légèrement différent de la fonction Partitionnement() (l’intervalle est ici fermé) :

template <typename T>
fonction partitionnement (tab   : in_out tableau de T, 
                          first : in     entier_naturel, 
                          last  : in     entier_naturel) renvoie entier_naturel

debut
    Declarer isUp : booleen;
    isUp <- vrai;
    Declarer pivot   : entier_naturel;
    Declarer courant : entier_naturel;
    Declarer incr    : entier;
    pivot   <- first;
    courant <- last;
    incr    <- -1;
    tant_que (pivot ne_vaut_pas courant)
    faire
        si (NON isUp ET_ALORS tab [pivot] < tab [courant]
                OU_SINON
            isUp ET_ALORS tab [courant] < tab [pivot])

            permuter (tab [pivot], tab [courant]);
            permuter (pivot, courant);
            isUp <- NON isUp;
            incr <- -incr;
        fsi
        courant <- courant + incr;
    ffaire
    renvoie pivot;

fin

Rappelons l’algorithme du quick-sort (intervalle semi-ouvert) :

template <typename T>
procedure quickSort (tab   : in_out tableau de T, 
                     beg   : in     entier_naturel, 
                     end   : in     entier_naturel)
debut
    si (beg < end)
        Déclarer pos : entier_naturel;
        pos <- partitionnement (tab, beg, end - 1);

        quickSort (tab, beg,     pos);
        quickSort (tab, pos + 1, end);
    fsi
fin

Travail à effectuer

Créer le projet QuickSort.

Dans l’espace de noms anonyme du fichier QuickSort.cpp, traduire en C++ les deux algorithmes ci-dessus.

Dans ce même espace de noms anonyme, ajouter la classe générique suivante :

    template <typename T>
    class ILessThanGen
    {
      public :
        virtual ~ILessThanGen (void) {}
        virtual bool operator () (const T &, const T &) const = 0;

    }; // ILessThanGen

Ajouter les classes TriParAgeAsc et TriParNomDesc, dérivées de la classe ILessThanGen, qui permet de comparer des Pers respectivement dans l’ordre d’ages croissants et de noms décroissants.

    class Pers
    {
        string   myNom;
        unsigned myAge;
 
      public :
        Pers (const string & Nom, unsigned Age)
            : myNom (Nom), myAge (Age) {}
 
        const string & getNom (void) const noexcept { return myNom; }
        unsigned       getAge (void) const noexcept { return myAge; }
 
    private :
        ostream & display (ostream & os)  const
        {
            return os << getAge () << " - " << getNom ();
 
        } // display()
 
      public :
        friend ostream & operator << (ostream & os, const Pers & p)
        {
            return p.display (os);
 
        }
 
    }; // Pers

Coder les fonctions génériques partitionnement() et quickSort().

Remarques

  1. En C++, le passage du tableau est inutile si la tranche du tableau à traiter est décrite par des itérateurs.
  2. Le type iterator nécessite d’être instancié pour être utilisé. Il ne le sera que lors de l’appel à quickSort(). On ne peut donc déclarer un paramètre de ce type sans que ce type soit un nouveau paramètre de généricité.
  3. La fonction de comparaison utilisée dans la procédure partitionnement() doit être passée sous la forme d’un functor.
  4. Veiller à limiter les variables locales.En particulier, lorsque c’est possible, préférer passer les itérateurs par valeur (par recopie) plutôt que d’en déclarer des instances locales.
  5. Pour des raisons purement algorithmiques, les intervalles sont semi-ouverts lorsqu’ils sont passés à la fonction quickSort() et fermés lorsqu’ils sont passés à la fonction partitionnement().

Test de la fonction quickSort().

La fonction suivante est mise à votre disposition pour tester votre programme :

    void functorSort (void)
    {
        cout << "FunctorSort : \n";
 
        typedef vector <Pers> CVPers;
 
        CVPers vPers;
 
        vPers.push_back ( Pers ("Charlotte", 21));
        vPers.push_back ( Pers ("Alfred",    12));
        vPers.push_back ( Pers ("Jean",      42));
        vPers.push_back ( Pers ("Noemie",    11));
        vPers.push_back ( Pers ("Berthe",    99));
        vPers.push_back ( Pers ("Agathe",    29));
        vPers.push_back ( Pers ("Sylvain",   42));
        vPers.push_back ( Pers ("Pierre",    75));
 
        cout << "\nTri par age croissant\n\n";
 
        quickSort (vPers.begin (), vPers.end (), TriParAgeAsc ());
 
        for (const Pers & personne : vPers)
            cout << personne << '\n';
 
        cout << "\nTri par nom decroissant\n\n";
 
        quickSort (vPers.begin (), vPers.end (), TriParNomDesc ());
 
        for (const Pers & personne : vPers)
            cout << personne << '\n';
 
    } // functorSort()

Dernière remarque

Pour y stocker provisoirement la valeur du pivot, il est nécessaire de déclarer, dans le corps de la fonction, une variable locale du type de l’objet pointé.

Malheureusement, ce type n’est pas connu, il dépend du type de l’itérateur qui a servi à instancier la fonction quickSort().

Il est cependant accessible par la ligne suivante, que vous ajouterez dans la fonction :

typedef typename std::iterator_traits ::value_type Value_t;

iterator_traits est une classe générique standard dont le paramètre de généricité est un type d’itérateur, et qui exporte le type (value_type) de l’objet pointé par un itérateur de type IterType.

Elle est définie dans la bibliothèque iterator.