datenstruktur welche sich "im kreis" dreht

[ruutaiokwu]

hallo zusammen

ich suche eine datenstruktur welche

- nicht unbedingt einen index hat (=list)
- keine key-value-paar sachen hat (=map)
- die reihenfolge (des einfügens) beibehält
- quasi "unendlich" ist beim durchlauf: intern sollte die datenstruktur, falls hasNext() false ist, auf den ersten eintrag springen - die sache sollte sich also im kreis drehen wenn man so will...

MyStructure myStructure = new MyStructure();
myStructure.add(1)
myStructure.add(2)
myStructure.add(3)

Integer elem = null

// das wäre dann eine endlosschleife:
while(myStructure.hasNext)
{
    elem = (Integer) myStructure.next()
}

...es geht NICHT darum, diese struktur in einer endlosschleife laufen zu lassen, das ist nur ein beispiel.

es geht vielmehr darum, inner einer schleife (mit n iterationen) auf die struktur zuzugreifen damit immer 1,2,3 dabei herauskommt. (die numerischen werte sind nicht auf meinen fall bezogen, von daher bitte keine kommentare in der art "mach doch das ohne datenstruktur")

vielen dank.

 

[Alex Unkreativ]

Es funktioniert nicht, eine ArrayList oder ähnliches zu nehmen und die zirkuläre Struktur dadurch zu erreichen, dass man den Zähler i einfach laufen lässt, aber intern mit (i % myStructure.size()) arbeitet?

 

[ruutaiokwu]

hallo

danke für dein feedback.

eine liste zu nehmen sehe ohnehin ich eher weniger, ich denke eher an eine modifizierte klasse "extends LinkedHashSet" oder so...

dann bei dieser klasse intern in der hasNext()-funktion prüfen ob "false" der fall ist. wenn ja, auf das anfangselement zurückspringen und "true" zurückgeben... so dass hasNext() immer "true" ist, und next() immer was zurückgibt...

 

[HarleyDavidson]

Was du suchst ist eine verkette Liste. Google mal, da findest du viel. Das Schaubild erklärt es aber eigentlich schon sehr gut:

 

[ruutaiokwu]

von verketteten listen habe ich auch schon gehört.

wenn ich nun 3 elemente einfüge und dabei die indexe 0 sowie 2 (=elements 1 u. 3) miteinander verkette, was passiert dann wenn ich folgendes mache:

for(int i=0; i<100;i++)
{
Object o = myList.get(i)
}

...was passiert dann, wenn i grösser als 2 ist? regelt die LinkedList das intern mit modulo ode so??

das beispiel mit der schleife ist in etwa genau so wie ich die sache verwenden will. (bspw. um die farbe von html-taballen-rows abzuwechseln:

myList.add("#000000");
myList.add("#ffffff");

for(int i=0; i<100;i++)
{
String colorHexValue = myList.get(i)
}

...was mir aber nicht ganz passt, die sache soll nicht index-abhängig (->liste) sein. das wäre besser:

myCircularLinkedHashSet.add("#000000");
myCircularLinkedHashSet.add("#ffffff");

for(int i=0; i<100;i++)
{
String colorHexValue = myCircularLinkedHashSet.next()
}

 

[ruutaiokwu]

Apropos LinkedList: Heisst das nicht, dass die List nicht arraybasiert ist, sondern auf verlinkten instanzen basiert? ist das überhaupt ein unterschied nach aussen im vergleiche zu ArrayList oder Vector??

 

[HarleyDavidson]

Nein.
Du kannst per ID auf ein bestimmtes Objekt zugreifen.

Allgemein navigierst du aber mit (hier in meinem Beispiel) "left" und "right" zum Nachfolger / Vorgänger.

 

[eMmiE]

Das kannst du doch einfach machen, wenn du eine Klasse von List/was auch immer ableitest und dann klassenintern eine Variable index auf 0 setzt und dann noch die Methoden links()/rechts() einfügst und dabei die Methoden von List, mit denen du quasi direkt auf indices zugreifen könntest disablest (private Methode...), dann sollte genau das rauskommen, was du suchst.

Das ist dann zwar keine eigene neue Datenstruktur, es sollte in deinem Fall aber ausreichen, es sei denn, du willst selbst eine Datenstruktur erfinden und dann mithilfe einer API und selbstgeschriebenen nativen Methoden darauf zugreifen

Gruß eMmiE

 

[ruutaiokwu]

hallo zusammen

ein bisschen durchgeknallt, aber es funktioniert:

import java.util.Iterator;

public class CircularIteratorWrapper implements Iterator
{
    private Iterator i;

    private final Iterable it;

    private CircularIteratorWrapper(final Iterable it)
    {
        this.it = it;
        this.i = it.iterator();
    }

    public boolean hasNext()
    {
        if (i.hasNext() == false)
        {
            this.i = this.it.iterator();
        }

        return true;
    }

    public Object next()
    {
        hasNext();
        return i.next();
    }

    public void remove()
    {
        i.remove();
    }

    public static Iterator wrap(final Iterable i)
    {
        return new CircularIteratorWrapper(i);
    }
}

/*
 * Iterate through elements of Java LinkedHashSet example This Java Example
 * shows how to iterate through elements Java LinkedHashSet object.
 */

import java.util.Iterator;
import java.util.LinkedHashSet;

public class CircularIteratorWrapperTestClass
{
    public static void main(String[] args)
    {
        //create object of LinkedHashSet
        final LinkedHashSet lhashSet = new LinkedHashSet();

        //add elements to LinkedHashSet object
        lhashSet.add(new Integer("1"));
        lhashSet.add(new Integer("2"));
        lhashSet.add(new Integer("3"));
        lhashSet.add(new Integer("4"));
        lhashSet.add(new Integer("5"));

        final Iterator itr = CircularIteratorWrapper.wrap(lhashSet);

        while (true)
        {
            System.out.println(itr.next());
        }
    }
}

 

[ruutaiokwu]

Kann mir jemand sagen, was für eine konkrete klasse auf das interface, welches von LinkedHashSet.iterator() zurückgegeben wird, intern instanziert wird?

Ich finde im ganzen JRE keine einzige klasse, welche das interface "java.util.Iterator" implementiert. (bspw. im ggs. zu List, das wird implementiert von ArrayList & Vector)


andere datenstrukturen verfügen auch über die funktion .iterator(), welche dort auch ein java.util.Iterator zurückgibt...

 

[Flown]

Also LinkedHashSet verwendet als Datenstruktur eine LinkedHashMap, die wiederum hat ein KeySet und dies implementiert das Interface Set, welches Iterable implementiert bzw. erweitert.

 

[ruutaiokwu]

"Also LinkedHashSet verwendet als Datenstruktur eine LinkedHashMap, die wiederum hat ein KeySet und dies implementiert das Interface Set, welches Iterable implementiert bzw. erweitert. "

schon klar.


ich frage mich nur wo die passende klasse zum Iterator ist? es kann ja nicht nur mit interfaces gearbeitet werden, also muss es irgendwo klassen dazugeben. (-> wo befindet sich die logik für die funktionen .hasNext(), .next(), remove()?)


na ja, evtl. werden die interfaces anonym implementiert in der art

new MyInterface() {
        public void test() {
        ...
        }
      };

könnte das sein?

 

[Flown]

HashMap hat eine eigene private abstrakte Klasse (HashIterator) die dann Implementiert wird z.B. von KeyIterator.

 

[ruutaiokwu]

Danke!

 

[ruutaiokwu]

...was mit hier ein wenig fehlt ist die kritik.

vor ein paar jahren wurde man hier übelst für alles kritisiert, auch wenn es soweit i.o. war...

hat diesbezüglich niemand was zu sagen? ;-)

 

[Joose]

public class CircularIteratorWrapper implements Iterator
{
    private Iterator i;

    private final Iterable it;
......
}

Die Namen der Attribute könnten besser sein.
Genug Kritik?


Früher wurde nicht viel kritisiert, eher diskutiert! Und da sind dann eben unterschiedlichste "Ansichten" aufeinandere geprallt.

 

[ruutaiokwu]

"Genug Kritik?"

immerhin etwas... ;-)

"Früher wurde nicht viel kritisiert, eher diskutiert! Und da sind dann eben unterschiedlichste "Ansichten" aufeinandere geprallt."

meistens war die kritik konstruktiv, deswegen vermisse ich das ein wenig...;-)

 

[Katharsas]

Kritik:

1.
Wenn du den Iterator in eine neue List/Set-Klasse einbaust, die z.B. von LinkedHashSet erbt, indem du dort die iterator()-Methode überschreibst, dann brauchts du nicht immer den inneren Iterator mit der unschönen static-Methode wrappen.

Dann könntest du einfach "new MyLinkedHashSet()" erzeugen und das Teil ganz normal z.B. in einer for-each Schleife benutzen.

2.
Dann solltest du auch gleich noch Generics einbauen.



Wenn du den Codes für beide Änderungen sehen willst, sag Bescheid, dann mach ich das schnell...

Edit: Habs eben mal ausprobiert, hier der Code:

JUnit TestCase.
Der Test versucht über alle Elemente zu iterieren, nach ca. 1000 Stück bricht er ab.
Er prüft außerdem die Reihenfolge (und ddafür die Werte) der Elemente.

public class CircularIteratorWrapperTest {

	@Test
	public void test() {
		
		final Set<Integer> circle = new CircularLinkedHashSet<>();
		
        circle.add(new Integer("0"));
		circle.add(new Integer("1"));
        circle.add(new Integer("2"));
        circle.add(new Integer("3"));
        circle.add(new Integer("4"));
        
        int counter = 0;
        for(Integer i : circle) {
        	assertEquals((Integer)(counter % 5), i);
        	if(counter++>1000) break;
        }
	}
}

Hier das neue Set inklusive Iterator.
Nach außen sollte diese Klasse exakt die gleichen Methoden anbieten wie ein LinkedHashSet.

import java.util.Iterator;
import java.util.LinkedHashSet;


public class CircularLinkedHashSet<T> extends LinkedHashSet<T> {
	private static final long serialVersionUID = 8616791810767741296L;
	
	@Override
	public Iterator<T> iterator() {
		return new CircularIterator<T>(this);
	}
	
	private Iterator<T> originalIterator() {
		return super.iterator();
	}
	
	
	private class CircularIterator<E> implements Iterator<E>{

	    private Iterator<E> iterator;
	    private final CircularLinkedHashSet<E> reference;
	 
	    private CircularIterator(final CircularLinkedHashSet<E> set)
	    {
	        this.reference = set;
	        this.iterator = set.originalIterator();
	    }
	 
	    public boolean hasNext() {
	        if (iterator.hasNext() == false)
	        {
	            this.iterator = this.reference.originalIterator();
	        }
	        return true;
	    }
	 
	    public E next() {
	        hasNext();
	        return iterator.next();
	    }
	 
	    public void remove() {
	        iterator.remove();
	    }
	}
}

 

[Tobse]

Ich bin jetzt etwa bei der hälfte eingestiegen falls ich etwas elementares verpasst haben sollte macht keinen Elefanten draus.

Wie im zweiten posting schon wunderbar gesagt wurde: i % size ist die lösung.
Du kannst ein einfaches array nehmen (das T ist gleich für die Generics da...):
Wer gerne noch Elemente hinzufügen oder löschen können möchte soll eben eine ArrayList in den Hintergrund packen. Aber beim Löschen/Hinzufügen vorsichtig sein, dass sich die interne position nicht falsch verschiebt.

[EDIT]Achja, ich vergas: Und warum ist jetzt meine Lösung besser? Sie ist im vergleich zu dem Iterator chaos übersichtlicher und deutlich performanter.[/EDIT]

T[] elems = ... ; // woher auch immer das array kommt
int position; // bewegt sich immer im interval [-elems.length;elems.length]
T get(int pos)
{
    if (pos < 0)
    {
        pos = -pos;
        if (pos > elems.length)
        {
            return get((pos - elems.length) % elems.length);
        }
        return elems[elems.length - pos];
    }
    return elems[pos % elems.length];
}
T next()
{
    synchronized(elems)
    { // damit next() und previous() sich nicht zoffen
        position = (position + 1) % elems.size;
        return get(position);
    }
}
T previous()
{
    synchronized(elems)
    { // damit next() und previous() sich nicht zoffen
        position = (position - 1) % elems.size;
        return get(position);
    }
}

 

[Katharsas]

Ich bin jetzt etwa bei der hälfte eingestiegen falls ich etwas elementares verpasst haben sollte macht keinen Elefanten draus.

Wie im zweiten posting schon wunderbar gesagt wurde: i % size ist die lösung.
Du kannst ein einfaches array nehmen (das T ist gleich für die Generics da...):
Wer gerne noch Elemente hinzufügen oder löschen können möchte soll eben eine ArrayList in den Hintergrund packen. Aber beim Löschen/Hinzufügen vorsichtig sein, dass sich die interne position nicht falsch verschiebt.

[EDIT]Achja, ich vergas: Und warum ist jetzt meine Lösung besser? Sie ist im vergleich zu dem Iterator chaos übersichtlicher und deutlich performanter.[/EDIT]

Wieso soll das denn ein Chaos oder unübersichtlicher sein?
Meine Methode ist
- nicht mehr Schreibaufwand, wenn man deinen Code noch in eine Klasse kapselt.
- leichter zu lesen und zu verstehen, da keine Rechnerei/Algorithmen
- Die Backing Collection-Implementation lässt sich extrem einfach austauschen mit quasi allem beliebigen
- Man braucht die Funktionen der Backing Collection nicht wrappen, da Verebung, wenn man mal mehr braucht
- for-each funktioniert im Gegensatz zu dem Array-Ding

 

[ruutaiokwu]

Danke für die Feedbacks!!

 

[Tobse]

Wieso soll das denn ein Chaos oder unübersichtlicher sein?
Meine Methode ist
- nicht mehr Schreibaufwand, wenn man deinen Code noch in eine Klasse kapselt.
- leichter zu lesen und zu verstehen, da keine Rechnerei/Algorithmen
- Die Backing Collection-Implementation lässt sich extrem einfach austauschen mit quasi allem beliebigen
- Man braucht die Funktionen der Backing Collection nicht wrappen, da Verebung, wenn man mal mehr braucht
- for-each funktioniert im Gegensatz zu dem Array-Ding

Bei Zwei Punkten kann ich dir nicht zustimmen.

- leichter zu lesen und zu verstehen, da keine Rechnerei/Algorithmen

Das, was da gerechnet wird ist 100% basic und kann von jedem nachgerechnet werden. Wenn das bei dir schon in die Kategorie Algorithmus fällt hast du eine falsche Vorstellung; die genauen Abläufe in deinem Code sind nämlich deutlich komplexer.

- for-each funktioniert im Gegensatz zu dem Array-Ding

LinkedList<T> l = ... ; // Instanz meines codes als Klasse

// foreach vom aktuellen element aus
for (int i = 0;i < l.size();i++)
{
    T current = l.next();
}

// foreach vom anfang der liste
for (int i = 0;i < l.size();i++)
{
    T current = l.get(i);
}

 

[Joose]

Das, was da gerechnet wird ist 100% basic und kann von jedem nachgerechnet werden. Wenn das bei dir schon in die Kategorie Algorithmus fällt hast du eine falsche Vorstellung; die genauen Abläufe in deinem Code sind nämlich deutlich komplexer.

Beide Möglichkeiten habe Vor- bzw. Nachteile!
Ich persönlich finde deinen Code komplexer => da ich rechnen muss um etwas nachzuvollziehen, bei Katharsas reicht mir ein logisches folgen der Methodenaufrufe
(Natürlich tun sich die Leute hier oder da leichter)
Außerdem sind mehrere "returns" in einer Methode auch oft unübersichtlich (in diesem Fall eher weniger, aber lieber gar nicht angewöhnen als mal ein Problem damit zu haben )

LinkedList<T> l = ... ; // Instanz meines codes als Klasse

// foreach vom aktuellen element aus
for (int i = 0;i < l.size();i++)
{
    T current = l.next();
}

// foreach vom anfang der liste
for (int i = 0;i < l.size();i++)
{
    T current = l.get(i);
}

Schön du kannst zwar jedes Element durchgehen, aber nicht in einer foreach-Schleife. Außerdem ist ein Array begrenzt, die Liste erweitert sich dynamisch.

 

[Tobse]

Beide Möglichkeiten habe Vor- bzw. Nachteile!
Ich persönlich finde deinen Code komplexer => da ich rechnen muss um etwas nachzuvollziehen, bei Katharsas reicht mir ein logisches folgen der Methodenaufrufe
(Natürlich tun sich die Leute hier oder da leichter)
Außerdem sind mehrere "returns" in einer Methode auch oft unübersichtlich (in diesem Fall eher weniger, aber lieber gar nicht angewöhnen als mal ein Problem damit zu haben )

Da hast du natürlich Recht, das ist letzten Endes Geschmackssache. Aber für einen geübten Programmiere sollte es bei soewtas trivialem eigentlich keinen Unterschied machen.

Schön du kannst zwar jedes Element durchgehen, aber nicht in einer foreach-Schleife.

Ob das jetzt ein

for (i = 0;i < ...;i++)[/c] oder ein [c]for (T current : collection)

ist, ist allenfalls eine Sache der ästhetik. Aber klar, auch hier wieder Geschmackssache.

Außerdem ist ein Array begrenzt, die Liste erweitert sich dynamisch.

Die Arrayzugriffe in meinem Code durch die Entsprechenden Methoden von ArrayList zu ersetzen wird ja wohl jeder Anfänger hinbekommen. Und solange das dynamische erweitern nicht zwingend notwendig ist, ist das Array jeder Collection performance-technisch weit überlegen. Gerade wenn so eine Klasse im Biolerplate-Code zum einsatz kommt ist das nicht zu vernachlässigen.

 

[Katharsas]

Das, was da gerechnet wird ist 100% basic und kann von jedem nachgerechnet werden. Wenn das bei dir schon in die Kategorie Algorithmus fällt hast du eine falsche Vorstellung; die genauen Abläufe in deinem Code sind nämlich deutlich komplexer.

Ich sage ja nicht, dass es ein komplexer Algorithmus ist, aber es ist halt algorithmischer als die Iterator-Lösung. Aber ja, jeder ließt und versteht das am leichtesten, was bzw. wie er selber schreibt...

 

[Natac]

Als KISS-Vertreter würde ich Katharsas zustimmen, dass seine Lösung "einfacher" aussieht, da ich sie zumindest schneller verstehe, weil es keine Rechnungen gibt, die ich (kurz) nachvollziehen müsste. Zudem ist sie sehr allgemein.

Beim Abtippen von Tobses Lösung hätte ich Angst mich zu vertippen und mir damit eine IndexOutOfBoundsException zuzuiehen. Allerdings ist sie, eben weil sie auf Arrays begrenzt ist, natürlich deutlich schneller, da weniger abstrahiert.

Ich denke die Frage ist nicht, welche Lösung "besser" ist. Die Frage ist viel mehr, ob man eine allgemeine und abstrakte oder eher feste dafür aber performantere Lösung bevorzugt.

 

[ruutaiokwu]

Danke für die Feedbacks!!