[Java] Sortowanie mapy bez użycia komparatora


(Vandavv96) #1

Witam.

Spotkałem się z kilkoma przypadkami na rożnych forach dotyczących sortowania mapy po wartościach, w których nie było rozwiązania lub rozwiązaniem były komparatory. Ja pokusiłem się o zrobienie klasy która zrobi to bez nich i oto wynik, jakbyście mieli jakieś zastrzeżenia bądź uwagi to jestem otwarty

import java.util.*;

@SuppressWarnings({"rawtypes", "unchecked"})
public class Sorter<K,V extends Comparable> {
	public Map<K, V> sort(Map<K,V> data) {
		
		//Lista, w której będą sortowane wartości
		List<V> mylist = new ArrayList<V>();
		Map<K,V> sortedMap = new LinkedHashMap<K,V>();
			
		Collection<V> temp = data.values();
		Iterator<V> ittemp = temp.iterator();
		while(ittemp.hasNext()) {
			//Wypełnienie listy wartościami mapy
			mylist.add(ittemp.next());
		}
		//Sortowanie
		Collections.sort(mylist);
		
		//Teraz trzeba wstawić je razem z odpowiadającymi im kluczami
		ListIterator<V> it = mylist.listIterator(mylist.size());
		while(it.hasPrevious()) {
			//Wartości od końca, żeby ułożenie było od max do min
			V val = it.previous();

			Iterator<Map.Entry<K,V>> its = data.entrySet().iterator();
			
			//Jeżeli znajdzie klucz z tą samą wartością, dodaje do posortowanej mapy i usuwa z oryginalnej
			while (its.hasNext()) {
			    Map.Entry<K,V> entry = its.next();
			    if(val.equals(entry.getValue())){
			        sortedMap.put(entry.getKey(), val);
			        its.remove();
			    }
			} 
		}
	//Zwrócenie wyniku
	return sortedMap;
	}
}

EDIT

 

Dodałem bezpieczne usuwanie znalezionej pary z oryginalnej mapy dzięki Frakfurterium


(Frankfurterium) #2

Całość nie zadziała poprawnie, jeżeli będziesz miał w mapie kilka takich samych wartości z różnymi kluczami. W czasie iteracji powinieneś (w bezpieczny sposób) usuwać z bazowej mapy parę, którą już przekopiowałeś.


(kostek135) #3

Nie rozumiem. Po prostu zamiast użyć zewnętrznej klasy Comparator, wymuszasz, aby V implementowało interfejs Comparable. W ten o to sposób, logikę porównywania przeniosłeś z zewnętrznej klasy do klasy biznesowej. Nie dość, że to głupie, to dodatkowo wprowadza pewne ograniczenia. Teraz mój obiekt, może być porównany na jeden sposób (chyba, że użyje jakiegoś tragicznego if-else/switch). Często gęsto sposób porównywania może zmieniać się od kontekstu (przykładowo w jednym widoku klasa Person ma być posortowana po Adresach, a w innym po Nazwisku), co wtedy? Nie wymyślaj koła na nowo jeśli chodzi o STL, Comparatory są najlepszym rozwiązaniem oraz zainteresuj się TreeMap ono robi to co chcesz (samosortuje się podczas wstawiania [prawdopodobnie użyto AVL lub R-B Tree]). Małe niedoczytanie twojego postu, TreeMap sortuje po kluczach, nie mniej do obu map można podać Comparator, w którym wymusisz użycie wartości w sortowaniu.


(Jim1961) #4

wersja PHP asort :smiley:


(Vandavv96) #5

 

Chodziło tu bardziej o zadania, które trzeba zrobić BEZ użycia komparatora i trzeba właśnie napisać podobną klasę. To dobre ćwiczenie na opanowanie kontenerów, mimo że faktycznie sama klasa Comparator robi to lepiej


(Enterbios) #6

 

Myślę i myślę... Możesz mi pomóc? Jakie zadania trzeba zrobić bez użycia komparatora ale można zrobić z wykorzystaniem comparable?


(Vandavv96) #7

U nas nauczyciel od Programowania zadał kilku osobom, także mi, zadanie polegającej na posortowaniu dowolnej przekazanej mapy. dla bardziej ambitnych była wersja , żeby napisać samemu coś na styl komparatora, żeby zrozumieć jak on działa ,,od środka" mniej więcej i mieć lepsze podstawy do wprowadzenia tematu ,,Komparatory"

 

EDIT

 

Była jeszcze opcja żeby zrobić to w ogóle bez Comparable, ale szczerze nie chciało mi się tego robić, bawić się QuickSortem czy czymś to bezsens szczególnie że są komparatory