unrolled-list
Unrolled lists

Next:

<unrolled-list> ( -- list )

Vocabulary
unrolled-lists

Class description
The class of unrolled lists.

All nodes in an unrolled list contain an array of 32 items. Nodes point to the previous node and next node, or f if they do not exist.

front	The front node of the list or f.
front-pos	The position of the front element of the list in front.
back	The back node of the list or f.
back-pos	The position of the back element of the list in back.

It is not recommended to modify any of these slots manually. Using the deque protocol provides safer operations.

Definition

USING: math unrolled-lists.private ;

IN: unrolled-lists

TUPLE: unrolled-list
    { front ?node initial: f } { front-pos fixnum initial: 0 }
    { back ?node initial: f } { back-pos fixnum initial: 0 } ;

Methods

USING: accessors deques kernel unrolled-lists ;

M: unrolled-list clear-deque
    f >>front 0 >>front-pos f >>back unroll-factor >>back-pos
    drop ;


USING: accessors deques kernel unrolled-lists ;

M: unrolled-list deque-empty?
    dup [ front>> ] [ back>> ] bi dup [
        eq?
        [ [ front-pos>> ] [ back-pos>> ] bi eq? ] [ drop f ] if
    ] [ 3drop t ] if ;


USING: accessors deques kernel math sequences.private
unrolled-lists ;

M: unrolled-list peek-back*
    dup back>>
    [ [ back-pos>> 1 - ] dip data>> nth-unsafe t ] [ drop f f ]
    if* ;


USING: accessors deques kernel sequences.private unrolled-lists
;

M: unrolled-list peek-front*
    dup front>>
    [ [ front-pos>> ] dip data>> nth-unsafe t ] [ drop f f ] if*
    ;


USING: accessors deques kernel unrolled-lists
unrolled-lists.private ;

M: unrolled-list pop-back*
    dup back>> [ empty-unrolled-list ] unless*
    over back-pos>> 1 eq?
    [ pop-back/new ] [ pop-back/existing ] if ;


USING: accessors deques kernel math unrolled-lists
unrolled-lists.private ;

M: unrolled-list pop-front*
    dup front>> [ empty-unrolled-list ] unless*
    over front-pos>> unroll-factor 1 - eq?
    [ pop-front/new ] [ pop-front/existing ] if ;


USING: accessors deques kernel unrolled-lists
unrolled-lists.private ;

M: unrolled-list push-back*
    dup [ back>> ] [ back-pos>> unroll-factor eq? not ] bi
    [ drop ] [ and ] 2bi
    [ push-back/existing ] [ drop push-back/new ] if f ;


USING: accessors deques kernel unrolled-lists
unrolled-lists.private ;

M: unrolled-list push-front*
    dup [ front>> ] [ front-pos>> 0 eq? not ] bi
    [ drop ] [ and ] 2bi
    [ push-front/existing ] [ drop push-front/new ] if f ;