java - Custom data structure (element + weight) -

which data structure should use keep elements ordered given weight? need add elements in collection each element generate specific weight, weight not contained (neither calculated) inside element itself; calculated else outside of element. moreover, weight not need stored (but if needed), insert parameter put element @ right position.

my specific use case sort music tracks. have list of tracks , list of rules apply on each tracks. iterate through each track, list of rules generate "score" given current track. add track "collection" given generated score, can pick first track highest score.

i can't see data structure use in java. have implement new 1 myself? best guess kind of heap data structure, can't figure out 1 specifically.

edit: weight calculated once @ beginning. can't provide "comparator" since compare tracks, , can't calculate score on "compareto method". algorithm like:

 public track determinenext() {      mystructure<track> trackscores;         (track track : tracks) {             int score = 0;              (rule rule : rules) {                 score += rule.applyscoreon(track);             }              trackscores.add(track, score);         }      return trackscores.first();  } 

i hope idea.

it looks me priorityqueue need:

the elements of priority queue ordered according natural ordering, or comparator provided @ queue construction time, depending on constructor used.

in case, natural ordering score. easy.

as point:

i can't provide "comparator" since compare tracks, , can't calculate score on "compareto method".

the key here don't use compareto() method calculate score. it's other way around. use score in implementation of compareto().

---

you have few ways implement this:

1. make track implements comparable<track>, , implement compareto(track t) compare scores scored, higher score --> "larger" object. priorityqueue take care of rest.
2. implement comparator<track> same thing compareto() option 1.

option 2 better if might sort using different criteria later in program, don't commit having tracks sort score.

ideally, both options store score inside track, score need calculated once; however, you'll have make sure score set before inserting priorityqueue. shouldn't issue though.

alternatively, can calculate score on fly inside comparing methods, if know score won't change on time; can expensive on time, though, if lots of comparisons have made. wouldn't recommend if know score won't change.

---

alternatively, if track objects ignorant scores (which makes sense), can use map tracks key , scores value associate track score:

hashmap<track, integer> scoremap = new hashmap<>(); (track track : tracks) { // copied question, altered     int score = 0;      (rule rule : rules) {         score += rule.applyscoreon(track);     }      scoremap.put(track, integer.valueof(score)); 

now can use comparator pulls scores map

public class trackcomparator implements comparator<track> {     private final map<track, integer> scores;      public trackcomparator(map<track, integer> scores) {         this.scores = scores;     }      @override     public int compare(track t1, track t2) {         // check see if tracks in map if didn't pre-fill map         // scores, compare, return     } } 

there few caveats, though:

• maps require define additional methods (hashcode() in addition equals() hashmap, , form of comparator treemap)
• the keys map should not mutable, although track objects can't see being issue
• you collection eat memory. however, if scores in range [-128, 127], shouldn't of issue. possible pass vm flags expand range, too. wouldn't worry memory consumption unless either have insane number of tracks or several different maps floating around.
• just changing map's value externally not reorder priority queue. have remove() , add() object "score" changed move new position in queue.

i'm not map solution best solution, think far worst, , should pretty on own.

a possible change memory issues put map inside comparator, , have comparator calculate scores if needed , add them map if track isn't there. depends on whether care scores being "frozen" later others. might affect performance adversely, that's big guess.