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