groupindex::IntervalIntersectionGList< Group, numeric, Dim, numeric_writer > Class Template Reference

Verwaltet G-invertierte Liste für Gruppen, deren Elemente -- z.B. More...

#include <IntervalIntersectionGList.h>

Inheritance diagram for groupindex::IntervalIntersectionGList< Group, numeric, Dim, numeric_writer >:

[legend]Collaboration diagram for groupindex::IntervalIntersectionGList< Group, numeric, Dim, numeric_writer >:

[legend]List of all members.


Public Types
typedef dynEkdTree< Interval< Group, numeric, Dim >, Dim, numeric, numeric_writer >	tpTREE
typedef avlTree< treeSaver< tpTREE > >	avl_tree_type
Public Member Functions
	IntervalIntersectionGList (const IntervalIntersectionGList< Group, numeric, Dim, numeric_writer > &glist)
	Copy-Konstruktor.
	IntervalIntersectionGList ()
	Standard-Konstruktor.
	IntervalIntersectionGList (long id)
	IntervalIntersectionGList (std::ifstream &ifs)
	Konstruktor zum Initialisieren aus einer Datei.
	IntervalIntersectionGList (std::fstream &ifs)
	Konstruktor zum Initialisieren aus einer Datei.
virtual	~IntervalIntersectionGList ()
	Destruktor.
iterator	begin ()
	Liefert einen Iterator, der auf den Anfang der Liste zeigt.
iterator	begin (bool)
pure_iterator	pure_begin ()
	Liefert einen Iterator, der auf den Anfang der Liste zeigt.
pure_iterator	pure_begin (bool)
iterator	end ()
	Liefert einen Iterator, der auf das Ende der Liset zeigt.
iterator	end (bool)
pure_iterator	pure_end ()
	Liefert einen Iterator, der auf das Ende der Liset zeigt.
pure_iterator	pure_end (bool)
int	size () const
	Anzahl Intervalle, die in der Liste gespeichert sind.
void	merge (IntervalIntersectionGList< Group, numeric, Dim, numeric_writer > &set2)
	Vereinigung zweier Listen.
void	setCredit (int credit)
	Anzahl erlaubter Mismatches als "Kredit" bei der Schnittmengenbildung festlegen.
void	intersect (IntervalIntersectionGList< Group, numeric, Dim, numeric_writer > &set2)
	Schnittmengenbildung ohne Mismatches.
void	intersect (IntervalIntersectionGList< Group, numeric, Dim, numeric_writer > &set2, int credit)
	Schnittmengenbildung mit mismatches.
void	setHeapStream (std::fstream &hps)
	Für Kompatibilität mit MultiDimGList.
Public Attributes
avlTree< treeSaver< tpTREE > >	treeList
	Liste mit den ekd-Bäumen, in denen die `ListTupel` der Liste gespeichert sind.
Protected Member Functions
numeric	distance (numeric g1, numeric g2)
	Berechnet die L-unendlich Distanz von g1 und g2.
numeric	distance (numeric *g1, Group g2)
	Berechnet die L-unendlich Distanz von g1 und g2.
numeric	distance (Group g1, Group g2)
	Berechnet die L-unendlich Distanz von g1 und g2.
void	writeToFile (std::ofstream &ofs)
	Sortiere die Tupel dieser Liste und schreibe diese in die Datei stream Diese Methode muß genau `this.byteSize()` viele Bytes in die Datei stream schreiben.
ListTupel< Group >	operator[] (int index)
	für interne Zwecke.
virtual void	readElements (ListTupel< Group > *buffer)
	liest die Elemente in `buffer`.
virtual void	readIntervals ()
	Liest alle ekd-Bäume und die zugehörigen Dateinummern in den Hauptspeicher.
void	readElements ()
	Liest alle Elemente.
void	initFileRead (std::ifstream &ifs)
	initalisieren des Index zum Bearbeiten von Suchanfragen.
void	initFileRead (std::fstream &ifs)
void	deleteFile (int fileindex)
	Löschen aller Einträge, deren `ListTupel` der Dateinummer `fileindex` zugeordnet ist.
bool	interval_range_search (Group x, int left, int right, int &hit_pos)
	Sucht im Array `elements2` nach Punkten, die in der `epsilon` - Umgebung von `x` liegen.
void	printElements ()
void	pure_printElements ()
int	rangeSearch (Group &g_1, tpTREE search_tree, int fileNum, Interval< Group, numeric, Dim > *result)
	Bereichssuche in einem ekdBaum.
Protected Attributes
Group	g_factor [maxStabSize]
int	g_factor_stabSize
int	intersects
	Zähler, wie oft die Routine intersect() aufgerufen wurde.
int	intervals_matched
	Zähler, wie viele Intervalle im letzten Aufruf von intersect() die Schnittbildung überlebt haben.
int	m_credit
	Anzahl Mismatches, die bei der Suche erlaubt sind:.
unsigned long	interval_count
	Gesanmtanzahl von Intervallen (bzw. Anzahl an `ListTupeln`), die in der Liste enthalten sind.
numeric	min_dist
	Minimaldistanz dieser Liste.
numeric	epsilon
	Minimaldistanz aller G-Listen einer gegebenen Anfrage.
unsigned long	tree_count
	Anzahl von kd-Bäumen, die in dieser Liste enthalten sind.
Interval< Group, numeric, Dim > *	intervals
	Puffer zum Speichern von Intervallen.
numeric *	ranking
numeric_writer	freadInit
	nur für interne Zwecke.
std::list< IntervalIntersectionGList * >	m_merged_with
	Liste von IntervalIntersectionGLists, mit denen diese Liste vereinigt wurde:.
Friends
bool	operator< (const IntervalIntersectionGList< Group, numeric, Dim, numeric_writer > &sl1, const IntervalIntersectionGList< Group, numeric, Dim, numeric_writer > &sl2)
	Vergleich zweier `IntervalIntersectionGList` -Objekte hinsichtlich ihrer Größe.
bool	operator> (const IntervalIntersectionGList< Group, numeric, Dim, numeric_writer > &sl1, const IntervalIntersectionGList< Group, numeric, Dim, numeric_writer > &sl2)
	Vergleich zweier `IntervalIntersectionGList` -Objekte hinsichtlich ihrer Größe.
std::ofstream &	operator<< (std::ofstream &o, IntervalIntersectionGList< Group, numeric, Dim, numeric_writer > &l)

Detailed Description

template<class Group, class numeric, int Dim, class numeric_writer = double_writer>
class groupindex::IntervalIntersectionGList< Group, numeric, Dim, numeric_writer >

Verwaltet G-invertierte Liste für Gruppen, deren Elemente -- z.B.

durch numerische Fehler verursacht -- ungenau dargestellt sein können.

Die Template-Parameter haben folgende Bedeutung:

Parameters:

Group	Gruppenklasse; zu deren Besonderheiten in diesem Zusammenhang siehe unten stehende Bemerkung.
numeric	Numerischer Datentyp, welcher den Rückgabetyp des Indexoperators der Gruppenklasse festlegt. Geeignet sind hier z.B. `double` , `float` oder `LEDA/real` ; bedingt tauglich sind auch `int` oder `short` .
Dim	Gibt die Dimension der Gruppe an. Der Indexoperator der Gruppenklasse muss für Werte größer 0 und kleiner `Dim` Werte vom Typ `numeric` zurückgegen.
numeric_writer	Klasse, die Operationen zum Lesen und Schreiben numerischer Datentypen zur Verfügung stellt. Zu deren weiteren Erklärung siehe unten.

Um die Ungenauigkeiten in der Rechnerdarstellung der Gruppenelemente handhaben zu können, ist in dieser Klasse die unscharfe Schnittmengenbildung implementiert. Wie bei der Standard-GInvertedList müssen in der Klasse Group folgende Member-Funktionen implementiert sein:

Group::getRepresentation zur Berechnung von Repräsentanten
Group::mult zum Verknüpfen von Gruppenelementen
Group::operate , um auf Instanzen von set operieren zu können und
Group::invert , um inverse Gruppenelemente berechnen zu können.

Zusätzlich werden die Member-Funktionen

Group::indexSize zum ermitteln des Platzbedarfs in Dateien
operator[] als Indexoperator und
readFromFile sowie
writeToFile zum Schreiben und Lesen in Dateien

benötigt.

Die Klasse numeric_writer stellt Methoden zum Lesen und schreiben von Werten des Typs numeric zur Verfügung. Der Grund für diese Abkapselung liegt darin, dass einige arithmetsiche (bzw. numerische) Datentypen nicht ohne weiteres in einer Datei gespeichert werden können, da die Darstellung sehr komplex ist - wie es z.B. beim Typ LEDA/real der Fall ist. Ein numeric_writer muss (in beiden Richtungen) Zuweisungskompatibel zum Typ numeric sein und die Methoden numeric_writer::read(...) und numeric_writer::write(...) für unterschiedliche Arten von Dateien zur Verfügung stellen; Der Standard-Parameter double_writer ist geeignet für eine Vielzahl von numeric - Typen, so z.B. double , float , int oder short und (mit #define USE_LEDA) auch LEDA/real. Alternativ stehen in writer.h auch die Typen int_writer und short_writer zur Verfügung.

Member Function Documentation

template<class Group, class numeric, int Dim, class numeric_writer>

void groupindex::IntervalIntersectionGList< Group, numeric, Dim, numeric_writer >::deleteFile ( int fileindex ) [protected]

Löschen aller Einträge, deren ListTupel der Dateinummer fileindex zugeordnet ist.
Die Liste muss zuvor mit initUpdate() zum Einfügen initialisiert worden sein.

template<class Group, class numeric, int Dim, class numeric_writer>

bool groupindex::IntervalIntersectionGList< Group, numeric, Dim, numeric_writer >::interval_range_search ( Group x,

int left,

int right,

int & hit_pos

) [protected]

Sucht im Array elements2 nach Punkten, die in der epsilon - Umgebung von x liegen.
Die Elemente aus elements2 müssen Minimaldistanz 2 epsilon haben! Durchsucht wird mit Binärsuche nur der Bereich elements2[left]...elements[right]; elements2 muß dazu bezüglich der Bit-interleaving-Funktion c sortiert sein.

template<class Group, class numeric, int Dim, class numeric_writer>

void groupindex::IntervalIntersectionGList< Group, numeric, Dim, numeric_writer >::writeToFile ( std::ofstream & ofs ) [protected, virtual]

Sortiere die Tupel dieser Liste und schreibe diese in die Datei stream Diese Methode muß genau this.byteSize() viele Bytes in die Datei stream schreiben.
FORMAT:

sizeof(numeric) Bytes Minimaldistanz
sizeof(unsigned_long) Bytes Anzahl von ekd-Bäumen
sizeof(unsigned_long) Bytes Anzahl von Einträgen insgesamt
sizeof(unsigned_long) Bytes Länge des verbleibenden Teils der Liste in Bytes

Danach für jeden ekd-Baum der Liste:

sizeof(int) Bytes Dateiindex *
n Bytes ekd-Baum

Reimplemented from groupindex::GInvertedList< Group >.

Member Data Documentation

template<class Group, class numeric, int Dim, class numeric_writer = double_writer>

numeric groupindex::IntervalIntersectionGList< Group, numeric, Dim, numeric_writer >::epsilon [protected]

Minimaldistanz aller G-Listen einer gegebenen Anfrage.
Dieser Wert wird der Liste "von aussen", nämlich von jener Funktion, welche intersect() aufruft, mitgeteilt. Dies ist z.B. die Routine search() in der Klasse NRGroupIndex

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

IntervalIntersectionGList.h

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

groupindex::IntervalIntersectionGList< Group, numeric, Dim, numeric_writer > Class Template Reference

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Friends

Detailed Description

template<class Group, class numeric, int Dim, class numeric_writer = double_writer> class groupindex::IntervalIntersectionGList< Group, numeric, Dim, numeric_writer >

Member Function Documentation

Member Data Documentation

template<class Group, class numeric, int Dim, class numeric_writer = double_writer>
class groupindex::IntervalIntersectionGList< Group, numeric, Dim, numeric_writer >