Changeset 27159 in project for wiki/eggref/4/skiplists


Ignore:
Timestamp:
08/02/12 14:48:17 (9 years ago)
Author:
juergen
Message:

kiplists documentation rewritten

File:
1 edited

Legend:

Unmodified
Added
Removed
  • wiki/eggref/4/skiplists

    r26733 r27159  
    2525== Documentation
    2626
    27 In this implementation skiplists are implemented in the Design by Contract style, i.e. using the contracts module. A corollary of this is, that the documentation is included in the module. By convention, there is a routine with the module's name, skiplists, which when called with no argument
    28 
    29   (skiplists)
    30 
    31 shows the exported contract-checked symbols, and called with one of its symbols, e.g.
    32 
    33   (skiplists 'skip-list)
    34 
    35 shows the documentation of this symbol in all it's glory, i.e. together with call-structure, docstring, assumptions and propositions.
    36 
    37 Note that most contract-checked routines have brethren whith identical signature which are not contract-checked and are not exported. They are prefixed with an % sign and used internally, especially for contract-checking, thus avoiding double-checking.
     27In this implementation skiplists are implemented in the Design by
     28Contract style, i.e. using the contracts module. A corollary of this is,
     29that the documentation is included in the module in form of procedure with the module's name.
     30
     31==== skiplists
     32
     33<procedure>(skiplists [sym])</procedure>
     34
     35returns all available routines of the module when called without an
     36argument, but when called with one of these routines as a symbol,
     37returns its contract and documentation string.
    3838
    3939Another way to get the complete documentation is to use print-doclist from the contracts module. Issuing
    4040
     41<enscript highlight=scheme>
    4142  (import skiplists (only contracts print-doclist))
    4243  (with-output-to-file "skiplists.docu" (lambda () (print-doclist)))
    43 
    44 you'll get a file skiplists.docu with the following content
    45 
    46   dups
    47   ----
    48   (dups x y)
    49   trivial numerical comparison operator to allow for duplicates
    50 
    51   skip-remove-all!
    52   ----------------
    53   (skip-remove-all! skp . items)
    54   remove nodes (all per found item) with items from skiplist
    55   (domain (%skiplist? skp))
    56   (effect (count (%skip-count skp) count >=))
    57 
    58   skip-remove!
    59   ------------
    60   (skip-remove! skp . items)
    61   remove nodes (one per found item) with items from skiplist
    62   (domain (%skiplist? skp))
    63   (effect (count (%skip-count skp) (- count (length items)) <=))
    64 
    65   skip-insert!
    66   ------------
    67   (skip-insert! skp . items)
    68   insert new nodes with items into skiplist
    69   (domain (%skiplist? skp))
    70   (effect (count (%skip-count skp) (+ count (length items)) (if (skip-dups? skp) = >=)))
    71 
    72   skip-found?
    73   -----------
    74   (skip-found? skp item)
    75   check, if last skip-search! was successfull
    76   (domain (%skiplist? skp))
    77   (range (boolean? result))
    78 
    79   skip-search!
    80   ------------
    81   (skip-search! skp item)
    82   move cursor to a place, where one can look for item
    83   (domain (%skiplist? skp))
    84   (effect (count (%skip-count skp) count =) (links (%skip-links skp) links =))
    85 
    86   skip-compare
    87   ------------
    88   (skip-compare skp)
    89   combined numerical comparison procedure
    90   (domain (%skiplist? skp))
    91   (range (procedure? result))
    92 
    93   skip-dups?
    94   ----------
    95   (skip-dups? skp)
    96   check if duplicates are allowed
    97   (domain (%skiplist? skp))
    98 
    99   skip-max-links
    100   --------------
    101   (skip-max-links skp)
    102   maximal number of links
    103   (domain (%skiplist? skp))
    104   (range (integer? result) (positive? result))
    105 
    106   skip-orders
    107   -----------
    108   (skip-orders skp)
    109   list of numerical comparison operators
    110   (domain (%skiplist? skp))
    111   (range ((list-of? procedure?) result))
    112 
    113   skip-list
    114   ---------
    115   (skip-list skp . ks)
    116   map skiplist to an ordinary list (at link level k, if provided)
    117   (domain (%skiplist? skp)
    118           ((list-of? (lambda (k)
    119                        (and (integer? k) (>= k 0) (< k (%skip-max-links skp)))))
    120            ks))
    121   (range (list? result))
    122 
    123   skip-for-each
    124   -------------
    125   (skip-for-each skp proc)
    126   apply proc to each item of skiplist
    127   (domain (%skiplist? skp) (procedure? proc))
    128 
    129   skip-restructure
    130   ----------------
    131   (skip-restructure skp max-links gap)
    132   restructure skiplist by changing max-links and gap
    133   (domain (integer? max-links) (positive? max-links) (integer? gap) (> gap 1))
    134   (range (%skiplist? result)
    135          (= (%skip-max-links result) max-links)
    136          (= (%skip-gap result) gap))
    137 
    138   skip-reorder
    139   ------------
    140   (skip-reorder skp . orders)
    141   reorder skiplist by changing the order of comparison operators
    142   (domain (%skiplist? skp)
    143           ((list-of? procedure?) orders)
    144           (set-in? orders (%skip-orders skp))
    145           (set-in? (%skip-orders skp) orders))
    146   (range (%skiplist? result)
    147          (= (%skip-count result) (%skip-count skp)))
    148 
    149   skip-filter
    150   -----------
    151   (skip-filter skp ok?)
    152   filter a skiplist according to predicate ok?
    153   (domain (%skiplist? skp)
    154           (procedure? ok?)
    155           one argument predicate)
    156   (range (%skiplist? result))
    157 
    158   make-skiplist-with-gap-from-list
    159   --------------------------------
    160   (make-skiplist-with-gap-from-list lst max-links gap . cmps)
    161   construct a skiplist with gap different from 2 from an ordinary list
    162   (domain (list? lst)
    163           list items must be comparable by operators in cmps
    164           (integer? max-links) (positive? max-links)
    165           (integer? gap) (> gap 1)
    166           ((list-of? procedure?) cmps) (not (null? cmps))
    167           numerical valued comparison procedures)
    168   (range (%skiplist? result))
    169 
    170   make-skiplist-from-list
    171   -----------------------
    172   (make-skiplist-from-list lst max-links . cmps)
    173   construct a skiplist from an ordinary list
    174   (domain (list? lst)
    175           list items must be comparable by operators in cmps
    176           (integer? max-links) (positive? max-links)
    177           ((list-of? procedure?) cmps) (not (null? cmps))
    178           numerical valued comparison procedures)
    179   (range (%skiplist? result))
    180 
    181   make-skiplist-with-gap
    182   ----------------------
    183   (make-skiplist-with-gap max-links gap . cmps)
    184   skiplist constructor with gap different from 2
    185   (domain (integer? max-links) (positive? max-links)
    186           (integer? gap) (> gap 1)
    187           ((list-of? procedure?) cmps) (not (null? cmps))
    188           numerical valued comparison procedures)
    189   (range (%skiplist? result))
    190 
    191   make-skiplist
    192   -------------
    193   (make-skiplist max-links . cmps)
    194   skiplist constructor
    195   (domain (integer? max-links) (positive? max-links)
    196           ((list-of? procedure?) cmps) (not (null? cmps))
    197           numerical valued comparison procedures)
    198   (range (%skiplist? result))
    199 
    200   skip-links
    201   ----------
    202   (skip-links skp)
    203   maximal number of occupied links
    204   (domain (%skiplist? skp))
    205   (range (integer? result) (>= (%skip-max-links skp) result 1))
    206 
    207   skip-count
    208   ----------
    209   (skip-count skp)
    210   number of nodes stored in skiplist
    211   (domain (%skiplist? skp))
    212   (range (integer? result) (>= result 0))
    213 
    214   skip-gap
    215   --------
    216   (skip-gap skp)
    217   gap of skiplist
    218   (domain (%skiplist? skp))
    219   (range (integer? result) (> result 1))
    220 
    221   skiplist?
    222   ---------
    223   (skiplist? xpr)
    224   type predicate
     44</enscript>
     45
     46you'll get a file skiplists.docu, which is the basis of the following documentation
     47
     48==== dups
     49
     50<procedure>(dups x y)</procedure>
     51
     52trivial numerical comparison operator to allow for duplicates
     53
     54==== skip-remove-all!
     55
     56<procedure>(skip-remove-all! skp . items)</procedure>
     57
     58<enscript highlight=scheme>
     59(domain (%skiplist? skp))
     60(effect (count (%skip-count skp) count >=))
     61</enscript>
     62
     63remove nodes (all per found item) with items from skiplist
     64
     65==== skip-remove!
     66
     67<procedure>(skip-remove! skp . items)</procedure>
     68
     69<enscript highlight=scheme>
     70(domain (%skiplist? skp))
     71(effect (count (%skip-count skp) (- count (length items)) <=))
     72</enscript>
     73
     74remove nodes (one per found item) with items from skiplist
     75
     76==== skip-insert!
     77
     78<procedure>(skip-insert! skp . items)</procedure>
     79
     80<enscript highlight=scheme>
     81(domain (%skiplist? skp))
     82(effect (count (%skip-count skp) (+ count (length items)) (if (skip-dups? skp) = >=)))
     83</enscript>
     84
     85insert new nodes with items into skiplist
     86
     87==== skip-found?
     88
     89<procedure>(skip-found? skp item)</procedure>
     90
     91<enscript highlight=scheme>
     92(domain (%skiplist? skp))
     93(range (boolean? result))
     94</enscript>
     95
     96check, if last skip-search! was successfull
     97
     98==== skip-search!
     99
     100<procedure>(skip-search! skp item)</procedure>
     101
     102<enscript highlight=scheme>
     103(domain (%skiplist? skp))
     104(effect (count (%skip-count skp) count =) (links (%skip-links skp) links =))
     105</enscript>
     106
     107move cursor to a place, where one can look for item
     108
     109==== skip-compare
     110
     111<procedure>(skip-compare skp)</procedure>
     112
     113<enscript highlight=scheme>
     114(domain (%skiplist? skp))
     115(range (procedure? result))
     116</enscript>
     117
     118combined numerical comparison procedure
     119
     120==== skip-dups?
     121
     122<procedure>(skip-dups? skp)</procedure>
     123
     124<enscript highlight=scheme>
     125(domain (%skiplist? skp))
     126</enscript>
     127
     128check if duplicates are allowed
     129
     130==== skip-max-links
     131
     132<procedure>(skip-max-links skp)</procedure>
     133
     134<enscript highlight=scheme>
     135(domain (%skiplist? skp))
     136(range (integer? result) (positive? result))
     137</enscript>
     138
     139maximal number of links
     140
     141==== skip-orders
     142
     143<procedure>(skip-orders skp)</procedure>
     144
     145<enscript highlight=scheme>
     146(domain (%skiplist? skp))
     147(range ((list-of? procedure?) result))
     148</enscript>
     149
     150list of numerical comparison operators
     151
     152==== skip-list
     153
     154<procedure>(skip-list skp . ks)</procedure>
     155
     156<enscript highlight=scheme>
     157(domain (%skiplist? skp)
     158        ((list-of? (lambda (k)
     159                     (and (integer? k) (>= k 0) (< k (%skip-max-links skp)))))
     160         ks))
     161(range (list? result))
     162</enscript>
     163
     164map skiplist to an ordinary list (at link level k, if provided)
     165
     166==== skip-for-each
     167
     168<procedure>(skip-for-each skp proc)</procedure>
     169
     170<enscript highlight=scheme>
     171(domain (%skiplist? skp) (procedure? proc))
     172</enscript>
     173
     174apply proc to each item of skiplist
     175
     176==== skip-restructure
     177
     178<procedure>(skip-restructure skp max-links gap)</procedure>
     179
     180<enscript highlight=scheme>
     181(domain (integer? max-links) (positive? max-links) (integer? gap) (> gap 1))
     182(range (%skiplist? result)
     183       (= (%skip-max-links result) max-links)
     184       (= (%skip-gap result) gap))
     185</enscript>
     186
     187restructure skiplist by changing max-links and gap
     188
     189==== skip-reorder
     190
     191<procedure>(skip-reorder skp . orders)</procedure>
     192
     193<enscript highlight=scheme>
     194(domain (%skiplist? skp)
     195        ((list-of? procedure?) orders)
     196        (set-in? orders (%skip-orders skp))
     197        (set-in? (%skip-orders skp) orders))
     198(range (%skiplist? result)
     199       (= (%skip-count result) (%skip-count skp)))
     200</enscript>
     201
     202reorder skiplist by changing the order of comparison operators
     203
     204==== skip-filter
     205
     206<procedure>(skip-filter skp ok?)</procedure>
     207
     208<enscript highlight=scheme>
     209(domain (%skiplist? skp)
     210        (procedure? ok?)
     211        one argument predicate)
     212(range (%skiplist? result))
     213</enscript>
     214
     215filter a skiplist according to predicate ok?
     216
     217==== make-skiplist-with-gap-from-list
     218
     219<procedure>(make-skiplist-with-gap-from-list lst max-links gap .  cmps)</procedure>
     220
     221<enscript highlight=scheme>
     222(domain (list? lst)
     223        list items must be comparable by operators in cmps
     224        (integer? max-links) (positive? max-links)
     225        (integer? gap) (> gap 1)
     226        ((list-of? procedure?) cmps) (not (null? cmps))
     227        numerical valued comparison procedures)
     228(range (%skiplist? result))
     229</enscript>
     230
     231construct a skiplist with gap different from 2 from an ordinary list
     232
     233==== make-skiplist-from-list
     234
     235<procedure>(make-skiplist-from-list lst max-links . cmps)</procedure>
     236
     237<enscript highlight=scheme>
     238(domain (list? lst)
     239        list items must be comparable by operators in cmps
     240        (integer? max-links) (positive? max-links)
     241        ((list-of? procedure?) cmps) (not (null? cmps))
     242        numerical valued comparison procedures)
     243(range (%skiplist? result))
     244</enscript>
     245
     246construct a skiplist from an ordinary list
     247
     248==== make-skiplist-with-gap
     249
     250<procedure>(make-skiplist-with-gap max-links gap . cmps)</procedure>
     251
     252<enscript highlight=scheme>
     253(domain (integer? max-links) (positive? max-links)
     254        (integer? gap) (> gap 1)
     255        ((list-of? procedure?) cmps) (not (null? cmps))
     256        numerical valued comparison procedures)
     257(range (%skiplist? result))
     258</enscript>
     259
     260skiplist constructor with gap different from 2
     261
     262==== make-skiplist
     263
     264<procedure>(make-skiplist max-links . cmps)</procedure>
     265
     266<enscript highlight=scheme>
     267(domain (integer? max-links) (positive? max-links)
     268        ((list-of? procedure?) cmps) (not (null? cmps))
     269        numerical valued comparison procedures)
     270(range (%skiplist? result))
     271</enscript>
     272
     273skiplist constructor
     274
     275==== skip-links
     276
     277<procedure>(skip-links skp)</procedure>
     278
     279<enscript highlight=scheme>
     280(domain (%skiplist? skp))
     281(range (integer? result) (>= (%skip-max-links skp) result 1))
     282</enscript>
     283
     284maximal number of occupied links
     285
     286==== skip-count
     287
     288<procedure>(skip-count skp)</procedure>
     289
     290<enscript highlight=scheme>
     291(domain (%skiplist? skp))
     292(range (integer? result) (>= result 0))
     293</enscript>
     294
     295number of nodes stored in skiplist
     296
     297==== skip-gap
     298
     299<procedure>(skip-gap skp)</procedure>
     300
     301<enscript highlight=scheme>
     302(domain (%skiplist? skp))
     303(range (integer? result) (> result 1))
     304</enscript>
     305
     306gap of skiplist
     307
     308==== skiplist?
     309
     310<procedure>(skiplist? xpr)</procedure>
     311
     312type predicate
    225313
    226314== Examples
     315
     316<enscript highlight=scheme>
    227317
    228318  (use skiplists)
     
    283373  ;; check if flt has only even members
    284374  (not (memq #f (map even? (skip-list flt))))
     375
     376</enscript>
    285377
    286378== Requirements
Note: See TracChangeset for help on using the changeset viewer.