First of all, it is not clear from your description of what you have done, but you need a PlaylistSongs table which contains a PlaylistId and a SongId, describing which songs belong to which playlists.

It is in this table that you have to add ordering information.

My favorite mechanism is with real numbers. I implemented it recently, and it worked like a charm. When you want to move a song to a specific position, you calculate its new Ordering value as the average of the Ordering values of the previous song and the next song. If you use an 64-bit real number, you will run out of precision at about the same time that hell will freeze over, but if you are really writing your software for posterity, then consider reassigning nice rounded integer Ordering values to all songs in each playlist every once in a while.

As an added bonus, here is the code that I have written which implements this. Of course you cannot use it as it is, and it would be too much work for me right now to sanitize it for you, so I am only posting it for you to get ideas from it.

The class is ParameterTemplate (whatever, don’t ask!) The method gets the list of parameter templates to which this template belongs from its parent ActivityTemplate. (Whatever, don’t ask!) The code contains some guard against running out of precision. The divisor is used for testing: the unit test uses a large divisor so as to run out of precision quickly, and thus trigger the precision guarding code. The second method is public and “for internal use only; do not invoke” so that the testing code can invoke it. (It could not be package-private because my testing code is not in the same package as the code it tests.) The field which controls the ordering is called Ordering, accessed via getOrdering() and setOrdering(). You don’t see any SQL because I am using Object-Relational Mapping via Hibernate.

/**
* Moves this {@link ParameterTemplate} to the given index in the list of {@link ParameterTemplate}s of the parent {@link ActivityTemplate}.
*
* The index must be greater than or equal to zero, and less than or equal to the number of entries in the list.  Specifying an index of zero will move this item to the top of
* the list. Specifying an index which is equal to the number of entries will move this item to the end of the list.  Any other index will move this item to the position
* specified, also moving other items in the list as necessary. The given index cannot be equal to the current index of the item, nor can it be equal to the current index plus
* one.  If the given index is below the current index of the item, then the item will be moved so that its new index will be equal to the given index.  If the given index is
* above the current index, then the new index of the item will be the given index minus one.
*
* NOTE: this method flushes the persistor and refreshes the parent node so as to guarantee that the changes will be immediately visible in the list of {@link
* ParameterTemplate}s of the parent {@link ActivityTemplate}.
*
* @param toIndex the desired new index of this {@link ParameterTemplate} in the list of {@link ParameterTemplate}s of the parent {@link ActivityTemplate}.
*/
public void moveAt( int toIndex )
{
moveAt( toIndex, 2.0 );
}

/**
* For internal use only; do not invoke.
*/
public boolean moveAt( int toIndex, double divisor )
{
MutableList<ParameterTemplate<?>> parameterTemplates = getLogicDomain().getMutableCollections().newArrayList();
parameterTemplates.addAll( getParentActivityTemplate().getParameterTemplates() );
assert parameterTemplates.getLength() >= 1; //guaranteed since at the very least, this parameter template must be in the list.
int fromIndex = parameterTemplates.indexOf( this );
assert 0 <= toIndex;
assert toIndex <= parameterTemplates.getLength();
assert 0 <= fromIndex;
assert fromIndex < parameterTemplates.getLength();
assert fromIndex != toIndex;
assert fromIndex != toIndex - 1;

double order;
if( toIndex == 0 )
{
order = parameterTemplates.fetchFirstElement().getOrdering() - 1.0;
}
else if( toIndex == parameterTemplates.getLength() )
{
order = parameterTemplates.fetchLastElement().getOrdering() + 1.0;
}
else
{
double prevOrder = parameterTemplates.get( toIndex - 1 ).getOrdering();
parameterTemplates.moveAt( fromIndex, toIndex );
double nextOrder = parameterTemplates.get( toIndex + (toIndex > fromIndex ? 0 : 1) ).getOrdering();
assert prevOrder <= nextOrder;
order = (prevOrder + nextOrder) / divisor;
if( order <= prevOrder || order >= nextOrder ) //if the accuracy of the double has been exceeded
{
parameterTemplates.clear();
parameterTemplates.addAll( getParentActivityTemplate().getParameterTemplates() );
for( int i = 0; i < parameterTemplates.getLength(); i++ )
parameterTemplates.get( i ).setOrdering( i * 1.0 );
rocs3dDomain.getPersistor().flush();
rocs3dDomain.getPersistor().refresh( getParentActivityTemplate() );
moveAt( toIndex );
return true;
}
}
setOrdering( order );
rocs3dDomain.getPersistor().flush();
rocs3dDomain.getPersistor().refresh( getParentActivityTemplate() );
assert getParentActivityTemplate().getParameterTemplates().indexOf( this ) == (toIndex > fromIndex ? toIndex - 1 : toIndex);
return false;
}