groupindex::GInvertedList< Group > Class Template Reference

Diese Template-Klasse implementiert die einfachste Form einer G-invertierten Liste. More...

#include <GInvertedList.h>

Inheritance diagram for groupindex::GInvertedList< Group >:

[legend]Collaboration diagram for groupindex::GInvertedList< Group >:

[legend]List of all members.


Public Member Functions
	GInvertedList (const GInvertedList< Group > &glist)
	Copy-Konstruktor.
	GInvertedList (long id)
	Standard-Konstruktor.
	GInvertedList ()
	Standard-Konstruktor.
	GInvertedList (std::fstream &ifs)
	Initialisiert die Suchphase des Index.
GInvertedList< Group > &	operator *= (const Group &g)
	Multipliziert die Einträge der Liste mit dem Gruppenelement `g` .
iterator	begin ()
	liefert die Position des ersten Treffers der invertierten Liste.
iterator	begin (bool dummy)
iterator	end ()
	liefert die Endposition der Treffermenge.
iterator	end (bool dummy)
int	size () const
	Anzahl von ListTupeln, die in der Liste gespeichert sind und noch credit haben.
void	setCredit (int credit)
virtual void	insert (const Group &g, int i)
	Fügt das Tupel (sh,i) in die invertierte Liste ein.
void	remove (int fileindex)
	Löschen aller `ListTupel` `lt` , bei denen `lt.i=fileindex` ist.
void	intersect (GInvertedList< Group > &set2, int &mismatches)
	bildet die Schnittmenge einer `GInvertedList` mit einer `ResultList`.
void	merge (GInvertedList< Group > &set2)
void	setHeapStream (std::fstream &hps)
	Für Kompatibilität mit MultiDimGList:.
	~GInvertedList ()
	Destruktor.
Protected Member Functions
void	initFileRead (std::ifstream &ifs)
void	initFileRead (std::fstream &ifs)
virtual void	readElements ()
	Liest die ListTupel der Liste in einen internen Puffer.
virtual void	readElements (int credit)
	Liest die ListTupel der Liste in einen internen Puffer.
virtual void	readElements (ListTupel< Group > *buffer, int credit)
	Liest die ListTupel der Liste in `buffer`.
void	clear ()
	Gib den in `readElements()` reservierten Speicher wieder frei.
void	setFileName (long id)
	Namen der temporären Datei anhand von `id` ermitteln.
virtual void	writeToFile (std::ofstream &ofs)
	Sortiert die ListTupel dieser Liste und schreibe diese in die Datei `stream`.
read_iterator	find (const ListTupel< Group > &lt)
	Binärsuche nach `lt` in den Elementen der invertierten Liste.
read_iterator	find (const ListTupel< Group > &lt, read_iterator &it)
void	remove (read_iterator &it)
void	decrease (read_iterator &it)
void	assign (const read_iterator &new_beg, const read_iterator &new_end)
	`assign()` legt den Bereich fest, der von Iteratoren zu durchlaufen ist.
void	initInsertion ()
	Bereitet die Liste darauf vor, dass durch Aufrufe von insert() neue Elemente eingefügt werden.
void	insert (read_iterator &pos, const ListTupel< Group > &lt)
	Einfüge-Methode zum Einfügen von Elementen bei der mismatch-Suche.
void	initUpdate ()
read_iterator	_begin (void *)
read_iterator	_end (void *)
Protected Attributes
ListTupel< Group > *	insertion_buffer
	Die öffentliche `iterator` - Klasse einer G-invertierten Liste hat in erster Linie die Funktion, die Ergebnisse der Schnittmengenberechnungen zurückzuliefern.
int	ins_buffer_size
int	ins_buffer_pos
std::fstream *	m_stream
	Zeiger auf Indexdatei, in der die Einträge der Liste beim Aufruf von `intersect`(...) bzw.
long	m_fileoffset
	startposition dieser Liste in der Indexdatei
long	m_id
	innerhalb eines Index eindeutige ID der Liste. Diese id wird der Liste durch den Konstruktor `GInvertedList(long)` mitgeteilt.
char	m_insertion_file_name [1024]
	Name der temporären Datei beim Einfügen. Dieser wird anhand von `m_id` ermittelt.
Group	m_factor_inverse
	Faktor, der im `operator*=()` gesetzt wird.
Group	m_factor
	Faktor, der im `operator*=()` gesetzt wird.
ListTupel< Group > *	m_pos_beg
	Postion für begin()-Iterator.
ListTupel< Group > *	m_pos_end
	Postion für end()-Iterator.
int	m_element_count
	Anzahl der Einträge in der G-invertierten Liste.
int	m_new_element_count
	und daher auch noch nicht bei der Suche berücksichtigt werden
ListTupel< Group > *	m_elements
	Elemente der invertierten Liste.
std::set< int >	m_deleted_fileindices
	aus dem Index gelöscht werden sollen
Friends
std::ofstream &	operator<< ANSI_BRACES (std::ofstream &o, GInvertedList< Group > &l)
	Operator zum Speichern einer `GInvertedList`.

Detailed Description

template<class Group>
class groupindex::GInvertedList< Group >

Diese Template-Klasse implementiert die einfachste Form einer G-invertierten Liste.

Es sind alle von einer GroupIndex - Instanz benötigten Schnitstellen definiert, so dass eine GInvertedList exakte Schnittmengenbildung zur Suche mit Mismatches und Fuzzy- Freiheitsgraden ermöglicht. Die Template-Klasse Group muss die Funktionalität einer Gruppenklasse implementieren.

Constructor & Destructor Documentation

template<class Group>

groupindex::GInvertedList< Group >::GInvertedList< Group > ( long id )

Standard-Konstruktor.
Diese id wird in erster Linie dazu verwendet, einen eindeutigen Namen für eine temporäre Datei zu ermitteln.

template<class Group>

groupindex::GInvertedList< Group >::GInvertedList< Group > ( std::fstream & ifs )

Initialisiert die Suchphase des Index.
Die Datei ifstream muß an der aktuellen Position eine von operator<<()} geschriebene Liste enthalten. Es werden die Anfangspositionen der einzelnen G-invertierten Listen ausgelesen, damit in getGList() vollständig initialisierte GInvertedList-Objekte zurückgegeben werden können.

Member Function Documentation

template<class Group>

void groupindex::GInvertedList< Group >::assign ( const read_iterator & new_beg,

const read_iterator & new_end

) [inline, protected]

assign() legt den Bereich fest, der von Iteratoren zu durchlaufen ist.
Die Iteratoren new_beg bzw. new_end zeigen auf die neue Start- bzw. Endposition. An der Speicherbelegung der Liste wird allerdings nichts geändert. Die Bedeutung von assign() ist also dieselbe wie die des assign() der stl-Container (z.B. list oder vector).

template<class Group>

void groupindex::GInvertedList< Group >::initInsertion ( ) [protected]

Bereitet die Liste darauf vor, dass durch Aufrufe von insert() neue Elemente eingefügt werden.
Als Temporärer Speicher dient das durch stream festegelegte file; nach Aufruf von writeToFile() werden die Tupel in dieser Liste sortiert und können in das Index-file geschrieben werden.

Parameters:

filename Name der temporären Datei, an die neue ListTupel angehangen werden. Die Dateinamen für diese temporären zu verwalten, ist Aufgabe einer Representation.

template<class Group>

void groupindex::GInvertedList< Group >::insert ( const Group & g,

int i

) [virtual]

Fügt das Tupel (sh,i) in die invertierte Liste ein.
Vor Aufruf muß initInsertion() aufgerufen werden, damit eine Datei zum anhängen der neuen Daten zur Verfügung steht.
Parameters:

sh Einzufügendes Gruppenelement

Dateinummer der einzufügenden Datei

Return values:

insert true, wenn das Einfügen erfolgreich war, sonst false.

Die Dateinummer sollte eine von einem - bzw. von einem Representation- Objekt verwaltete Nummer sein; insert() wird i.A. von einem Representation- Objekt aufgerufen, niemals direkt aus einer Anwendung.

template<class Group>

void groupindex::GInvertedList< Group >::intersect ( GInvertedList< Group > & set2,

int & mismatches

)

bildet die Schnittmenge einer GInvertedList mit einer ResultList.

Parameters:

set2 gibt die ResultList, deren GInvertedList mit den Elementen der Liste aus dem this -Objekt geschnitten werden soll. In set2 ist auch das Gruppenelement gespeichert, mit dem die Liste aus set2 zu multiplizieren ist.

In Erweiterungen der Klasse GInvertedList<Group> können in der Methode intersect algebraische Eigenschaften für spezielle Anwendungen genutzt werden.

template<class Group>

GInvertedList< Group > & groupindex::GInvertedList< Group >::operator *= ( const Group & g ) [inline]

Multipliziert die Einträge der Liste mit dem Gruppenelement g .
Intern wird diese Multiplikation "lazy" ausgeführt, d.h. erst dann, wenn auf ein Element tatsächlich zugegriffen wird. Nach aussen liefert die Liste die Einträge (durch die iterator - Klasse) so zurück, dass diese mit dem Faktor g multipliziert wurden.

template<class Group>

void groupindex::GInvertedList< Group >::readElements ( ListTupel< Group > * buffer,

int credit

) [protected, virtual]

Liest die ListTupel der Liste in buffer.

Parameters:

buffer Puffer zum Einlesen der ListTupel. buffer muss groß genug sein, daß this.size() viele ListTupel Platz finden.

Return values:

readElements Rückgabe true, wenn das Lesen erfolgreich abgeschlossen wurde,

template<class Group>

void groupindex::GInvertedList< Group >::writeToFile ( std::ofstream & ofs ) [protected, virtual]

Sortiert die ListTupel dieser Liste und schreibe diese in die Datei stream.
Es werden folgende ListTupel in den Index eingefügt:

Alle ListTupel, die in der Indexdatei gespeichert sind, mit welcher das Indexobjekt verknüpft ist. Zur Erläuterung: Ein Indexobjekt ist mit der Datei verknüft, die dem Konstruktor GroupIndex::GroupIndex(ifstream&) übergeben wird. Die Verknüpfung wird vom GroupIndex-Objekt an das Representation -Objekt und alle G-invertierten-Listen-Objekte übergeben.

Alle ListTupel, die durch GroupIndex::insert() in den Index eingefügt wurden und dadurch in den temporären Dateien der G-invertierten Listen (/list/glist_N ) gespeichert sind.

Parameters:

ofs fstream, in welchen die GInvertedList geschrieben werden soll. Diese Datei muss zum binären Schreiben (Parameter "std::ios::binary") geöffnet sein.

Return values:

writeToFile Rückgabe true, wenn das Schreiben erfolgreich abgeschlossen wurde, sonst false.

Reimplemented in groupindex::IntervalIntersectionGList< Group, numeric, Dim, numeric_writer >.

Member Data Documentation

template<class Group>

ListTupel<Group>* groupindex::GInvertedList< Group >::insertion_buffer [protected]

Die öffentliche iterator - Klasse einer G-invertierten Liste hat in erster Linie die Funktion, die Ergebnisse der Schnittmengenberechnungen zurückzuliefern.
Zum bearbeiten einer Suchanfrage wird i.A. von einem GInvertedList - Objekt mehrfach die Methode intersect(...) aufgerufen. Bei diesen Schnittmengenberechnungen bleiben nur die Trefferelemente übrig (bzw. haben im Falle einer mismatch-Suche nur die Trefferelemente einen Kredit, der größer 0 ist). Genau diese Treffer-Elemente muss ein iterator zurückliefern. Also gibt GInvertedList::begin() den ersten Treffer zurück, (GInvertedList::begin())++ den zweiten usw.

template<class Group>

std::fstream* groupindex::GInvertedList< Group >::m_stream [protected]

Zeiger auf Indexdatei, in der die Einträge der Liste beim Aufruf von intersect(...) bzw.
readElements() zu finden sind.

The documentation for this class was generated from the following file:

GInvertedList.h

The GroupIndex-Template-Library
Universität Bonn, Institut für Informatik III, 2001

groupindex::GInvertedList< Group > Class Template Reference

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

template<class Group> class groupindex::GInvertedList< Group >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class Group>
class groupindex::GInvertedList< Group >