From b159bc0c5f64dd4030f18cfa38539c5851d5157d Mon Sep 17 00:00:00 2001 From: Max Kellermann Date: Tue, 19 Jul 2011 00:34:33 +0200 Subject: queue: implement song "priorities" Sorts remaining songs by priority. This can be used for the much-demanded "queue feature". --- src/queue.c | 274 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 269 insertions(+), 5 deletions(-) (limited to 'src/queue.c') diff --git a/src/queue.c b/src/queue.c index 9225590fc..cd932875e 100644 --- a/src/queue.c +++ b/src/queue.c @@ -21,6 +21,8 @@ #include "queue.h" #include "song.h" +#include + /** * Generate a non-existing id number. */ @@ -104,6 +106,7 @@ queue_append(struct queue *queue, struct song *song) .song = song, .id = id, .version = queue->version, + .priority = 0, }; queue->order[queue->length] = queue->length; @@ -220,6 +223,30 @@ queue_move_range(struct queue *queue, unsigned start, unsigned end, unsigned to) } } +/** + * Moves a song to a new position in the "order" list. + */ +static void +queue_move_order(struct queue *queue, unsigned from_order, unsigned to_order) +{ + assert(queue != NULL); + assert(from_order < queue->length); + assert(to_order <= queue->length); + + const unsigned from_position = + queue_order_to_position(queue, from_order); + + if (from_order < to_order) { + for (unsigned i = from_order; i < to_order; ++i) + queue->order[i] = queue->order[i + 1]; + } else { + for (unsigned i = from_order; i > to_order; --i) + queue->order[i] = queue->order[i - 1]; + } + + queue->order[to_order] = from_position; +} + void queue_delete(struct queue *queue, unsigned position) { @@ -308,15 +335,123 @@ queue_finish(struct queue *queue) g_rand_free(queue->rand); } -void -queue_shuffle_order(struct queue *queue) +static const struct queue_item * +queue_get_order_item_const(const struct queue *queue, unsigned order) +{ + assert(queue != NULL); + assert(order < queue->length); + + return &queue->items[queue->order[order]]; +} + +static uint8_t +queue_get_order_priority(const struct queue *queue, unsigned order) +{ + return queue_get_order_item_const(queue, order)->priority; +} + +static gint +queue_item_compare_order_priority(gconstpointer av, gconstpointer bv, + gpointer user_data) +{ + const struct queue *queue = user_data; + const unsigned *const ap = av; + const unsigned *const bp = bv; + assert(ap >= queue->order && ap < queue->order + queue->length); + assert(bp >= queue->order && bp < queue->order + queue->length); + uint8_t a = queue->items[*ap].priority; + uint8_t b = queue->items[*bp].priority; + + if (G_LIKELY(a == b)) + return 0; + else if (a > b) + return -1; + else + return 1; +} + +static void +queue_sort_order_by_priority(struct queue *queue, unsigned start, unsigned end) { + assert(queue != NULL); assert(queue->random); + assert(start <= end); + assert(end <= queue->length); - for (unsigned i = 0; i < queue->length; i++) + g_qsort_with_data(&queue->order[start], end - start, + sizeof(queue->order[0]), + queue_item_compare_order_priority, + queue); +} + +/** + * Shuffle the order of items in the specified range, ignoring their + * priorities. + */ +static void +queue_shuffle_order_range(struct queue *queue, unsigned start, unsigned end) +{ + assert(queue != NULL); + assert(queue->random); + assert(start <= end); + assert(end <= queue->length); + + for (unsigned i = start; i < end; ++i) queue_swap_order(queue, i, - g_rand_int_range(queue->rand, i, - queue->length)); + g_rand_int_range(queue->rand, i, end)); +} + +/** + * Sort the "order" of items by priority, and then shuffle each + * priority group. + */ +void +queue_shuffle_order_range_with_priority(struct queue *queue, + unsigned start, unsigned end) +{ + assert(queue != NULL); + assert(queue->random); + assert(start <= end); + assert(end <= queue->length); + + if (start == end) + return; + + /* first group the range by priority */ + queue_sort_order_by_priority(queue, start, end); + + /* now shuffle each priority group */ + unsigned group_start = start; + uint8_t group_priority = queue_get_order_priority(queue, start); + + for (unsigned i = start + 1; i < end; ++i) { + uint8_t priority = queue_get_order_priority(queue, i); + assert(priority <= group_priority); + + if (priority != group_priority) { + /* start of a new group - shuffle the one that + has just ended */ + queue_shuffle_order_range(queue, group_start, i); + group_start = i; + group_priority = priority; + } + } + + /* shuffle the last group */ + queue_shuffle_order_range(queue, group_start, end); +} + +void +queue_shuffle_order(struct queue *queue) +{ + queue_shuffle_order_range_with_priority(queue, 0, queue->length); +} + +static void +queue_shuffle_order_first(struct queue *queue, unsigned start, unsigned end) +{ + queue_swap_order(queue, start, + g_rand_int_range(queue->rand, start, end)); } void @@ -337,3 +472,132 @@ queue_shuffle_range(struct queue *queue, unsigned start, unsigned end) queue_swap(queue, i, ri); } } + +/** + * Find the first item that has this specified priority or higher. + */ +G_GNUC_PURE +static unsigned +queue_find_priority_order(const struct queue *queue, unsigned start_order, + uint8_t priority, unsigned exclude_order) +{ + assert(queue != NULL); + assert(queue->random); + assert(start_order <= queue->length); + + for (unsigned order = start_order; order < queue->length; ++order) { + const unsigned position = queue_order_to_position(queue, order); + const struct queue_item *item = &queue->items[position]; + if (item->priority <= priority && order != exclude_order) + return order; + } + + return queue->length; +} + +G_GNUC_PURE +static unsigned +queue_count_same_priority(const struct queue *queue, unsigned start_order, + uint8_t priority) +{ + assert(queue != NULL); + assert(queue->random); + assert(start_order <= queue->length); + + for (unsigned order = start_order; order < queue->length; ++order) { + const unsigned position = queue_order_to_position(queue, order); + const struct queue_item *item = &queue->items[position]; + if (item->priority != priority) + return order - start_order; + } + + return queue->length - start_order; +} + +bool +queue_set_priority(struct queue *queue, unsigned position, uint8_t priority, + int after_order) +{ + assert(queue != NULL); + assert(position < queue->length); + + struct queue_item *item = &queue->items[position]; + uint8_t old_priority = item->priority; + if (old_priority == priority) + return false; + + item->version = queue->version; + item->priority = priority; + + if (!queue->random) + /* don't reorder if not in random mode */ + return true; + + unsigned order = queue_position_to_order(queue, position); + if (after_order >= 0) { + if (order == (unsigned)after_order) + /* don't reorder the current song */ + return true; + + if (order < (unsigned)after_order) { + /* the specified song has been played already + - enqueue it only if its priority has just + become bigger than the current one's */ + + const unsigned after_position = + queue_order_to_position(queue, after_order); + const struct queue_item *after_item = + &queue->items[after_position]; + if (old_priority > after_item->priority || + priority <= after_item->priority) + /* priority hasn't become bigger */ + return true; + } + } + + /* move the item to the beginning of the priority group (or + create a new priority group) */ + + const unsigned before_order = + queue_find_priority_order(queue, after_order + 1, priority, + order); + const unsigned new_order = before_order > order + ? before_order - 1 + : before_order; + queue_move_order(queue, order, new_order); + + /* shuffle the song within that priority group */ + + const unsigned priority_count = + queue_count_same_priority(queue, new_order, priority); + assert(priority_count >= 1); + queue_shuffle_order_first(queue, new_order, + new_order + priority_count); + + return true; +} + +bool +queue_set_priority_range(struct queue *queue, + unsigned start_position, unsigned end_position, + uint8_t priority, int after_order) +{ + assert(queue != NULL); + assert(start_position <= end_position); + assert(end_position <= queue->length); + + bool modified = false; + int after_position = after_order >= 0 + ? (int)queue_order_to_position(queue, after_order) + : -1; + for (unsigned i = start_position; i < end_position; ++i) { + after_order = after_position >= 0 + ? (int)queue_position_to_order(queue, after_position) + : -1; + + modified |= queue_set_priority(queue, i, priority, + after_order); + } + + return modified; +} -- cgit v1.2.3