Dziś właśnie w swej codziennej pracy stanąłem przed problemem wyznaczenia części wspólnej dwóch przedziałów. Chcesz dowiedzieć się jak sobie z tym poradziłem w języku Java ?
Przyjmijmy, że mamy 2 zakresy zakres X = <x1 , x2> oraz zakres Y = <y1 , y2>. Teraz poukładajmy rosnąco wszystkie te wielkości (czyli x1, x2, y1, y2), pamiętając przy tym, do którego zakresu należy dana wartość. Jeśli po posortowaniu tych wartości pierwsze dwie należą do różnych zakresów, to będzie oznaczać, że część wspólna istnieje. Przyjmujemy także, że 2-ga i 3-cia liczba w posortowanym zbiorze stanowią końce części wspólnej obu przedziałów - i to jest to czego szukamy.

Brzmi to bardzo prosto, czyż nie ? I rzeczywiście ta dość prosta reguła sprawdza się prawie zawsze. Jak to w życiu lubi bywać wyjątki komplikują sprawę. Problemy pojawiają się w sytuacji, gdy jeden z punktów końcowych jest identyczny w obu zakresach. W tej sytuacji musimy przyjąć zasadę, że jeden zakresów ma pierwszeństwo względem drugiego, np.: wywołując

TRange commonRange = rangeX.and(rangeY);

traktujemy zakres X (rangeX) w metodzie and, jako uprzywilejowany względem zakresu Y (rangeY). A zatem w sytuacji gdy y2 będzie równe x1, po posortowaniu tablicy wartość x1 będzie zawsze przed wartością y2.

Niesamowite, czyżby zadziałało! Tak, doprawdy ten pomysł okazał się bardzo trafiony i pozwolił rozwiązać, niemal wszystkie przypadki. Pojawił się jeden jedyny wyjątek, gdy x1 < x2, x2 == y1, y1 < y2. Przy założeniu pierwszeństwa dla X, algorytm zwróci zakres pusty ponieważ po posortowaniu zbioru danych będziemy nieć [x1, x2, y1, y2], a ponieważ powiedzieliśmy, że gdy pierwsze 2 wartości należą do tego samego zakresu (brak skrzyżowania zakresów) to zakresy są rozłączne. W takim razie odwróćmy ich priorytety, niech Y będzie ważniejszy od X’a, we wszystkich takich sytuacjach kiedy x1 < y1.

Teraz przystępujemy do testów wszystkich możliwych kombinacji przedziałów. Pamiętajmy, że musimy testować zakresy także zamieniając ich kolejność.

I jak myślisz co się okazało ?

Opracowany algorytm okazał się prawidłowy i zdaje się dawać prawidłowe wyniki. Zajrzyjmy więc pod Java’ową maskę tej maszyny.
Klasą bazową będzie TRange reprezentująca zakres liczbowy, która dla potrzeb realizacji swoich algorytmów będzie wykorzystywać klasę TRangePoint przedstawiającą punkt końcowy zakresu.
Oto główna metoda klasy TRange realizująca nasz algorytm.

public TRange and(TRange tr)
{
	int thisIdx;
	int otherIdx;

// ustalenie ważności punktów - normalnie obiekt z wywołaną metodą and() ma pierwszeństwo
// gdy jest to konieczne wyższy priorytet jest nadawany zakresowi zewnętrznemu tr
	if (m_t1.getValue() < tr.m_t1.getValue())
	{
		thisIdx = 2;
		otherIdx = 1;
	}
	else
	{
		thisIdx = 1;
		otherIdx = 2;
	}

	m_t1.setGroupId(thisIdx);
	m_t2.setGroupId(thisIdx);
	tr.m_t1.setGroupId(otherIdx);
	tr.m_t2.setGroupId(otherIdx);

	TRangePoint[] pts = new TRangePoint[4];

	pts[0] = m_t1;
	pts[1] = m_t2;
	pts[2] = tr.m_t1;
	pts[3] = tr.m_t2;

	Arrays.sort(pts);
	TRange res = null;

	// jeśli istnieje część wspólna tworzymy nowy obiekt zakresu o odpowiednich końcach
	if (pts[0].getGroupId() != pts[1].getGroupId())
		res = new TRange(pts[1].getValue(), pts[2].getValue());

	return res;
}

Metoda statyczna Arrays.sort() pozwala sortować obiekty typu Comparable. Klasę pomocniczą TRangePoint konstruujemy implementując specjalne metody porównawcze. Porównanie punktów odbywa się z udziałem wartości punktów, a gdy są one identyczne brany jest pod uwagę identyfikator grupy(czyli zakresu), który pełni jednocześnie rolę priorytetu.

public int compareTo(Object o)
{
	return (int) compareTo((TRangePoint)o);
}

public long compareTo(TRangePoint o)
{
	long result = m_val - o.m_val;
	if (result != 0)
		return result;
	else
		return m_grpId - o.m_grpId;
}

Tags: algorytmy, Programowanie w Java