Next / Previous / Contents / TCC Help System / NM Tech homepage

4.7. SkipList.__estimateLevels()

Here's the .__estimateLevels() function used in the constructor:

pyskip.py
# - - -   S k i p L i s t . _ _ e s t i m a t e L e v e l s   - - -

    def __estimateLevels ( self, n ):
        """Estimate how many levels of list we need for n child objects.

          [ n is a positive integer ->
              return ceiling(log base 4(n)) + 1 ]
        """

        #-- 1 --
        result  =  1

        #-- 2 --
        # [ result  +:=  k, where k is the the number of bits required
        #       to represent n, rounded to the next higher even number ]
        while  n > 0:
            result  +=  1
            n  >>=  2

        #-- 3 --
        return result

In the while loop, we count the number of times we have to shift n to the right two bits before it goes to zero, effectively computing the ceiling of the log base 4 of n. This gives us a result of 1 for n=0, 2 for n in the range [1,4), 3 for n in the range [4,16), 4 for n in the range [16,256), and so on.