-USING: bit-sets tools.test new-sets kernel bit-arrays ;
+USING: bit-sets tools.test sets kernel bit-arrays ;
IN: bit-sets.tests
[ T{ bit-set f ?{ t f t f t f } } ] [
! Copyright (C) 2009 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
-USING: kernel accessors sequences byte-arrays bit-arrays math hints new-sets ;
+USING: kernel accessors sequences byte-arrays bit-arrays math hints sets ;
IN: bit-sets
TUPLE: bit-set { table bit-array read-only } ;
compiler.cfg.comparisons
compiler.cfg.instructions
compiler.cfg.representations.preferred ;
+FROM: namespaces => set ;
IN: compiler.cfg.alias-analysis
! We try to eliminate redundant slot operations using some simple heuristics.
! See http://factorcode.org/license.txt for BSD license.
USING: accessors assocs kernel namespaces sequences
compiler.cfg.instructions compiler.cfg.def-use
-compiler.cfg.rpo compiler.cfg.predecessors hash-sets new-sets ;
+compiler.cfg.rpo compiler.cfg.predecessors hash-sets sets ;
FROM: namespaces => set ;
IN: compiler.cfg.dce
namespaces quotations sequences sets slots words
compiler.cfg.instructions compiler.cfg.instructions.syntax
compiler.cfg.rpo ;
+FROM: namespaces => set ;
IN: compiler.cfg.def-use
GENERIC: defs-vreg ( insn -- vreg/f )
USING: accessors assocs combinators sets math fry kernel math.order
dlists deques vectors namespaces sequences sorting locals
compiler.cfg.rpo compiler.cfg.predecessors ;
+FROM: namespaces => set ;
IN: compiler.cfg.dominance
! Reference:
[ accum push ]
[ dom-children work-list push-all-front ] bi
] slurp-deque
- accum ;
\ No newline at end of file
+ accum ;
compiler.cfg.linear-scan.allocation
compiler.cfg.linear-scan.allocation.state
compiler.cfg.linear-scan.live-intervals ;
+FROM: namespaces => set ;
IN: compiler.cfg.linear-scan.assignment
! This contains both active and inactive intervals; any interval
namespaces sequences combinators combinators.short-circuit
fry math compiler.cfg.rpo compiler.cfg.utilities
compiler.cfg.loop-detection compiler.cfg.predecessors
-new-sets hash-sets ;
+sets hash-sets ;
FROM: namespaces => set ;
IN: compiler.cfg.linearization.order
hashtables dlists compiler.cfg.def-use compiler.cfg.instructions
compiler.cfg.rpo compiler.cfg.liveness compiler.cfg.utilities
compiler.cfg.predecessors ;
+FROM: namespaces => set ;
IN: compiler.cfg.liveness.ssa
! TODO: merge with compiler.cfg.liveness
: live-in? ( vreg bb -- ? ) live-in key? ;
-: live-out? ( vreg bb -- ? ) live-out key? ;
\ No newline at end of file
+: live-out? ( vreg bb -- ? ) live-out key? ;
! See http://factorcode.org/license.txt for BSD license.
USING: accessors assocs combinators deques dlists fry kernel
namespaces sequences sets compiler.cfg compiler.cfg.predecessors ;
+FROM: namespaces => set ;
IN: compiler.cfg.loop-detection
TUPLE: natural-loop header index ends blocks ;
compiler.cfg.utilities compiler.cfg compiler.cfg.rpo
compiler.cfg.instructions compiler.cfg.def-use ;
FROM: compiler.cfg.instructions.syntax => insn-def-slot insn-use-slots insn-temp-slots scalar-rep ;
+FROM: namespaces => set ;
IN: compiler.cfg.representations.preferred
GENERIC: defs-vreg-rep ( insn -- rep/f )
compiler.cfg.loop-detection
compiler.cfg.renaming.functor
compiler.cfg.representations.preferred ;
+FROM: namespaces => set ;
IN: compiler.cfg.representations
! Virtual register representation selection.
! See http://factorcode.org/license.txt for BSD license.
USING: kernel accessors namespaces make math sequences sets
assocs fry compiler.cfg compiler.cfg.instructions ;
+FROM: namespaces => set ;
IN: compiler.cfg.rpo
SYMBOL: visited
dupd '[ _ optimize-basic-block ] each-basic-block ; inline
: needs-post-order ( cfg -- cfg' )
- dup post-order drop ;
\ No newline at end of file
+ dup post-order drop ;
compiler.cfg.renaming
compiler.cfg.renaming.functor
compiler.cfg.ssa.construction.tdmsc ;
+FROM: namespaces => set ;
IN: compiler.cfg.ssa.construction
! The phi placement algorithm is implemented in
[ compute-defs compute-phi-nodes insert-phi-nodes ]
[ rename ]
[ ]
- } cleave ;
\ No newline at end of file
+ } cleave ;
! Copyright (C) 2009 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
USING: accessors arrays assocs bit-arrays bit-sets fry
-hashtables hints kernel locals math namespaces sequences new-sets
+hashtables hints kernel locals math namespaces sequences sets
compiler.cfg compiler.cfg.dominance compiler.cfg.rpo ;
FROM: namespaces => set ;
IN: compiler.cfg.ssa.construction.tdmsc
compiler.cfg.ssa.interference.live-ranges
compiler.cfg.utilities
compiler.utilities ;
+FROM: namespaces => set ;
IN: compiler.cfg.ssa.destruction
! Maps vregs to leaders.
compiler.cfg.dominance
compiler.cfg.def-use
compiler.cfg.instructions ;
+FROM: namespaces => set ;
IN: compiler.cfg.ssa.liveness
! Liveness checking on SSA IR, as described in
compiler.cfg.registers
compiler.cfg.stacks.height
compiler.cfg.parallel-copy ;
+FROM: namespaces => set ;
IN: compiler.cfg.stacks.local
! Local stack analysis. We build three sets for every basic block
: peek-set ( bb -- assoc ) peek-sets get at ;
: replace-set ( bb -- assoc ) replace-sets get at ;
-: kill-set ( bb -- assoc ) kill-sets get at ;
\ No newline at end of file
+: kill-set ( bb -- assoc ) kill-sets get at ;
USING: accessors assocs combinators.short-circuit
compiler.cfg.instructions compiler.cfg.rpo kernel namespaces
sequences sets ;
+FROM: namespaces => set ;
IN: compiler.cfg.write-barrier
SYMBOL: fresh-allocations
compiler.cfg.builder
compiler.codegen.fixup
compiler.utilities ;
+FROM: namespaces => set ;
IN: compiler.codegen
SYMBOL: insn-counts
compiler.tree.def-use
compiler.tree.recursive
compiler.tree.combinators ;
+FROM: namespaces => set ;
IN: compiler.tree.checker
! Check some invariants; this can help catch compiler bugs.
arrays combinators columns stack-checker.backend
stack-checker.branches compiler.tree compiler.tree.combinators
compiler.tree.dead-code.liveness compiler.tree.dead-code.simple ;
+FROM: namespaces => set ;
IN: compiler.tree.dead-code.branches
M: #if mark-live-values* look-at-inputs ;
dlists kernel sequences compiler.utilities words sets
stack-checker.branches compiler.tree compiler.tree.def-use
compiler.tree.combinators ;
+FROM: namespaces => set ;
IN: compiler.tree.dead-code.liveness
SYMBOL: work-list
stack-checker.branches
compiler.tree
compiler.tree.combinators ;
+FROM: namespaces => set ;
IN: compiler.tree.def-use
SYMBOL: def-use
! See http://factorcode.org/license.txt for BSD license.
USING: sequences kernel fry vectors accessors namespaces assocs sets
stack-checker.branches compiler.tree compiler.tree.def-use ;
+FROM: namespaces => set ;
IN: compiler.tree.def-use.simplified
! Simplified def-use follows chains of copies.
! See http://factorcode.org/license.txt for BSD license.
USING: accessors assocs namespaces sequences kernel math
combinators sets disjoint-sets fry stack-checker.values ;
+FROM: namespaces => set ;
IN: compiler.tree.escape-analysis.allocations
! A map from values to classes. Only for #introduce outputs
compiler.tree.def-use
compiler.tree.def-use.simplified
compiler.tree.late-optimizations ;
+FROM: namespaces => set ;
IN: compiler.tree.modular-arithmetic
! This is a late-stage optimization.
compiler.tree.debugger compiler.tree.checker slots.private words
hashtables classes assocs locals specialized-arrays system
sorting math.libm math.floats.private math.integers.private
-math.intervals quotations effects alien alien.data new-sets ;
+math.intervals quotations effects alien alien.data sets ;
FROM: math => float ;
SPECIALIZED-ARRAY: double
SPECIALIZED-ARRAY: void*
USING: alien.c-types kernel sequences words fry generic accessors
classes.tuple classes classes.algebra definitions
stack-checker.dependencies quotations classes.tuple.private math
-math.partial-dispatch math.private math.intervals new-sets.private
+math.partial-dispatch math.private math.intervals sets.private
math.floats.private math.integers.private layouts math.order
vectors hashtables combinators effects generalizations assocs
-new-sets combinators.short-circuit sequences.private locals growable
+sets combinators.short-circuit sequences.private locals growable
stack-checker namespaces compiler.tree.propagation.info ;
FROM: math => float ;
-FROM: new-sets => set ;
+FROM: sets => set ;
IN: compiler.tree.propagation.transforms
\ equal? [
! See http://factorcode.org/license.txt for BSD license.
USING: kernel assocs arrays namespaces accessors sequences deques fry
search-deques dlists combinators.short-circuit make sets compiler.tree ;
+FROM: namespaces => set ;
IN: compiler.tree.recursive
TUPLE: call-site tail? node label ;
sorting splitting strings vectors vocabs vocabs.loader words
words.symbol ;
FROM: prettyprint.sections => with-pprint ;
+FROM: namespaces => set ;
IN: help.markup
PREDICATE: simple-element < array
sequences strings io.styles vectors words quotations mirrors
splitting math.parser classes vocabs sets sorting summary
debugger continuations fry combinators ;
+FROM: namespaces => set ;
IN: inspector
SYMBOL: +number-rows+
sets unicode.categories compiler.units parser effects.parser
words quotations memoize accessors locals splitting
combinators.short-circuit generalizations ;
+FROM: namespaces => set ;
IN: peg
TUPLE: parse-result remaining ast ;
namespaces prettyprint.config prettyprint.custom
prettyprint.sections prettyprint.stylesheet quotations sbufs
sequences strings vectors words words.symbol hash-sets ;
-FROM: new-sets => members ;
+FROM: sets => members ;
IN: prettyprint.backend
M: effect pprint* effect>string "(" ")" surround text ;
parser prettyprint.backend prettyprint.config prettyprint.custom
prettyprint.sections quotations sequences sorting strings vocabs
vocabs.prettyprint words sets generic ;
+FROM: namespaces => set ;
IN: prettyprint
: with-use ( obj quot -- )
namespaces make sequences strings io.styles vectors words
prettyprint.config splitting classes continuations
accessors sets vocabs.parser combinators vocabs ;
+FROM: namespaces => set ;
IN: prettyprint.sections
! State
unicode.categories regexp.transition-tables words sets hashtables
combinators.short-circuit unicode.data regexp.ast
regexp.classes memoize ;
+FROM: namespaces => set ;
IN: regexp.nfa
! This uses unicode.data for ch>upper and ch>lower
prettyprint.backend prettyprint.config prettyprint.custom
prettyprint.sections sequences sets sorting strings summary words
words.symbol words.constant words.alias vocabs slots ;
+FROM: namespaces => set ;
+FROM: classes => members ;
IN: see
GENERIC: synopsis* ( defspec -- )
definitions sets hints macros stack-checker.state
stack-checker.visitor stack-checker.errors stack-checker.values
stack-checker.recursive-state stack-checker.dependencies summary ;
+FROM: namespaces => set ;
IN: stack-checker.backend
: push-d ( obj -- ) meta-d push ;
combinators.short-circuit classes.tuple alien.c-types ;
FROM: classes.tuple.private => tuple-layout ;
FROM: assocs => change-at ;
+FROM: namespaces => set ;
IN: stack-checker.dependencies
! Words that the current quotation depends on
stack-checker.state stack-checker.visitor stack-checker.errors
stack-checker.values stack-checker.recursive-state
stack-checker.dependencies ;
+FROM: namespaces => set ;
IN: stack-checker.transforms
: call-transformer ( stack quot -- newquot )
math.vectors classes.tuple classes boxes calendar alarms combinators
sets columns fry deques ui.gadgets ui.gadgets.private ascii
combinators.short-circuit ;
+FROM: namespaces => set ;
IN: ui.gestures
: get-gesture-handler ( gesture gadget -- quot )
ui.tools.listener.history ui.images ui.tools.error-list
tools.errors.model ;
FROM: source-files.errors => all-errors ;
+FROM: namespaces => set ;
IN: ui.tools.listener
! If waiting is t, we're waiting for user input, and invoking
compiler.units parser io.encodings.ascii values interval-maps
ascii sets combinators locals math.ranges sorting make
strings.parser io.encodings.utf8 memoize simple-flat-file ;
+FROM: namespaces => set ;
IN: unicode.data
<PRIVATE
USING: accessors assocs checksums checksums.crc32
io.encodings.utf8 io.files kernel namespaces sequences sets
source-files vocabs vocabs.errors vocabs.loader ;
+FROM: namespaces => set ;
IN: vocabs.refresh
: source-modified? ( path -- ? )
: refresh ( prefix -- ) to-refresh do-refresh ;
-: refresh-all ( -- ) "" refresh ;
\ No newline at end of file
+: refresh-all ( -- ) "" refresh ;
USING: kernel classes classes.private combinators accessors
sequences arrays vectors assocs namespaces words sorting layouts
math hashtables kernel.private sets math.order ;
+FROM: classes => members ;
IN: classes.algebra
<PRIVATE
slots.private namespaces make sequences strings words words.symbol
vectors math quotations combinators sorting effects graphs
vocabs sets ;
+FROM: namespaces => set ;
IN: classes
ERROR: bad-inheritance class superclass ;
! Copyright (C) 2008, 2010 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
-USING: accessors kernel new-sets namespaces make sequences parser
+USING: accessors kernel sets namespaces make sequences parser
lexer combinators words classes.parser classes.tuple arrays
slots math assocs parser.notes classes classes.algebra ;
IN: classes.tuple.parser
: contiguous-range? ( keys -- ? )
dup [ fixnum? ] all? [
dup all-unique? [
- [ prune length ]
+ [ length ]
[ [ supremum ] [ infimum ] bi - ]
bi - 1 =
] [ drop f ] if
sequences words vocabs definitions hashtables init sets math
math.order classes classes.private classes.algebra classes.tuple
classes.tuple.private generic source-files.errors kernel.private ;
+FROM: namespaces => set ;
IN: compiler.units
SYMBOL: old-definitions
! See http://factorcode.org/license.txt for BSD license.
USING: accessors continuations kernel namespaces make
sequences vectors sets assocs init math ;
+FROM: namespaces => set ;
IN: destructors
SYMBOL: disposables
hashtables definitions kernel.private classes classes.private
classes.algebra quotations arrays vocabs effects combinators
sets ;
+FROM: namespaces => set ;
IN: generic
! Method combination protocol
! Copyright (C) 2010 Daniel Ehrenberg
! See http://factorcode.org/license.txt for BSD license.
-USING: new-sets tools.test kernel sorting prettyprint hash-sets ;
+USING: sets tools.test kernel sorting prettyprint hash-sets ;
IN: hash-sets.tests
[ { 1 2 3 } ] [ HS{ 1 2 3 } members natural-sort ] unit-test
! Copyright (C) 2010 Daniel Ehrenberg
! See http://factorcode.org/license.txt for BSD license.
-USING: accessors assocs hashtables kernel new-sets
+USING: accessors assocs hashtables kernel sets
sequences parser ;
QUALIFIED: sets
IN: hash-sets
-USING: kernel sets tools.test ;
+! Copyright (C) 2010 Daniel Ehrenberg
+! See http://factorcode.org/license.txt for BSD license.
+USING: sets tools.test kernel prettyprint hash-sets sorting ;
IN: sets.tests
-[ f ] [ { 0 1 1 2 3 5 } all-unique? ] unit-test
-[ t ] [ { 0 1 2 3 4 5 } all-unique? ] unit-test
-
-[ V{ 1 2 3 } ] [ { 1 2 2 3 3 } prune ] unit-test
-[ V{ 3 2 1 } ] [ { 3 3 2 2 1 } prune ] unit-test
-
[ { } ] [ { } { } intersect ] unit-test
[ { 2 3 } ] [ { 1 2 3 } { 2 3 4 } intersect ] unit-test
[ { } ] [ { } { } diff ] unit-test
[ { 1 } ] [ { 1 2 3 } { 2 3 4 } diff ] unit-test
-[ V{ } ] [ { } { } union ] unit-test
-[ V{ 1 2 3 4 } ] [ { 1 2 3 } { 2 3 4 } union ] unit-test
-
-[ V{ 1 2 3 } ]
-[ 3 V{ 1 2 } clone [ adjoin ] keep ] unit-test
-
-[ V{ 1 2 3 } ]
-[ 3 V{ 1 3 2 } clone [ adjoin ] keep ] unit-test
+[ { } ] [ { } { } union ] unit-test
+[ { 1 2 3 4 } ] [ { 1 2 3 } { 2 3 4 } union ] unit-test
[ t ] [ { 1 2 } { 1 3 } intersects? ] unit-test
[ f ] [ { 1 } { } intersects? ] unit-test
+[ t ] [ 4 { 2 4 5 } in? ] unit-test
+[ f ] [ 1 { 2 4 5 } in? ] unit-test
+
+[ V{ 1 2 3 } ] [ 3 V{ 1 2 } clone [ adjoin ] keep ] unit-test
+[ V{ 1 2 } ] [ 2 V{ 1 2 } clone [ adjoin ] keep ] unit-test
+[ V{ 1 2 } ] [ 3 V{ 1 2 } clone [ delete ] keep ] unit-test
+[ V{ 2 } ] [ 1 V{ 1 2 } clone [ delete ] keep ] unit-test
+
+[ t ] [ { 1 2 3 } { 2 1 3 } set= ] unit-test
+[ f ] [ { 2 3 } { 1 2 3 } set= ] unit-test
+[ f ] [ { 1 2 3 } { 2 3 } set= ] unit-test
+
+[ { 1 } ] [ { 1 } members ] unit-test
+
+[ { 1 2 3 } ] [ { 1 1 1 2 2 3 3 3 3 3 } dup set-like natural-sort ] unit-test
+[ { 1 2 3 } ] [ HS{ 1 2 3 } { } set-like natural-sort ] unit-test
+
+[ HS{ 1 2 3 } ] [ { 1 2 3 } fast-set ] unit-test
+
+[ { 1 2 3 } ] [ { { 1 } { 2 } { 1 3 } } combine ] unit-test
+
+[ f ] [ { 0 1 1 2 3 5 } all-unique? ] unit-test
+[ t ] [ { 0 1 2 3 4 5 } all-unique? ] unit-test
+
+[ { 1 2 3 } ] [ { 1 2 2 3 3 } { } set-like ] unit-test
+[ { 3 2 1 } ] [ { 3 3 2 2 1 } { } set-like ] unit-test
+
+[ { 2 1 2 1 } ] [ { 1 2 3 2 1 2 1 } duplicates ] unit-test
+[ f ] [ HS{ 1 2 3 1 2 1 } duplicates ] unit-test
+
+[ H{ { 3 HS{ 1 2 } } } ] [ H{ } clone 1 3 pick adjoin-at 2 3 pick adjoin-at ] unit-test
-! Copyright (C) 2008, 2009 Slava Pestov, Doug Coleman.
+! Copyright (C) 2010 Daniel Ehrenberg
! See http://factorcode.org/license.txt for BSD license.
-USING: assocs hashtables kernel sequences vectors ;
+USING: accessors assocs hashtables kernel vectors
+math sequences ;
IN: sets
-: adjoin ( elt seq -- ) [ remove! drop ] [ push ] 2bi ;
+! Set protocol
+MIXIN: set
+GENERIC: adjoin ( elt set -- )
+GENERIC: in? ( elt set -- ? )
+GENERIC: delete ( elt set -- )
+GENERIC: set-like ( set exemplar -- set' )
+GENERIC: fast-set ( set -- set' )
+GENERIC: members ( set -- sequence )
+GENERIC: union ( set1 set2 -- set )
+GENERIC: intersect ( set1 set2 -- set )
+GENERIC: intersects? ( set1 set2 -- ? )
+GENERIC: diff ( set1 set2 -- set )
+GENERIC: subset? ( set1 set2 -- ? )
+GENERIC: set= ( set1 set2 -- ? )
+GENERIC: duplicates ( set -- sequence )
+GENERIC: all-unique? ( set -- ? )
+
+! Defaults for some methods.
+! Override them for efficiency
+
+M: set union
+ [ [ members ] bi@ append ] keep set-like ;
-: conjoin ( elt assoc -- ) dupd set-at ;
+<PRIVATE
-: conjoin-at ( value key assoc -- )
- [ dupd ?set-at ] change-at ;
+: tester ( set -- quot )
+ fast-set [ in? ] curry ; inline
-: (prune) ( elt hash vec -- )
- 3dup drop key? [ 3drop ] [
- [ drop conjoin ] [ nip push ] 3bi
- ] if ; inline
+: sequence/tester ( set1 set2 -- set1' quot )
+ [ members ] [ tester ] bi* ; inline
-: prune ( seq -- newseq )
- [ ] [ length <hashtable> ] [ length <vector> ] tri
- [ [ (prune) ] 2curry each ] keep ;
+PRIVATE>
-: duplicates ( seq -- newseq )
- H{ } clone [ [ key? ] [ conjoin ] 2bi ] curry filter ;
+M: set intersect
+ [ sequence/tester filter ] keep set-like ;
-: gather ( seq quot -- newseq )
- map concat prune ; inline
+M: set diff
+ [ sequence/tester [ not ] compose filter ] keep set-like ;
-: unique ( seq -- assoc )
- [ dup ] H{ } map>assoc ;
+M: set intersects?
+ sequence/tester any? ;
+
+M: set subset?
+ sequence/tester all? ;
+
+M: set set=
+ 2dup subset? [ swap subset? ] [ 2drop f ] if ;
-: (all-unique?) ( elt hash -- ? )
- 2dup key? [ 2drop f ] [ conjoin t ] if ;
+M: set fast-set ;
-: all-unique? ( seq -- ? )
- dup length <hashtable> [ (all-unique?) ] curry all? ;
+M: set duplicates drop f ;
+
+M: set all-unique? drop t ;
<PRIVATE
-: tester ( seq -- quot ) unique [ key? ] curry ; inline
+: (pruned) ( elt hash vec -- )
+ 3dup drop in? [ 3drop ] [
+ [ drop adjoin ] [ nip push ] 3bi
+ ] if ; inline
+
+: pruned ( seq -- newseq )
+ [ f fast-set ] [ length <vector> ] bi
+ [ [ (pruned) ] 2curry each ] keep ;
PRIVATE>
-: intersect ( seq1 seq2 -- newseq )
- tester filter ;
+! Sequences are sets
+INSTANCE: sequence set
-: intersects? ( seq1 seq2 -- ? )
- tester any? ;
+M: sequence in?
+ member? ; inline
-: diff ( seq1 seq2 -- newseq )
- tester [ not ] compose filter ;
+M: sequence adjoin
+ [ delete ] [ push ] 2bi ;
-: union ( seq1 seq2 -- newseq )
- append prune ;
+M: sequence delete
+ remove! drop ; inline
-: subset? ( seq1 seq2 -- ? )
- tester all? ;
+M: sequence set-like
+ [ members ] dip like ;
-: set= ( seq1 seq2 -- ? )
- [ unique ] bi@ = ;
+M: sequence members
+ [ pruned ] keep like ;
+
+M: sequence all-unique?
+ dup pruned sequence= ;
+
+: combine ( sets -- set )
+ f [ union ] reduce ;
+
+: gather ( seq quot -- newseq )
+ map concat members ; inline
+
+: adjoin-at ( value key assoc -- )
+ [ [ f fast-set ] unless* [ adjoin ] keep ] change-at ;
+
+! Temporarily for compatibility
+
+ALIAS: prune members
+: unique ( seq -- assoc )
+ [ dup ] H{ } map>assoc ;
+: conjoin ( elt assoc -- )
+ dupd set-at ;
+: conjoin-at ( value key assoc -- )
+ [ dupd ?set-at ] change-at ;