Changeset 27159 in project for wiki/eggref/4/skiplists
 Timestamp:
 08/02/12 14:48:17 (9 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

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