RedBlackTree with Array Store

Thu Jan 13 21:25:17 PST 2011

Hi,

I've noticed that, just as you can have a heap with an array-backed store, you
can also have a binary search tree with the same store (although structured
differently; see attachment for a bare-bones unsorted binary tree
implementation -- which I have NOT yet tested, but which I can test if it will
be used). The improvement will be in data locality, and while it may seem to
use a bit more space than a link-based tree, I think it's worth it to let the
RedBlackTree class use a custom store, such as any store that has
getLeft/getRight/setLeft/setRight methods, and that uses opaque pointers.

How does this idea sound?
Thank you!
begin 644 arraycontainer.d
M<')I=F%T92!I;7!O<G0@<W1D+F%L9V]R:71H;2`Z(&UA>"P@<W=A<#L-"G!R
M:79A=&4@:6UP;W)T('-T9"YC;VYT86EN97([#0H-"G!U8FQI8R!S=')U8W0@
M3F]D92A4*0T*>PT*"7!U8FQI8R!4('9A;'5E.PT*"7!R:79A=&4@<'1R9&EF
M9E]T('-E;&8[#0H)<')I=F%T92!P=')D:69F7W0@<&%R96YT.PT*"7!R:79A
M=&4@<'1R9&EF9E]T(&QE9G0[#0H)<')I=F%T92!P=')D:69F7W0@<FEG:'0[
M#0I]#0H-"G!U8FQI8R!C;&%S<R!!<G)A>4)I;F%R>51R964H5"D-"GL-"@EP
M<FEV871E($)I;F%R>4AE87`A*'!T<F1I9F9?=%M=*2!O<&5N26YD:6-E<SL-
M"@EP<FEV871E($YO9&4A*%0I6UT@:71E;7,[#0H)<')I=F%T92!P=')D:69F
M7W0@:5)O;W0@/2`M,3L-"@T*"6EN=F%R:6%N="@I#0H)>PT*"0DO+V9O<F5A
M8V@@*&D[('1H:7,N;W!E;DEN9&EC97,I('L at 87-S97)T*'1H:7,N:71E;7-;
M:5TN<V5L9B`\(#`L(")/<&5N('-L;W0@:6YD97@@=V%S(&YO;FYE9V%T:79E
M+B(I.R!]#0H)"7-I>F5?="!C;W5N="`](#`[#0H)"69O<F5A8V@@*&DL(&ET
M96T[('1H:7,N:71E;7,I('L@:68@*&ET96TN<V5L9B`^/2`P*2![(&%S<V5R
M="AI=&5M+G-E;&8@/3T@:2P@(DET96T@:6YD97@@9&ED(&YO="!P;VEN="!T
M;R!I=&5M+B(I.R!C;W5N="LK.R!]('T-"@D)87-S97)T*&-O=6YT(#T]('1H
M:7,N:71E;7,N;&5N9W1H("T@=&AI<RYO<&5N26YD:6-E<RYL96YG=&@L(")4
M:&4@:71E;2!C;W5N="!W87,@:6YV86QI9"XB*3L-"@E]#0H-"@EP<FEV871E
M('9O:60@=F%L:61A=&4H:6X at 8V]N<W0H3F]D92$H5"DI*B!N;V1E*0T*"7L-
M"@D):68@*&YO9&4@(3T@;G5L;"D-"@D)>PT*"0D)87-S97)T*"9T:&ES+FET
M96US6VYO9&4N<V5L9ET@/3T@;F]D92D[#0H)"0EA<W-E<G0H;F]D92YL969T
M(#P@,"!\?"!T:&ES+F=E=$QE9G0H;F]D92DN<&%R96YT(#T](&YO9&4N<V5L
M9BD[#0H)"0EA<W-E<G0H;F]D92YR:6=H="`\(#`@?'P@=&AI<RYG9712:6=H
M="AN;V1E*2YP87)E;G0@/3T@;F]D92YS96QF*3L-"@D)"6%S<V5R="AN;V1E
M+G!A<F5N="`\(#`@?'P@*"AT:&ES+F=E=%!A<F5N="AN;V1E*2YL969T(#T]
M(&YO9&4N<V5L9BD@?"`H=&AI<RYG971087)E;G0H;F]D92DN<FEG:'0@/3T@
M;F]D92YS96QF*2DI.PT*"0E]#0H)?0T*#0H)<'5B;&EC($!P<F]P97)T>2!C
M;VYS="A.;V1E(2A4*2DJ(')O;W0H*2![(')E='5R;B!T:&ES+FE2;V]T(#X]
M(#`@/R`F=&AI<RYI=&5M<UMT:&ES+FE2;V]T72`Z(&YU;&P[('T-"@EP=6)L
M:6, at 8V]N<W0H3F]D92$H5"DI*B!G971087)E;G0H8V]N<W0H3F]D92$H5"DI
M*B!N;V1E*2!I;B![('1H:7,N=F%L:61A=&4H;F]D92D[('T@;W5T("AP*2![
M('1H:7,N=F%L:61A=&4H<"D[('T at 8F]D>2![(')E='5R;B!N;V1E+G!A<F5N
M="`^/2`P(#\@;G5L;"`Z("9T:&ES+FET96US6VYO9&4N<&%R96YT73L@?0T*
M"7!U8FQI8R!C;VYS="A.;V1E(2A4*2DJ(&=E=$QE9G0H8V]N<W0H3F]D92$H
M5"DI*B!N;V1E*2!I;B![('1H:7,N=F%L:61A=&4H;F]D92D[('T@;W5T("AP
M*2![('1H:7,N=F%L:61A=&4H<"D[('T at 8F]D>2![(')E='5R;B!N;V1E+FQE
M9G0@/CT@,"`_(&YU;&P at .B`F=&AI<RYI=&5M<UMN;V1E+FQE9G1=.R!]#0H)
M<'5B;&EC(&-O;G-T*$YO9&4A*%0I*2H at 9V5T4FEG:'0H8V]N<W0H3F]D92$H
M5"DI*B!N;V1E*2!I;B![('1H:7,N=F%L:61A=&4H;F]D92D[('T@;W5T("AP
M*2![('1H:7,N=F%L:61A=&4H<"D[('T at 8F]D>2![(')E='5R;B!N;V1E+G)I
M9VAT(#X](#`@/R!N=6QL(#H@)G1H:7,N:71E;7-;;F]D92YR:6=H=%T[('T-
M"@T*"7!U8FQI8R!V;VED('-E=$QE9G0H8V]N<W0H3F]D92$H5"DI*B!N;V1E
M+"!I;B!C;VYS="A.;V1E(2A4*2DJ(&QE9G0I#0H):6X@>R!A<W-E<G0H;F]D
M92`A/2!N=6QL*3L@=&AI<RYV86QI9&%T92AN;V1E*3L@=&AI<RYV86QI9&%T
M92AL969T*3L@?0T*"6)O9'D@>R!T:&ES+FET96US6VYO9&4N<V5L9ETN;&5F
M="`](&QE9G0@(3T@;G5L;"`_(&QE9G0N<V5L9B`Z("TQ.R!I9B`H;&5F="`A
M/2!N=6QL*2![('1H:7,N:71E;7-;;&5F="YS96QF72YP87)E;G0@/2!N;V1E
M+G-E;&8[('T@?0T*#0H)<'5B;&EC('9O:60@<V5T4FEG:'0H8V]N<W0H3F]D
M92$H5"DI*B!N;V1E+"!I;B!C;VYS="A.;V1E(2A4*2DJ(')I9VAT*0T*"6EN
M('L at 87-S97)T*&YO9&4@(3T@;G5L;"D[('1H:7,N=F%L:61A=&4H;F]D92D[
M('1H:7,N=F%L:61A=&4H<FEG:'0I.R!]#0H)8F]D>2![('1H:7,N:71E;7-;
M;F]D92YS96QF72YR:6=H="`](')I9VAT("$](&YU;&P@/R!R:6=H="YS96QF
M(#H at +3$[(&EF("AR:6=H="`A/2!N=6QL*2![('1H:7,N:71E;7-;<FEG:'0N
M<V5L9ETN<&%R96YT(#T@;F]D92YS96QF.R!]('T-"@T*"7!U8FQI8R!C;VYS
M="A.;V1E(2A4*2DJ(&%L;&]C3F]D92 at I#0H);W5T("AP*2![('1H:7,N=F%L
M:61A=&4H<"D[('T-"@EB;V1Y#0H)>PT*"0ET:&ES+G)E<V5R=F4H=&AI<RYI
M=&5M<RYL96YG=&@@*R`Q*3L-"@D)875T;R!I(#T@=&AI<RYO<&5N26YD:6-E
M<RYF<F]N=#L-"@D)=&AI<RYI=&5M<UMI72`]($YO9&4A*%0I*%0N:6YI="P@
M:2P at +3$L("TQ+"`M,2D[#0H)"71H:7,N;W!E;DEN9&EC97,N<F5M;W9E1G)O
M;G0H*3L-"@D):68@*'1H:7,N:5)O;W0@/"`P*2![('1H:7,N:5)O;W0@/2!I
M.R!]#0H)"7)E='5R;B`F=&AI<RYI=&5M<UMI73L-"@E]#0H-"@EP=6)L:6,@
M=F]I9"!R97-E<G9E*'-I>F5?="!C87!A8VET>2D-"@E[#0H)"6EF("AT:&ES
M+F]P96Y);F1I8V5S+FQE;F=T:"`\(&-A<&%C:71Y*0T*"0E[#0H)"0EA=71O
M('!R979,96X@/2!T:&ES+FET96US+FQE;F=T:#L-"@D)"71H:7,N:71E;7,N
M;&5N9W1H(#T@;6%X*&-A<&%C:71Y+"`R("H@=&AI<RYI=&5M<RYL96YG=&@I
M.PT*"0D)875T;R!I;F1I8V5S(#T@;F5W('!T<F1I9F9?=%MT:&ES+FET96US
M+FQE;F=T:%T[#0H)"0ES:7IE7W0@:2`](#`[#0H)"0EW:&EL92`H(71H:7,N
M;W!E;DEN9&EC97,N96UP='DI('L@:6YD:6-E<UMI*RM=(#T@=&AI<RYO<&5N
M26YD:6-E<RYF<F]N=#L@=&AI<RYO<&5N26YD:6-E<RYR96UO=F5&<F]N="@I
M.R!]#0H)"0EF;W)E86-H("AJ.R!P<F5V3&5N("XN('1H:7,N:71E;7,N;&5N
M9W1H*2![(&EN9&EC97-;:2LK72`](&H[('T-"@D)"71H:7,N;W!E;DEN9&EC
M97,N86-Q=6ER92AI;F1I8V5S+"!I*3L-"@D)?0T*"7T-"@T*"7!U8FQI8R!V
M;VED(&9R965.;V1E*&-O;G-T*$YO9&4A*%0I*2H@;F]D92D-"@EI;B![('1H
M:7,N=F%L:61A=&4H;F]D92D[('T-"@EB;V1Y#0H)>PT*"0EI9B`H;F]D92`A
M/2!N=6QL*0T*"0E[#0H)"0EA=71O('!->4YO9&4@/2`F=&AI<RYI=&5M<UMN
M;V1E+G-E;&9=.PT*"0D)=&AI<RYF<F5E3F]D92AT:&ES+F=E=$QE9G0H<$UY
M3F]D92DI.PT*"0D)<$UY3F]D92YL969T(#T at +3$[#0H)"0ET:&ES+F9R965.
M;V1E*'1H:7,N9V5T4FEG:'0H<$UY3F]D92DI.PT*"0D)<$UY3F]D92YR:6=H
M="`]("TQ.PT*"0D):68@*'!->4YO9&4N<&%R96YT(#X](#`@)B8@=&AI<RYI
M=&5M<UMP37E.;V1E+G!A<F5N=%TN;&5F="`]/2!P37E.;V1E+G-E;&8I('L@
M=&AI<RYI=&5M<UMP37E.;V1E+G!A<F5N=%TN;&5F="`]("TQ.R!]#0H)"0EI
M9B`H<$UY3F]D92YP87)E;G0@/CT@,"`F)B!T:&ES+FET96US6W!->4YO9&4N
M<&%R96YT72YR:6=H="`]/2!P37E.;V1E+G-E;&8I('L@=&AI<RYI=&5M<UMP
M37E.;V1E+G!A<F5N=%TN<FEG:'0@/2`M,3L@?0T*"0D)<$UY3F]D92YP87)E
M;G0@/2`M,3L-"@D)"71H:7,N;W!E;DEN9&EC97,N:6YS97)T*'!->4YO9&4N
M<V5L9BD[#0H)"0EP37E.;V1E+G-E;&8@/2`M,3L-"@D)"6EF("AT:&ES+FE2
M;V]T(#T]('!->4YO9&4N<V5L9BD@>R!T:&ES+FE2;V]T(#T at +3$[('T-"@D)
M?0T*"7T-"@T*"7!R:79A=&4@=F]I9"!S=V%P4VQO='-.;TYO=&EF>4AE87`H
M<'1R9&EF9E]T(&DL('!T<F1I9F9?="!J*0T*"7L-"@D)87-S97)T*&D@/CT@
M,"`F)B!J(#X](#`I.PT*"0ES=V%P*'1H:7,N:71E;7-;:5TL('1H:7,N:71E
M;7-;:ETI.PT*"0ES=V%P*'1H:7,N:71E;7-;:5TN<V5L9BP@=&AI<RYI=&5M
M<UMJ72YS96QF*3L-"@D):68@*'1H:7,N:71E;7-;:5TN;&5F="`^/2`P*2![
M('1H:7,N:71E;7-;=&AI<RYI=&5M<UMI72YL969T72YP87)E;G0@/2!J.R!]
M#0H)"6EF("AT:&ES+FET96US6VE=+G)I9VAT(#X](#`I('L@=&AI<RYI=&5M
M<UMT:&ES+FET96US6VE=+G)I9VAT72YP87)E;G0@/2!J.R!]#0H)"6EF("AT
M:&ES+FET96US6VI=+FQE9G0@/CT@,"D@>R!T:&ES+FET96US6W1H:7,N:71E
M;7-;:ETN;&5F=%TN<&%R96YT(#T@:3L@?0T*"0EI9B`H=&AI<RYI=&5M<UMJ
M72YR:6=H="`^/2`P*2![('1H:7,N:71E;7-;=&AI<RYI=&5M<UMJ72YR:6=H
M=%TN<&%R96YT(#T@:3L@?0T*"0EI9B`H=&AI<RYI4F]O="`]/2!I*2![('1H
M:7,N:5)O;W0@/2!J.R!]#0H)"65L<V4@:68@*'1H:7,N:5)O;W0@/3T@:BD@
M>R!T:&ES+FE2;V]T(#T@:3L@?0T*"7T-"@T*"7!U8FQI8R!V;VED('1R:6TH
M*0T*"7L-"@D)<VEZ95]T(&QE;E9A;&ED(#T@=&AI<RYI=&5M<RYL96YG=&@[
M#0H)"69O<F5A8VA?<F5V97)S92AI+"!R968@:71E;3L@=&AI<RYI=&5M<RD-
M"@D)>PT*"0D):68@*'1H:7,N;W!E;DEN9&EC97,N96UP='DI('L at 8G)E86L[
M('T-"@D)"65L<V4-"@D)"7L-"@D)"0EL96Y686QI9"`](&D[#0H)"0D)875T
M;R!O<&5N26YD97@@/2!T:&ES+F]P96Y);F1I8V5S+F9R;VYT.PT*"0D)"71H
M:7,N;W!E;DEN9&EC97,N<F5M;W9E1G)O;G0H*3L-"@D)"0ET:&ES+G-W87!3
M;&]T<TYO3F]T:69Y2&5A<"AI+"!O<&5N26YD97 at I.PT*"0D)"71H:7,N;W!E
M;DEN9&EC97,N:6YS97)T*&DI.PT*"0D)?0T*"0E]#0H)"71H:7,N:71E;7,N
M;&5N9W1H(#T@;&5N5F%L:60[#0H)?0T*#0H)<'5B;&EC(&EN="!O<$%P<&QY
M*&EN="!D96QE9V%T92AR968 at 8V]N<W0H3F]D92$H5"DI*BD at 9&<I#0H)>PT*
M"0EI;G0@<F5S=6QT(#T@,#L-"@D)875T;R!S=&%C:R`](&YE=R!.;V1E(2A4
M*2I;,%T[#0H)"6EF("AT:&ES+G)O;W0@(3T@;G5L;"D-"@D)>PT*"0D)<W1A
M8VL@?CT@=&AI<RYI4F]O="`^/2`P(#\@)G1H:7,N:71E;7-;=&AI<RYI4F]O
M=%T at .B!N=6QL.PT*"0D)=VAI;&4@*'-T86-K+FQE;F=T:"`^(#`I#0H)"0E[
M#0H)"0D)875T;R!N;V1E(#T@<W1A8VM;)"`M(#%=.PT*"0D)"7-T86-K+FQE
M;F=T:"`M/2`Q.PT*"0D)"69O<B`H875T;R!T96UP(#T@=&AI<RYG9712:6=H
M="AN;V1E*3L@=&5M<"`A/2!N=6QL.R!T96UP(#T@=&AI<RYG971,969T*'1E
M;7`I*0T*"0D)"7L-"@D)"0D)<W1A8VL@?CT@=&5M<"`A/2!N=6QL(#\@)G1H
M:7,N:71E;7-;=&5M<"YS96QF72`Z(&YU;&P[#0H)"0D)?0T*"0D)"7)E<W5L
M="`](&1G*&YO9&4I.PT*"0D)"6EF("AR97-U;'0I('L at 8G)E86L[('T-"@D)
M"7T-"@D)?0T*"0ER971U<FX@<F5S=6QT.PT*"7T-"GT-"@T*86QI87, at 07)R
M87E":6YA<GE4<F5E(2AI;G0I($EN=%1R964[("\O2G5S="!F;W(@=&5S=&EN
!9P``
`
end