Friday 12 February 2010

DIVs-tree size-measure and offset-calculation recurcive-algorithm, O(n)

<div> Tree size-measure and offset-calculation recurcive-algorithm, O(n) complexity

I have a tree of <div>s and want a rendering algorithm to calculate total size and detailed offests, so, each <div> will implement the following recursive algorithm.

<div style="block">

   <div style="block"><div style="inline"></div><div style="inline"></div><div style="inline"></div></div>
   <div style="block"><div style="inline"></div><div style="inline"></div><div style="inline"></div></div>
   <div style="block"><div style="inline"></div><div style="inline"></div><div style="inline"></div></div>
</div>


Measure Algorithm:
. I'm <div> object, that is the single input to the algorithm
. I have mySize of (X,Y) and myOffset of (x,y)
. Initilaize a runningOffset to equal myOffset
. Initialize runningInnerSize with (0,0)
. Loop through my children:
    . If child flow is INLINE, then, set child offset to runningOffset
    . If child flow is BLOCK, then, set child offset as follows:
        . childOffset.x = myOffset.x
        . childOffset.y = myOffset.y + runningInnserSize.height
    . Calculate childSize by recursive call to Measure Algorithm
        . childSize = Measure Algorithm
    . If child flow is INLINE:
        . Increment runningInnerSize.width by childSize.width
        . Keep runningInnerSize.height unchanged if it is longer than childSize.height
           . else  runningInnerSize.height=childSize.height
        . Prepare runningOffset for next sibling "next child"
           . runningOffset.x increment by childSize.width
    . If child flow is BLOCK:
        . Increment runningInnerSize.height by childSize.height

        . Keep runningInnerSize.width unchanged if it is longer than childSize.width
           . else runningInnerSize.width = childSize.width
        . Prepare runningOffset for next sibling "next child"
            . runningOffset.x increment by childSize.width
    . Change my size to srround runningInnerSize
    . Keep track of runningInnerSize for latter use

    . Return my size to the caller
. End of Algorithm

No comments:

Post a Comment