Hi all,
I have seen (on this ML and elsewhere) many proposals how should REBOL
blocks behave. (recently e.g. BrianH's rage-related proposal in R3 blog
discussion). I think, that it may be interesting to find the behaviour
that will be "the most popular" between REBOL users.
===How to specify the behaviour?
Variants are:
*Specify results of some expressions
*Write a REBOL prototype code implementing the behaviour you prefer
*Other way?
===Results of expressions
Problems:
*This kind of specification may be "incomplete" - not specifying all
properties
*Such a specification may even be "unimplementable", if we choose
properties that contradict each other
===REBOL prototype implementation
I prefer REBOL prototype implementation as a way how to specify the
behaviour, since it:
*It is easily translatable to other programming languages
*Instantly proves the "implementability" of the behaviour
*Allows us to estimate the "cost" of the implementation (estimate the
memory requirements and the speed)
*Completely and unambiguously specifies the behaviour
*Allows everyone to devise his behaviour tests and check the results
(see some tests below e.g.)
===My contributions
I wrote two implementation prototypes in REBOL, one of them is my
"past-tail/past-head tolerant" implementation called UNL, which is
optimized for easy any-based indexing (not just one-based, or
zero-based, see below).
My second prototype called IMP is a "position-preserving" (as opposed to
index-preserving) implementation. I was inspired by BrianH's
contribution to the R3 blog range discussion when writing it. It is
interesting, since it shows, that even blocks can "preserve position".
My current favourite is the UNL implementation (see the reasons below).
Rebol [
Author: "Ladislav Mecir"
Title: "unl-block"
Purpose: {
past-tail/past-head tolerant block implementation prototype
with zero-based indexing
Advantages:
- the same speed as the current implementation has
- the same memory consumption as for the current implementation
- past-tail/past-head handling allows for any-base indexing
- strings can work the same way
Disadvantages:
- small backward incompatibility
}
]
unl-min-index: -536870912
unl-max-index: 2147483647 + unl-min-index
unl-add: func [
a [integer!]
b [integer!]
] [
any [
all [
unl-max-index - a <= b
unl-max-index
]
all [
unl-min-index - a >= b
unl-min-index
]
a + b
]
]
unl-block: make object! [
aux: none
index: none
]
unl-index?: func [
u-blk [object!]
] [
u-blk/index
]
unl-skip: func [
u-blk [object!]
offset [integer!]
] [
make u-blk [index: unl-add u-blk/index offset]
]
unl-head: func [
u-blk [object!]
] [
make u-blk [index: 0]
]
unl-head?: func [
u-blk [object!]
] [
u-blk/index = 0
]
unl-past-head?: func [
u-blk [object!]
] [
u-blk/index < 0
]
unl-aux: make object! [
data: none
]
unl-make-empty: func [] [
make unl-block [
aux: make unl-aux [data: copy []]
index: 0
]
]
unl-pick: func [
u-blk [object!]
offset [integer!]
] [
pick u-blk/aux/data 1 + unl-add u-blk/index offset
]
unl-tail: func [
u-blk [object!]
] [
make u-blk [index: length? u-blk/aux/data]
]
unl-tail?: func [
u-blk [object!]
] [
u-blk/index = length? u-blk/aux/data
]
unl-empty?: func [
u-blk [object!]
] [
u-blk/index >= length? u-blk/aux/data
]
unl-past-tail?: func [
u-blk [object!]
] [
u-blk/index > length? u-blk/aux/data
]
unl-length?: func [
u-blk [object!]
] [
max 0 (length? u-blk/aux/data) - max 0 u-blk/index
]
unl-insert-only: func [
[catch]
u-blk [object!]
value [any-type!]
] [
if unl-past-head? u-blk [
throw make error! "past head!"
]
if unl-past-tail? u-blk [
throw make error! "past tail!"
]
if unl-max-index <= length? u-blk/aux/data [
throw make error! "series overflow!"
]
insert/only skip u-blk/aux/data u-blk/index get/any 'value
make u-blk [index: u-blk/index + 1]
]
unl-remove: func [
u-blk [object!]
] [
if any [
unl-tail? u-blk
unl-past-tail? u-blk
unl-past-head? u-blk
] [return u-blk]
remove at u-blk/aux/data u-blk/index + 1
u-blk
]
unl-same?: func [
a [object!]
b [object!]
] [
found? all [
a/index = b/index
same? a/aux/data b/aux/data
]
]
comment [
; one-base indexing made easy:
; make an empty u-blk
u-blk: unl-make-empty
; insert 1
unl-insert-only u-blk 1
; skip "past head"
u-blk1: unl-skip u-blk -1
; index check
unl-index? u-blk1 ; == -1
; now we can use one-based indexing
unl-pick u-blk1 1 ; == 1
]
Rebol [
Author: "Ladislav Mecir"
Date: 14-Feb-2007/9:11:06+1:00
Title: "imp-block"
Purpose: {
A "position keeping" block implementation variants
with zero-based indexing
Advantages:
- improved LIST! compatibility
- may look more "natural" to some users
- does not "generate" past-tail positions
Disadvantages:
- speed - one more indirection level
- memory consumption: additional 96 bits per element
- small backward incompatibility
- impractical for strings
}
]
imp-element: make object! [
value: none
reference: none
]
imp-reference: make object! [
index: none
next: none
]
imp-aux: make object! [
start: none
tail: none
]
imp-block: make object! [
aux: none
reference: none
]
handle-removed: func [
reference [object!]
] [
if reference/next [
handle-removed reference/next
reference/index: reference/next/index
reference/next: none
]
]
imp-tail?: imp-empty?: func [
i-block [object!]
] [
handle-removed i-block/reference
i-block/reference/index = i-block/aux/tail
]
imp-head?: func [
i-block [object!]
] [
handle-removed i-block/reference
i-block/reference/index = 0
]
imp-tail: func [
i-block [object!]
/local tail+1
] [
tail+1: i-block/aux/tail + 1
make i-block [reference: i-block/aux/start/:tail+1/reference]
]
imp-head: func [
i-block [object!]
] [
make i-block [reference: i-block/aux/start/1/reference]
]
imp-index?: func [
i-block [object!]
] [
handle-removed i-block/reference
i-block/reference/index
]
imp-length?: func [
i-block [object!]
] [
i-block/aux/tail - imp-index? i-block
]
imp-skip: func [
i-block [object!]
offset [integer!]
/local index
] [
index: imp-index? i-block
if offset < negate index [return imp-head i-block]
if i-block/aux/tail - index <= offset [return imp-tail i-block]
index: index + offset + 1
make i-block [reference: i-block/aux/start/:index/reference]
]
imp-pick: func [
i-block [object!]
index [integer!]
/local base
] [
base: imp-index? i-block
if index < negate base [return none]
if i-block/aux/tail - base <= index [return none]
base: pick i-block/aux/start index + base + 1
return get/any in base 'value
]
imp-remove: func [
{just the "basic" remove - without refinements}
i-block [object!]
/local index start index+1 i-tail new-reference
] [
if imp-empty? i-block [return i-block]
index: imp-index? i-block
index+1: index + 1
i-tail: i-block/aux/tail
start: i-block/aux/start
; move the elements
repeat i i-tail - index [
new-reference: pick start index+1 + i
new-reference/reference/index: index + i - 1
poke start index + i new-reference
]
remove back tail start
; shorten the i-block
i-block/aux/tail: i-tail - 1
; mark the original reference as "removed"
new-reference: start/:index+1/reference
i-block/reference/next: new-reference
i-block/reference: new-reference
i-block
]
imp-insert-only: func [
{just the "basic" insert/only - no other refinements}
i-block [object!]
value [any-type!]
/local index i-tail start new-reference index+1
] [
index: imp-index? i-block
index+1: index + 1
i-tail: i-block/aux/tail
start: i-block/aux/start
; enlarge the i-block
insert tail start none
; move the elements
repeat i i-tail - index + 1 [
new-reference: pick start i-tail + 2 - i
new-reference/reference/index: i-tail + 2 - i
poke start i-tail + 3 - i new-reference
]
i-block/aux/tail: i-tail + 1
; create a new element
start/:index+1: make imp-element [reference: make imp-reference []]
start/:index+1/reference/index: index
error? set/any in start/:index+1 'value get/any 'value
i-block
]
imp-same?: func [
i-block1 [object!]
i-block2 [object!]
] [
found? all [
same? i-block1/aux i-block2/aux
equal? imp-index? i-block1 imp-index? i-block2
]
]
imp-make-empty: func [] [
make imp-block [
aux: make imp-aux [
start: reduce [make imp-element []]
tail: 0
]
reference: make imp-reference [index: 0]
aux/start/1/reference: reference
]
]
imp-to-block: func [
i-block [object!]
/local result start
] [
start: skip i-block/aux/start imp-index? i-block
result: make block! 0
repeat i imp-length? i-block [
insert/only tail result get in start/:i 'value
]
result
]
imp-mold: func [
i-block [object!]
] [
mold/all imp-to-block i-block
]
comment [
; behaviour comparisons
include %unl-block.r
; empty block creation
i-blk: imp-make-empty
u-blk: unl-make-empty
blk: make block! 0
; tail? test #1
imp-tail? i-blk ; == true
unl-tail? u-blk ; == true
tail? blk ; == true
; insert 1
imp-insert-only i-blk 1
unl-insert-only u-blk 1
insert/only blk 1
; insert tail 2
imp-insert-only imp-tail i-blk 2
unl-insert-only unl-tail u-blk 2
insert/only tail blk 2
; position change after insert test #1, see the differences
imp-tail? i-blk ; == true - i-blk "keeps the original position"
unl-tail? u-blk ; == false - u-blk "keeps index"
tail? blk ; == false - blk "keeps index"
; jump to tail
i-blk: imp-tail i-blk
u-blk: unl-tail u-blk
blk: tail blk
; big positive skip test #1
imp-head? imp-skip i-blk 2147483647 ; == false - correct!
unl-head? unl-skip u-blk 2147483647 ; == false - correct!
head? skip blk 2147483647 ; == true - bug!
; index? test #1
imp-index? i-blk ; == 2 - zero-based
unl-index? u-blk ; == 2 - zero-based
index? blk ; == 3 - one-based
; pre-tail position
i-blk2: imp-skip i-blk -1
u-blk2: unl-skip u-blk -1
blk2: skip blk -1
; index? test #2
imp-index? i-blk2 ; == 1 - zero-based
unl-index? u-blk2 ; == 1 - zero-based
index? blk2 ; == 2 - one-based
; pick test #1
imp-pick i-blk2 0 ; == 2
unl-pick u-blk2 0 ; == 2
pick blk2 1 ; == 2
; remove the first element
imp-remove imp-head i-blk
unl-remove unl-head u-blk
remove head blk
; pick test #2
imp-pick i-blk2 0 ; == 2 - i-blk2 keeps position
unl-pick u-blk2 0 ; == none - u-blk2 keeps index
pick blk2 1 ; == none - blk keeps index
; index? test #3
imp-index? i-blk2 ; == 0 - i-blk2 keeps position
unl-index? u-blk2 ; == 1 - u-blk2 keeps index
index? blk2 ; == 2 - blk keeps index
; tail? test #2
imp-tail? i-blk2 ; == false - keeps position
unl-tail? u-blk2 ; == true - keeps index
tail? blk2 ; == true - keeps index
; index? test #4
imp-index? i-blk ; == 1 - keeps position
unl-index? u-blk ; == 2 - keeps index
index? blk ; == 2 - suspicious result
; tail? test #3
imp-tail? i-blk ; == true - really the tail position
unl-tail? u-blk ; == false - (actually past-tail; tail? and empty?
are *not* identical)
tail? blk ; == true - suspicious result, see below
; same? test #1
imp-same? i-blk imp-tail i-blk ; == true - consistent with the above
unl-same? u-blk unl-tail u-blk ; == false - consistent with the above
same? blk tail blk ; == false - inconsistent with the above
; insert again
imp-insert-only imp-head i-blk 1
unl-insert-only unl-head u-blk 1
insert/only head blk 1
; index? test #5
imp-index? i-blk2 ; == 1 - keeps position
unl-index? u-blk2 ; == 1 - keeps index
index? blk2 ; == 2 - keeps index
; pick test #3
imp-pick i-blk2 0 ; == 2 - keeps position
unl-pick u-blk2 0 ; == 2 - keeps index
pick blk2 1 ; == inconsistent with index? test #3 & #4
; index? test #6
imp-index? i-blk ; == 2 - keeps position
unl-index? u-blk ; == 2 - keeps index
index? blk ; == 3 - inconsistent with index? test #3 & #4
]
- Ladislav
--
To unsubscribe from the list, just send an email to
lists at rebol.com with unsubscribe as the subject.
