I have a agenda with multiple dates, each date can contain
0 > ... items. Items can be sorted by position, positions should be Integer values without gaps and duplicates.
class Item(models.Model): date = models.DateField() position = models.IntegerField() def move_to(position): qs = self.__class__.objects.filter(date=self.date) # if the position is taken, move up all items gte position # 1 spot to free the wanted position if position in qs.values_list('position', flat=True): qs.filter(position__gte=position).update(position=F('position') + 1) self.position = position self.save()
This kinda works but if I move items back and forth between dates I am left with position gaps, e.g.
"1, 4, 13"
So it doesn't truncate the gaps, I have tried to look for algorithms but MPTT and stuff like that seems an overkill I don't have any requiement for parent hierarchies
I came up with an algoritm that seems to do what I want, but I'm not sure how to implement it
l = [0, 2, 13] def is_compressed(l): return len(l) == sum(l) while not is_compressed(l): m = 0 for i in l[m:]: while i - 1 >= 0 and i - 1 not in l: m += 1 index = l.index(i) l.remove(i) l.insert(index, i - 1) >>> print l [0, 1, 2]