queue: implement song "priorities"

Sorts remaining songs by priority.  This can be used for the
much-demanded "queue feature".

10 files changed, 701 insertions, 6 deletions

diff --git a/.gitignore b/.gitignore
index 977ae6a1..3e993688 100644
--- a/.gitignore
+++ b/.gitignore
@@ -59,3 +59,4 @@ test/dump_playlist
 test/run_normalize
 test/tmp
 test/run_inotify
+test/test_queue_priority
diff --git a/Makefile.am b/Makefile.am
index 0471bcc8..c699397b 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -869,9 +869,13 @@ sparse-check:
 
 if ENABLE_TEST
 
-TESTS =
+C_TESTS = \
+	test/test_queue_priority
+
+TESTS = $(C_TESTS)
 
 noinst_PROGRAMS = \
+	$(C_TESTS) \
 	test/read_conf \
 	test/run_input \
 	test/dump_playlist \
@@ -1153,6 +1157,12 @@ test_run_inotify_SOURCES = test/run_inotify.c \
 test_run_inotify_LDADD = $(GLIB_LIBS)
 endif
 
+test_test_queue_priority_SOURCES = \
+	src/queue.c \
+	test/test_queue_priority.c
+test_test_queue_priority_LDADD = \
+	$(GLIB_LIBS)
+
 endif
 
 
diff --git a/doc/protocol.xml b/doc/protocol.xml
index affe852c..aba080a6 100644
--- a/doc/protocol.xml
+++ b/doc/protocol.xml
@@ -204,6 +204,47 @@
   </chapter>
 
   <chapter>
+    <title>Recipes</title>
+
+    <section>
+      <title>Queuing</title>
+
+      <para>
+        Often, users run MPD with "<link
+        linkend="command_random">random</link>" enabled, but want to
+        be able to insert songs "before" the rest of the playlist.
+        That is commonly called "queuing".
+      </para>
+
+      <para>
+        MPD implements this by allowing the client to specify a
+        "priority" for each song in the playlist (commands <link
+        linkend="command_prio"><command>prio</command></link> and
+        <link
+        linkend="command_prioid"><command>prioid</command></link>).  A
+        higher priority means that the song is going to be played
+        before the other songs.
+      </para>
+
+      <para>
+        In "random" mode, MPD maintains an internal randomized
+        sequence of songs.  In this sequence, songs with a higher
+        priority come first, and all songs with the same priority are
+        shuffled (by default, all songs are shuffled, because all have
+        the same priority "0").  When you increase the priority of a
+        song, it is moved to the front of the sequence according to
+        its new priority, but always after the current one.  A song
+        that has been played already (it's "before" the current song
+        in that sequence) will only be scheduled for repeated playback
+        if its priority has become bigger than the priority of the
+        current song.  Decreasing the priority of a song will moved it
+        farther to the end of the sequence.  Changing the priority of
+        the current song has no effect on the sequence.
+      </para>
+    </section>
+  </chapter>
+
+  <chapter>
     <title>Command reference</title>
 
     <note>
@@ -1092,6 +1133,46 @@ OK
             </para>
           </listitem>
         </varlistentry>
+
+        <varlistentry id="command_prio">
+          <term>
+            <cmdsynopsis>
+              <command>prio</command>
+              <arg choice="req"><replaceable>PRIORITY</replaceable></arg>
+              <arg choice="req" rep="repeat"><replaceable>START:END</replaceable></arg>
+            </cmdsynopsis>
+          </term>
+          <listitem>
+            <para>
+              Set the priority of the specified songs.  A higher
+              priority means that it will be played first when
+              "random" mode is enabled.
+            </para>
+
+            <para>
+              A priority is an integer between 0 and 255.  The default
+              priority of new songs is 0.
+            </para>
+          </listitem>
+        </varlistentry>
+
+        <varlistentry id="command_prioid">
+          <term>
+            <cmdsynopsis>
+              <command>prioid</command>
+              <arg choice="req"><replaceable>PRIORITY</replaceable></arg>
+              <arg choice="req" rep="repeat"><replaceable>ID</replaceable></arg>
+            </cmdsynopsis>
+          </term>
+          <listitem>
+            <para>
+              Same as <link
+              linkend="command_prio"><command>prio</command></link>,
+              but address the songs with their id.
+            </para>
+          </listitem>
+        </varlistentry>
+
         <varlistentry id="command_shuffle">
           <term>
             <cmdsynopsis>
diff --git a/src/command.c b/src/command.c
index e369da69..3e60e0ac 100644
--- a/src/command.c
+++ b/src/command.c
@@ -1171,6 +1171,68 @@ handle_previous(G_GNUC_UNUSED struct client *client,
 }
 
 static enum command_return
+handle_prio(struct client *client, int argc, char *argv[])
+{
+	unsigned priority;
+
+	if (!check_unsigned(client, &priority, argv[1]))
+		return COMMAND_RETURN_ERROR;
+
+	if (priority > 0xff) {
+		command_error(client, ACK_ERROR_ARG,
+			      "Priority out of range: %s", argv[1]);
+		return COMMAND_RETURN_ERROR;
+	}
+
+	for (int i = 2; i < argc; ++i) {
+		unsigned start_position, end_position;
+		if (!check_range(client, &start_position, &end_position,
+				 argv[i], need_range))
+			return COMMAND_RETURN_ERROR;
+
+		enum playlist_result result =
+			playlist_set_priority(&g_playlist,
+					      client->player_control,
+					      start_position, end_position,
+					      priority);
+		if (result != PLAYLIST_RESULT_SUCCESS)
+			return print_playlist_result(client, result);
+	}
+
+	return COMMAND_RETURN_OK;
+}
+
+static enum command_return
+handle_prioid(struct client *client, int argc, char *argv[])
+{
+	unsigned priority;
+
+	if (!check_unsigned(client, &priority, argv[1]))
+		return COMMAND_RETURN_ERROR;
+
+	if (priority > 0xff) {
+		command_error(client, ACK_ERROR_ARG,
+			      "Priority out of range: %s", argv[1]);
+		return COMMAND_RETURN_ERROR;
+	}
+
+	for (int i = 2; i < argc; ++i) {
+		unsigned song_id;
+		if (!check_unsigned(client, &song_id, argv[i]))
+			return COMMAND_RETURN_ERROR;
+
+		enum playlist_result result =
+			playlist_set_priority_id(&g_playlist,
+						 client->player_control,
+						 song_id, priority);
+		if (result != PLAYLIST_RESULT_SUCCESS)
+			return print_playlist_result(client, result);
+	}
+
+	return COMMAND_RETURN_OK;
+}
+
+static enum command_return
 handle_listall(struct client *client, G_GNUC_UNUSED int argc, char *argv[])
 {
 	char *directory = NULL;
@@ -2062,6 +2124,8 @@ static const struct command commands[] = {
 	{ "plchanges", PERMISSION_READ, 1, 1, handle_plchanges },
 	{ "plchangesposid", PERMISSION_READ, 1, 1, handle_plchangesposid },
 	{ "previous", PERMISSION_CONTROL, 0, 0, handle_previous },
+	{ "prio", PERMISSION_CONTROL, 2, -1, handle_prio },
+	{ "prioid", PERMISSION_CONTROL, 2, -1, handle_prioid },
 	{ "random", PERMISSION_CONTROL, 1, 1, handle_random },
 	{ "readmessages", PERMISSION_READ, 0, 0, handle_read_messages },
 	{ "rename", PERMISSION_CONTROL, 2, 2, handle_rename },
diff --git a/src/playlist.h b/src/playlist.h
index 4f8291dc..569db7bc 100644
--- a/src/playlist.h
+++ b/src/playlist.h
@@ -195,6 +195,15 @@ enum playlist_result
 playlist_swap_songs_id(struct playlist *playlist, struct player_control *pc,
 		       unsigned id1, unsigned id2);
 
+enum playlist_result
+playlist_set_priority(struct playlist *playlist, struct player_control *pc,
+		      unsigned start_position, unsigned end_position,
+		      uint8_t priority);
+
+enum playlist_result
+playlist_set_priority_id(struct playlist *playlist, struct player_control *pc,
+			 unsigned song_id, uint8_t priority);
+
 bool
 playlist_get_repeat(const struct playlist *playlist);
 
diff --git a/src/playlist_edit.c b/src/playlist_edit.c
index 505247f5..92c3d44b 100644
--- a/src/playlist_edit.c
+++ b/src/playlist_edit.c
@@ -212,6 +212,61 @@ playlist_swap_songs_id(struct playlist *playlist, struct player_control *pc,
 	return playlist_swap_songs(playlist, pc, song1, song2);
 }
 
+enum playlist_result
+playlist_set_priority(struct playlist *playlist, struct player_control *pc,
+		      unsigned start, unsigned end,
+		      uint8_t priority)
+{
+	if (start >= queue_length(&playlist->queue))
+		return PLAYLIST_RESULT_BAD_RANGE;
+
+	if (end > queue_length(&playlist->queue))
+		end = queue_length(&playlist->queue);
+
+	if (start >= end)
+		return PLAYLIST_RESULT_SUCCESS;
+
+	/* remember "current" and "queued" */
+
+	int current_position = playlist->current >= 0
+		? (int)queue_order_to_position(&playlist->queue,
+					       playlist->current)
+		: -1;
+
+	const struct song *queued = playlist_get_queued_song(playlist);
+
+	/* apply the priority changes */
+
+	queue_set_priority_range(&playlist->queue, start, end, priority,
+				 playlist->current);
+
+	playlist_increment_version(playlist);
+
+	/* restore "current" and choose a new "queued" */
+
+	if (current_position >= 0)
+		playlist->current = queue_position_to_order(&playlist->queue,
+							    current_position);
+
+	playlist_update_queued_song(playlist, pc, queued);
+
+	return PLAYLIST_RESULT_SUCCESS;
+}
+
+enum playlist_result
+playlist_set_priority_id(struct playlist *playlist, struct player_control *pc,
+			 unsigned song_id, uint8_t priority)
+{
+	int song_position = queue_id_to_position(&playlist->queue, song_id);
+	if (song_position < 0)
+		return PLAYLIST_RESULT_NO_SUCH_SONG;
+
+	return playlist_set_priority(playlist, pc,
+				     song_position, song_position + 1,
+				     priority);
+
+}
+
 static void
 playlist_delete_internal(struct playlist *playlist, struct player_control *pc,
 			 unsigned song, const struct song **queued_p)
diff --git a/src/queue.c b/src/queue.c
index 9225590f..cd932875 100644
--- a/src/queue.c
+++ b/src/queue.c
@@ -21,6 +21,8 @@
 #include "queue.h"
 #include "song.h"
 
+#include <stdlib.h>
+
 /**
  * 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;
+}
diff --git a/src/queue.h b/src/queue.h
index 03323d1d..5cb5c196 100644
--- a/src/queue.h
+++ b/src/queue.h
@@ -46,6 +46,13 @@ struct queue_item {
 
 	/** when was this item last changed? */
 	uint32_t version;
+
+	/**
+	 * The priority of this item, between 0 and 255.  High
+	 * priority value means that this song gets played first in
+	 * "random" mode.
+	 */
+	uint8_t priority;
 };
 
 /**
@@ -181,6 +188,15 @@ queue_position_to_order(const struct queue *queue, unsigned position)
 	}
 }
 
+G_GNUC_PURE
+static inline uint8_t
+queue_get_priority_at_position(const struct queue *queue, unsigned position)
+{
+	assert(position < queue->length);
+
+	return queue->items[position].priority;
+}
+
 /**
  * Returns the song at the specified position.
  */
@@ -320,6 +336,14 @@ queue_restore_order(struct queue *queue)
 }
 
 /**
+ * Shuffle the order of items in the specified range, taking their
+ * priorities into account.
+ */
+void
+queue_shuffle_order_range_with_priority(struct queue *queue,
+					unsigned start, unsigned end);
+
+/**
  * Shuffles the virtual order of songs, but does not move them
  * physically.  This is used in random mode.
  */
@@ -341,4 +365,13 @@ queue_shuffle_order_last(struct queue *queue, unsigned start, unsigned end);
 void
 queue_shuffle_range(struct queue *queue, unsigned start, unsigned end);
 
+bool
+queue_set_priority(struct queue *queue, unsigned position,
+		   uint8_t priority, int after_order);
+
+bool
+queue_set_priority_range(struct queue *queue,
+			 unsigned start_position, unsigned end_position,
+			 uint8_t priority, int after_order);
+
 #endif
diff --git a/src/queue_print.c b/src/queue_print.c
index a3082a35..d149e8b6 100644
--- a/src/queue_print.c
+++ b/src/queue_print.c
@@ -41,6 +41,10 @@ queue_print_song_info(struct client *client, const struct queue *queue,
 	song_print_info(client, queue_get(queue, position));
 	client_printf(client, "Pos: %u\nId: %u\n",
 		      position, queue_position_to_id(queue, position));
+
+	uint8_t priority = queue_get_priority_at_position(queue, position);
+	if (priority != 0)
+		client_printf(client, "Prio: %u\n", priority);
 }
 
 void
diff --git a/test/test_queue_priority.c b/test/test_queue_priority.c
new file mode 100644
index 00000000..d61b8c8d
--- /dev/null
+++ b/test/test_queue_priority.c
@@ -0,0 +1,174 @@
+#include "queue.h"
+#include "song.h"
+
+void
+song_free(G_GNUC_UNUSED struct song *song)
+{
+}
+
+G_GNUC_UNUSED
+static void
+dump_order(const struct queue *queue)
+{
+	g_printerr("queue length=%u, order:\n", queue_length(queue));
+	for (unsigned i = 0; i < queue_length(queue); ++i)
+		g_printerr("  [%u] -> %u (prio=%u)\n", i, queue->order[i],
+			   queue->items[queue->order[i]].priority);
+}
+
+static void
+check_descending_priority(G_GNUC_UNUSED const struct queue *queue,
+			 unsigned start_order)
+{
+	assert(start_order < queue_length(queue));
+
+	uint8_t last_priority = 0xff;
+	for (unsigned order = start_order; order < queue_length(queue); ++order) {
+		unsigned position = queue_order_to_position(queue, order);
+		uint8_t priority = queue->items[position].priority;
+		assert(priority <= last_priority);
+		last_priority = priority;
+	}
+}
+
+int
+main(G_GNUC_UNUSED int argc, G_GNUC_UNUSED char **argv)
+{
+	struct song songs[16];
+
+	struct queue queue;
+	queue_init(&queue, 32);
+
+	for (unsigned i = 0; i < G_N_ELEMENTS(songs); ++i)
+		queue_append(&queue, &songs[i]);
+
+	assert(queue_length(&queue) == G_N_ELEMENTS(songs));
+
+	/* priority=10 for 4 items */
+
+	queue_set_priority_range(&queue, 4, 8, 10, -1);
+
+	queue.random = true;
+	queue_shuffle_order(&queue);
+	check_descending_priority(&queue, 0);
+
+	for (unsigned i = 0; i < 4; ++i) {
+		assert(queue_position_to_order(&queue, i) >= 4);
+	}
+
+	for (unsigned i = 4; i < 8; ++i) {
+		assert(queue_position_to_order(&queue, i) < 4);
+	}
+
+	for (unsigned i = 8; i < G_N_ELEMENTS(songs); ++i) {
+		assert(queue_position_to_order(&queue, i) >= 4);
+	}
+
+	/* priority=50 one more item */
+
+	queue_set_priority_range(&queue, 15, 16, 50, -1);
+	check_descending_priority(&queue, 0);
+
+	assert(queue_position_to_order(&queue, 15) == 0);
+
+	for (unsigned i = 0; i < 4; ++i) {
+		assert(queue_position_to_order(&queue, i) >= 4);
+	}
+
+	for (unsigned i = 4; i < 8; ++i) {
+		assert(queue_position_to_order(&queue, i) >= 1 &&
+		       queue_position_to_order(&queue, i) < 5);
+	}
+
+	for (unsigned i = 8; i < 15; ++i) {
+		assert(queue_position_to_order(&queue, i) >= 5);
+	}
+
+	/* priority=20 for one of the 4 priority=10 items */
+
+	queue_set_priority_range(&queue, 3, 4, 20, -1);
+	check_descending_priority(&queue, 0);
+
+	assert(queue_position_to_order(&queue, 3) == 1);
+	assert(queue_position_to_order(&queue, 15) == 0);
+
+	for (unsigned i = 0; i < 3; ++i) {
+		assert(queue_position_to_order(&queue, i) >= 5);
+	}
+
+	for (unsigned i = 4; i < 8; ++i) {
+		assert(queue_position_to_order(&queue, i) >= 2 &&
+		       queue_position_to_order(&queue, i) < 6);
+	}
+
+	for (unsigned i = 8; i < 15; ++i) {
+		assert(queue_position_to_order(&queue, i) >= 6);
+	}
+
+	/* priority=20 for another one of the 4 priority=10 items;
+	   pass "after_order" (with priority=10) and see if it's moved
+	   after that one */
+
+	unsigned current_order = 4;
+	unsigned current_position =
+		queue_order_to_position(&queue, current_order);
+
+	unsigned a_order = 3;
+	unsigned a_position = queue_order_to_position(&queue, a_order);
+	assert(queue.items[a_position].priority == 10);
+	queue_set_priority(&queue, a_position, 20, current_order);
+
+	current_order = queue_position_to_order(&queue, current_position);
+	assert(current_order == 3);
+
+	a_order = queue_position_to_order(&queue, a_position);
+	assert(a_order == 4);
+
+	check_descending_priority(&queue, current_order + 1);
+
+	/* priority=70 for one of the last items; must be inserted
+	   right after the current song, before the priority=20 one we
+	   just created */
+
+	unsigned b_order = 10;
+	unsigned b_position = queue_order_to_position(&queue, b_order);
+	assert(queue.items[b_position].priority == 0);
+	queue_set_priority(&queue, b_position, 70, current_order);
+
+	current_order = queue_position_to_order(&queue, current_position);
+	assert(current_order == 3);
+
+	b_order = queue_position_to_order(&queue, b_position);
+	assert(b_order == 4);
+
+	check_descending_priority(&queue, current_order + 1);
+
+	/* priority=60 for the old prio50 item; must not be moved,
+	   because it's before the current song, and it's status
+	   hasn't changed (it was already higher before) */
+
+	unsigned c_order = 0;
+	unsigned c_position = queue_order_to_position(&queue, c_order);
+	assert(queue.items[c_position].priority == 50);
+	queue_set_priority(&queue, c_position, 60, current_order);
+
+	current_order = queue_position_to_order(&queue, current_position);
+	assert(current_order == 3);
+
+	c_order = queue_position_to_order(&queue, c_position);
+	assert(c_order == 0);
+
+	/* move the prio=20 item back */
+
+	a_order = queue_position_to_order(&queue, a_position);
+	assert(a_order == 5);
+	assert(queue.items[a_position].priority == 20);
+	queue_set_priority(&queue, a_position, 5, current_order);
+
+
+	current_order = queue_position_to_order(&queue, current_position);
+	assert(current_order == 3);
+
+	a_order = queue_position_to_order(&queue, a_position);
+	assert(a_order == 6);
+}