# datenstruktur welche sich "im kreis" dreht



## ruutaiokwu (25. Mrz 2014)

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 (25. Mrz 2014)

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 (25. Mrz 2014)

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 (25. Mrz 2014)

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


----------



## ruutaiokwu (25. Mrz 2014)

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 (25. Mrz 2014)

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 (25. Mrz 2014)

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 (25. Mrz 2014)

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 (25. Mrz 2014)

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 (25. Mrz 2014)

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 (25. Mrz 2014)

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


----------



## ruutaiokwu (25. Mrz 2014)

"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 (25. Mrz 2014)

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


----------



## ruutaiokwu (25. Mrz 2014)

Danke!


----------



## ruutaiokwu (28. Apr 2014)

...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 (28. Apr 2014)

jmar83 hat gesagt.:


> ```
> public class CircularIteratorWrapper implements Iterator
> {
> private Iterator i;
> ...



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 (28. Apr 2014)

*



			"Genug Kritik?"
		
Zum Vergrößern anklicken....

*
immerhin etwas... ;-)


_*



			"Früher wurde nicht viel kritisiert, eher diskutiert! Und da sind dann eben unterschiedlichste "Ansichten" aufeinandere geprallt."
		
Zum Vergrößern anklicken....

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


----------



## Katharsas (4. Mai 2014)

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 (4. Mai 2014)

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 (4. Mai 2014)

Tobse hat gesagt.:


> 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...):
> ...



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 (5. Mai 2014)

Danke für die Feedbacks!!


----------



## Tobse (5. Mai 2014)

Katharsas hat gesagt.:


> 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
> ...



Bei Zwei Punkten kann ich dir nicht zustimmen.



Katharsas hat gesagt.:


> - 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.



Katharsas hat gesagt.:


> - 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 (5. Mai 2014)

Tobse hat gesagt.:


> 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 )




Tobse hat gesagt.:


> ```
> LinkedList<T> l = ... ; // Instanz meines codes als Klasse
> 
> // foreach vom aktuellen element aus
> ...



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 (5. Mai 2014)

Joose hat gesagt.:


> 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.



Joose hat gesagt.:


> 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.



Joose hat gesagt.:


> 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 (6. Mai 2014)

Tobse hat gesagt.:


> 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 (6. Mai 2014)

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 (17. Jan 2018)

Danke für die Feedbacks!!


----------

