11.6. Exercise: Generics

11.6. Exercise: Generics
	Chapter 11. Generics and Containers

[ fromfile: ex-generics.xml id: ex-generics ]

This exercise requires you to come up with data structures that keep track of relationships between symbols. Our relationship is a boolean operator frop on a set S of symbols that has two properties:

Reflexivity – For any symbol s in S,
```
s frop s  is always true.
```

Symmetry – For any symbols s and t in S,

if s frop t is true, then t frop s is also true.

frop is similar to the boolean operator is-friends-with between people on a social networking site. is-friends-with is not transitive; you do not automatically become friends with all your friends' friends.^[87]

In this problem, you build a data structure for storing the relationships between symbols. Each symbol is an arbitrary string of alphanumerics. This data structure should use one or more QSet, QMap, or QMultiMap.

Write a program that repeatedly asks the user to enter relationships or commands, and keeps track of relationships between all pairs of symbols that it sees. The interface should be pretty simple: The user enters a string that is parsed and processed by the dispatching function, processLine(). In other words, processLine() should expect strings of the following forms.
1. To add a frop between two strings: string1=string2
2. To list the friends of string1: string1 (no = symbol in the line)

Add another function, takeback(int n), where n refers to the n^th assertion. If the n^th assertion added a frop, the function should "undo" that assertion, ensuring that relational integrity is kept. After this, show the updated friend lists of both symbols (string1 and string2) involved.

Have the processLine() function scan for messages of the form "takeback n" and call the takeback() function in response.

It is possible to do this with a QMultiMap instead of a map of sets. That approach is shown in Section 13.6

Example 11.19. solution/generics/friendslist/friendslist.h

[ . . . . ]
class FriendList :public QSet<QString> { };
class FriendMap : public QHash<QString, FriendList > {
  public:
    void set(QString k1, QString k2);
    void unset(QString k1, QString k2);
    FriendList& friends(QString key);
};


#endif        //  #ifndef FRIENDSLIST_H

Example 11.20. solution/generics/friendslist/friendslist.cpp

#include "engine.h"
#include <QDebug>

void FriendMap::unset(QString id1, QString id2) {
   friends(id1).remove(id2);
   friends(id2).remove(id1);
}

FriendList& FriendMap::friends(QString key) {
      FriendList& retval = operator[](key);
      if (retval.isEmpty()) {
          retval << key;
          insert(key, retval);
      }
      return retval;
}


void FriendMap::set(QString id1, QString id2) {
    FriendList &c1 = operator[](id1);   
    c1 += id2;                          
    operator[](id2) <<  id1;            
}

	Find all the mapped values matching first key
	We could have used operator<<() here
	Same as above but shorter

Example 11.21. solution/generics/friendslist/engine.h

#ifndef ENGINE_H
#define ENGINE_H
#include "friendslist.h"


/* An engine is a console front-end app for the FriendMap test
program */

class Engine : public QObject {
    Q_OBJECT
  public:
    void showFriends(QString symbol);
    QString processLine(QString inputline);
    void history() const;
    QString takeback(int index);   
  private:
    QVector<QString> m_Messages;   
    FriendMap m_friendMap;         
};


#endif        //  #ifndef ENGINE_H

	Removes a previous assertion
	A log of incoming messages
	Maintains a mapping of symbols to heap EquivClass objects.

Example 11.22. solution/generics/friendslist/engine.cpp

#include "engine.h"
#include <QtCore>

void Engine::showFriends(QString key) {
    qDebug() << "Friends of " << key << endl;
    FriendList& eq = m_friendMap[key];
    foreach (QString k, eq) 
        if (key != k) 
            qDebug() << QString(" [ %1=%2 ] ").arg(key).arg(k);
}
QString Engine::processLine(QString l) {
    if (l.startsWith("takeback")) {
        int wschar = l.lastIndexOf(' ');
        int removeIndex = l.mid(wschar).toInt();
        return takeback(removeIndex);
    }

    int i = l.indexOf('=');
    if (i>0) {
        QString key = l.left(i);
        QString value = l.mid(i+1);
        m_Messages.append(l);     
        m_friendMap.set(value, key);
        m_friendMap.set(key, value);
        return key;
    }
    else {                        
        showFriends(l);
        return l;
    }
    return QString("Unrecognized Line: %1").arg(l);
}



QString Engine::takeback(int index) {
    if (m_Messages.count() < index) {
        qDebug() << "invalid index" << endl;
        return "";
    } else {
        QString line = m_Messages[index];
        qDebug() << "Taking Back: " << line << endl;
        int i = line.indexOf('=');
        QString key = line.left(i);
        QString value = line.mid(i+1);
        m_friendMap.unset(key, value);
        return key;
    }
}

void Engine::history() const {
    //    iterator itr<QString> =
}

int main(int argc, char** argv) {
    QTextStream cout(stdout);
    QTextStream cin(stdin);
    Engine engine;
    QString currentline;
    QString key;
    do {
        cout << " > " << flush;
        currentline = cin.readLine();
        key = engine.processLine(currentline);
    } while (currentline != QString()) ;
    return 0;
}

	By adding to a vector, we maintain integer id on each message
	No "=" in input line - just print out the equalities of that symbol

^[87]Transitivity is a third property of boolean operators that we are not assuming – for any symbols s, t, and u in S, if s op t and t op u are both true, then s op u is also true.

If a boolean operator op is Reflexive, Symmetric, and Transitive, then it is an Equivalence Relation.


11.5. Flyweight Pattern: Implicitly Shared Classes		11.7. Review Questions