IEqualityComparer

Hallo,

ich habe eine Klasse definiert, die eine Linie darstellen soll. Als Member hat sie vier String^ xVon, yVon, xNach, yNach. Per Definition soll eine Linie bei mir identisch sein, wenn ihre Endpunkte identisch sind, sprich, die Linie von A nach B ist die gleiche Linie wie von B nach A. Da ich diese Linie später als Schlüssel eines Dictionaries verwenden möchte, muss ich wohl noch eine Klasse LinienComparer erstellen, die von IEqualityComparer<Linie> abgeleitet werden muss und in dieser dann die Methoden Equals() und GetHashCode() überschreiben. Mein Ansatz dazu sieht aus wie folgt:

ref class CLinieComparer : public System::Collections::Generic::IEqualityComparer<CLinie^>
{
public:
	virtual bool Equals(CLinie^ lhs, CLinie^ rhs)
	{
		if ((	(this->xVon  == rhs->xVon  && this->yVon == rhs->yVon) 
			&& (this->xNach == rhs->xNach && this->yNach == rhs->yNach))
			|| 
			(	(this->xVon  == rhs->xNach && this->yVon == rhs->yNach) 
			&& (this->xNach == rhs->xVon  && this->yNach == rhs->yVon)))
			return true;
		return false;
	}

	virtual int GetHashCode(CLinie^ linie)
	{
		String^ hash;

		// der Hash (verketteter String) wird so bestimmt, dass die Linie immer von links nach rechts 
		// oder von unten nach oben verläuft; somit sind zwei Linien identisch, auch wenn sie
		// entgegengesetzt verlaufen
		if (linie->xVon->CompareTo(linie->xNach) < 0)
			hash = linie->xVon + linie->yVon + linie->xNach + linie->yNach;
		else if (linie->xVon == linie->xNach)
		{
			if (linie->yVon->CompareTo(linie->yNach) < 0)
				hash = linie->xVon + linie->yVon + linie->xNach + linie->yNach;
			else 
				hash = linie->xNach + linie->yNach + linie->xVon + linie->yVon;
		}
		else 
			hash =	linie->xNach + linie->yNach + linie->xVon + linie->yVon;
		return hash->GetHashCode();
	}
};

...und hier die Linienklasse:

ref class CLinie : public IComparable
{
public:
	String^ xVon, ^yVon;
	String^ xNach, ^yNach;
	String^ typ;

public:
	CLinie^ Clone()
	{
		CLinie^ klon = gcnew CLinie;
		klon->typ	= this->typ;
		klon->xVon	= this->xVon;
		klon->yVon	= this->yVon;
		klon->xNach = this->xNach;
		klon->yNach = this->yNach;
		return klon;
	}
};

Das mit dem Hash klappt auch, nur habe ich festgestellt, dass die Equals()-Methode, so wie ich sie hier implementiert habe, ab und zu einen ganz schönen Schei.. miteinander vergleicht und somit eine zweite Linie in das Dictionary schreibt, die laut meiner obigen Definition bereits eine identische Linie drinstehen hat. Offensichtlich habe ich etwas nicht richtig verstanden. Schreibe ich in die Equals()-Methode ein lässiges 'return true;', klappt die ganze Sache hervorragend.
Für einen Hinweis, was ich hier falsch mache wäre ich aber mal richtig dankbar - vielleicht hat ja jemand eine Idee.

Merci, Bernd

witte

1. Wieso ein extra CLinieComparer? Wieso implementierst Du nicht IEquatable<CLinie > in CLinie? "If type TKey implements the System::IEquatable<(Of <(T>)>) generic interface, the default equality comparer uses that implementation."

public bool Equals(CLinie^ rhs)
            {
                return this->xVon  == rhs->xVon  && this->yVon == rhs->yVon)
            && (this->xNach == rhs->xNach && this->yNach == rhs->yNa ...
            }

2. Wieso Stringtypen zur Aufnahme von numerischen Werten? Wieso nicht int oder double?

double xVon, yVon;
double xNach, yNach;

3. Wenn Du Fließkommaarithmetik verwendest, solltest Du nicht direkt auf Gleichheit, sondern ε-Umgebung prüfen.

4. Warum selber hashen? Es gibt soch Containertypen für sowas.

5. Effizienz prüfen. Bei vielen Linien könnte ein SortedDictionary<> / SortedList<> eine bessere Performanz O(log n) zeigen. Hierzu muss aber IComparable<CLinie> implementiert werden.

Hallo witte,

das mit IEquatable muss ich mir mal näher anschauen, danke dafür. String deshalb, weil ich die Daten schon als String bekomme (ich weiß, wandeln wäre ein leichtes), (noch) nicht damit rechnen muss und der Test auf Gleichheit eben einfacher ist als mit Double-Werten.
Könntest Du das mit dem hashen mal etwas näher erläutern?

Gruß, Bernd

witte

Lemmes schrieb:

String deshalb, weil ich die Daten schon als String bekomme (ich weiß, wandeln wäre ein leichtes), (noch) nicht damit rechnen muss und der Test auf Gleichheit eben einfacher ist als mit Double-Werten.

... somit eine zweite Linie in das Dictionary schreibt, die laut meiner obigen Definition bereits eine identische Linie drinstehen hat.

Ich wollte fragen, ob diese Koordinaten wirklich identisch sind. Ist ja egal, ob Du sie als String oder als double vergleichst, 10.00000045 != 9.999999687 oder "10.00000045" != "9.999999687". Wenn Du sie aber in ein double wandelst kannst Du auf Umgebung prüfen. Wenn es nur int's sind, entfällt ja dieses Problem.
Bei dem Hashen dachte ich jetzt an HashSet<>, aber das gibt's ja erst seit 3.5

die Koordinatenpärchen, die ich bekomme, haben alle drei Nachkommastellen (und sind dann auch tatsächlich identisch) und sind somit problemlos als String zu vergleichen.
Wie meinst Du das eigentlich mit "auf Umgebung prüfen"? Bei double-Werten bin ich bisher so vorgegangen, dass ich Math::Abs(wert1 - wert2) < Grenzwert geschrieben habe. Gibt es da was Eleganteres?

witte

Nein, das abs(v1 - v2) meinte ich mit Umgebung.

Aber was anderes zu Deinen Equals() in CLinieComparer. Wieso verwendest Du dort this-> statt lhs->?

upps, das ist nur ein Kopierfehler, ich habe da noch ein wenig in Code rumgespielt und dann Teile davon hier eingestellt. Ursprünglich stand bzw. steht jetzt wieder lhs->blabla

Gruß, Bernd

Hallo,

bevor ich mir jedes mal den Aufwand mache ob die Linie von x nach y oder umgekehrt definiert ist würde ich eine Normalize Methode am Ende vom Konstruktor definieren, die die Koordinaten so umschreibt, das die Linie immer z.B. von links oben nach rechts unten geht.