permanent "sortierte" Struktur

Larrywayn

Larrywayn

Mitglied
Eigentlich wollte ich nur mal fragen, ob es so eine Datenstruktur gibt:
verhalten ungefähr wie eine Queue. Es werden Objekte drauf gepackt. Die Reihenfolge ist eigentlich 2. rangig. Auf jedenfall haben die Objekte natürlich mehrere Attribute/Variablen. Sobald sich ein bestimmter Wert ändert, quasi so eine Art Key, soll das Objekt automatisch, nach vorne/an den Anfang rutschen.
Hier ein kleines Bild, was das verdeutlicht.
http://i39.photobucket.com/albums/e197/papasassa/problem1.png

Jedes mal die komplette Struktur/Liste zu durchlaufen oder permanent selber sortieren, würde ich gerne vermeiden, weil sowieso immer nur 1 Objekt abgearbeitet wird. Es kann sein, dass kein Objekt geholt werden kann, was das durchlaufen unnütz machen würde. Deshalb wäre es praktisch nur zu gucken, ob das 1. Objekt die Anforderung erfüllt, wenn nicht, dann wird nichts weiter gemacht. Ansonsten wird das Objekt von der Struktur geholt und aus ihr entfernt.

Hatte überlegt, dass die Objekte eine Referenz auf ihre Struktur/Liste bekommen und wenn die entsprechende Methode aufgerufen wird, es sich selber nach vorne packt. Was ich nur absolut nicht schön finde, weil danach ist das Objekt nicht mehr an diese Struktur/Liste gebunden.
Wäre für jeden Denkanstoß dankbar ^^
 
Ich kenne HashMaps und Queues , dass ist nicht das Problem. Auch nicht irgendwas selber zu implementieren. Nur ein Ansatz fehlt bzw. ein Hinweis ob es so was eben gibt was das automatisch macht.
HashMap, die müsste man selber sortieren, sobald sich der Wert bzw, Key ändert. ich dachte da gibt es vll. schon irgendwas ähnliches. =)

Aber trotzdem erstmal danke für die Antwort. ist wirklich schwer zu erklären mh
 
Naja je nachdem.
Nehmen wir einfach an der Wert/Key wäre ein Boolean, welche am Anfang alle auf false sind. Diese Objekte liegen nun in dieser Struktur. irgendwann, dass kann nach 2 Sekunden oder nach 2 Stunden sein, ändert sich der Wert des Booleans auf true und dadurch soll das Objekt in der Struktur an den Anfang rutschen, damit gesehen wird. Aha Objekt bereit kann runter genommen werden. Und eben ohne, dass ich die Struktur permanent selber durchlaufen oder sortieren muss :/
Ich weiß ist ziemlich speziell. O:
 
Warum nimmst Du nicht eine Implementierung der BlockingQueue und legst das Object erst dann in die Queue, wenn dieses Flag gesetzt wird? Der Konsument (am besten in einem eigenen Thread) würde so lange nichts machen, bis er ein Element in der Queue findet. Die Elemente könnten sich selbst in die Queue legen ...

Die Elemente in der Queue zu sortieren ginge mit einer PriorityQueue oder eben auch einer PriorityBlockingQueue.

Dazu müsste deine Object Klasse über eine natürliche Ordnung verfügen (also Comparable implementieren) oder Du stellst einen Comparator bereit.

Hoffe es hilft.
 
Das passiert ja schon ich kann es ja mal kurz erklären. es ist eine server-client Anwendung.
Der Socket kommt in eine Queue, welche abgearbeitet wird, dann wird ein Objekt erzeugt, welches die benötigten Streams und Daten beinhaltet und dieses soll dann in eine HashMap<Integer, Daten>. Das Problem an der Sache ist, das der Integerwert erst aus einer Datenbank geholt werden kann, nachdem dass Datenobjekt bestimmte Daten empfangen hat. Also muss ich es zwischenspeichern und solange warten lassen. Es darf aber den eigentlichen Thread, welcher die Arbeit macht und neue Objekte bearbeitet nicht blockieren. Deshalb macht dass das Objekt in einen eigenen Thread.

Priority Queue stimmt die hatte ich gesucht aber ob die genau dass macht weiß ich jetzt nicht. Werd ich auf jedenfall noch mal angucken :)
Das mit dem Comparable implementieren und co wäre kein Problem. Aber muss man dann nicht trotzdem selber noch aufrufen, dass sie sortiert werden soll?
Zu wenig schlaf, falls jetzt etwas komisch klingt sorry=)
 
Hallo,

muss wirklich die Struktur permanent sortiert sein, oder reicht es, wenn man nur über die Einträge gemäß ihrer "Ordnung" iterieren kann?
Wenn das reicht könntest du einfach folgendes machen:

Java: 
package de.tutorials;

import java.util.ArrayList;
import java.util.SortedSet;
import java.util.TreeSet;

public class DynamicallySortedDataStructureExample {

  public static void main(String[] args) {
    final SortedSet<Item> items = new TreeSet<Item>();
    Item itemA = new Item("A");
    items.add(itemA);
    Item itemB = new Item("B");
    items.add(itemB);
    Item itemC = new Item("C");
    items.add(itemC);

    print(items);
    itemB.setValue(3);
    print(items);
    itemC.setValue(5);
    print(items);
    itemA.setValue(8);
    print(items);
    itemB.setValue(null);
    print(items);
    itemA.setValue(null);
    print(items);
  }

  private static void print(SortedSet<Item> items) {
    for (Item item : new TreeSet<Item>(new ArrayList<Item>(items))) { // recompute order for iteration
      System.out.println(item);
    }
    System.out.println("#######");
  }

  static class Item implements Comparable<Item> {
    private final String id;
    private volatile Comparable<? super Object> value;


    public Item(String id) {
      this.id = id;
    }


    public String getId() {
      return id;
    }


    public Comparable<?> getValue() {
      return value;
    }


    @SuppressWarnings("unchecked")
    public void setValue(Comparable value) {
      this.value = value;
    }


    @Override
    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + ((id == null) ? 0 : id.hashCode());
      return result;
    }


    @Override
    public boolean equals(Object obj) {
      if (this == obj) return true;
      if (obj == null) return false;
      if (getClass() != obj.getClass()) return false;
      Item other = (Item) obj;
      if (id == null) {
        if (other.id != null) return false;
      } else if (!id.equals(other.id)) return false;
      return true;
    }


    @Override
    public String toString() {
      StringBuilder builder = new StringBuilder();
      builder.append("Item [id=");
      builder.append(id);
      builder.append(", value=");
      builder.append(value);
      builder.append("]");
      return builder.toString();
    }


    @Override
    public int compareTo(Item that) {
      int order = 0;

      if (this.value != that.value) { // greates value up
        if (this.value == null) {
          order = 1;
        } else if (that.value == null) {
          order = -1;
        } else {
          order = -this.value.compareTo(that.value);
        }
      }

      if (order == 0) {
        order = this.id.compareTo(that.id); //default sort by alpha asc
      }
      return order;
    }
  }
}

Ausgabe:
Code: 
Item [id=A, value=null]
Item [id=B, value=null]
Item [id=C, value=null]
#######
Item [id=B, value=3]
Item [id=A, value=null]
Item [id=C, value=null]
#######
Item [id=C, value=5]
Item [id=B, value=3]
Item [id=A, value=null]
#######
Item [id=A, value=8]
Item [id=C, value=5]
Item [id=B, value=3]
#######
Item [id=A, value=8]
Item [id=C, value=5]
Item [id=B, value=null]
#######
Item [id=C, value=5]
Item [id=A, value=null]
Item [id=B, value=null]
#######

Gruß Tom
 
Also ehrlich gesagt, ich verstehe noch nicht, was für ein Problem Du lösen möchtest, evtl. leide ich da einfach unter einer Verständnisblockade :confused:

Hast Du ein Sequenzidagramm o.ä. zu der Problemstellung? Wäre für deine Doku vielleicht eh nicht schlecht. Wenn mal jemand anderes außer Dir diese Programmstelle warten muss, wäre der bestimmt dankbar ... :D
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück