Objekte in ArrayList vertauschen :(

[Guest]

Hallo, ich habe eine folgende, sortierte Datenstruktur in einer Liste mit unterschiedlichen Objekten:

A
--
B
B
B
--
C
C
C
C
C
--
D
D
D
D
D

Nun sollen alle C Objekte mit denen von B in der Reihenfolge getauscht werden. Ich hab das irgendwie mit BubbleSort probiert aber das haut nicht hin. Kriege immer eine ConcurrentModificationException
Wer kann mir helfen.

 

[Gast]

Also spontan würde mir jetzt keine Möglichkeit einfallen das automatisch zu sortieren. Ich würde ne Methode schreiben die ne neue ArrayList erstellt und in diese würde ich die Objekte dann in der richtigen Reihenfolge einfügen.

 

[mikachu]

dat geht mit

Collections.sort( arraylistInstance, comparatorInstance );

musst dir nur einen eigenen Comparator schreiben

 

[Guest]

danach hab ich auch schon geforscht. aber das haut nicht hin.

		    Collections.sort(list, new Comparator<Elements>() {

				public int compare(Element o1, Element o2) {
					// TODO Auto-generated method stub
					return o1.getID().compareTo(o2.getID());
				}
		    	
		    });

Also ich weiß nicht, wie ich das richtig vergleichen soll (Kriterien). Zum Beispiel haben alle Objekte eine ID die A,B,C oder D zurückgibt. Nach diesem Ansatz passiert leider nichts ;(

 

[Gast]

Klar da musst du dann schon manuell in der Methode prüfen sonst hat er halt A<B<C<D und daher wird die Reihenfolge immer gleich bleiben.

 

[Marco13]

Das ist jetzt doch nicht so einfach, wie es auf den ersten Blick aussieht. Also, es ist schon einfach, aber nicht mit Collections.sort. Eigentlich dachte ich "Och, das sort ist ja 'stable', da muss man nur im Comparator an den passenden Stellen 0 zurückgeben, dann passt das schon" ... aber bei genauerem Hinsehen habe ich keine einfachere Möglichkeit gefunden, als die "Intervalle" der beiden IDs zu bestimmen, und die Liste dann neu zusammenzubauen :? Da müßte es aber eigentlich eine geschicktere Möglichkeit geben, nur spontan fällt mir keine ein. Naja. Das mit den Intervallen ist nicht "schlecht" (Laufzeit O(n), Speicher O(2n)), aber sieht irgendwie umständlich aus... Vielleicht hat ja jemand noch eine schönere Lösung.

import java.util.*;

class Element
{
    private int id;

    public Element(int id)
    {
        this.id = id;
    }

    public int getID()
    {
        return id;
    }

    public String toString()
    {
        return String.valueOf(id);
    }
}



class SortTest2
{
    public static void main(String args[])
    {
        List<Element> list = new ArrayList<Element>();
        list.add(new Element(1));
        list.add(new Element(2));
        list.add(new Element(2));
        list.add(new Element(3));
        list.add(new Element(3));
        list.add(new Element(3));
        list.add(new Element(4));
        list.add(new Element(4));
        list.add(new Element(4));
        list.add(new Element(4));
        list.add(new Element(5));
        list.add(new Element(5));
        list.add(new Element(5));
        list.add(new Element(5));
        list.add(new Element(5));

        System.out.println("Before "+list);
        swapID(list, 2, 4);
        System.out.println("After  "+list);
    }

    private static void swapID(List<Element> list, final int lo, final int hi)
    {
        int lo0 = -1;
        int lo1 = -1;
        int hi0 = -1;
        int hi1 = -1;
        for (int i=0; i<list.size(); i++)
        {
            Element e = list.get(i);
            if (e.getID() == lo)
            {
                if (lo0 == -1)
                {
                    lo0 = i;
                }
                lo1 = i;
            }
            if (e.getID() == hi)
            {
                if (hi0 == -1)
                {
                    hi0 = i;
                }
                hi1 = i;
            }
        }
        List<Element> result = new ArrayList<Element>();
        for (int i=  0;   i< lo0;         i++) { result.add(list.get(i)); }
        for (int i=hi0;   i<=hi1;         i++) { result.add(list.get(i)); }
        for (int i=lo1+1; i< hi0;         i++) { result.add(list.get(i)); }
        for (int i=lo0;   i<=lo1;         i++) { result.add(list.get(i)); }
        for (int i=hi1+1; i< list.size(); i++) { result.add(list.get(i)); }
        list.clear();
        list.addAll(result);
    }

}

Du solltest aber ggf. mal überlegen, ob du das, was du da machst, nicht auch anders modellieren kannst... Und falls nicht, und falls do obigen Test verwendest, genauer prüfen, was passiert/passieren soll, wenn die IDs nicht enthalten sind, oder am Rand liegen usw...

 

[SlaterB]

also das compare ist wirklich nicht schwer, falls du das meinst,
dabei ist auch egal, ob stable, vorsortiert oder sonstwas

public class Test
{
    public static void main(String[] args)
        throws Exception
    {
        List<String> list = new ArrayList<String>();
        Collections.addAll(list, "A", "B", "B", "C", "C", "C", "D");
        Collections.sort(list, new Comparator<String>()
            {
                public int compare(String o1, String o2)
                {
                    int c = o1.compareTo(o2);
                    if ((o1.equals("B") && o2.equals("C")) || (o1.equals("C") && o2.equals("B")))
                    {
                        c = -c;
                    }
                    return c;
                }
            });

        System.out.println(list);
    }

}

 

[Marco13]

Nicht so ganz. Einen ähnlichen Ansatz hatte ich auch probiert. Und vermutlich hätte ich auch gedacht, dass es funktioniert, wenn ich eine andere Eingabe verwendet hätte (nämlich so eine wie du). Aber mit anderem Inhalt, und dem Versuch, B und D zu vertauschen, funktioniert das nichtmehr....

class SortTest3
{
    public static void main(String[] args)
        throws Exception
    {
        List<String> list = new ArrayList<String>();
        //Collections.addAll(list, "A", "B", "B", "C", "C", "C", "D");
        Collections.addAll(list, "A", "B", "B", "C", "C", "C", "D", "D", "D", "D", "E", "E", "E", "E", "E");
        Collections.sort(list, new Comparator<String>()
            {
                public int compare(String o1, String o2)
                {
                    int c = o1.compareTo(o2);
                    if ((o1.equals("B") && o2.equals("D")) || (o1.equals("D") && o2.equals("B")))
                    {
                        c = -c;
                    }
                    return c;
                }
            });

        System.out.println(list);
    }
}

Das hängt wohl damit zusammen, dass jetzt nie mehr der Fall eintritt, dass zwei direkt nebeneinander liegende Elemente vertauscht werden müssen. Er läuft beim Sort sozusagen einmal durch die Liste (das kann man sich mit Debug-Ausgaben ansehen: 14 Vergleiche bei 15 Listenelementen), und stellt bei jedem Vergleich fest, dass alles in Ordnung ist.... Für genaueres müßte man sich die sort-Implementierung wohl mal genauer ansehen...

 

[Gast]

Das kann funktionieren. Man darf aber nicht nur eine Regel definieren man muss alle Fälle abdecken.

 

[Marco13]

Ja, natürlich... man kann dem Comparator eine Liste übergeben, mit der gewünschten ID-Reihenfolge, und dann sowas machen wie
return idList.indexOf(e0.getID()) - idList.indexOf(e1.getID());
aber effizient wäre das vmtl. nicht, und solche Fragen wie ob ALLE möglichen IDs bekannt sind (oder aufgelistet werden können) wären ja noch zu klären....

 

[Gast]

Es gäbe da noch ne ganz üble Lösung. Man prüft die ID und wenn diese "C" ist setzt man sie auf "AC", vergleicht dann und setzt dann wieder zurück auf "C". Ist zwar keine saubere Lösung aber es funktioniert

 

[SlaterB]

> Das hängt wohl damit zusammen

das hänt wohl damit zusammen, dass B < C nicht korrigiert wird,
mann muss dann neben B und D auch B und C sowie C und D gesondert behandeln,

macht aber mit if schon keinen Sinn mehr, da bietet sich dann wirklich die Liste der Reihenfolge an, wenn möglich

edit: noch eine Idee gerade wieder wegeditiert

edit2:
nun noch mal korrigiert:

noch ein guter Trick, der es wieder einfacher macht und auch für beliebig viele Elemente klappt:

public class Test
{
    public static void main(String[] args)
        throws Exception
    {
        List<String> list = new ArrayList<String>();
        Collections.addAll(list, "A", "B", "B", "C", "C", "C", "D", "E");
        Collections.sort(list, new Comparator<String>()
            {
                public int compare(String o1, String o2)
                {
                    if (o1.equals("B"))
                    {
                        o1 = "D";
                    }
                    else if (o1.equals("D"))
                    {
                        o1 = "B";
                    }
                    if (o2.equals("B"))
                    {
                        o2 = "D";
                    }
                    else if (o2.equals("D"))
                    {
                        o2 = "B";
                    }

                    return o1.compareTo(o2);
                }
            });

        System.out.println(list);
    }

}

weiß nicht ob das gast eben meinte, dann nur Konkretisierung

 

[Marco13]

Hm. Für Strings mag sowas gehen (habs nicht getestet), aber ob man "mal kurz" ein Element mit einer beliebigen ID erzeugen kann, ist auch nicht klar. Trotz allem wird kein Verfahren, dass auf einer Sortierung aufbaut, schneller laufen können als die (etwas umständliche) O(n)-Lösung....

 

[Guest]

Hallo und Danke für die Diskussion!

also ein Kollege hat mir zwischenzeitlich geholfen und da hat sich herausgestellt, dass mein kompletter Ansatz für die gegebene Datenstruktur schon falsch war und alles viel viel einfacher geht. Ich will das genaue Problem jetzt nicht alles runterschreiben aber wie schon ein Hinweis von Marco13 kam:

prüfen ob das nicht anders geht bzw. aufgebaut oder modelliert werden kann. Und das war hier der Fall. Da hätte ich mir die ganzen Sortiergedanken sparen können. Toll ;(

Der Hintergrund war der, dass die gegeben Struktur eine Baumstruktur ist und dann anders dargestellt werden sollte. Alles verstanden habe ch das nicht, aber es ist schonmal beruhigend, dass es doch einfach wie zunächst gedacht sein kann.