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

4.6. SkipList.__init__()

Here's the SkipList constructor. First we make local copies of all the constructor arguments except count, and set up the invariants for several internal state values:

pyskip.py
# - - -   S k i p L i s t . _ _ i n i t _ _   - - -

    def __init__ ( self, keyFun=None, cmpFun=None, allowDups=0,
                   count=1000000 ):
        """Constructor for SkipList"""

        #-- 1 --
        self.keyFun     =  keyFun
        self.cmpFun     =  cmpFun
        self.allowDups  =  allowDups
        self.nSearches  =  0
        self.nCompares  =  0
        self.__nLevels  =  1
        self.__nItems   =  0

Then we compute self.__maxLevels based on the count argument. Based on our p value of 0.25, we'd expect to need two levels when we have about four elements, three levels when we have sixteen, and so forth. To be generous, we'll use one plus the ceiling of the log (base 4) of count. See Section 4.7, “SkipList.__estimateLevels().

pyskip.py
        #-- 2 --
        # [ self.__maxLevels  :=  (number of bits required to
        #       represent count, rounded to the next even number)/2+1 ]
        self.__maxLevels  =  self.__estimateLevels ( count )

Next we have to set up the .__heads and .__terminator elements. They are both special instances of the _SkipItem class; in the former, all links point to the latter, and in the latter, all links point to itself.

pyskip.py
        #-- 3 --
        # [ self.__terminator  :=  a new _SkipItem object whose
        #       links all point to itself
        #   self.__heads  :=  a new _SkipItem object whose links
        #       all point to that new terminator _SkipItem object ]
        self.__terminator  =  _SkipItem ( None, self.__maxLevels )
        self.__heads       =  _SkipItem ( None, self.__maxLevels )
        for i in xrange ( self.__maxLevels ):
            self.__terminator.links[i]  =  self.__terminator
            self.__heads.links[i]  =  self.__terminator