Designfrage - Templates ja/nein/vielleicht?

[HumeSikkins]

Hallo,
ich bastle zur Zeit mal wieder etwas an meinem dirstream (ein uralte und
ziemlich kaputte Version findet man auf meiner HP, eine etwas neuere
in meinem cpp2html-Tool) rum, kann mich derzeit aber nicht wirklich für eine Implementationsstrategie entscheiden.

dirstream stellt den Inhalt eines Verzeichnisesses in Form eines Streams
dar. Für die Auswahl von Verzeichniseinträgen bei
der Verzeichnisdurchwanderung verwendet dirstream zwei verschiedene
Filter. Einen Filter für die generelle Auswahl von Einträgen sowie einen
Filter für die Auswahl von Unterverzeichnissen, der nur verwendet wird,
falls Unterverzeichnisse rekursiv berücksichtigt werden sollen.
Man kann also z.B. dirstream-Objekte für folgende Anfragen erstellen:
* Alle Dateien im Verzeichnis x
* Alle Dateien im Verzeichnis x und in den Unterverzeichnissen von x
* Alle cpp-Dateien im Verzeichnis x.
usw.

Nun spiele ich gerade mit drei verschiedenen Implementationen rum und mich würde mal
interessieren, welche ihr am Besten findet bzw. ob ihr vielleicht eine
viel bessere Idee habt.

Version 1: Templates
--------------------
* dirstream ist eine Template-Klasse die zwei Parameter erwartet, nämlich
den Typ der beiden Filter (sowie man es z.B. von den assoziativen Standardcontainern kennt).

struct TypeFilter {
    TypeFilter(EntryType t);                // EntryType ist eine Aufzählung
    bool operator()(const string& e) const; // wählt Einträge in Abhängigkeit ihres Typs
};

// alle Dateien des aktuellen Verzeichnisses
dirstream<TypeFilter> str(".", FILES);
for (string s; str >> s;) cout << s << endl;

// alle cpp-Dateien - rekursiv - nur Unterverzeichnisse mit Namen src
dirstream<PatternFilter, PatternFilter> str2(".", "*.cpp", RECURSIVE_YES, "src");
...

Vorteile:
* Beste Performance - Die Typen der Filter sind zur Compile-Zeit bekannt.
Der Aufruf der Filter kann direkt und sogar inline expandiert erfolgen.
* Flexibel - Filter können Funktionsobjekte oder Funktionen sein.
Memberfunktionen können leicht durch einen Adapter unterstützt werden.

Nachteile:
* Der Filter-Typ ist Teil des statischen Typs von dirstream - Man kann also
nicht mit ein und demselben dirstream-Objekt erst mit einem Filter A und
dann mit einem Filter B arbeiten.
* Jeder Client von dirstream muss den konkreten Filtertyp kennen bzw. selbst
ein Template sein.

Version 2: OOP
---------------
* dirstream ist eine Klasse die eine abstrakte Klasse IFilter verwendet.
* IFilter ist die Basisklasse für alle Filter
* Es gibt zusätzlich Adapter für Funktionen, Prädikate und Memberfunktionen
(machen aus einer Funktion, einem Prädikat oder einer Memberfunktion ein
IFilter-Objekt).

// alle Dateien des aktuellen Verzeichnisses
// make_filter(TypeFilter(FILES)) liefert ein dynamisch alloziertes Prädikat-Adapter-Objekt
dirstream str(".", make_filter(TypeFilter(FILES)));
for (string s; str >> s;) cout << s << endl;

// alle cpp-Dateien - rekursiv - nur Unterverzeichnisse mit Namen src
// kein neues Objekt nötig.
str.open(".", 
		make_filter(PatternFilter("*.cpp")), 
		RECURSIVE_YES, 
		make_filter(PatternFilter("src"))
);
...

Diese Variante hat ihre Vorteile im Bereich Flexibilität und ihre Nachteile
im Bereich Performance.
Da der Typ dirstream unabhängig vom konkreten Filter ist, habe ich
die Möglichkeit beliebige Suchen hinter ein und dem selben Typ zu verbergen.
Clients müssen weder Templates sein, noch konkrete Filter kennen.

Der Aufruf der Filter ist dafür allerdings immer ein virtueller Aufruf, kann also nicht inline expandiert werden. Außerdem müssen die Filter dynamisch alloziert werden, was im Vergleich zu einer Stackallokierung deutlich teurer ist.

Variante 3: Kombiniere 1 und 2:
-------------------------------
* Die Implementation des dirstreams ist ein Template (ähnlich wie in Variante 1)
* Dazu gibt es eine Facade-Klasse die einen beliebigen dirstream hinter
einem einheitlichen Typ versteckt.

// Template-Interface - genau wie Variante 1
dirstream<TypeFilter> str(".", FILES);
for (string s; str >> s;) cout << s << endl;

dirstream<PatternFilter, PatternFilter> str2(".", "*.cpp", RECURSIVE_YES,"src");

// alternativ
// vewendet intern dirstream<TypeFilter>
dirstream_holder str(new dirstream<TypeFilter>(".", FILES));	
...

// der selbe Holder kann auch einen anderen Typen aufnehmen
str.open(new dirstream<PatternFilter, PatternFilter>(".", "*.cpp", RECURSIVE_YES,"src"));
for (string s; str >> s;) cout << s << endl;

Vorteile:
* Der Benutzer kann abhängig von seiner konkreten Situation die
für ihn effizientere Zugriffsvariante wählen.
* Die Holder-Variante ist im Regelfall laufzeit-effizienter als die reine OOP- Variante.

Nachteile:
* Komplexere Implementation
* Komplexere Nutzung - Der Benutzer kann nicht nur eine Variante auswählen,
er muss dies tun. D.h. aber gleichzeitig, dass er mehr Dokumentation lesen
muss.

* Die Holder-Variante benötigt mehr Speicher als die reine OOP-Variante:
für die Verwaltung von N verschiedenen dirstream-Typen werden N vtables (bzw. in diesem Fall vtable-ähnliche Strukturen)
benötigt. Nicht genau eine wie bei der OOP-Variante.

Welche Version würdet ihr bevorzugen?

PS: dirstream kann genausogut ein dirstream_iterator sein. Das Problem bleibt das selbe.

[virtuell Realisticer]

Nabend,

IMHO sollte Flexibilitaet auf _jeden_ Fall vorhanden sein, sprich die erste
Version wuerde bei mir wegfallen.

Die beiden anderen Versionen sind eigentlich ganz Ok. Welche ich jetzt konkret
einsetzen wuerde? Das ist eine gute Frage, denn beide lassen sich, IMHO, recht
gut einsetzen. Von der Leserlichkeit ist wuerde ich jedoch ein

str.open(".",
        make_filter(PatternFilter("*.cpp")),
        RECURSIVE_YES,
        make_filter(PatternFilter("src"))
);

einem

str.open(new dirstream<PatternFilter, PatternFilter>(".", "*.cpp", RECURSIVE_YES,"src"));

vorziehen, da ich hier quasi "mitlesen" kann. Um die Geschwindigkeit braucht
man sich hier, IMHO, nicht so sehr viele Gedanken machen, denn schliesslich
gibt es hier einen viel groesseren Flaschenhals -> die Festplatte.

Das mit der Leserlichkeit ist natuerlich vom Einzelnen abhaengig. War jetzt
vielleicht nicht die grosse Hilfe, nur so meine Gedanken.

mfg
v R

[ZuK]

Ich würde auf die OOP Variante setzen. Performance sollte für diesen einsatzbereich überhaupt kein entscheidungskriterium sein denn diese wird wahrscheinlich haptsächlich von der zufriffszeit auf die festplatte abhängen. Ich glaube flexibilität und einfache anwendbarkeit ist das wichtigste.
K.

[otze]

Die 3. variante halt ich für ganz schlecht,sie ist nichts halbes und nichts ganzes, sie erlaubt keine echte filtervariablität,sondern kann maximal einen satz vordefinierter filtersätze bieten.
Das problem beginnt dann, wenn man ein programm schreiben will,das einem verschiedenste möglichkeiten gibt nach dateien zu suchen, sie zu sortieren etc.
dann kommt man schnell auf eine stattliche anzahl filter, und damit dem user keine kombination verwehrt bleibt, müsste man alle implementieren, und das ist arbeit.
deshalb würde ich am besten 1+2 nehmen, 1 für die fälle, in denen man alles zur compilezeit weis, und 2 für die fälle, in denen man es nicht weis.

ps: auch wenns die aufgaben eines dirstreams vielleicht ein bischen weit ausdehnt, vielleicht kannst du ja noch einen support für archive einbauen, damit man auch innerhalb von ihnen nach dateien/ordnern suchen kann.

ich dachte dabei an sowas:

class ArchivReader{...};
dirstream<PatternFilter, PatternFilter,ArchivReader> str(...);

[HumeSikkins]

otze schrieb:

Die 3. variante halt ich für ganz schlecht,sie ist nichts halbes und nichts ganzes, sie erlaubt keine echte filtervariablität,sondern kann maximal einen satz vordefinierter filtersätze bieten.

Wie kommst du auf die Idee? Die 3. Variante bietet beliebige Filter. Genau wie die erste und zweite auch.
Ein Filter ist in der ersten und dritten Variante eine Funktion bzw. ein Funktionsobjekt, dass einen const std::string& entgegennimmt und ein bool liefert. In der zweiten Variante ist ein Filter eine Klasse die von IFilter erbt dessen pure virtuelle-Methode bool operator()(const std::string&) = 0 überschreibt.

Standardmäßig bringt der dirstream einen Typfilter (unterscheidet Dateien und Verzeichnisse) und einen Patternfilter mit (einfache Wildcard-Strings wie
"a[bcd]foo??.*").
Man kann aber z.B. auch einen stat-Filter schreiben:

struct LastModifiedOn
{
	LastModifiedOn(int day, int mon, int year)
		: day_(day)
		, mon_(mon - 1)
		, year_(year - 1900)
	{}
	bool operator()(const std::string& e) const
	{
		struct stat info;
		if (stat(e.c_str(), &info) == -1) return false;
		struct tm* fileTime = localtime(&info.st_mtime);
		return	fileTime->tm_mday == day_ &&
				fileTime->tm_mon  == mon_ &&
				fileTime->tm_year == year_;
	}
private:
	int day_, mon_, year_;
};

// mit Variante 1:
dirstream<LastModifiedOn> str(".", LastModifiedOn(31, 12, 2003));
// mit Variante 2:
dirstream str(".", make_filter(LastModifiedOn(31, 12, 2003)));
// mit Variante 3:
dirstream<LastModifiedOn> str(".", LastModifiedOn(31, 12, 2003));
// oder
dirstream_holder str(new dirstream<LastModifiedOn>(".", LastModifiedOn(31, 12, 2003)));

Ansonsten schon mal danke für die Antworten.

[otze]

die 3. variante bietet so wie du sie beschrieben hast keine "beliebigen" filter und erst recht keine beliebigen filterkombinationen.

str.open(new dirstream<PatternFilter, PatternFilter>(".", "*.cpp", RECURSIVE_YES,"src"));

die beiden templateparameter legen zur compiletime die filterkombination fest.
will ich filter aus plugins laden, bin ich da _komplett_ aufgeschmissen,auch wenn ich zur compilezeit ein paar filter einstellen kann,deshalb ist es nichts halbes und nichts ganzes.

[HumeSikkins]

otze schrieb:

will ich filter aus plugins laden, bin ich da _komplett_ aufgeschmissen,auch wenn ich zur compilezeit ein paar filter einstellen kann,deshalb ist es nichts halbes und nichts ganzes.

Achso meinst du das. In diesem Punkt ist die dritte Variante halt genau wie die erste. Alles was du mit der ersten machen kannst, kannst du auch mit der dritten machen. Nur das du halt zusätzlich auch einen gemeinsamen Typ hast (dirstream_holder), so dass du beliebige Typen an ein Subsystem übergeben kannst ohne das dieses den konkreten Typen kennen muss.
Und das ist genau das Ziel gewesen: Konstruktion und Verwendung so zu trennen, dass nur der Teil der dirstream_t-Objekte konstruiert genaue Typinformationen haben muss. So wird also ein Factory-Ansatz möglich. Das geht mit der ersten Variante hingegen nicht.

Durch die Basisklasse IFilter ist die zweite Variante aber natürlich noch flexibler. Nur kommt diese Flexibilität halt auch mit einem Preis.

[Shade Of Mine]

Es wäre super, wenn ich mehrere Filter anwenden könnte (und nicht jedesmal einen neuen Filter schreiben muss):

//finde alle Dateien die auf .cpp enden, aber nicht temporär sind (kein ~ als erstes zeichen)
dirstream str(".");
str.addFilter(new FilerExtension("cpp"));
str.addFilter(new FilerNoTemporary());

Sowas wäre IMHO das wichtigste. Nur das da eine schöner Syntax her sollte - ich will mehrere Filter gleich in Ctor angeben können -> inline_containers??

Dadurch geht die Template Variante nicht mehr.

Somit denke ich, dass die 2. Variante die sinnvollste ist. Obwohl ich nicht ganz glücklich mit ihr bin... Die dynamischen allokierungen stören irgendwie - aber ich wüsste nicht, wie man sie wegbekommen könnte

Dynamische Filter sind aber das wichtigste. Denn es kann oft vorkommen, dass man zur Compilezeit einfach nicht die Typen kennt. Wenn ich zB 10 Suchkriterien habe, und der User sich diese beliebig aussuchen kann, bin ich mit der Template Variante schnell am Ende. Und dieses Szenario ist denke ich nicht so unwahrscheinlich.

[HumeSikkins]

@Shade
Meinst du echt es müssen mehrere Filter sein oder reicht vielleicht auch sowas wie ein Composer (à la boost::compose bzw. boost::bind)?
Man könnte ja sowas wie and und or-Adapter bauen:

bool filter1(const string& e);
bool filter2(const string& e);

// wird zu if (filter1(e) && filter2(e))
dirstream s(".", make_filter(and(filter1, filter2)));

// wird zu if (filter1(e) || filter2(e))
dirstream s2(".", make_filter(or(filter1, filter2)));

Über die Syntax könnte man ja noch nachdenken.

Die Unterstützung mehrerer Filter würde das Ganze auf jeden Fall doch deutlich komplizieren.

[Shade Of Mine]

HumeSikkins schrieb:

Meinst du echt es müssen mehrere Filter sein oder reicht vielleicht auch sowas wie ein Composer (à la boost::compose bzw. boost::bind)?

Jo, daran habe ich nicht gedacht. Die Frage ist allerdings: wie läuft das mit dynamischen Filtern - wenn die Filter nicht zur Compilezeit feststehen -> garnicht, oder?

Die Unterstützung mehrerer Filter würde das Ganze auf jeden Fall doch deutlich komplizieren.

Ja, allerdings würde es die Verwendung vereinfachen - denn sonst muss ich mir sehr oft selber Filter schreiben die dann nur

return foo("bla") && bar("bla");

machen... das finde ich n bisschen doof. Es sei denn natürlich man könnte zur Laufzeit Filter zusammenfügen - mit and und or - dann noch ein not und du hast die perfekte Flexibilität.

Ich danke da vorallem an Programme wo der User diese Filter angibt. Und da wäre so eine Flexibilität Goldwert.

[Gast]

Mehrere Filter könnte man gut realisieren, wenn die Filter selber streams sind und ein Filter auf dem anderen arbeitet. So ein bisschen ähnlich wie die Streams in Java.

Also nicht

str.addFilter(filter1);
str.addFilter(filter2);

sondern

stream myFilteredStream(new ExtensionFilterStream(".cpp", new TempFilterStream(myDirStream) ));

Leseoperationen delegieren dann die Filter entsprechend an ihrem Stream, den sie verwalten, so entsteht eine richtig schöne Verkettung und jeder filtert sein Zeug heraus.
Ich sehe nur das Problem mit der Resourcenverwaltung. Vielleicht kann man das über autopointer schön machen. Hmmm müssen die Dinger überhaupt auf dem Heap liegen?

Die erste Variante finde ich hässlich und unflexibel ist sie ja auch. Bei Festplattenzugriffen ist die Performance eh schon hinüber.

[virtuell Realisticer]

HumeSikkins schrieb:

@Shade
Meinst du echt es müssen mehrere Filter sein oder reicht vielleicht auch sowas wie ein Composer (à la boost::compose bzw. boost::bind)?
Man könnte ja sowas wie and und or-Adapter bauen:

bool filter1(const string& e);
bool filter2(const string& e);

// wird zu if (filter1(e) && filter2(e))
dirstream s(".", make_filter(and(filter1, filter2)));

// wird zu if (filter1(e) || filter2(e))
dirstream s2(".", make_filter(or(filter1, filter2)));

Über die Syntax könnte man ja noch nachdenken.

Die Unterstützung mehrerer Filter würde das Ganze auf jeden Fall doch deutlich komplizieren.

Ich finde die Idee sehr gut. Vor allem spart man sich das temporaere
Speicher + durchsuchen eines Verzeichnisses, falls man nur einen Filter setzen
kann. Da du hier boost ansprichst, man koennte zur Implementierung der
Filter doch boost::regex einsetzen. Das vereinfacht nicht nur dir die
Implementierung, sondern auch dem Anwender die Anwendung. Und mehrere Filter
zu durchlaufen sollte doch mit ner einfachen list moeglich sein, oder nicht?

Wahrscheinlich stelle ich mir das viel zu einfach vor.

mfg
v R

[otze]

die list hat ein problem: filter werden linear abgearbeitet, dh wenn der langsamste filter vorne steht, wird dein programm von vornherein langsam werden, da der filter immer aufgerufen wird, egal was passiert.

da find ich die konstruktion mit and/or und not viel hilfreicher

and(name("*.txt"),wordInFile("hallo"));

[virtuell Realisticer]

otze schrieb:

die list hat ein problem: filter werden linear abgearbeitet, dh wenn der langsamste filter vorne steht, wird dein programm von vornherein langsam werden, da der filter immer aufgerufen wird, egal was passiert.

da find ich die konstruktion mit and/or und not viel hilfreicher

Ja das stimmt, daran hab ich gar nicht gedacht.

mfg
v R

[HumeSikkins]

Shade Of Mine schrieb:

HumeSikkins schrieb:

Meinst du echt es müssen mehrere Filter sein oder reicht vielleicht auch sowas wie ein Composer (à la boost::compose bzw. boost::bind)?

Jo, daran habe ich nicht gedacht. Die Frage ist allerdings: wie läuft das mit dynamischen Filtern - wenn die Filter nicht zur Compilezeit feststehen -> garnicht, oder?

Dynamisch:

class IFilter
{
public:
    virtual bool operator()(const std::string& e) = 0;
    ...
};

class AndFilter : public IFilter
{
public:
    AndFilter(IFilter* f1, IFilter* f2)
        : f1_(f1)
        , f2_(f2)
    {}
    bool operator()(const std::string& e) {return (*f1_)(e) && (*f2_)(e);}
private:
    std::auto_ptr<IFilter> f1_;
    std::auto_ptr<IFilter> f2_;
};

class NotFilter : public IFilter
{
public:
    NotFilter(IFilter* f1)
        : f1_(f1)
    {}
    bool operator()(const std::string& e) {return !(*f1_)(e);}
private:
    std::auto_ptr<IFilter> f1_;
};
...

Allerdings würde ich hier dann doch Templates verwenden und die einzelnen Filter "by value" an And, Or und Not binden. Das endgültige Funktionsobjekt würde ich dann durch einen Prädikat-Adapter zu einem IFilter-kompatiblen Objekt machen. So habe nur eine dynamische Allokation.
Alles andere erscheint mir für den Anfang etwas overkill zu sein.

Mehrere Filter könnte man gut realisieren, wenn die Filter selber streams sind und ein Filter auf dem anderen arbeitet.

Da sehe ich ehrlich gesagt jetzt keinen Vorteil. Warum sollen die Filter Streams sein? Sie beeinflussen doch nur das Verhalten eines Streams, stellen selbst aber keinen Stream dar.

[Gast]

Naja, ich sehe es als eine Art FilterStream.
Ein Stream ist doch konzeptionell nichts anderes als ein Bytestrom. Es ist völlig egal, woher die Bytes kommen, die ich z.B. in einem ZipStream auslese, der ZipStream liest sie einfach, komprimiert ein bisschen was und das was rauskommt ist wieder ein Bytestrom (was auch sonst?), der hoffentlich kürzer ist.
Abstrakter als ein ZipStream ist IMHO ein allgemeiner FilterStream. Ich könnte mir vorstellen, von istream FilterInputStream abzuleiten (welcher einen anderen Stream liest und verändert wiedergibt) und davon
- ZipInputStream
- ExtensionFilterInputStream
- TempFilterInputStream
- usw.

Du musst mir da nicht zustimmen, aber für mich sind Filter, die einen Stream lesen und praktisch einen veränderten Stream weiterleiten eben auch Streams, bzw. finde ich es eine gute Idee, sie zu streams zu machen. Dadurch benutzt man sie wie nen normalen Stream und interessiert sich gar nicht dafür, was er überhaupt macht.
Und einfach zu benutzen ist es auch:

...
TempFilterInputStream myTempFilterStream(myDirStream);
ExtensionFilterInputStream myFilteredStream(".cpp", myTempFilterStream);

myFilteredStream  >>  ... ;

[otze]

sie geben keine werte weiter, und verändern auch keine. sie testen nur

[Gast]

Achso? Ich hab das so verstanden, dass ein Stream von Files reinkommt und die Filter alles unpassende aus dem Stream herausnehmen.
Na dann...

[HumeSikkins]

Ein Stream ist doch konzeptionell nichts anderes als ein Bytestrom

Meine Filter sind aber keine Byteströme. Die Filter sind vielmehr wie ein
Türsteher der entscheidet ob jemand in den Strom überhaupt erst reinkommt.

Deine Alternative, so wie ich es verstehe, würde bedeuten, dass ich erst einen allgemeinen Verzeichnisstrom baue, der alle Einträge auswählt und dahinter dann mehrere Filterströme setze, die nur noch bestimmte Einträge durchlassen. Diesen Ansatz habe ich aber bewusst verworfen, da er mir zu ineffizient ist. Warum soll ich erst alle Unterverzeichnisse öffnen und durchsuchen (was für jeden Eintrag ein Systemaufruf ist) nur um dann später rauszufinden, dass der Nutzer nur Unterverzeichnisse mit dem Namen "src" durchsuchen will?

Du musst mir da nicht zustimmen, aber für mich sind Filter, die einen Stream lesen und praktisch einen veränderten Stream weiterleiten eben auch Streams

Das sehe ich ein, ist aber nicht meine Situation. Wie gesagt, in meiner Situation stehen die Filter logisch gesehen *vor* dem Strom. Zuerst kommen die Systemaufrufe, dann die Filter und alles was diese durchlassen wird dem Nutzer als Strom dargestellt.

Ich bin allerdings mittlerweile nicht mehr davon überzeugt, dass dieses Stromkonzept in diesem Fall überhaupt einen Sinn macht. Ein Input-Iterator wäre imo ausreichend (ich habe derzeit beides, einen Strom und einen Iterator der auf einem Strom arbeitet).

Optimizer schrieb:

Und einfach zu benutzen ist es auch:

...
TempFilterInputStream myTempFilterStream(myDirStream);
ExtensionFilterInputStream myFilteredStream(".cpp", myTempFilterStream);

myFilteredStream  >>  ... ;

Den Punkt verstehe ich nicht.
Was ist hieran weniger einfach?

Filter noTempFiles;
Filter cppFilesNotTempFiles("*.cpp", noTempFiles);
dirstream str(".", cppFilesNotTempFiles);
for (string s; str >> s;)
{
...
}

Meine and/or/not-Combiner erlauben jetzt folgendes:

// zeigt alle cpp-Dateien des aktuellen Verzeichnisses
// die *nicht* am 17.10.2004 verändert wurden
dirstream str(".", 
		make_filter(
			and_f(new PatternFilter("*.cpp"), 
				not_f(LastModifiedOn(17, 10, 2004)
				)
			)
		)
);
copy(dirstream_iterator(str), dirstream_iterator(), ostream_iterator<string>(cout, "\n"));

Man kann also sowohl IFilter-Objekte (per new alloziert) als auch Prädikate/Funktionen/Memberfunktionen kombinieren. Das Ergebnis ist ein Combiner-Objekt das durch make_filter in ein IFilter-Objekt adaptiert wird.
Das Combiner-Objekt übernimmt dabei die Zerstörung der Teilobjekt und wird selbst durch den Strom zerstört.

Das ist natürlich alles noch reichlich unflexibel. Aber solange ich nicht weiß, wie man das Ganze konkret einsetzen kann, werde ich wohl erstmal damit leben können.

[otze]

lass doch make_filter raus, und lass and_f() bzw not_f ein IFilter* sein