pavone@202: { pavone@202: linearWithEls <- :els { pavone@74: key:val <- :k v { pavone@74: #{ pavone@74: key <- k pavone@74: val <- v pavone@74: } pavone@74: } pavone@74: find <- :tofind { pavone@74: idx <- 0 pavone@164: while: { pavone@164: if: idx < (els length) { pavone@74: ((els get: idx) key: ) != tofind pavone@164: } else: {false} pavone@74: } do: { pavone@74: idx <- idx + 1 pavone@74: } pavone@74: if: idx < (els length) {idx} else: {-1} pavone@74: } pavone@74: #{ pavone@74: set <- :k v { pavone@74: idx <- find: k pavone@74: if: idx < 0 { pavone@74: els append: (key: k val: v) pavone@74: } else: { pavone@74: (els get: idx) val!: v pavone@74: } pavone@74: self pavone@74: } pavone@164: pavone@74: get <- :k { pavone@74: get: k withDefault: false pavone@74: } pavone@164: pavone@74: get:withDefault <- :k default { pavone@74: idx <- find: k pavone@74: if: idx < 0 { pavone@74: default pavone@74: } else: { pavone@74: (els get: idx) val pavone@74: } pavone@74: } pavone@164: pavone@164: get:elseSet <- :k :else { pavone@248: get: k else: { pavone@164: v <- else: pavone@164: els append: (key: k val: v) pavone@164: v pavone@248: } pavone@248: } pavone@248: pavone@248: get:else <- :k :else { pavone@248: idx <- find: k pavone@248: if: idx < 0 { pavone@248: else: pavone@164: } else: { pavone@164: (els get: idx) val pavone@164: } pavone@164: } pavone@164: pavone@192: contains? <- :k { pavone@192: (find: k) >= 0 pavone@192: } pavone@192: bill@91: foreach <- :l { bill@91: foreach: els :idx el { bill@94: l: (el key) (el val) bill@91: } bill@91: } bill@94: pavone@202: map <- :fun { pavone@202: newels <- #[] pavone@202: foreach: els :idx el { pavone@202: newels append: (key: (el key) val: (fun: (el val))) pavone@202: } pavone@202: linearWithEls: newels pavone@202: } pavone@202: pavone@164: length <- { els length } pavone@74: } pavone@74: } pavone@250: _empty <- #{ pavone@250: empty? <- { true } pavone@250: } pavone@250: _makeBucket <- :key val { pavone@250: #{ pavone@250: empty? <- { false } pavone@250: k <- key pavone@250: v <- val pavone@250: = <- :other { k = other } pavone@250: } pavone@250: } pavone@202: #{ pavone@202: //requires only that keys support equality pavone@202: linear <- { pavone@202: linearWithEls: #[] pavone@202: } pavone@250: pavone@250: //requires that keys support equality and hash pavone@250: hash <- { pavone@250: pavone@250: _buckets <- #[ pavone@250: _empty pavone@250: _empty pavone@250: _empty pavone@250: _empty] pavone@250: _size <- 0 pavone@250: _hashdiffs <- #[0] pavone@250: #{ pavone@250: size <- { size } pavone@250: ifget:else <- :key ifpres :ifnot { pavone@250: basehash <- key hash pavone@250: notdone <- true pavone@250: i <- 0 pavone@250: ret <- _empty pavone@250: pavone@250: while: { if: notdone { i < (_hashdiffs length)}} do: { pavone@250: hv <- basehash + (_hashdiffs get: i) pavone@250: trunc <- hv % (_buckets length) pavone@250: if: trunc < 0 { trunc <- 0 - trunc } pavone@250: bucket <- _buckets get: trunc pavone@250: if: (bucket empty?) { pavone@250: notdone <- false pavone@250: } else: { pavone@250: if: bucket = key { pavone@250: ret <- bucket pavone@250: notdone <- false pavone@250: } pavone@250: } pavone@253: i <- i + 1 pavone@250: } pavone@250: if: (ret empty?) ifnot else: { pavone@250: ifpres: (ret v) pavone@250: } pavone@250: } pavone@250: pavone@250: get:else <- :key :else { pavone@250: ifget: key :val { pavone@250: val pavone@250: } else: else pavone@250: } pavone@250: pavone@250: contains? <- :key { pavone@250: ifget: key :_ { pavone@250: true pavone@250: } else: { pavone@250: false pavone@250: } pavone@250: } pavone@250: pavone@250: set <- :key val { pavone@250: notdone <- true pavone@250: basehash <- key hash pavone@250: i <- 0 pavone@250: while: { if: notdone { i < (_hashdiffs length) } } do: { pavone@250: hv <- basehash + (_hashdiffs get: i) pavone@250: trunc <- hv % (_buckets length) pavone@250: if: trunc < 0 { trunc <- 0 - trunc } pavone@250: bucket <- (_buckets get: trunc) pavone@250: if: (bucket empty?) { pavone@250: _size <- _size + 1 pavone@250: _buckets set: trunc (_makeBucket: key val) pavone@250: notdone <- false pavone@250: } else: { pavone@250: if: bucket = key { pavone@250: bucket v!: val pavone@250: notdone <- false pavone@250: } pavone@250: } pavone@250: i <- i + 1 pavone@250: } pavone@250: if: notdone { pavone@250: newsize <- (_buckets length) * 3 + 1 pavone@250: lastdiff <- _hashdiffs get: ((_hashdiffs length) - 1) pavone@250: if: lastdiff <= 0 { pavone@250: _hashdiffs append: 0 - lastdiff + 1 pavone@250: } else: { pavone@250: _hashdiffs append: 0 - lastdiff pavone@250: } pavone@250: newbucks <- #[] pavone@250: newbucks resize: newsize pavone@250: while: { (newbucks length) < newsize } do: { pavone@250: newbucks append: _empty pavone@250: } pavone@250: oldbucks <- _buckets pavone@250: _buckets <- newbucks pavone@250: _size <- 0 pavone@250: foreach: oldbucks :idx el { pavone@250: if: (not: (el empty?)) { pavone@250: set: (el k) (el v) pavone@250: } pavone@250: } pavone@250: set: key val pavone@250: } pavone@250: self pavone@250: } pavone@250: pavone@250: foreach <- :fun { pavone@250: foreach: _buckets :idx el { pavone@250: if: (not: (el empty?)) { pavone@250: fun: (el k) (el v) pavone@250: } pavone@250: } pavone@250: } pavone@250: } pavone@250: } pavone@250: pavone@250: main <- { pavone@250: d <- hash pavone@250: d set: "foo" "bar" pavone@250: d set: "baz" "qux" pavone@250: i <- 0 pavone@250: while: { i < 32 } do: { pavone@250: d set: (string: i) "blah " . (string: i) pavone@250: i <- i + 1 pavone@250: } pavone@250: foreach: d :k v { pavone@250: print: "k: " . k . ", v: " . v . "\n" pavone@250: } pavone@250: 0 pavone@250: } pavone@202: } pavone@74: }