These attributes and methods are defined on a
SkipList
object:
.insert ( c
)
Inserts a new child element
into the skip list.
c
If you created the skip list with
allowDups=0
and the new
element has the same key as an existing member of
the list, this method will raise a
KeyError
exception.
If duplicates are allowed (the
allowDups=1
option to the
constructor), and the new element's key duplicates
one or more already in the list, the new child will
be added in sequence after the other duplicates.
This makes the ordering stable; see Section 2.1.3, “Stability”.
.delete ( k
)
Deletes the first or only element whose key is equal to
,
and returns the deleted child element (or
k
None
if there are no matching
elements).
If duplicates are allowed and there are multiple
elements equal to
,
only the first one will be deleted.
e
.match ( k
)
Returns the first or only object whose key equals
.
If there are no such objects, this method raises a
k
KeyError
exception.
.find ( k
)
Searches for the first element whose key is equal
to or greater than
,
and returns an iterator that iterates over all
those elements.
k
.first()
If there are any elements in the skip list, this
method returns the first element. If the skip list
is empty, it raises KeyError
.
.__len__(self)
This special method defines the meaning of the
ordinary len()
function when
applied to a SkipList
. It returns
the number of child elements in the list.
.__iter__(self)
Returns an iterator object that can be used to iterate over the elements of the skip list. You can have multiple independent iterators pointing at the same skip list, and each will move independently of the others. This allows constructs like:
for i in s: ...
where s
is a SkipList
object.
Such a loop will set i
to
each child value from s
in
turn.
.__contains__ ( self, k
)
Defines the meaning of the Python
“in
” and
“not in
”
operators in the usual way for container classes.
If s
is a
SkipList
, the expression
k in s
returns true if and
only if k
is equal to at least
one member of s
. Similarly,
the expression k not in s
returns true iff k
is not
equal to any member of s
.
.__delitem__ ( self,
k
)
Same as
.delete(
.
k
)
.__getitem__ ( self,
k
)
This method defines the usual meaning of
s[k]
, where
s
is a
SkipList
. It has the same
semantics as s.match[k]
.
This syntax is useful mainly for skip lists that
don't allow duplicates. If you need to retrieve
multiple members that all compare equal, use the
.find()
method.
.nSearches
Read-only; equal to the number of times the list
has been searched. Each call to the
.match()
,
.find()
, or
.delete()
method is counted as
one search.
.nCompares
Read-only; equal to the number of times two elements
have been compared with the
cmpFun
function (or its default).
Statistically, the ratio of
.nCompares
to
.nSearches
should be
proportional to the log of the number of elements.
For analysis, see Pugh's original article.