Reinsertion
Let's call the process of moving one already existing item from a list to a new position reinsertion. As mentioned in the previous chapter Positions when you are going to reinsert some item may not be as easy as it appears.
The first goal here is to avoid to sort the most you can the items when a reinsertion is done, because each new item will slow down your sorting time. Plus it would be the same case when is desired to insert a new item in a specific position or you want to recover a deleted item and keep the list order for its original position. So what can we do?
To answer the past question, start thinking with an example. What value is between 1 and 2? One response would be the average value 1.5. So you can use it for insert a new item with that position thus you do not need to sort the list, still your new item is between those values. This is the basic principle to reinsert an item and avoid sorting.
How about we continue using the example from the Positions chapter? But only use the letters.
Now let's try to move c between a and b.
Then you can use what was mentioned in String Comparison and change the value of c to ab to still have a value that is between a and b.
Although ab is a valid numbers has no room for future values between a and itself. Here is useful what we mention at the beginning, the middle character n mentioned in Number System is the average weight from the first to the last character, so using this allows future reinsertions.
We can keep reinserting using the average weight as long as you need it, but what happens when now you run out of space again?
In this case, consider the strings as a numbers with the same length with hidden leading zeroes in order that a will become a!! and aa will be aa!. In this way there is only a mather of get the average weight from the point where the strings start to differ. In this case in the position 2. Thus the value between !! and a! being the value !n, and finally at the end attach this new number to the part of the numbers that not differ in this case a. Getting the final number and a!n that can be used safley as the new position, to start again the cycle 🔄.
Now that you learned how the reinsertion is handled you may want to know what happens when you are only interested in insert a new item at the top your market list. As a matter of a fact it would be more often that you may add a new item to a list rather than reinserting something, thats why a Staquia Position is divided in Segments. This is properly expanded in the next chapter.
Note: Here you can see the reason why in a previous lesson was mentioned that in real scenarios it can be used a wider range because with relatively this small set it ran out of space in 5 reinsertions. To see more about the possible reinsertions before expanding see Maths
Note: This is only the basic idea, so don't worry if you see some random numbers when Staquia generates a new position. There are preformance improvements that are applied.
