5ANEWFRAMEWORKFORTABULARCOMPOSITION5-21representationofatablemustbeatextualdescriptionofthetable.ThisrepresentationiseditablebytheTiogatexteditor.Whilethisisanadvantagefortestingtheprototype,itisexpectedthataninteractiveuserinterfacewillbebuilttopermitmosteditingactionswithoutresortingtoeditingthetextualrepresentationdirectly.Webelieve,however,thatthetextualdescriptionisusefulfordebugging,fordocumentinterchange,andforpossiblyfinetuningtablestructures.AtableisrepresentedasasubtreeofnodesinaTiogadocumenthierarchy.TherootnodeofthetablesubtreehasanArtworkClassproperty(describedinChapter3)ofTabletodistinguishthesubtreeasbeingatableobject(asdistinctfromtextorillustrations).ThisTablepropertyisrecognizedbythetableformattingprototypewhichinterpretsthecontentsofthesubtreeasacollectionoftableentries.Thetableentriesthemselvesmaycontainanobjectofanydocumentobjectclasssincetheobjectlayoutandrenderingproceduresunderstandthecontentoftheobject.Thisobject-orienteddesignpermitsarbitraryrecursionwithindocumentcontentatanytime.ThetablerepresentationisconvertedintotheinternaldatastructurewheneveratableiseditedinaWYSIWYGfashionorformatted.Aftermanipulatingtheinternaldatastructure(perhapschangingthetabletopologyorthecontentofsometableentries)theinternaldatastructureisconvertedbackintoaTiogadocumentsubtree.Thenewsubtreeissplicedintotheoriginaldocumenttoreplacetheprevioustablerepresentation.Onlytopologicalinformationisrepresentedinthetabledescription.Tableentriesaredescribedbythegridcoordinatesthattheyoccupy.Typographicrulesaredescribedbythegridlinesalongwhichtheyrun.ThetablepreviouslyshownasFigure5-6hasbeenannotatedwithgridcoordinatevaluesinFigure5-12.Horizontalandverticalgridlinesareeachnumberedbeginningat0andincrementingforeachsuccessivegridline.Acolumnorrowiscontainedwithintwogridlines(notnecessarilytwoconsecutivegridlines).Thusthecolumncontainingtheheading``SpannedoverFourColumns''iscontainedwithinverticalgridlines1and5.Twotypographicrulesareshownalongverticalgridline1andalonghorizontalgridline3.ThetableinFigure5-12willbeusedbothtoillustratetheexternaltablerepresentation(inFigure5-13)andtheinternaldatastructure(inFigure5-15).sfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^ g ):"%!&+ 4q69[>z\ g ) !$[),D27:,;>5Z g^7 ! "p)S,/ 7 :AaDXb gV[!@&,35;E>V/ g )$!1'=.E14|9 BgS gQ }-& 023u6%<?Q g} N\ B"F#)x+0K2O38Z@ L gUxb y&D)7~+LL, rL:J` g _c~ J`J`!rJ`'C)H 14u:A@= E g %W*4 14s:= ?EC g ?Pg!%,)B. 6:@`BA gxU@"&7)-26A= ?d g "(,S7<=2 g-^}'3-/2+:,6 !#+G.17;D7 g?U  "t#x77$r7+^1(3G ;5 g pIc#)07:>Ex3 g@&8%}(V.p28:BB1c g6$f'+T1 28];>/0 g!%W)m,* F %R' /148 Bd) gM!&$ -Z04e; ' gp:#R'2+04;8];? % g"*f. 1 9>@#a g S"a%),0W8A?ACR!/ g b $(,\.84*6I9;LB gw "% .2'7;> g xQ%<(-46>5 g2> $~ -14_9> Ce g] $"'c)-G1^3b8<`?A3 gIM "<&S 138=;@} g!$^TVm$5ANEWFRAMEWORKFORTABULARCOMPOSITION5-22xxxxxxxxxxxxxxxxxxxxxxxx,N,]D`D-1N8D`D`5qN5q]D`D5N8D`D`>N>]D`D>qN8D`D`Thin!TBTD`8D`!TrD`DBWr!WrD`DBWD`8D`!ZBZD`8D`!ZrD`DThinVery WideVery WideEqual WidthUnequal WidthSpanned over Four ColumnsFirst Row01234012345xxxxxxxxxxxxxxxxxxxxxxxxSecond Row5N]D`DQN8D`D`!]B]D`8D`!]rD`DB]BN8D`D`BQ]D`DBNr!NrD`DBND`8D`BQr!QrD`DBQD`8D`$1N$1]D`D$N8D`D`$q]$qN@ CC$Q]CC@@!TBTC@ C!T@CC@Figure5-12.ATABLEWITHAGRIDCOORDINATESYSTEMsuperimposed.ThetableisaduplicateofFigure5-6thatwillbeusedtoillustratetheexternalTiogadocumentstructureinFigure5-13,andtheinternalcornerstitcheddatastructureinFigure5-15.Atableisdescribedingeneraltermsbythecontentsoftherootnodeofitstablesubtree.InFigure5-13,thetableisformattedona6by6grid(for5rowsand5columns).Agridoverlay3-pointsthickinalightgraycolor(hue0,saturation0,brightness0.7)issuperimposedonthetabletomakethegridcoordinatesystemvisible.(Thisgridoverlaywouldnotappearonprintedtables,exceptforexpositorypurposes,althoughthegridoverlayservesasausefultargetforinteractivelymanipulatingthegridtopology.)Thedirectdescendantsofthetablerootnodewithinthedocumentdescribethetablestructureandtableentriesinmoredetail.Therearefourthingstodescribe:constraintsonthegridcoordinatelayout,boxescontainingtableentries,typographicrules,andbackgroundshadedareas.ConstraintsConstraintsarelinearinequalitiesorequalitiesgeneratedautomaticallybythetablelayoutprocedure.ThetableinFigure5-12hastwoauxiliaryconstraintssuppliedbythetabledesignertoforceequalcolumnwidths.Thefirstconstrainsthecolumnbetweengridlines1and2tohavethesamewidthasthecolumnbetween2and3.Thesecondconstraintforcesthecolumnbetweengridline0and1tohavethesamewidthasthecolumnbetween1and3(acolumnwhichspanstwogridlines).ThecompletedetailsoftheconstraintmechanismaredeferreduntilSection5.5.sfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFb g`;#'TVm$Rx$R0R69R?+R###>U###/U$U6U(sX 6X )<[5Rs4]4Z4W4T4Q^e$^e,^e5R^e=^eBB^ex$O0O69O?+O5O s4N########(nTVm$vK g|KKK KK "d *vK/ 9;?S@AI gn:9 &).k2c8>q@DmH gey"(*i. gE;#rB\ &+-0X68;?LCoE@ g}Q}"%)+3$568j:<=?BDh>w gG"$c*.02M6!9=A/268=?: g  $d'-25; =yCD7 gD :#*u-N06;j=n>C5 g f "o%H( 1+49> BgDx3{ g}%D '.J1#5:<?_1H g "m%8(-/6 ?AvDO/ g  &*0 9>, g u w) g r%0 f0 (* 2 9 C" g@V[ !3$(*0 369 g N $+/-41d5;B& g ^ Q&*M.-/24T6Y:G= APEg g@3* l"&P+ 3g86;A5 gGK9"&B*,/5qAh g  l#o *0z27 ?@| gGhW "%)*,0[5#8:@BF\ gR"'\ .`0Z3 :m= g # "(y*'-24g6;=f?C+ gr;#,TVm$5ANEWFRAMEWORKFORTABULARCOMPOSITION5-24TableBoxesTableentryboxesarespecifiedbytheirtop-leftandbottom-rightgridcoordinatepairs.Thecontentofthetableentryisspecifiedasthedescendantofthetableentrynode.Thisdescendantnodemaybeanydocumentobject.ThefirsttableentryinFigure5-13describesthespannedheading.Itscoordinatesarefrom(0,1)to(1,5),spanningfourgridmodules.ThealignmentattributesareTopBaseline(horizontalalignment)andCenter(verticalalignment).Theobjectwithinthistableentryisthetextobject,descendedfromthefirsttableentryandshownindentedinthefigure,containingthephrase``SpannedoverFourColumns''.Thenexttableentryalsospanscolumnentries,hasthesamealignmentattributes,andcontainsthetextobject``EqualWidth''.Tableentriesmayappearinthedocumentrepresentationinanyorderbecausethecoordinatespecificationsdeterminewhereinthetabletheywillappear.Thenestingofobjectsasdescendentsoftheircorrespondingtableentrydescriptionistheonlyrequirementforincludingcontentwithinatablerepresentation.TypographicRulesTypographicrulesrunalonggridlinesandhaveacertainspecifiedthickness.ThetworulesinFigure5-12areboth1-pointthick.Onerulerunsalongverticalgridline1,throughtheentiretable,andtheotherrulerunsalonghorizontalgridline3.Rulesmayrunalongportionsofagridline.Thus,averticalruleunderthespanningheadtoseparatetheequalandunequalpairsofcolumnsmightrunfromgridcoordinate(1,3)to(5,3).BackgroundsBackgroundareasarespecifiedbytherectangletheyshadeandthecoloroftheshading.Therectangleisspecifiedbytwopairsofcoordinatevaluesjustasfortableboxes.Thecolorspecificationcouldbeanyrecognizedcolornamingscheme,andintheprototype,colorisgivenashue,saturation,andbrightness.5.4.2CornerStitchingDataStructureTheinternaldatastructureforrepresentingtablesmustmeetseveralcriteria.Itmustrepresentthearrangementoftableentriesinboththehorizontalandverticaldirections.Itmustsupportrowandcolumnselectionsandaselectionsfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbw^ gr[]O &)\-K3$6f @X g "$'+0218:= F/V g@V )-303%6L>S &B)13:aAQ~ g %~Q~Q~.rQ~"r~$vQ~Q~%r*EQ~Q~+N2V59lAOK g h~2OKOK\ rOK+ 3 <>~?OKOK@rM g {$f),0569<J gm["'&*h/6v8z;SH g xQ$A', 48i<@,DwF g"c&.G 59@?BDP gRAI]O"$'/P :<?>? gh  '/m4W6[94=J@< gG #% .04 ?C: g q) &)606h;<8 gw4 g r0 U] x$(n,N/34:S. g $,!0&*/,06;?cB,g g(iF%(b-147< ?uC.*4 g 6h"%(-H3575:>C( g2lE$M(V*[038;aAE% g"b ~*%%+r%0~2%%4r8%%w! g r &)',3 6;^>AyE g@b ")k+/3 5 =9B=Ef g-F v ).{03 <=@m g "&(- /2 :> s gT!r:#&l /48<B2 g)@qJ %',1V3Z7<: A k g2  &)-?32 :=??CTVm$_5ANEWFRAMEWORKFORTABULARCOMPOSITION5-25hierarchywithincontainingrowsandcolumns.Itmustalsopermitfastalgorithmssuitableforinteractivetableeditingoperationsandforconversionto/fromanexternalform.ThedatastructurechosenforthetableformattingprototypewasthecornerstitchingdatastructureemployedbyOusterhout[Ousterhout,CornerStitching]forhisVLSIlayouttools.AnimplementationbyShand[Shand,CornerStitching]whichrunsintheCedarenvironmentwasmodifiedandextendedfortheprototype.Thecornerstitchingdatastructuretesselatestheplanewithrectangulartiles.Eachtileisconnectedtoitsneighborsbyfourcompass-pointlinksandeachtilereferencesitsassociateddata.Thecornerstitchingimplementationusesspecialbordertilessurroundingthetesselationtosimplifythealgorithms.Figure5-14illustratesaprototypicaltileandafragmentofthetesselationshowinghowseveraltilesareconnectedtogether.; "; "0 0 ; ;";C@ C:@CC@"; "0 @ CC"; CC@@"//@CC@"0C@ C0 ; CC@@0 @ CC,? @? @+ ,+ ,? 58 08 03 53 58 5707@CC@58C@ C08 03 @ CC08 CC@@0353C@ C02@CC@53 58 CC@@53 @ CC<3 03 0. <. <3 <202@CC@<3C@ C03 0. @ CC03 CC@@0.<.C@ C0-@CC@<. <3 CC@@<. @ CC<= 0= 08 <8 <= <<0<@CC@<=C@ C0= 08 @ CC0= CC@@08<8C@ C07@CC@<8 <= CC@@<8 @ CC :  < D@D` : D@D@!9-#9-D@D@!8D@D`11D@D`2-D@D@1 / D@D@1 D@D`NorthEastWestSouth039-139-D@D@038D@D`1718D@D`17D@D@1213D@D`12D@D@1-1.D@D`1-D@D@4847D@D@48D@D`034-134-D@D@033D@D`03/-13/-D@D@03.D@D`636536D@D`637-D@D@1M1MD@ D0@DD@2M2MD@ D1@DD@ :M :MD@ D 9@DD@!9M!9MD@ D!8@DD@139M139MD@ D138@DD@134M134MD@ D133@DD@13/M13/MD@ D13.@DD@537M537MD@ D536@DD@1818D@ D18M@DD@1313D@ D13M@DD@1.1.D@ D1.M@DD@4747D@ D47M@DD@;=;<D@D@;=D@D`;<;<D@ D;5\ g P %U)k. 6::< Z g XW#%(, 4<\?BiU\ g%#' t0)U\U\0 8< rU\CES) g )+t1S)S)1g6rS)@wP g $ #&-18(:= MK")m 03\7; D,K gc!&(+!. 9=@DI g 6o %"&6+a2 =AkGZ g? !g )^+c14 =CE( g 2 Z!2$u%,.1 9@:B gX# g@;#GTVm$zx####(####x####x########<$81-#################################################HTVm$v)G g|)G)Gd)G)G d)G$ v)G+.14q6:@SB-'\ gNY#'f+r.14/68}:A%p g%2A#|%v'+%/&25:@4 # gAf 5#d&),/&058R g!R;#rKK>B#'.e269 :s g X"o)B0#25]8?B g w!/$*,35'9=>A g?  (S.28A P gw!#' /5B85>  gk1"%}(,02 ;?D\ g0 )i+m.F2\9<> g}M!2$u'+-15j8?1 g ) "&)-11H68P?LAPTVm$5ANEWFRAMEWORKFORTABULARCOMPOSITION5-26prototypetohelpdistinguishbetweenadjacenttiles.Thusthetablegridcoordinatesareinfactmultipliedbyfourtocreatecornerstitchingcoordinatevalues.)ThecoordinatemappingisindicatedinFigure5-15,whichpresentsthecornerstitcheddatastructureforthetableinFigure5-6.P"C"CPP4!4!$$4664466!6!446!6A6A4!4!6N!N!66N1234567891011121314152200222C@ C2@CC@20@ CC2CC@@00@CC@0C@ C02CC@@0@ CC#:%:%8#8#:#:%:C@ C#:@CC@%:%8@ CC%:CC@@%8#8@CC@%8C@ C#8#:CC@@#8@ CC#2%2%0#0#2#2%2C@ C#2@CC@%2%0@ CC%2CC@@%0#0@CC@%0C@ C#0#2CC@@#0@ CC+:-:-8+8+:+:-:C@ C+:@CC@-:-8@ CC-:CC@@-8+8@CC@-8C@ C+8+:CC@@+8@ CC+2-2-0+0+2+2-2C@ C+2@CC@-2-0@ CC-2CC@@-0+0@CC@-0C@ C+0+2CC@@+0@ CC3:5:58383:3:5:C@ C3:@CC@5:58@ CC5:CC@@5838@CC@58C@ C383:CC@@38@ CC32525030323252C@ C32@CC@5250@ CC52CC@@5030@CC@50C@ C3032CC@@30@ CC;:=:=8;8;:;:=:C@ C;:@CC@=:=8@ CC=:CC@@=8;8@CC@=8C@ C;8;:CC@@;8@ CC;2=2=0;0;2;2=2C@ C;2@CC@=2=0@ CC=2CC@@=0;0@CC@=0C@ C;0;2CC@@;0@ CC3B=B=@3@3B3B=BC@ C3B@CC@=B=@@ CC=BCC@@=@3@@CC@=@C@ C3@3BCC@@3@@ CC016171819201234567891011121314150161721#B-B-@#@#B#B-BC@ C#B@CC@-B-@@ CC-BCC@@-@#@@CC@-@C@ C#@#BCC@@#@@ CC#J=J=H#H#J#J=JC@ C#J@CC@=J=H@ CC=JCC@@=H#H@CC@=HC@ C#H#JCC@@#H@ CC6!6C@ C6@CC@4!4C@ C4@CC@NCNC@ CN@CC@!JCJC@ C!J@CC@!HCHC@ C!H@CC@!BCBC@ C!B@CC@!@C@C@ C!@@CC@!:C:C@ C!:@CC@!8C8C@ C!8@CC@22C@ C2@CC@!2C2C@ C!2@CC@00C@ C0@CC@!0C0C@ C!0@CC@66C@ C6@CC@A6C6C@ CA6@CC@44C@ C4@CC@A4C4C@ CA4@CC@1 1C@ C0@CC@10@ CC1CC@@!1" 1C@ C!0@CC@"1"0@ CC!1CC@@#1$ 1C@ C#0@CC@$1$0@ CC#1CC@@%1& 1C@ C%0@CC@&1&0@ CC%1CC@@+1, 1C@ C+0@CC@,1,0@ CC+1CC@@-1. 1C@ C-0@CC@.1.0@ CC-1CC@@314 1C@ C30@CC@4140@ CC31CC@@516 1C@ C50@CC@6160@ CC51CC@@;1< 1C@ C;0@CC@<1<0@ CC;1CC@@=1> 1C@ C=0@CC@>1>0@ CC=1CC@@10@ CC}1CC@@0 0C@ C0t@CC@32@ CC}3CC@@2 2C@ C2t@CC@32@ CC}3CC@@2 2C@ C2t@CC@32@ CC}3CC@@2 2C@ C2t@CC@#3#2@ CC#}3CC@@#2$ 2C@ C#2t@CC@%3%2@ CC%}3CC@@%2& 2C@ C%2t@CC@+3+2@ CC+}3CC@@+2, 2C@ C+2t@CC@-3-2@ CC-}3CC@@-2. 2C@ C-2t@CC@3332@ CC3}3CC@@324 2C@ C32t@CC@5352@ CC5}3CC@@526 2C@ C52t@CC@;3;2@ CC;}3CC@@;2< 2C@ C;2t@CC@=3=2@ CC=}3CC@@=2> 2C@ C=2t@CC@54@ CC}5CC@@4 4C@ C4t@CC@!5!4@ CC!}5CC@@!4" 4C@ C!4t@CC@76@ CC}7CC@@6 6C@ C6t@CC@A7A6@ CCA}7CC@@A6B 6C@ CA6t@CC@#;#:@ CC#};CC@@#:$ :C@ C#:t@CC@%;%:@ CC%};CC@@%:& :C@ C%:t@CC@+;+:@ CC+};CC@@+:, :C@ C+:t@CC@-;-:@ CC-};CC@@-:. :C@ C-:t@CC@3;3:@ CC3};CC@@3:4 :C@ C3:t@CC@5;5:@ CC5};CC@@5:6 :C@ C5:t@CC@;;;:@ CC;};CC@@;:< :C@ C;:t@CC@=;=:@ CC=};CC@@=:> :C@ C=:t@CC@#C#B@ CC#}CCC@@#B$ BC@ C#Bt@CC@-C-B@ CC-}CCC@@-B. BC@ C-Bt@CC@3C3B@ CC3}CCC@@3B4 BC@ C3Bt@CC@=C=B@ CC=}CCC@@=B> BC@ C=Bt@CC@#K#J@ CC#}KCC@@#J$ JC@ C#Jt@CC@=K=J@ CC=}KCC@@=J> JC@ C=Jt@CC@ON@ CC}OCC@@N NC@ CNt@CC@!O!N@ CC!}OCC@@!N" NC@ C!Nt@CC@!3" 3C@ C!2@CC@"3"2@ CC!3CC@@5 5C@ C4@CC@54@ CC5CC@@A5B 5C@ CA4@CC@B5B4@ CCA5CC@@7 7C@ C6@CC@ 7 6@ CC7CC@@!7" 7C@ C!6@CC@"7"6@ CC!7CC@@!9" 9C@ C!8@CC@"9"8@ CC!9CC@@#9$ 9C@ C#8@CC@$9$8@ CC#9CC@@%9& 9C@ C%8@CC@&9&8@ CC%9CC@@+9, 9C@ C+8@CC@,9,8@ CC+9CC@@-9. 9C@ C-8@CC@.9.8@ CC-9CC@@394 9C@ C38@CC@4948@ CC39CC@@596 9C@ C58@CC@6968@ CC59CC@@;9< 9C@ C;8@CC@<9<8@ CC;9CC@@=9> 9C@ C=8@CC@>9>8@ CC=9CC@@!;" ;C@ C!:@CC@";":@ CC!;CC@@!A" AC@ C!@@CC@"A"@@ CC!ACC@@#A$ AC@ C#@@CC@$A$@@ CC#ACC@@-A. AC@ C-@@CC@.A.@@ CC-ACC@@3A4 AC@ C3@@CC@4A4@@ CC3ACC@@=A> AC@ C=@@CC@>A>@@ CC=ACC@@!C" CC@ C!B@CC@"C"B@ CC!CCC@@!I" IC@ C!H@CC@"I"H@ CC!ICC@@#I$ IC@ C#H@CC@$I$H@ CC#ICC@@=I> IC@ C=H@CC@>I>H@ CC=ICC@@!K" KC@ C!J@CC@"K"J@ CC!KCC@@SSC@ CS@CC@0S!SC@ CS@CC@'S)SC@ C'S@CC@/S1SC@ C/S@CC@7S9SC@ C7S@CC@?SASC@ C?S@CC@12345NL@ CCNCC@@FD@ CCFCC@@><@ CC>CC@@64@ CC6CC@@.,@ CC.CC@@012341 1C@ C0@CC@10@ CC1CC@@64@ CC6CC@@!6!4@ CC!6CC@@76@ CC}7CC@@6 6C@ C6t@CC@5 5C@ C4@CC@ 5 4@ CC5CC@@!7!6@ CC!}7CC@@!6" 6C@ C!6t@CC@!5" 5C@ C!4@CC@"5"4@ CC!5CC@@**((***C@ C*@CC@*(@ CC*CC@@((@CC@(C@ C(*CC@@(@ CC#*%*%(#(#*#*%*C@ C#*@CC@%*%(@ CC%*CC@@%(#(@CC@%(C@ C#(#*CC@@#(@ CC+*-*-(+(+*+*-*C@ C+*@CC@-*-(@ CC-*CC@@-(+(@CC@-(C@ C+(+*CC@@+(@ CC3*5*5(3(3*3*5*C@ C3*@CC@5*5(@ CC5*CC@@5(3(@CC@5(C@ C3(3*CC@@3(@ CC;*=*=(;(;*;*=*C@ C;*@CC@=*=(@ CC=*CC@@=(;(@CC@=(C@ C;(;*CC@@;(@ CC18192021**C@ C*@CC@!*C*C@ C!*@CC@((C@ C(@CC@!(C(C@ C!(@CC@$C$C@ C$@CC@) )C@ C(@CC@)(@ CC)CC@@% %C@ C$@CC@ % $@ CC%CC@@!)" )C@ C!(@CC@")"(@ CC!)CC@@#)$ )C@ C#(@CC@$)$(@ CC#)CC@@%)& )C@ C%(@CC@&)&(@ CC%)CC@@+), )C@ C+(@CC@,),(@ CC+)CC@@-). )C@ C-(@CC@.).(@ CC-)CC@@3)4 )C@ C3(@CC@4)4(@ CC3)CC@@5)6 )C@ C5(@CC@6)6(@ CC5)CC@@;)< )C@ C;(@CC@<)<(@ CC;)CC@@=)> )C@ C=(@CC@>)>(@ CC=)CC@@!%" %C@ C!$@CC@"%"$@ CC!%CC@@)(@ CC})CC@@( (C@ C(t@CC@+*@ CC}+CC@@* *C@ C*t@CC@+*@ CC}+CC@@* *C@ C*t@CC@+*@ CC}+CC@@* *C@ C*t@CC@#+#*@ CC#}+CC@@#*$ *C@ C#*t@CC@%+%*@ CC%}+CC@@%*& *C@ C%*t@CC@+++*@ CC+}+CC@@+*, *C@ C+*t@CC@-+-*@ CC-}+CC@@-*. *C@ C-*t@CC@3+3*@ CC3}+CC@@3*4 *C@ C3*t@CC@5+5*@ CC5}+CC@@5*6 *C@ C5*t@CC@;+;*@ CC;}+CC@@;*< *C@ C;*t@CC@=+=*@ CC=}+CC@@=*> *C@ C=*t@CC@!+" +C@ C!*@CC@"+"*@ CC!+CC@@&$@ CC&CC@@5) )C@ C(@CC@)(@ CC)CC@@Figure5-15.TABLEMAPPEDONTOAGRIDDATASTRUCTUREforthetableinFigure5-6.Themediumgreytilescorrespondtotableboxesandthedarkgreytilestotypographicrules.Becauseofthewaycornerstitchingcoordinatesaredetermined,gridmodulesareunitsquaresandgridboundariesarelinesofunitwidthorheight.Thelightgreyshadingrepresentsthebordertilesthatholdthetableentriestogetherinthecornerstitcheddatastructure.Thetworulesintersectandarerepresentedbyseveralfragments,oneofwhichistheintersectionoftherules.Theexternaldescriptionofthetableisparsedtocreatetheinternaldatastructure.Theinternaltabledescriptionisheldinatableobjectrecord,whichremembersthetabledocumentsubtree.Later,anupdatedexternaltabledescriptionissplicedintothesubtreeafteredits.Thetableobjectrecordalsosfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^ g !(/37:>\ g %) %!'+!-%17!= Z gn %n'#.G0K59>DXb gO"1$'+-3( gV/;#!TVm$s(~Q~Q~Q~Q!~Q#~Q%~Q'~Q)~Q+.Q-.Q/.Q1.Q3.Q5.Qx ####x####x####x####x####x####x####x####x####x####~Q7.Q9.Q;.Q=.Q?.Q>L'>J'>H'>F'>D'>B'>@'>>'><':'8'6'4'2'0'>N'.','A.Qx ####x############################################################################################################################################################~T ##### ~T(~T0~T8~T@~T #####~MG~EG~=G~5G~-G ############x####x####x####x####x####*'('&'$'########################################################~%G ##"UTVm$v! g|! ! d! ! H! "9#e! &! *v! 24669;?C( g } 5#'|*,{/257U >B3 gs5 $m& .(06K8;@jC H g Jh!"'*-05 C!\ gJX"#&*T/t2 90<>Bp ge  %(d*-/s1 9D:=P g=;#r7n !#&*,138;A g Q! *h,/13@7VE g !"d(/,14q8=rBV2TVm$O5ANEWFRAMEWORKFORTABULARCOMPOSITION5-27pointstothegridtesselationoftableentriesandtherearefieldsforthegridpositionsandtableoriginthatwillbecomputedlaterbythetablelayoutalgorithm.Theauxiliaryconstraintsprovidedbythetabledesignerarecontainedinalinkedlist.TableRec:TYPE=RECORD[branchInDocument:REFDocumentObject,--documentsubtreegridTesselation:REFTesselation,--areastructurefortilesnumberOfRows,numberOfColumns,INTEGER,rowGridPositions:ARRAY[0..numberOfRows)OFDimension,columnGridPositions:ARRAY[0..numberOfColumns)OFDimension,backgrounds:LISTOFREFTableEntryRec,origin:Position,constraints:LISTOFConstraint];Dimension:TYPE=RECORD[value:REAL,units:Units];Position:TYPE=RECORD[x,y:Dimension];Units:TYPE={in,cm,mm,pt,pc,...};DocumentObject:TYPE;--representationofadocumentobjectTesselation:TYPE;--representationofthegriddatastructurethatcontainsTileRecsConstraint:TYPE;--representationofalinearinequalityThecornerstitchingdatastructuretesselatestheplanewithtiles.Aninitialtesselationcontainsasingletilethatservesasauniverse.Atileobjectcontainsfourpointersforthemajorcompass-points,atesselationcoordinatevalue,andagenericpointertoitsassociateddata.(InCedar,agenericpointerpermitsadatastructuretobeusedinseveraldifferentapplicationswithoutthealgorithmknowingthetypeofthedata.Theapplicationisresponsibleforprovidingthepointervalueandforlaterassertingthetypeofthepointerwheneverthepointerisdereferencedtoaccessthedatafields.)Newtilesareaddedbysplittingtheuniversaltiletomaintaina``maximalEast-Weststrip''property,whichcanbeseeninFigures5-14and5-15.TileRec:TYPE=RECORD[north,south,east,west:REFTileRec,x,y:Coordinate,--NEcornerinthetesselationcoordinatesystemdata:REFANY];--aREFTableEntryRecwhenusedfortableformattingCoordinate:TYPE=INTEGER;Thetableformattingprototypecreatesatableentryrecordforeachcornerstitchedtile.Thetableentrycontainsthegridcoordinatesandthekindoftableobject.Aboxtableentrypointstothedocumentobjectthatwillappearinthetable,andretainstheboxdimensions,origin,andalignmentpointcomputedbysfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^ g^c< !#'-%0g47p;>Ak\ gU|"&(b036@9=/Z g X 'W.S037>5@Xb gkTVm${V/x|V/V/{V/|rV/V/F{`V/V/S|,SS{S8TVm$8y+SS+,36TVm${Q|}QQQ{QH HTVm$y%@QQ%&)/\1hTVm${O |'JOO'{,OOMc|McMc{Mc |,McMc-{Mc. K1|K1K1{K1"|1K1K11{K13) H |HHHH,{H FD |DDD{D Bex |BeBe{Bei|NBeBe"{ @2@2{@2|@2@2i{@2@2! =x|==k{=#` "$;x|;;]{;;hTVm$y;; (=)+11!TVm${9x | 99{99 TVm$y|99 $&J(+c.h4 6<0:TVm$&{7gx |7g7gd{7g7gVTVm$y7g7g $D%'* r4`K")m 03\7;@B2. g ^: #'$,./i78;@/ gb ,- 5 > BF- g$ #(|+:017=nCaD+ gJN#) 28;)d g#6& /0 9s<#C'2 g%| C' )-/2y86?B% g !%J+U/H25:<C@" goGL, (/4z;@{C g $fTVm$!{hx|hh{h|ihh={Whh5|i55 ={5"3  DTVm$EyA?#%' .v 5N*TVm$"{|{ax TVm$#yGTVm$|{ TVm$y*8-026F TVm${x |{|o{ TVm$)r6 T&,D-16 ;7=Ad gc".(+. 7:=AC2 gY5w$&)1c6N9<BNDR g*}V (-18=,D TVm$}5ANEWFRAMEWORKFORTABULARCOMPOSITION5-28thelayoutalgorithms.Typographicrulesandbackgroundtableentrieshavenocontent.Thestyleattributesarerememberedasalistofattribute-valuepairs.TableEntryRec:TYPE=RECORD[top,left:GridCoordinate,--inthetablegridcoordinatesystembottom,right:GridCoordinate,object:SELECTboxType:{box,rule,background}FROMbox=>[contents:REFDocumentObject,extents:BoxDimensions,--computedlateralignmentPoint:Position,origin:Position],rule=>[],background=>[],ENDCASE,styleAttributes:LISTOFAttributes];GridCoordinate:TYPE=INTEGER;BoxDimensions:TYPE=RECORD[left,right,top,bottom:Dimension];Attributes:TYPE;--formattingattribute,valuepair5.4.3OverlappingPlanesThecornerstitchingdatastructureisinherentlyplanar,whereassometablesmayinvolveoverlappingtableentriesorrules.Therearethreethingsthatmayoverlap:tableentriesthatare``pastedover''otherentries,rulesthatintersectwithotherrules,andbackgroundsthatunderlaypartorallofthetable.Thepositionsofalltheseoverlappingelementscanbeexpressedintermsofgridboundaries,sonoadditionallayoutinformationisnecessaryorgeneratedbyoverlappedentries.Backgroundscanbeeasilyhandledbecausetherearegenerallyfewofthem(oftenonlyonepertable)andtheirsizedependsonanddoesnotinfluencethetablelayout.Itissufficienttomaintainalistofbackgroundrectanglestobeshadedinthetableobject,sotherenderingalgorithmcantraversethelistandpainttheshadedbackgroundbeforerenderingtherulesandtableentries.Overlappingruleswithintablesaremoreinterestingandmorecommon.Rulesintersectwhenahorizontalruleandaverticalrulemeet.Eveniftherulesareofequalthicknesses,theendpointsoftherulesmustbeadjustedtoensurethattheyavoidanotchedcorner,suchastheleftmostexamplesinFigure5-16.Additionalcomplicationsarisewhentworulesofdifferentcolorsortexturessfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^ g@D j ' +.T 7b;x@D\ gU !$ .H0L14b6sAyTVm$~{Zx |mZZ&{Z|ZZ{"ZZXaWE2TVm$0y!!XaXa!"$>&), 3< TVm$ {V/vS|SS{S ##' |/OSS0{QQO|OOh{O_Me TVm$My$MeMe%%, TVm${K2I& FsD &|Bh{BhBh@5|'@5@5@5&{@5@ >;x|;;{;c|H;;{#;;9x |99{9@|%99{#99#w&D),1 7kx |i7k7k#{W7k7kTVm$y7k7kR "u (A+s3 gT r/K")m+" 28>C - g "(E*d/t4C7;L@6C+S gG"p(q,1U7;>y) g!y. %)80358:<B & gUf %+.1F8:?WAh$ g Mk !& /1`8:BV" g  #w)/4;7>ABCSQ gD1##&*103$6f::=,D] g}L !2#6*+|.,0= 9K @B g F"d%=,4<7I=q@JB g~ "#'O.158= ,4"T' ). 6/9q= gy %H(+-Y3$6;?ADiO g2C !$)+.269?A  grV%=)+-4K;{=B g  "'X*.07n<<>[fcTVm$5ANEWFRAMEWORKFORTABULARCOMPOSITION5-29intersect.Thenoneoftherulesdominatesandtheotherruleshouldhaveitsendpointadjustedtoavoidpenetratingthefirst,asshownbythemiddleexamplesinFigure5-16.Theprototypeimplementationonlyhandlesruleswithsquareendsbutanextensioncapabilityisavailabletoaddotherintersectiontypes.$/L$/H./H./L$/L$OL$OHD@D@$LD@D`$/H./HD@D@$/HD@D`.H.LD@D`.OHD@D@./L$/LD@D`./LD@D@=/?E~V;9?vCBEXh{4%4$CxH,?}t?i`9C}tCA#x*x'D}r3 CGCAuD}_A𗼲rCEXh|DhsDh, >CMRE}耾`AxD}EXEXٻ3D}f=?D弶$#ؿBa(CCDl1*Cƻ3Vﶼ~Bɾ(CD@<@48:D̩x0о9BY%PCDr$DH :H 輰:`BUXBrC2CC@B<}BHDŷ1^RBPx*nC0Dr-CBX @*mDh\=ؼȬ(B'Cv`HBC@Cv`;CcC]AIо2XAAN)%}CڂDq#CZ%~%~CXh|AJi1HAOxCՒ ҀC0CՒ;C@DXh{HAPCDjCڲ9ڀDi`\@@(]BFCڃ%~~CڂCځ:C>\DUB!^RA5CTD\&DEmS4Dq&AHBcxlBFھ8?}ɠD@D_CV;BKlľZ?0CaH݀BdCc8/D1 BL۳@LC@DlBD̢CˬC@p6OlD@D@6D3] 4SB`\p9`BDrCveDŶiDH~CO:CEB1vOCE5D:IECL|1T  *kDr-CՕ Dt`|DhC^ؽ=6>pPC}Cvf@IC|4CjIA̾|AI?ྲؾH%~%}~Dq#Cځ%}CXCXAAJ](C/CՕCBb*j@C.4C@x*x'BQ40%Q`9%hDjC9DDzDi.CB@B>CڂCڃCZ%~Cڂ4Bg>BCT$F$5pB8D\*CɀEC}wDwQC[WB@p ;CCCژ‼C3Ap5CP]BN9/0hDHCh@dBiDoCW^B\@9sx7@hCTCDEg7CT3U@D2wA:BH P?ĀCKD@? mCrABM"_BbChDYd @Bb3O?@{1NCJ Bx@fA@Bp+C̟CBp2TD0CC,CA~HAeO6 D@D`;3v>Cͫ3hBBA0Cw3BLCCwtDMB6CNTA;hC DlԀ3a@3=|DIN:1BͤCJ^AJphhCս ـC @CռKDtB~C\tBQȽCDr̀#4<CSj$꾸Aʅ"CM=DkA~@AIB^BdPCbDYD瀼BdP>1jļɖ5AćB0Z4D\%C̀W= ?NBcCܽL?|A|D@D` žH?ߺ A DICbn>nCnI $4ICnBmۺD$>nBmCn$DmI CnEFI$D$D$)$BmEfnDm)$I*EFI%EFI$>nD$I&)$<?DI$ %)p1MB^3h CDk.L@ CsXg (BVHD@D@;@nD|n-$ P4B\bCsDr~ _CշU%2#'PB}BpL CjC@Bn;A%nDZ"IPBNh0AC DrB0@C "Vؽ (BdCr BCsCr;8BKCnAa䐽3}AY %~CڃDq"CZ%~%~CI$9Ad6ཞݴ2HAC2CC:BDFI$?E 8KpBD}CĜDi}Cz;bDT$AbPBGHCڂ%}݀CڂCځ:bC TDC%AEؽȘACPDZDFyDxI/BQlCsXgBB-AP[PCr BCt@Cr*IDpBCJ{dAدrC DxJHOAR B]KxB] CxDY@B]$"!p6,AlԀBDzDZC}< ?eBJ&CY%/{bB@?zJ AY0D@D`@$.2U ?A8DHwCx@8/?>/?>/E2/E2/98/98/?/2438=I 5 g%K "$#)I-@0z3~9z>3 g/il #%&(+i0F4<7w=@ 1 g| ',/2 g/;#r- $+.3f479X>@+V g ! *,25`:< )# gp "% -/6e<0>C& g@ Q$')/4<>$ g ?Q!#*,/ 8m?( g  |#O *-24 =A g ,B"'X)0 2k ;=C g   %(*-g04};` g#&N /Z57;g@lDZX gH! #k',.4:@*& gf#&-/4b7;9; g$Kx'$ (-.wr5 7h<7 D- g s"%) 358 2!TVm$5ANEWFRAMEWORKFORTABULARCOMPOSITION5-305.4.4GridAlgorithmsThemainalgorithmspresentedinthissectionarethetablelayoutandtablerenderingalgorithms.Thetablelayoutalgorithmtakesatablearrangementandproducesthepositionsofthegridlinesandtableentries.Thetablerenderingalgorithmisresponsibleforcreatingaprintableordisplayableversionofthetablegiventhepositionsandcontentofthetable.Thesetwoalgorithmsrequireanenumerationalgorithmtoactonallofthetableentriesintheinternaltabledatastructure.Interactivemanipulationoftablesrequiresahit-testingalgorithm,whichresolvesthetableentrythatisbeingpointedatonthescreen,anddynamicrestructuringalgorithmstoinsertanddeletepartsofatable.TableLayoutAlgorithmThetablelayoutalgorithmdeterminesthecoordinates(relativetoatableorigin)ofthegridlinesgiventhegriddatastructurerepresentingthetablearrangement.Thelayoutalgorithmalsoneedstheboundingboxdimensionsandalignmentpointofeachtableentry,whichareobtainedthroughtheobjectlayoutprocedureassociatedwiththeclassofdocumentcontentinthattableentry.Typographicrulesalsohavewidthswhichareobtainedthroughthestylemachinery.Linearinequalityconstraintsdescribethepositioningrelationshipsbetweentableentriesandgridlines.AmathematicalconstraintsolverisdescribedlaterinSection5.5,wherethecompletetablelayoutalgorithmispresented.Thetimecomplexityofthelayoutalgorithmisdominatedbythealgorithmforsatisfyingthelinearinequalityconstraints.TableRenderingAlgorithmThetablemustberenderedinaformsuitablefordisplayorprinting.Thetablerenderingalgorithmtakesthegridpositionsdeterminedbythetablelayoutalgorithmalongwiththecollectionoftableentriesinthegriddatastructureandinstantiateseachtableentryatitsappropriateposition.Thecontentofeachtableentryisrenderedviatherenderingprocedureassociatedwiththatdocumentobjectclass.Tohandlethepossibleoverlapofdata,thetablecontentisrenderedinbacktofrontorder:shadedbackgroundsfirst,thenrules,thentableentries.Thetablerenderingalgorithmusesadeviceindependentimagingmodel[Warnock&Wyatt,CedarGraphics]forrasterdevicestoproduceformattedoutputforbothdisplaysandprintingdevices.DeviceindependenceprovidesaWYSIWYGcapabilityforinteractiveeditingoftablesbecausethedisplayscreenpresentsthesfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbs^ gT' r[O m&(,14n7G;]@bCX g   v$)15A6: DMV gqJ7I""%)y,07-:>T g = '0(/1 :S@B RR g}!'),169 B P g Y!$&)B+S.,2C79(@,A? g("z%S(,i3L <?=q g in&*I.19=< E!;> gtY"p'%,.5;>9 gk< $'+W-h5;= @g6 g Ya"&+03:o@C4 g  "{ *1,4 < 2u gV#') 3 ;@`0C gq"'s*L1c5y:~A. g Y $&)x.|57?BK+ g  %S - w( gr$+6L$&(,264:<C! g}|#&)0 9< >B ge &k(|,136::=D g !&#%J .#5y8>@a g}}y )#*2Q :=/ g)K &(,/39;kBgDk gk) &*.q26:6&5)+,0K 9@t g r!$Z(.07>D gI &,k 6=t> @^r Z g  $%&6*139>E jTVm${5ANEWFRAMEWORKFORTABULARCOMPOSITION5-31samefontsandgraphicsastheprintedformofthetable,subjecttodifferencesindeviceresolution.Theimplementationofatableeditorsharesthetablerenderingalgorithmwiththedocumentformatter.AlgorithmR(TableRendering)R1[OutputBackgrounds]Traversethelistofshadedbackgroundsinthetableandforeachone,outputashadedrectanglewithcornersdeterminedbythecoordinatesofthetableentry'sfourgridlinepositions,andwiththecolorspecifiedbytheareacolorstyleattribute.R2[EnumerateRuleTiles]Traversethetablegridstructureandrendereachtablerule:R2.1[DrawRule]Determinetheruleshapefromthegridlineposition,therulethicknessspecifiedbyastyleattribute,andanyintersectionswithotherrules.Drawtheruleinthecolorspecifiedbytherulecolorstyleattribute.R3[EnumerateTableEntries]Traversethetablegridstructureandrendereachtableentry:R3.1[OutputTableContent]Invoketherenderingprocedureforthistableobjectatitsorigin(x,y).Onemightextendtherenderingalgorithmforinteractiveusesothatitperformsonlyminimalrepainting.ThetechniqueissimilartothatusedbyWYSIWYGtexteditors.Bykeepingstateinformationabouttableentriesthatchange,onlythoseentriesneedberepainted.Bykeepingtrackofgridpositionsthatchange,ablock-moveinstructiononportionsofthebit-mappedscreenpermitsopeningup(orclosingup)gridlinestoupdatethetablewithouthavingtorerendertheentiretable.Thetableeditorwouldhavetocooperatewiththetablerenderingalgorithmtomaintainthesestatevariables.EnumerateAreaAlgorithmBoththetablelayoutandthetablerenderingalgorithmmustenumerateallofthetableentriesandrulesinthegriddatastructure.Thecornerstitchingdatastructurehasadirectedareaenumerationalgorithm[Ousterhout,CornerStitching]thattakeslineartimeinthenumberoftilesenumerated.Thealgorithmisgiventhecornerstitchingdatastructureandarectangularsearcharea.sfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^ g #^)*-?/P2)6E \ gk F +-.37<?Z gf !) wWo?] tTrTS 's.+135;\ ERVS,B #5' */1b6>AP#S !r$K - /16 ;]>BsMS  $'+247;\?KS tHrHS 8#A(^/169}@`FSn#tCrC#+.2@6:=AMAN [#3&-468\2@6C< "%)'-W1+ t9r9S 8#*1P4)8?;B7Sn#t4r4$+1z4S;C2y %').w/N2yr2y0=w02yr2y1m/sTx Q'/P1 :<?Bs-@ go( &)13I8:>At+ gr+M &* 38K$w gZ2#j&x)-/5Q8*<@BN"E gk!%-)C.379 @DD  g}|!(a,0t w9 gr_"%)1d8<E- gxQh"$ &*Z- 59N>z gA!%0 .t6N6 >= g r ;"$'-/3B =X@ gf!2$+.0\ 8>TVm$-5ANEWFRAMEWORKFORTABULARCOMPOSITION5-32AlgorithmEA(EnumerateAreaAlgorithm)EA1[LocateLowerLeftTile]Usethecorner-stitchingpoint-findingalgorithmtolocatethetileatthelowerleftcornerofthesearcharea.EA2[WalkLeftEdge]Walkthetilesalongtheleftedgeandforeachtileencounteredinvokethefollowingstepsrecursively:EA2.1[EnumerateThisTile]Performsomeuser-suppliedactiononthistile,orifnoactionwassupplied,thenappendthistiletoanenumerationlist.EA2.2[CheckRightBoundary]Iftherightedgeofthistileisoutsidethesearcharea,thenreturn.EA2.3[LocateRightNeighbors]Usethecorner-stitchingneighbor-findingalgorithmtoenumerateneighborsalongtherightedgeofthistile.Foreachneighborthatintersectsthesearcharea:EA2.3.1[RecurseonNeighbor]Ifthetop-leftcorneroftheneighbortouchesthecurrenttile,orifthetopedgeofthesearchareacutsboththecurrenttileanditsneighbor,thenrecurseatstepEA2.1ontheneighbor.TheimplementationoftheenumerationalgorithmusedinthetableformattingprototypeusesanonrecursivealgorithmduetoShand[Shand,CornerStitching]thatisbasedontraversingthetileslikeathreadedtree.Theimplementationrequiresthecallertosupplyanactionproceduretobeperformedforeachtile.Theenumerationalgorithmisusedinthetablelayout,tablerendering,deletion,andinsertionalgorithms.Forexample,thetablerenderingalgorithmsuppliesanactionprocedurethatrendersthecontentofaparticulartableentry.Hit-testingAlgorithmAhit-testingalgorithmisnecessaryforinteractivemanipulationofatable.Thehit-testingalgorithmdeterminesthetableentrycorrespondingtoapositiononthedisplayscreenpointedatbytheuser.Thealgorithmmustbequiterapidifthetableentryistobecontinuouslyhighlightedastheusermovesthepointingdeviceacrossthetableonthescreen.Thealgorithmdependsonacornerstitchingalgorithmforlocatingacornerstitchedtilegiventhetilecoordinates.ThecornerstitchingalgorithmtakesO()n)timeonaveragewhensfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbw^ob #8'3 t[r[S+!V$)f,/;Z YS$'r*J,5/36;=@WStTrTS.$(w+P.3F69=@CBRRS+ "'*26/ tOKrOK "&@*145~ ?DM "*#&?+).^5u9<?"BKE#J %tGrG8#,.R1+5&9;&>NA&E`"9'K+F/ tBrBz$ -303h@u&M-/7?D >C!#&*-18< C8<t9 Sr9 "h$-V/%17=?6#),2579R& g5 "T +3q5&9; =A$r g} g-"o)C 2h5<?p"? gf!$)04/:<BD g w3 g rY U "), 4 >@B& g  '*Z.q2 =~?@ gQc"p$[&)..19=.?C gIV ) 136:/?M g#&Q)*/C2:,@C ] g3"b()/(5D8<?g + g ,%b,w1 +r +2\z2 +w +4r5 + +6:=CTVm$H5ANEWFRAMEWORKFORTABULARCOMPOSITION5-33tileshavearelativelyuniformsizeandO(n)timeintheworstcasewhenallthetilesareinasinglecolumnorrow[Ousterhout,CornerStitching].Giventhescreen(x,y)coordinatesofthepointingdevice,thehit-testingalgorithmfirstconvertsthescreencoordinatesrelativetothedisplaywindowintotablecoordinatesrelativetothetableorigin.Theappropriaterowandcolumngridsarefoundbysearchingthetablegridpositionarrays.Thegridcoordinatesareconvertedintocornerstitchedcoordinatesandthetilelocatingalgorithmreturnsthetableentrytilethatcontainsthedatapointertothetableentryobject.AlgorithmH(Hit-testingAlgorithm)H1[ConvertCoordinates]Given(Sx,Sy),thescreencoordinates,subtractthescreencoordinatesofthetableorigin,(Ox,Oy),relativetothedisplaywindow,toproducethetablecoordinates(Tx,Ty)ofthepoint.Reportanerrorif(Tx,Ty)liesoutsidethetable.H2[Findrowandcolumngrids]SearchthetwovectorsofgridcoordinatesforrowgridlineGrprecedingTxandthecolumngridlineGcprecedingTy.Thiscanbedonewithalogarithmicsearch.H3[FindTableEntry]Locatethegridtileatthegridcoordinates(Gr,Gc)usingthecornerstitchinglocationalgorithmandextractthereferencepointertotheresultingtableentry.DeleteAlgorithmTwoalgorithmsfordynamicallyinsertinganddeletingtableelementswereincorporatedintothetableformattingprototype.Thedevelopmentofinteractivetoolsfortableeditingwasnotcentraltotheresearchinthisthesis,butthetoolswereusefulforconstructingexamplesandgaininginsightintothevalueofthegridstructureforinteractiveediting.Chapter6containsplanstoimplementbetteralgorithmsbasedonbetterdatastructures.Therearetwovariationsofthedeletionalgorithm.Thefirstvariantdeletestableentrieswithoutchangingthetabletopology,andtheseconddeletesgridlinesandhencechangesthetopology.Inthefirstvariantthatdeletesonlytableentries,thedeletionalgorithmisgiventwopairsofgridlinesthatdeterminearectangularregion.Byenumeratingtheareawithinthatrectangularregionallofthetableentriesintersectingthatregionarefound.Someentriesmaybepartiallyoutsidetheregionandthereforeshouldnotbedeleted.Thisalgorithmtakestimelinearinsfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^ g1 T"%w)3^r^*~w+^r^+-%025::=B2D\ g "t&%\\& .2 r8m\\Yw5YrY$wYrYT )C+T.-4:G= W gP % .}4T6Y92>E UQ g} ;!#(-1F :=n@S g}G$!$(,728i;?J P g26b%~ .<1~4W7/=dN g E #{),0k6)8-;?L gwIot "- tF|rF|S& 'p,tw-F|F5yF5.rF|.w/?F|F5yF50GrF|025`:q DISp$ -?/P2)6@;xw< DIDyD=TrDI>w>DIDyD?rDI@uBBSW0 'r)v/26 ?w@ BAyAA6rBAwBgBAyAC|rBD"ER?S,$#&v*,@w,??y?-r?.w/??y?0.r?024:=t<r<S!!d'V,147=?:S !%(w+::ey:e,r:.w5::ey:e6r:82;t>MD@8zSw8z83y83r8zw#8z83y83$r8z%U&\*-#/w37T8 Ait5sr5sSz%**-d0358v; 3ASw3A2y2r3Aw3A2y24r3A d#=(i/ 5J<@ En1S#A%F(.2w-5 g{r)[{ I '~.D17;B'( g }V m ( 14} >Q@b $ gb("(G*L-%358=@C" gbL !M(|+16:a=:AC gq !u(.c/6M:<_ g* H ^%"( YO "$&-J 59;<B-& g}"%)14W70<B' gGL![$! &*?.U46=HD g'!$,. 6< g c!$ -v2469= W g 2 y&]*0K36=<Br $ g!?$1&-Y18<@E/TVm$I5ANEWFRAMEWORKFORTABULARCOMPOSITION5-34thenumberofentriesenumeratedintherectangularregionduetothebehavioroftheareaenumerationalgorithm.AlgorithmE(TableEntryDeletionAlgorithm)E1[EnumerateAreatoDelete]Enumerateallthetableentrieswithinthetwopairsofgridlines,andforeachtableentry:E1.1[DeleteTableEntry]Ifthetableentryiscompletelywithinthetwopairsofgridlines,thendeletethetableentryfromthegriddatastructure.Thesecondvariantofthedeletionalgorithmdeletesgridlinesandalltableentriesbetweenthem.Thealgorithmisgivenapairofgridlines.Allgridlinesbetweenthepairofgridlines(inclusive)aredeletedandreplacedbyasinglegridline.Alltableentriesfoundentirelywithinthepairofgridlinesaredeleted.Anytableentrythatcrossesoutsidethepairofgridlinesischangedtoreflectthenewtopology.Thisdeletionalgorithmispresentedinitssimplestform,whichcreatesanewcopyofthegriddatastructure.AlgorithmG(TableGridsDeletionAlgorithm)G1[PrepareNewGridStructure]Prepareasecondgriddatastructuretoreceivethemodifiedtabletopology.G2[EnumeratetheOldGrid]Usetheareaenumerationalgorithmtofindallthetableentriesthatintersecttheregiondefinedbythepairofgridlines.Foreachtableentry,performoneofthefollowingactions:G2.1[TableEntryWithinGridPair]Ignorethistableentry;itwillnotappearinthenewstructureandisnotcopied.G2.2[TableEntryPrecedesGridPair]Createatileinthenewgridstructureandcopythistableentry.G2.3[TableEntryStraddlesGridPair]Adjustthefarthestgridcoordinateofthistableentrybythenumberofgridlinesdeleted,andcreateatileinthenewgridstructureforthischangedtableentry.G2.4[TableEntryFollowsGridPair]Adjustbothgridcoordinatesofthistableentrybythenumberofgridlinesdeleted,andcreateatileinthenewgridstructureforthischangedtableentry.G3[InstallNewGridStructure]Updatethetableobjecttousethisnewgridstructure.sfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^ g@u %'* 3[8y;=@\ gxQ  wYo2P")m tVrVS 8#@%D+46b9;=RBTS,a i"z%*<-~0.48tR rR _$)+._2u68u @O{#%)@-1Q6/9=AiE~M J$ 5#)j06f9=@CRHp g? (o*#./3d5u8=@DF= g/@" *-X3$6f=?g@D g' [%8+70V3/68=t g2 $&(),x0 w:mo?]")> t7gr7gS $ -(3B4:#=A954SW '+t2r2S 8"%`*~-04E =Ec0S+#(n+2^57:U@UB.VSE$-'a+5/L4:j=?,#St)r)#Z(,169> BD'w"$&*d1G46>91t$r$#Z*..628 9nKA$D" #'*/t Qr Q#Z*.3 8t;MAA !#&+/[14:<@S#')O,'.+147>A '$=t@r@#Z)-2"7v;X> "'<),w2484<BJr"$'+.5j8;BAt/r/S# ,148=?B SN TVm$_5ANEWFRAMEWORKFORTABULARCOMPOSITION5-35TheimplementationofthedeletionalgorithminthetableprototypereliesontheexistingcornerstitchingimplementationandavoidsdesigningorimplementingamoredynamicdatastructuresuggestedinChapter6.Thedeletionalgorithmusestwocopiesofthetablegridstructureandpingpongsbetweenthem.Thetimetocreatethenewgridstructureisdominatedbythetimeneededtorefreshthedisplayscreen.Amajorperformancebenefitisavoidingautomaticstoragecollection,sincethecornerstitchingimplementationcachesdeletedgridtilesandreusesthemwithoutallocatingnewones.InsertAlgorithmTheinsertionalgorithmalsocomesintwovariants,(a)onewhichinsertsatableentryintoanemptygridmodulewithoutchangingthetopology,and(b)anotherwhichinsertsanewgridlinethatchangesthetabletopology.Intheinserttableentryvariant(a),thenewtableentryiscreatedandinsertedintothegridstructureatthegridcoordinatescorrespondingtoanemptytile.Intheinsertgridlinevariant(b),thedualgridstructuretechniqueshownaboveisusedtocreateanewtabletopology.5.5TableLayoutviaConstraintsAlinearconstraintsolverisemployedtodeterminethetablegeometryfromthetabletopology,thecontentoftableentries,andexplicitauxiliaryconstraintssuppliedbythetablecreator.Thegriddatastructurerepresentsthetopologyofallthetableentriesandcontainspointerstotheircontent.Thelayoutalgorithmenumeratesallofthetableentriesandgeneratesappropriateconstraintsontheirpositions.Additionalconstraintsmaybesuppliedwiththetabletoimposespecialconditionssuchasforcingcolumnsofequalwidth.Solvingtheresultingsystemoflinearinequalitiesproducesthecomputedpositionsofallthegridlinesandtableentries.5.5.1ConstraintSystemsExamplesofconstraintsystemsincomputergraphicsprovidedthemotivationforthistechnique.Sutherland'sSketchpad[Sutherland,Sketchpad]wasaseminalinteractivegraphicssystemthatreliedonconstraintsatisfactiontopositiongraphicalelements.Borning'simplementationofThinglab[Borning,Thinglab]demonstratedtheuseofconstraintsinseveralproblemdomains.Thedocumentlayoutanddocumentcontentexamplesinhisreportwereofparticularsfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^ ! #*>136:B2\ g# /^27?#Z g L#B&-577;=@Xb gC! &(*/29h<@qV/ g2b!f&6),0 68@C<S g-y R%,-2 BD: gk;%;q3 g r/8 "$V+-58<C- g@Vl#S%d)z/82z8F? +N guNe"&_)-u4X <(?E) g@$+-17;_@c& g %xb y%)0L 9% A^C$ g ]  $(m*1n5(8<>" g %;+-2^8>@ S g !=(G+ 29;>)ADy gsF gT qrl5F &(0K6=9 g ] #) w,99-t94 @ TVm$Q5ANEWFRAMEWORKFORTABULARCOMPOSITION5-36interest.Thelayoutexample[Borning,Thinglab,p29]showedaparagraphsurroundedbyarectanglepreciselylargeenoughtoholdtheparagraph.Whenthewidthoftherectangleorcontentoftheparagraphwaschanged,therectangle'sheightwasadjustedaccordingly.Severalothergraphicssystemsusedconstraintstopositionthings.JUNO[Nelson,Juno]andideal[vanWyk,ideal]bothusenonlinearconstraintstodeterminethepositionofgraphicalobjects.pic[Kernighan,pic]labelsthecornersofboxesandpositionobjectsrelativetothoselabellings.ThegraphicaldebuggerIncense[Myers,Incense]containedaheuristicforpositioningnestedobjectsinadatastructurebydividingtheavailablespaceintwo.Theabilityofthesesystemstopositionpartsofanillustrationrelativetooneanotherwasveryattractiveandanalogoustothelayoutoftableentriesrelativetooneanother.Linearinequalitiesaresufficienttodescribethepositioningrelationshipsbetweentableentries,suchasmakingacolumnwideenoughforanentry,ormakingarowheadingtallenoughtospanseveralrows.Restrictingtheconstraintstolinearinequalitiespreventsexpressingarearelationships,butitismorecommontoexpresssuchrelationshipsbyestablishingaratioamongthesidesoftherectanglewhichcanbedescribedbylinearinequalities.Allthedistancesinatablecanbeexpressedasrectilinear(horizontalorvertical)distances.Thusaddition,subtractionandscalarmultiplicationaretheonlyoperationsneededtoexpressthetablepositioningrelationships.Usinginequalitiesintroducesthenotionofslackvariablesthatturntheinequalityintoanequalityfortheconstraintsolver.Theseslackvariablescapturetheextraroomleftoverforthetableentrytofitthegridlines.Smallertableentrieshavegreaterslackthanlargerentries,andoneormoretableentrieswillhavezeroslack.Theslackvariablesarehelpfulindeterminingwhethertheconstraintsystemmustberecomputedwheneditingatable.Atableentrywithslackmaygroworshrinkwithoutrequiringtheconstraintsystemtoberecomputed,whileatableentrywithzeroslackthatchangessizewillalwaysrequirerecomputingthegridlines.ThelinearinequalitysolverduetoNelson[Nelson,ProgramVerification]usedinthetableformattingprototypehasanusefulpropertyforimplementinganundofacilityinaninteractivetableeditor.Theconstrainttableaumaintainsastackof`dead'tableaucolumnswhichpermitsapreviousstateofthetableautoberecomputedquickly.Changestothetablethatmodifytablelayoutconstraintsmaybequicklyundonethroughthismechanismwithoutrecomputingtheentiresolutionoftheconstraintsystem.sfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^ gGt"F^^"(N.r^179\ g 3 &*0269 BYZ g@!'),47>Xb g x#R U[ ]&]*> 2x4}:t@U[U[AXS) grS)~S)S))tS)n"q&rS))-08- @gP g6^p&~-$PP.MtP1? 8rP;@DN g2C,"{(-/49 <@L gtLLrL$+- 36f >J_ gZ"=(+2m68=!@EH- g#% 's /57:@D E g  #_(c*u.39;>B  ')013 ; @ g "(})/39Cn> gKB %(+1_6U ><] g L $ * 26= @FCGD:+ gS#( ,/( 89=`B7 gpZc!@$M&.0i5 >A5 gcg E') 1 9< 3 g k (+W/ :=I@"1a g k).!$( 1p .[ B %G( -Y/j3:`=A^,( g  )"% -M3#7<) gN'J $Z' )-2D4I6u9N<A' g}H#]'%+148 :+>uB% g'D#*-o3 5$ >fD#_ g cy (-\24J9h;D?ZC!- g}=\m%{,/ 7<> g _$&'+}/29&+  gY22$u'0@6O ?B g ; GTVm$5ANEWFRAMEWORKFORTABULARCOMPOSITION5-375.5.2TheComplexityofLinearConstraintSolversSolvingasystemoflinearinequalitiesisequivalenttotheLINEARPROGRAMMINGproblem,whichisknowntobesolvableinpolynomialtime[Khachiyan,LP].Atablearrangementwithoutcenteredtableentriescanbedescribedbyasystemoflinearinequalitiesusingonlytwovariablesperinequality,asdescribedinthenextsection.ThisparticularLINEARINEQUALITYproblemfortwovariablescanbesolvedinO(n3)worstcasetime[Aspvall&Shiloach,LinearInequalities],wherenisthenumberofconstraints.AlgorithmsforsolvingmoregeneralsystemsoflinearinequalitiesbasedontheSimplexmethodhaveO(n3)expectedtimebehavior[Dantzig,LP].AversionoftheSimplexalgorithmduetoNelson[Nelson,ProgramVerification]wasimplementedinthetableformattingprototype.5.5.3TheConstraintTableLayoutProblemThetablelayoutalgorithmintroducedinSection5.4.4dependsonalinearinequalityconstraintsolvertocomputethepositionsofthegridandtableentries.Thissectiondiscussesthelinearinequalitiesactuallyusedtodescribethetablearrangement.Consideraparticulartableentryrepresentedasaboxk.ThistableentryispositionedwithinapairofhorizontalgridlinesandapairofverticalgridlinesasshowninFigure5-17.Thealignmentpointoftheboxistobealignedwithotherboxesthatsharethesamepairofgridlines.LabelthefourgridlinessurroundingtheboxasleftGridk,rightGridk,topGridk,bottomGridk.LabeltheoffsetsfromthealignmentpointtotheedgeoftheboxasdistancesleftOffsetk,rightOffsetk,topOffsetkandbottomOffsetk(theseoffsetsarefixedbythecontentandcanbedeterminedbeforetablelayout).Thepositionofthealignmentpointwithinboxkwillbe(Xk,Yk).TheverticalgridlinesrepresentcolumnboundariesandtheirpositionsaredesignatedbythevariablesCi.ThehorizontalgridlinesrepresentrowboundariesandtheirpositionsaredesignatedbythevariablesRj.BoxeswithinthepairofgridlinesleftandrightthatareverticallyalignedwillbepositionedatthevariableVleft,right,whileboxeshorizontallyalignedwithintherowbetweengridlinestopandbottomwillbepositionedatHtop,bottom.Allvariablesarerestrictedtopositivevalues.sfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbs^ gT nq# +r[ n#& +- 57t:z[[;aX g rX$&E+-0 6g8k A tV g r1VV '[-i48-=@T g/# ,j047>RR g "&z- 0 t87RRRR9>B rP g"%,*Jw,NP rP -w.+P PtP/rP /05b8tM gA r#MM$w)MrM+d-/6&87 K g M!'b-a/r4 <ACI gwIrIwIJtJrI >!n(Q,t2II3N8r:II<>pD-GW g@) l"pt(GWGW(z-3" rGW;>S E$ gkD[ y sAK gT  &%r=q6:# ,.37>]@B0;? g   ")Q,*35)8;y>9 g{"%*s 309K=-?1E6 g} 3# #' 024Gw73r38x:=AF91 g kY k (9+/24879?~B/o gk# */1)47D8:=QC-= gg$&')-169=@+ g w+ + Ly*#+r+ #w$+ + %y*+gr+ ,.w-7+ + -y*2~r+ 3Ew4N+ + 5"y*<>r+ =>CR( g 5$&)k-Y/k2D57w>((>y(Dr(Ew& g y&_r&w&&Cy&_r&w &&! y&_)r&+60517<,>Af$t g "' -17b9s r gQ*wlr+y+ rr#' 06;>A@ gw@@Er@w@@r@#%i -mw/W@y0 r@68;]B> g TVm$}5ANEWFRAMEWORKFORTABULARCOMPOSITION5-38 \ R9R9\ \"Z6Z6T"T"Z"Z6ZD@D@"ZrD@D`6Z6TD@D@6ZD@D`6Tr"TrD@D`6TD@D@"T"ZD@D`"TD@D@ ] Q@ CC ]CC@@R:RC@ CR@CC@9Q9]CC@@9Q@ CC:\\@CC@:\C@ C&Q&]CC@@&Q@ CC&U&UD@ D&UR@DD@*Q&U~CZC"Bڈ~}*QCZ~݀%xCZCZCHCleftGridleftGrid ,rightGridrightGridtopGridtopGrid ,bottomGridbottomGridRVRXYkk,U:UC@ CU@CC@kkkkkkkkFigure5-17.CONSTRAINTVARIABLESFORAPARTICULARTABLEENTRYareshowninthisdiagram.Theboxrepresentingthetableentryisindarkgreyandthegridmoduleformedbytwopairsofgridlinesisshowninlightgrey,thecolumnlinesCleftandCrightandtherowlinesRtopandRbottom.Thealignmentpointofthetableentryboxgoesthroughthetwoalignmentlines,Vleft,rightandHtop,bottom.Theobjectivefunctionfortheconstraintsolverwillbetominimizethewidthanddepthofthetable.Foratablewithmrowsandncolumns,theobjectivefunctionwouldbeMin{(CnC0)+(RmR0)}.Thetablelayouttherelationshipsamonggridlinesandalignmentpointscanbedescribedbyinequalityconstraints.Thefirstsetofconstraints(1)ensurethatallofthegridlinesareintheexpectedorderandthatthealignmentlineiswithinthecolumn.Onesetofconstraintsisrequiredforeachpairofgridlines,leftandright,thatcontainatableentry.(Columnconstraintsareusedintheexamplesthatfollow;rowconstraintsaresimilar.)CrightCleft>0Vleft,rightCleft>0(1)CrightVleft,right>0.Aconstrainttoensurethatthegridlinesaresufficientlyfaraparttocontainthewidthofatableentryisgeneratedforeachtableboxk:CrightGridkCleftGridk>leftOffsetk+rightOffsetk.(2)Inpractice,thesetwosetsofconstraintsarenotgeneratedexplicitlysincetheyaresubsumedbythealignmentconstraintsbelow.Thealignmentconstraintsvarywiththetypeofalignmentrequested.Aligningatableboxflushleftinthecolumnwithoutregardtoanyotherboxinsfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFb g`;#'TVm$R}x###########O"^Q6O~OU#]7OU@_K< g] "&%)*,./S2W47U:">CE^IP gp=w!%H',y}/IPI  TVm$|I 0TVm$vIP2}5bIPI TVm$I 6`TVm$vIP9";>!@}DIPI TVm$I EIPTVm$vGd g}GdGTVm$GTVm$vGdK!_# %k(,Z/2*7J9 gR#&E'+w/z>r>1g5Tw8>r>:A; gc8!-w"88y8#r8% w'f88t8(r8)F*w,w-O88y8.r804w2z88t83r84[6_56: (.15v8@mEd3 g! 8 )y,0M24 =!?D1k g")-1:47q?%Bg/8 g_Z!# +-4-6:>@,Cw- gr-Bw--#r--= !{%*1 :<@B* g (*w'#_y'$r''w*9''y'+ir'z-'r'0#w$"Ey$#u r$)w+T$$y$,r$z/$r$1>$Ew!!My!{"}r!%w('!!{y!{)W r!z.!r!1.2 ,1 w#&*%.0 9L;@ B$ g@_u!u)+/3w6r7wy= ZTVm$pg0TVm$rw =y="2 TVm$p&<TVm$rz'rw* *y=0yr1w4%4 y=;r=E}t#% -Z0%3: AK g' /E # &*s-L03 :  g, #%'-39 ;>5BE> TVm$5ANEWFRAMEWORKFORTABULARCOMPOSITION5-39thecolumngeneratesthesetwoconstraintstopositiontheboximmediatelyadjacenttothecolumngrid:XkCleftGridk=leftOffsetk(3L)CrightGridkXk>rightOffsetk.Similarly,aligningatableboxflushrightinthecolumnwithoutregardtoanyotherboxswitchestheequalityandinequalityconstraintsfromthosein(3L):XkCleftGridk>leftOffsetk(3R)CrightGridkXk=rightOffsetk.Centeringatableboxwithinthecolumnmayinvolveoneoftwocenteringconcepts.Thefirstforcestheboxalignmentpointtobeequidistantbetweenthecolumngridlines:2XkCleftGridkCrightGridk=0.(3C)Thesecondcenteringconceptpositionstheboxtobalancetheexcesswhitespacesurroundingthebox.Theexcesswhitespaceisthewidthofthecolumn(CrightGridkCleftGridk)lessthewidthofthebox(leftOffsetk+rightOffsetk):XkleftOffsetkCleftGridk=1/2[(CrightGridkCleftGridk)(leftOffsetk+rightOffsetk)]whichcanbesimplifiedtotheform:2XkCleftGridkCrightGridk=leftOffsetkrightOffsetk.(3C()Thetwocenteringconstraints(3C)and(3C()areequivalentonlyifthetwooffsetsareequal,whichiswhenthealignmentpointisinthecenterofthebox.Notethatupuntilnownoneofthesealignmentconstraintsinvolvedaligningasetofboxeswitheachother,onlypositioningtheboxwithinthecolumn.Toalignseveralboxes,weneedtoforcethealignmentpointwithinaboxtobeequaltothepositionofthealignmentlinewithinthatcolumn.Thus,foreachboxkintheset,generateanequalityconstraint:XkVleftGridk,rightGridk=0(4)Infact,ifthevariableXkdoesnotappearinanyotherconstraint,thenitmaybedispensedwithandtreatedasanalias.sfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^ g@3p # ,.!4p7I: \ gwYyYz rY"$w$jYYzyYz%TVm$pY3* TVm$rY+Kw-YY.yYz4rYDwVyVt@TVm$(pV-$TVm$rV%w(VVtyVt)NrVz*VrVw,VV- yVt4xrV5S 'u"&3*W.R0V3/9"?0D\Q g) y&* 1 9>BhOP gwLJyL rLJ"(w$nLJLyL%TVm$pK*LTVm$rLJz+OLJrLJw-LJLJ.yL3rLJDwID yH<NTVm$,pH$hTVm$rID%w(IDHyH)JrID*w,IDID- yH4|rID5F>] %:(.17m:<?D g)"%-136L >ENA gZ>z>w>y>r> Ow">>y>#jTVm$p>F(8TVm$r>*w,[>>y>- TVm$p>F2(TVm$r>4#6i7>D;%,/24:=9 g    %.(- 57:q?A*7h gZw7h7"y7"*TVm$Xp6vTVm$r7hw7h7"y7"* TVm$p6"TVm$r7h#<$l'*_/1374w77h7h8<y7">5r7h?w56 g y4r56w20y1r20w2020=y16r20w201y1HTVm$_p1#TVm$r20$/z/r/iwr//y/TVm$%p/q$TVm$r/ :w"//y/#& TVm$p/q(#0TVm$r/(),9w,//-Ay/3:r/4w6//7 y/>lr/?3, gDR Z _#8)zj)w)>y)nr)w))y)J2ITVm$`p)e|TVm$r) w#A))y)$q~ TVm$p)e)TVm$r)+ w-O))-y)3r)5%w7k))8 y)>r)@W)D^zF)r)G]& g6 "p&6)xz,&r&,x-0s 8x<0=@$ g]G%$L'%.32469>@C!;!E%g'y+3k ; g\!$)-e 58<A'O ga $'-+6-;1k4D;@QEp g_#%(0M38< C gw-r&)(}. wy r"-w$sy%TVm$#pW*bTVm$t*y+ +d TVm$pW0gnTVm$r13E g2wy%r#^&Q+-05C =HAB gVR"$'4piTVm$R5ANEWFRAMEWORKFORTABULARCOMPOSITION5-40Thepositioningconstraintsforeachboxalignedwithinasetaresimplerbecausetheyonlyrequirethattheboxfitwithinthecolumn:VleftGridk,rightGridkCleftGridk>leftOffsetk(5)CrightGridkVleftGridk,rightGridk>rightOffsetk.However,theseconstraintsarenotsufficienttoforcethesetofboxestobeflushleft,flushright,orcenteredwithinthecolumn.Thismustbeaccomplishedbyguidingtheconstraintsolvertoaparticulardesiredsolution.Forexample,toforcethesetofalignedboxesflushleft,theobjectivefunctiontobeminimizedbytheconstraintsolvermustbeaugmentedwithatermfortheleftdistance:Min{(VleftGridk,rightGridkCleftGridk)}.(6)Asimilartermisnecessarytoforcethesetofalignedboxesflushright.Centeringthealignmentlineforasetofboxeswithinacolumnmaybeaccomplishedintwoways.Thefirstsimplypositionsthealignmentlineequidistantbetweenthecolumngridlinesanddoesnotinvolveanadditionaltermintheobjectivefunction:2VleftGridk,rightGridkCleftGridkCrightGridk=0.(7)Thesecondcenteringtechniqueistobalancethewhitespacebetweenthesetofalignedboxesandthegridlines.Theobjectivefunctionrequiresanewvariableequaltothemaximumwhitespaceinthecolumn.Thiswasnotdoneintheprototypebutisconsideredlaterinsection5.5.4whensuch`maximum'variablesareintroducedtohandlelargetables.Theselinearconstraintscanbegeneratedautomaticallyforatablefromtheinformationkeptinthegriddatastructure.Asmallexpressionlanguageforconstraintinequalitiesisprovidedintheprototypeforthetabledesignertodescribeadditionalconstraintsforspecialeffects.Forinstance,tocreatetwocolumnsofequal-width,saythecolumnbetweengridlinesleftandrightandthecolumnbetweenleft(andright(,thefollowingequalityconstraintisaddedtothetablespecification:(Cleft(Cright()(CleftCright)=0.(8)Theexpressionlanguageacceptsastandardformofthevariablenames.TwosuchconstraintswereincludedintheexternalrepresentationshowninFigure5-13.Avarietyofuserinterfacestothisconstraintexpressionfacilityarepossible.Onlythesimplesttextualinterfaceoftypingtheconstraintequationsissupportedintheprototype.sfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^  #&*e-3r89<?J\ g<#%)++X0w3PwYDyYztTVm$pY3TVm$tYz y YzYz!b TVm$pY3&8TVm$rY'vw)YYzyYz* TVm$pY3/_TVm$rYz0YrYw2YY3RyYz9KrYEwVyVsTVm$,pV,LTVm$rV w"VVsyVs$ TVm$pV,(rTVm$tVs)y)jVsVs) TVm$pV,.TVm$rVz0VrVw2@VV2 yVs9rV;,S(g #&k)^ 0269<%>7BDQ g p%<*[-44.7;OO g ! )z.I0M1 9&>M g"-$>*.2609 @J gkL% %*.09t=.>BE2H gZE4w EEkyEk!kTVm$pE$&<\TVm$tEk&y'3EkEk'^ TVm$pE$,hTVm$rE-w0EEkyEk1Bj TVm$pE$5tTVm$rE6S8WEEB gCS "&),4.E48<?]6!%,')A+-279>B=r g  $X'-46>;@ g iB$4'+.25;^= 9 gUY2.6z6w6y5v TVm$p5z]TVm$t5yT55 TVm$p5z$TVm$r6%w(265y5)c TVm$p5z-TVm$r6/w1Y65y52 TVm$p5z7TVm$r69";h<6E3 gM}$%'-0 9?B^D0 g2 k%S(/6K<> A. g %'*15x8;?A,j g $&,80#48kA *7 g2 #'1, !e$s&.T 8x;'<@D$ g s-1 !% - .3> ;NB<" g  t%p't*M14}7V;mA g  "%*1 4T;=Ah g !g$@*304.w8hh8rh:w>,hh>rhBE`5 gZw55Uz5r5#wf55 z"5r5#"$+'.M4 <8=BD g} wyrw!y#%r&'O)w*'y+Wr-w0y1Jr45?78E g $%,025;B g< vp#8%<(.d 9&>R@V gdu %l'q* 24 :D? _ g!#&-Y/j47b >Fp - g+/ TVm$5ANEWFRAMEWORKFORTABULARCOMPOSITION5-41H4,5R4>6.225697(flushleftbox4,0)R4H4,5>15.25376H3,4R4>6.225697(flushleftbox3,0)R3H3,4>14.97279H4,5R5>6.0(flushleftbox4,4)R4H4,5>12.22937H4,5R5>6.0(flushleftbox4,3)R4H4,5>12.22937H4,5R5>6.0(flushleftbox4,2)R4H4,5>12.22937H4,5R5>6.0(flushleftbox4,1)R4H4,5>12.22937H3,4R4>6.0(flushleftbox3,4)R3H3,4>12.22937H3,4R4>6.0(flushleftbox3,3)R3H3,4>12.22937H3,4R4>6.0(flushleftbox3,2)R3H3,4>12.22937H3,4R4>6.0(flushleftbox3,1)R3H3,4>12.22937H2,3R3>6.0(flushleftbox2,4)R2H2,3>15.25376H2,3R3>8.257013(flushleftbox2,3)R2H2,3>15.25376H2,3R3>6.0(flushleftbox2,2)R2H2,3>15.25376H2,3R3>8.257013(flushleftbox2,1)R2H2,3>15.25376H1,2R2>8.482721(flushleftbox1,3)R1H1,2>15.25376H1,2R2>8.482721(flushleftbox1,1)R1H1,2>15.25376H0,1R1>8.482721(flushleftbox0,1)R0H0,1>15.25376Figure5-18.THEROWCONSTRAINTSGENERATEDforthetableinFigure5-6.ThevariablesfortherowgridlinepositionsareR0,R1,R2,R3,R4,R5andthehorizontalalignmentlinepositionsareH0,1,H1,2,H2,3,H3,4,H4,5.sfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFb g`;#y^/#%(TVm$V|]$O(TVm$t^/&4y(^/],TVm$|]).TVm$t^/*(^/t^/,^/<@CEy\C#%0TVm$$|[$#LTVm$t\C%4y'\C[NTVm$|[(CPTVm$t\C*(\Ct\C,yZX#%T TVm$|Z$O^TVm$tZX&4y(ZXZbTVm$|Z)dTVm$tZX*(ZXtZX,ZX<@CEyXl#%fTVm$$|X%$#TVm$tXl%4y'XlX%TVm$|X%(CTVm$tXl*(XltXl,yV$ TVm$|V9&TVm$tV'y)VV9TVm$|V9*TVm$tV+VtV-V<@CEyT#%TVm$$|TN$#TVm$tT%4y'TTNTVm$|TN(CTVm$tT*(TtT,yR$ TVm$|Rb&TVm$tR'y)RRbTVm$|Rb*TVm$tR+RtR-R<@CEyP#%TVm$$|Pv$#TVm$tP%4y'PPvTVm$|Pv(CTVm$tP*(PtP,yN$ TVm$|N&TVm$tN'y)NNTVm$|N*TVm$tN+NtN-N<@CEyL#%TVm$$|L$#TVm$tL%4y'LLTVm$|L(CTVm$tL*(LtL,yJ$ TVm$|J&$TVm$tJ'y)JJ(TVm$|J**TVm$tJ+JtJ-J<@CEyI #%,TVm$$|H$#BTVm$tI %4y'I HDTVm$|H(CFTVm$tI *(I tI ,yG"$J TVm$|F&TTVm$tG"'y)G"FXTVm$|F*ZTVm$tG"+G"tG"-G"<@CEyE6#%\TVm$$|D$#rTVm$tE6%4y'E6DtTVm$|D(CvTVm$tE6*(E6tE6,yCJ$z TVm$|C&TVm$tCJ'y)CJCTVm$|C*TVm$tCJ+CJtCJ-CJ<@CEyA^#%TVm$$|A$#TVm$tA^%4y'A^ATVm$|A(CTVm$tA^*(A^tA^,y?s$ TVm$|?,&TVm$t?s'y)?s?,TVm$|?,*TVm$t?s+?st?s-?s<@CEy=#%TVm$$|=@$#TVm$t=%4y'==@TVm$|=@(CTVm$t=*(=t=,y;$ TVm$|;T&TVm$t;'y);;TTVm$|;T*TVm$t;+;t;-;<@CEy9#%TVm$$|9i$#TVm$t9%4y'99iTVm$|9i(CTVm$t9*(9t9,y7$ TVm$|7}&TVm$t7'y)77}TVm$|7}*TVm$t7+7t7-7<@CEy5#%TVm$$|5$#2TVm$t5%4y'554TVm$|5(C6TVm$t5*(5t5,y3#%: TVm$|3$ODTVm$t3&4y(33HTVm$|3)JTVm$t3*(3t3,3<@CEy2#%LTVm$$|1$#hTVm$t2%4y'21jTVm$|1(ClTVm$t2*(2t2,y0$p TVm$|/&zTVm$t0'y)0/~TVm$|/*TVm$t0+0t0-0<@CEy.)#%TVm$$|-$#TVm$t.)%4y'.)-TVm$|-(CTVm$t.)*(.)t.),y,=#% TVm$|+$OTVm$t,=&4y(,=+TVm$|+)TVm$t,=*(,=t,=,,=<@CEy*Q#%TVm$$|* $#TVm$t*Q%4y'*Q* TVm$|* (CTVm$t*Q*(*Qt*Q,y(e#% TVm$|($OTVm$t(e&4y((e(TVm$|()TVm$t(e*((et(e,(e<@CEy&y#%TVm$$|&3$#TVm$t&y%4y'&y&3TVm$|&3(CTVm$t&y*(&yt&y,y$#% TVm$|$G$OTVm$t$&4y($$GTVm$|$G)TVm$t$*($t$,$<@CEy"#%TVm$$|"[$#:TVm$t"%4y'""[<TVm$|"[(C>TVm$t"*("t",y #%B TVm$| p$OLTVm$t &4y( pPTVm$| p)RTVm$t *( t , <@CEy#%TTVm$$|$#pTVm$t%4y'rTVm$|(CtTVm$t*(t,v g|du #Tv*-/z248< >D gq=} z|z v }!rz|z"pv"}#z|z$v%d}&Az|z'>v'}(z|z)v*3}+z|z, v-/2 8>A g}|vP},|Vv}|v}|$v}a|v g;#xTVm$5ANEWFRAMEWORKFORTABULARCOMPOSITION5-422.0C1C0C3=02.0C2C1C3=0C0V0,1>3.0(flushleftbox4,0)C1V0,1>69.31976C0V0,1>3.0(flushleftbox3,0)C1V0,1>55.72097C5C4>24.0675(centerbox4,4)2.0V4,5C4C5=0C4C3>60.2025(centerbox4,3)2.0V3,4C3C4=0C3C2>24.0675(centerbox4,2)2.0V2,3C2C3=0C2C1>60.2025(centerbox4,1)2.0V1,2C1C2=0C5C4>24.0675(centerbox3,4)2.0V4,5C4C5=0C4C3>60.2025(centerbox3,3)2.0V3,4C3C4=0C3C2>24.0675(centerbox3,2)2.0V2,3C2C3=0C2C1>60.2025(centerbox3,1)2.0V1,2C1C2=0C5C4>30.86088(centerbox2,4)2.0V4,5C4C5=0C4C3>63.23784(centerbox2,3)2.0V3,4C3C4=0C3C2>30.86088(centerbox2,2)2.0V2,3C2C3=0C2C1>63.23784(centerbox2,1)2.0V1,2C1C2=0C5C3>88.15895(centerbox1,3)2.0V3,5C3C5=0C3C1>73.83745(centerbox1,1)2.0V1,3C1C3=0C5C1>159.6822(centerbox0,1)2.0V1,5C1C5=0Figure5-18(continued).THECOLUMNCONSTRAINTSGENERATEDforthetableinFigure5-6.Thefirsttwoconstraintsaretheauxiliaryconstraintstoforcetheequalcolumnwidths;therestaregeneratedbythetablelayoutalgorithm.ThevariablesforthecolumngridlinepositionsareC0,C1,C2,C3,C4,C5andtheverticalalignmentlinepositionsareV0,1,V1,2,V1,3,V1,5,V2,3,V3,4,V3,5,V4,5.sfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFb g`;#t^/"$i^/y^/%,TVm$^|]&,TVm$t^/'(y) ^/].TVm$|]* 0TVm$t^/+y-^/]2TVm$|]-4TVm$t^//0\C"$i\Cy\C%6TVm$|[&>TVm$t\C'(y) \C[@TVm$|[* BTVm$t\C+y-\C[DTVm$|[-FTVm$t\C/0yZX$HTVm$|Z%LTVm$tZX'y(ZXZNTVm$|Z)PTVm$tZX+ZXtZX-ZX<@CEyXl#;TTVm$$|X%$9jTVm$tXl%Jy'/XlX%lTVm$|X%(-nTVm$tXl*XltXl+yV$r TVm$|V9%|TVm$tV'y(VV9~TVm$|V9)TVm$tV+VtV-V<@CEyT#;TVm$$|TN$9TVm$tT%Jy'/TTNTVm$|TN(-TVm$tT*TtT+yR# TVm$|Rb$TVm$tR& y'RRbTVm$|Rb(TVm$tR*RtR+R>iCEP"F#PyP$TVm$)|Pv%TVm$tP'y)wPPvTVm$|Pv*uTVm$tP+y-kPPvTVm$|Pv.iTVm$tP/z1_yN#TVm$|N$TVm$tN& y'NNTVm$|N(TVm$tN*NtN+N>iCEL"F#LyL$TVm$)|L%TVm$tL'y)wLLTVm$|L*uTVm$tL+y-kLLTVm$|L.i TVm$tL/z1_yJ# TVm$|J$TVm$tJ& y'JJTVm$|J(TVm$tJ*JtJ+J>iCEI"F#IyI$TVm$)|H%2TVm$tI'y)wIH6TVm$|H*u8TVm$tI+y-kIH:TVm$|H.i<TVm$tI/z1_yG"#>TVm$|F$BTVm$tG"& y'G"FDTVm$|F(FTVm$tG"*G"tG"+G">iCEE6"F#E6yE6$HTVm$)|D%dTVm$tE6'y)wE6DhTVm$|D*ujTVm$tE6+y-kE6DlTVm$|D.inTVm$tE6/z1_yCJ#pTVm$|C$tTVm$tCJ& y'CJCvTVm$|C(xTVm$tCJ*CJtCJ+CJ>iCEA^"F#A^yA^$zTVm$)|A%TVm$tA^'y)wA^ATVm$|A*uTVm$tA^+y-kA^ATVm$|A.iTVm$tA^/z1_y?s#TVm$|?,$TVm$t?s& y'?s?,TVm$|?,(TVm$t?s*?st?s+?s>iCE="F#=y=$TVm$)|=@%TVm$t='y)w==@TVm$|=@*uTVm$t=+y-k==@TVm$|=@.iTVm$t=/z1_y;#TVm$|;T$TVm$t;& y';;TTVm$|;T(TVm$t;*;t;+;>iCE9"F#9y9$TVm$)|9i%TVm$t9'y)w99iTVm$|9i*uTVm$t9+y-k99iTVm$|9i.iTVm$t9/z1_y7#TVm$|7}$ TVm$t7& y'77} TVm$|7}(TVm$t7*7t7+7>iCE5"F#5y5$TVm$)|5%,TVm$t5'y)w550TVm$|5*u2TVm$t5+y-k554TVm$|5.i6TVm$t5/z1_y3#8TVm$|3$<TVm$t3%y'33>TVm$|3(@TVm$t3)3t3+3>iCE2"F#2y2$BTVm$)|1%^TVm$t2'y)w21bTVm$|1*udTVm$t2+y-k21fTVm$|1.ihTVm$t2/z1_y0#jTVm$|/$nTVm$t0%y'0/pTVm$|/(rTVm$t0)0t0+0>iCE.)"F#.)y.)$tTVm$)|-%TVm$t.)'y)w.)-TVm$|-*uTVm$t.)+y-k.)-TVm$|-.iTVm$t.)/z1_y,=#TVm$|+$TVm$t,=%y',=+TVm$|+(TVm$t,=),=t,=+,=>iCE*Q"F#*Qy*Q$TVm$)|* %TVm$t*Q'y)w*Q* TVm$|* *uTVm$t*Q+y-k*Q* TVm$|* .iTVm$t*Q/z1_y(e#TVm$|($TVm$t(e%y'(e(TVm$|((TVm$t(e)(et(e+(e>iCE&y"F#&yy&y$TVm$)|&3%TVm$t&y'y)w&y&3TVm$|&3*uTVm$t&y+y-k&y&3TVm$|&3.iTVm$t&y/z1_y$#TVm$|$G$TVm$t$%y'$$GTVm$|$G(TVm$t$)$t$+$>iCE""F#"y"$ TVm$)|"[%&TVm$t"'y)w""[*TVm$|"[*u,TVm$t"+y-k""[.TVm$|"[.i0TVm$t"/z1_y #2TVm$| p$6TVm$t %y' p8TVm$| p(:TVm$t ) t + >iCE"F#y$<TVm$)|%XTVm$t'y)w\TVm$|*u^TVm$t+y-k`TVm$|.ibTVm$t/z1_y#dTVm$|$hTVm$t%y'jTVm$|(lTVm$t)t+>iCE"F#y$nTVm$)|%TVm$t'y)wTVm$|*uTVm$t+y-kTVm$|.iTVm$t/z1_v g |$S ,v469"<>+B g@" % &2 -6.2l48s=EADV g< '*0h249<?BE} g| ev }|vY}5|3v}|v'}|v}k|ivzy$W*-U3}5x|6jv7}8|9v:};|<}>)?|?}AYB5|C'}D g| Yv}|v}|v g ;#QTVm$=5ANEWFRAMEWORKFORTABULARCOMPOSITION5-435.5.4HandlingLargeTablesTheconstraintschemejustoutlinedsuffersfromrapidgrowthintheproblemsizeasthetablesgrowlarger.Severalstrategiescangreatlyreducethenumberofconstraintsgenerated.Thefirststrategyeliminatesredundantvariableswhenevertheyappearasaliasesofothervariables.Forexample,theboxpositionXkisoftenanaliasforVleftGridk,rightGridkwhentheyaresetequalandthereforeXkcanbeeliminated.Inmanytablelayouts,asimplifyingassumptionmaybemadetosolvetherowandcolumnconstraintsseparately.Treatingthetwosetsofconstraintsindependentlyreducesthenumberofconstraintsandthesizeofthecorrespondingconstrainttableau.Itisworthassessingthenecessityofthisassumptionandthesituationsinwhichitisviolated.Theindependenceassumptiondoesnotholdwhenonewantstocreategriddesignswithmodulesthataresquareorhavespecificaspectratios.Asquaremoduleresultsfromconstrainingtherowheighttoequalthecolumnwidth.Obviously,inthissituationthesetsofrowandcolumnconstraintsarenotindependent.Theassumptionisalsonottruewhentryingtodistributewhitespacewithinatable,forexample,byfoldingwidehorizontally-orientedtableentriestotradeoffmoreverticaldepthforlesshorizontalwidth.Inthissituation,decreasingthecolumnwidthincreasestherowheightandtheconstraintsareagainnotindependent.Theindependenceassumptioncanbetestedautomaticallybyexaminingthevariablesineachconstraint.Constraintsthatmixrowandcolumnvariables,suchasonespecifyingthatarowheightequalsacolumnwidth,areinterdependentandmustbesolvedsimultaneously.Constraintsthatdonotmixvariablesareindependentandcanbesolvedseparatelyassmallerproblems.Theprototypecurrentlyassumesthattherowandcolumnconstraintsareindependent,butonecouldeasilychecktheexplicitlysuppliedconstraintsforviolationsofthisassumptionandthusdetermineautomaticallywhethertosolvethetablelayoutconstraintsindependentlyornot.Whatisthecostofsolvinginterdependentrowandcolumnconstraints?Whenthetwosetsarecombinedintoasingleconstraintsystemtheproblemsizeisdoubled.SincetheconstraintsolvertakesO(n3)timeonaverage,thecombinedconstraintlayoutwouldrequireaboutfourtimesasmuchasthesumofthetwosmallerindependentcomputations.sfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbs^ gTCr[  #*@/38=?X g:>#)/t 69?DuV g  S $r,k3K:>jCQ g # *,0 w6oQQ8yQ87rQ9:?AXEwOL gyO hTVm$pN hTVm$tOyOOj TVm$pN[tTVm$rOL !$' +.w5OLOyO7rOL8{;= LFn ! * 3<69.=?CJ g !$ )03X69; G g 78 &F(W 0369;E g ) %'Z)-47>j@{C} g Z3 "$)m+,@w  &Q*%-05^8=:??D>E g2"'*.38>k@G< gg $'+012669?9 g  #k&(+/55( =b@,7 g ^ #$(+.279 5{ g @"p)k+1|5x3I g}#(-023L ;@B1 g  u$h)/26&;8>z. g k +  &Q)_+0v :<D) gGK ! *s-14n7= 'z g<@t 6 !%H*Z/y06;%G g 0!&2 ;>A_DR# gG "%(;-Y 57<E g!M$'*.4 : C$~ g  !%(0t :@BL g@V[ +e-F6 2# /C25;  gQ*_Q$(c).| 6;w>PD g $)Qw-r.w/]ntn0Br02"58W> g  %+q038:!>@C| gxQC # vTVm$5ANEWFRAMEWORKFORTABULARCOMPOSITION5-44Areductioninthenumberofconstraintscanalsobeachievedbyobservingthestructureoftheconstraintinequalities.Theconstraintsthatdeterminethegridpositionssurroundingaparticulartableentryareallsimilar:VleftGridk,rightGridkCleftGridk>leftOffsetk(5)CrightGridkVleftGridk,rightGridk>rightOffsetk.Forthesetoftableentrieswithinaparticularcolumn,theseinequalitiesaredominatedbyasinglemaximumvalueoftherighthandside.Themaximumvaluecouldbedeterminedbysimplermeansthanexpressingsomanyredundantconstraints.Wecandiscoverthevaluebyalinearpreprocessingpassthroughallthetableentriesinthatparticularcolumntodeterminethemaximumleftandrightoffsets.Thetwomaximumvaluesareassignedtonewvariablesusedbytheconstraintsolver:maxLeftleft,right=max{leftOffsetkforallboxeskincolumnleft,right}maxRightleft,right=max{rightOffsetkforallboxeskincolumnleft,right}.Withthesemaximumvaluesknownbythesevariablenames,thesetofinequalitiespercolumn(oneormoreconstraintforeachtableentry)canbereplacedbyoneinequalitypercolumn.Thisvastlyreducesthenumberofconstraintsfromtheproductofthenumberofentriespercolumntimesthenumberofcolumnstosimplythenumberofcolumns:Vleft,rightCleft>maxLeftleft,right(5()CrightVleft,right>maxRightleft,right.Afurtheroptimizationinthelinearconstraintsolvercanbemadebasedontheobservationthatmostoftheconstraintinequalitieshaveonlytwovariableterms.Thus,sparsematrixtechniquesmightreducethespacerequirementsofthesolverattheexpenseofmoreoverheadintheconstraintsolver.Theprototypeimplementationusesaconventionalmatrixstructurefortheconstrainttableau.5.5.5TheLayoutAlgorithmThecompletetablelayoutalgorithmincludingtheconstraintsolvercannowbepresented.Thealgorithmrequiresthegriddatastructureforthetablearrangementandthecontentsofallofitstableentries.Thefirststepinthealgorithmensuresthatthedimensionsofallofthetableentriesareknown.Thesedimensionsareprovidedbyinvokingtheparticularlayoutalgorithmforeachtableentryobject.Intheeventthatatableentrycontainsanothersfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^$ & .U1b47=@H\ g@#4 " ,m/ 8;oC>Z g ! (- 1U4 6swWDyWGtTVm$pWTVm$tWG y WGWG!b TVm$pW&8TVm$rW'vw)WWGyWG* TVm$pW/_TVm$rWz0WrWw2WW3RyWG9KrWEwTyT@ TVm$,pSL$TVm$rT w"TT@yT@$& TVm$pS(r0TVm$tT@)y)jT@T@)2 TVm$pS.<TVm$rTz0TrTw2@TT2 yT@9rT;,Q gt% x%& .p49 AON gg$)O+`.9256f:>AM gZ l"(-1 9;@FJ g "9%)x+->1 <=?FH g@V %+r-w5F8?BF gc5%*,3c5h8?CDR g@ wALmyAf rALEw"ALAL"yA(rAL),.w3ALrAL5&7*w=ALAL=r?YALwAL?rCALALw>Ey= r>Emw!>E>E"% y=) r>E*s-"/vw4>Er>E57w=>E>E>r?>Ew>E@GrC>E>EE ;? g!')w-399 g % !#(9 /26X:n?KBY6 gh Q#D*>-28;xA4 g !#&,.4<7/="A2v g?C"%o+-w/o5y/)et B/)y/) r/o#w&D/o/)y/)'tr/oz)/or/ow,./o/o-|y/)2' r/oEzF/or/oG]w,hy,"r,h Sw",h,"y,"#t%,"y,"%r,hz)c,hr,hw+,h,h,y,"2 r,h8-)b( "%*= 169<@E0'/ g@ u~!$h , 48 g #Q$ .o3:=;@ f gs gTar6L#Q*24 <A^Dk g C"-(+b.2y9[< >M g :"$&)+G/^59#<@B  g)  (*- /16 ;]>( g6 #&,/ 7<#C g;R #(+e,05+;>{TVm$k5ANEWFRAMEWORKFORTABULARCOMPOSITION5-45subtable,thenthelayoutalgorithmwouldbeinvokedonthatsubtablefirst.Thedimensioninformationforeachtableentryiscachedinthetableentryobjectsincetheboxdimensionsareusedtwicewhentherowandcolumnconstraintsareindependent.AlgorithmL(TableLayout)L1[DimensiontheBoxes]Determinethedimensionsofthetableentriesbyinvokingthelayoutprocedureforthatclassofobject.Rememberthedimensionssincetheyareusedforbothrowandcolumnlayout.L2[LayouttheRows]L2.1[EstablishRowConstraints]Enumeratethetablegridstructureandgeneratetheappropriateconstraintsforeachtableentry.L2.2[Solve]Invoketheconstraintsolverontherowconstraints,andrecordtherowgridcoordinates.L2.3[PositionTableEntries]Enumeratethetablegridstructureandcomputethelayoutcoordinatesoftheoriginforeachtableentryfromthecomputedgridpositions.L3[LayouttheColumns]L3.1[EstablishColumnConstraints]Enumeratethetablegridstructureandgeneratetheappropriateconstraintsforeachtableentry.L3.2[Solve]Invoketheconstraintsolveronthecolumnconstraints,andrecordthecolumngridcoordinates.L3.3[PositionTableEntries]Enumeratethetablegridstructureandcomputethelayoutcoordinatesofthealignmentpositionfortheeachtableentryfromthecomputedgridpositions.5.6ConclusionsThischapterhasintroducedanewframeworkforinteractivetableformatting.Theseparationoftabletopologyfromtablegeometryhasbeenincorporatedintothisframework.Agridstructuredescribesthetopologicaltablearrangementandamathematicalconstraintsolvercomputesthetablelayout.AprototypetableformatterwasbuiltusingextensionstotheTiogasfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^ gd+&+-4/69@D\ gj w &#(,\.358k<@Z gc G"%*?.148> Xb g2 wU[o2PtRUrRUS 7"'0-3 ;=@P"S$',478:>i@zMS! *W.z2&48;?dBKSFtHrHSmFtErE !!% .7C:>3AC~#&\ /4 7n:=B t@xr@x%5( /4x69= >E"$(8+ t;?r;? t%+4B7;2>9 #&+ 4G6X91=@6"&(04 t3r3SmFt0r0 !!' 1Q9<@. #*e-> 6 >QA,it)br)b%5( /4x69? '0"$*.S t$)r$) t%+4B7;2>!#&+ 4G6X91@R+"'+`/v2O:=| q g roUH $&)14 < g  "'-16=D@7\ g } %'+R259K<$ * g} Q ( 0u5C<? gsO'1*e.U2 :<?TVm$5ANEWFRAMEWORKFORTABULARCOMPOSITION5-46documentmodelandtothestylemachinery.Unlikemanyotherdocumentformattingsystems,thisapproachallowsmoregeneraltabledesignstobedescribedandeditedwithinteractivetools.ThegridstructureprovidesanexplicitrepresentationofthetabletopologysuitableforWYSIWYGinteractiveeditingoftables.Thegridstructurerepresentsareasdirectly,permittingsymmetrictreatmentofrowsandcolumns,andenablingtypographicrulesandbackgroundareastobetreatedexplicitly.Animplementationofthegridstructureexistswithlinearalgorithmssuitableforinteractivemanipulationwhichsupportselectionhierarchiesoftablestructures,tableentries,row,columns,andtheentiretable.Supportforoverlappingtabledesignsispossible;backgroundsareeasy.Themathematicalconstraintsolvercomputesthetablegeometryfromlinearinequalitiesthatexpressthetablealignmentpossibilities.Mostoftheinequalitiesaregeneratedautomaticallyfromalignmentandpositioningstyleattributes,whileadditionalconstraintsmaybespecifiedbythetabledesignertoenforcespeciallayoutrequirements.Thetableobjectclassinthedocumentmodelpermitstablestoexistwithindocumentsandbeinteractivelyeditedbyappropriateclasseditors.Tablesmaycontainarbitrarycontentsinceatableentryistreatedasanarbitrarydocumentobject.Styleattributesfortablesaremanagedbyextensionstothestylemachinery.NewattributesfortablealignmentandvarioustypographicfeaturesuniquetotableshavebeenaddedtothestylemechanismofChapter3.Asearchpathappropriatetotherow/columnstructureoftabularinformationdeterminesthevaluesofattributesinforceateachtableentry.Theprototypetableformatterworkedwellforthetablesinthisthesis.AllofthetablesinChapter4,thecomplextableinFigure5-3,andtheremainingtablesinChapter5wereformattedbytheprototype.Thegridsystemprovedtobeasimpleconcepttoworkwith,andcreatingadditionallinearinequalityconstraintsforspecialeffectsappearstohaveconsiderablepromiseforextendingthekindsofachievabletabledesigns.Severalofthelargetablesbecametedioustomanipulateintheirtextualform,acomplaintthatwillberemediedwiththecompletionofaninteractivetableeditor.AnimplementationofaninteractivetableeditorwithinTiogabasedonthisprototypeisunderway.GoalsofthisfurtherworkaredescribedinChapter6.sfc%vpffWsfWv_ff]f&sf*Mv+qff,dsf1v3ff4%ufE#fEfFbr^ g.pu!N%" .;38B<\ g %H*L.4`8v>A@EZ g 'Wy$%&x,D 79;@U\ gt2U\U\rU\ %*,2s59T@7 S) g &.p04o7>P g . 7#y ,025: BN g ?P) '+/4V J` g}; $1' +07;9 BH. g2 $s'>E( C $)138??CTB g %M!&%=, 6;=@ g %} )-5j8 A4> g  R (,*.~5`7:>EA<^ gL 9X6 !$,17<@>EB7& gR #(+ 37>*Cp4 g?#$u(,.468l?32 gY}  y%/'/1c 9Y;^>70 g s #o'/:2|89 AH.] g %'*.X69 ?jA,* gyA  " ,m3P5a; ) g  &(,D..26&&+/j249;>Di$ gxQ h D#)-/5)8k;>" g ~&(+ 4I7;)@F  [ g f!%)/^ 7!; ) g Q!')- 7c=@a g@ !(.03s7<=B= gk "d&(H/3[68@.C g b !f%}+T. 9<>[ _ g}Ml#&()Q02;(?A- g- ^"b(jTVm$n TIMESROMAN TIMESROMAN TIMESROMAN TIMESROMAN  TIMESROMAN LAUREL HELVETICA  XEROXBOOK TIMESROMAN  HELVETICA HELVETICA HELVETICAGACHAY HELVETICA TIMESROMAN$ HELVETICA OLDENGLISH MATH XEROXBOOK TIMESROMAN TIMESROMAN HIPPOY MATHY TIMESROMAN HELVETICAY TIMESROMANY TIMESROMAN HELVETICA TIMESROMAN TIMESROMANY TIMESROMANY TIMESROMAN TIMESROMAN " ,/2a ksLOb3 8 W L  0i  )!b'\/j/42p[]<>Beach>Thesis>Chapter5.TiogaSunday, May 5, 1985 8:42 am PDT