v3_Last

Option Explicit

Private Const EPS As Double = 0.000001
Private Const ROLL_GAP As Double = 5#
Private Const MAX_ROLLS As Long = 100

Private Const MAX_RIGHT_WASTE As Double = 10#
Private Const ALIGN_TOLERANCE As Double = 0.5

' Local search
Private Const MAX_LOCAL_SEEDS As Long = 5
Private Const MAX_PAIR_MOVES As Long = 80
Private Const MAX_REINSERT_MOVES As Long = 100
Private Const MAX_TRIPLE_MOVES As Long = 40
Private Const MAX_LOCAL_PASSES As Long = 3

Private Type TBanner
    Label As String
    OrigW As Double
    OrigH As Double
    margin As Double
End Type

Private Type TFreeRect
    x As Double
    y As Double
    w As Double
    h As Double
End Type

Private Type TPlaced
    rid As Long
    x As Double
    y As Double
    w As Double
    h As Double
    Rotated As Boolean
End Type

Private Type TRoll
    placed() As TPlaced
    placedCount As Long
    UsedHeight As Double
End Type

Private Function MinD(ByVal a As Double, ByVal b As Double) As Double
    If a < b Then
        MinD = a
    Else
        MinD = b
    End If
End Function

Private Function MaxD(ByVal a As Double, ByVal b As Double) As Double
    If a > b Then
        MaxD = a
    Else
        MaxD = b
    End If
End Function

Private Function AbsD(ByVal a As Double) As Double
    If a < 0# Then
        AbsD = -a
    Else
        AbsD = a
    End If
End Function

Private Function AreaOf(ByRef item As TBanner) As Double
    AreaOf = (item.OrigW + 2# * item.margin) * (item.OrigH + 2# * item.margin)
End Function

Private Function SortValue(ByRef item As TBanner, ByVal sortMode As Long) As Double
    Dim w As Double
    Dim h As Double
    Dim shortSide As Double
    Dim longSide As Double

    w = item.OrigW + 2# * item.margin
    h = item.OrigH + 2# * item.margin

    shortSide = MinD(w, h)
    longSide = MaxD(w, h)

    Select Case sortMode
        Case 1
            SortValue = w * h
        Case 2
            SortValue = w
        Case 3
            SortValue = h
        Case 4
            SortValue = shortSide
        Case 5
            SortValue = longSide
        Case 6
            If shortSide > EPS Then
                SortValue = longSide / shortSide
            Else
                SortValue = 0#
            End If
        Case Else
            SortValue = w * h
    End Select
End Function

Private Sub SortIndex(ByRef items() As TBanner, ByRef sourceIdx() As Long, ByVal n As Long, ByVal sortMode As Long, ByRef sortedIdx() As Long)
    Dim i As Long
    Dim j As Long
    Dim tmp As Long

    ReDim sortedIdx(1 To n)

    For i = 1 To n
        sortedIdx(i) = sourceIdx(i)
    Next i

    For i = 1 To n - 1
        For j = i + 1 To n
            If SortValue(items(sortedIdx(j)), sortMode) > SortValue(items(sortedIdx(i)), sortMode) Then
                tmp = sortedIdx(i)
                sortedIdx(i) = sortedIdx(j)
                sortedIdx(j) = tmp
            End If
        Next j
    Next i
End Sub

Private Sub BuildInitialOrder(ByRef items() As TBanner, ByVal n As Long, ByVal sortMode As Long, ByRef order() As Long)
    Dim sourceIdx() As Long
    Dim i As Long

    ReDim sourceIdx(1 To n)
    ReDim order(1 To n)

    For i = 1 To n
        sourceIdx(i) = i
    Next i

    SortIndex items, sourceIdx, n, sortMode, order
End Sub

Private Sub CopyOrder(ByRef source() As Long, ByRef target() As Long, ByVal n As Long)
    Dim i As Long

    ReDim target(1 To n)

    For i = 1 To n
        target(i) = source(i)
    Next i
End Sub

Private Sub SwapLong(ByRef arr() As Long, ByVal i As Long, ByVal j As Long)
    Dim tmp As Long

    tmp = arr(i)
    arr(i) = arr(j)
    arr(j) = tmp
End Sub

Private Sub MoveItemOrder(ByRef arr() As Long, ByVal fromPos As Long, ByVal toPos As Long, ByVal n As Long)
    Dim value As Long
    Dim i As Long

    If fromPos = toPos Then Exit Sub

    value = arr(fromPos)

    If fromPos < toPos Then
        For i = fromPos To toPos - 1
            arr(i) = arr(i + 1)
        Next i
    Else
        For i = fromPos To toPos + 1 Step -1
            arr(i) = arr(i - 1)
        Next i
    End If

    arr(toPos) = value
End Sub

Private Function RectsIntersect(ByRef a As TFreeRect, ByRef b As TFreeRect) As Boolean
    If a.x >= b.x + b.w - EPS Then
        RectsIntersect = False
        Exit Function
    End If

    If b.x >= a.x + a.w - EPS Then
        RectsIntersect = False
        Exit Function
    End If

    If a.y >= b.y + b.h - EPS Then
        RectsIntersect = False
        Exit Function
    End If

    If b.y >= a.y + a.h - EPS Then
        RectsIntersect = False
        Exit Function
    End If

    RectsIntersect = True
End Function

Private Function IsContained(ByRef a As TFreeRect, ByRef b As TFreeRect) As Boolean
    If a.x + EPS < b.x Then
        IsContained = False
        Exit Function
    End If

    If a.y + EPS < b.y Then
        IsContained = False
        Exit Function
    End If

    If a.x + a.w > b.x + b.w + EPS Then
        IsContained = False
        Exit Function
    End If

    If a.y + a.h > b.y + b.h + EPS Then
        IsContained = False
        Exit Function
    End If

    IsContained = True
End Function

Private Sub PruneFree(ByRef freeRects() As TFreeRect, ByRef freeCount As Long)
    Dim i As Long
    Dim j As Long
    Dim k As Long
    Dim contained As Boolean

    If freeCount <= 1 Then Exit Sub

    i = 1

    Do While i <= freeCount

        contained = False

        For j = 1 To freeCount
            If i <> j Then
                If IsContained(freeRects(i), freeRects(j)) Then
                    contained = True
                    Exit For
                End If
            End If
        Next j

        If contained Then

            For k = i To freeCount - 1
                freeRects(k) = freeRects(k + 1)
            Next k

            freeCount = freeCount - 1

        Else
            i = i + 1
        End If

    Loop

    If freeCount <= 0 Then
        ReDim freeRects(1 To 1)
    Else
        ReDim Preserve freeRects(1 To freeCount)
    End If
End Sub

Private Sub AddIfValid(ByRef arr() As TFreeRect, ByRef count As Long, ByVal x As Double, ByVal y As Double, ByVal w As Double, ByVal h As Double)
    If w <= EPS Then Exit Sub
    If h <= EPS Then Exit Sub

    count = count + 1

    arr(count).x = x
    arr(count).y = y
    arr(count).w = w
    arr(count).h = h
End Sub

Private Sub PlaceAndSplit(ByRef freeRects() As TFreeRect, ByRef freeCount As Long, ByVal placedX As Double, ByVal placedY As Double, ByVal placedW As Double, ByVal placedH As Double)
    Dim oldCount As Long
    Dim newCount As Long
    Dim maxNew As Long
    Dim i As Long

    Dim fr As TFreeRect
    Dim placed As TFreeRect
    Dim tmp() As TFreeRect

    oldCount = freeCount

    If oldCount <= 0 Then Exit Sub

    maxNew = oldCount * 4 + 10

    ReDim tmp(1 To maxNew)

    placed.x = placedX
    placed.y = placedY
    placed.w = placedW
    placed.h = placedH

    For i = 1 To oldCount

        fr = freeRects(i)

        If Not RectsIntersect(fr, placed) Then

            AddIfValid tmp, newCount, fr.x, fr.y, fr.w, fr.h

        Else

            AddIfValid tmp, newCount, fr.x, fr.y, placed.x - fr.x, fr.h

            AddIfValid tmp, newCount, placed.x + placed.w, fr.y, (fr.x + fr.w) - (placed.x + placed.w), fr.h

            AddIfValid tmp, newCount, fr.x, fr.y, fr.w, placed.y - fr.y

            AddIfValid tmp, newCount, fr.x, placed.y + placed.h, fr.w, (fr.y + fr.h) - (placed.y + placed.h)

        End If

    Next i

    If newCount <= 0 Then
        ReDim freeRects(1 To 1)
        freeCount = 0
        Exit Sub
    End If

    ReDim freeRects(1 To newCount)

    For i = 1 To newCount
        freeRects(i) = tmp(i)
    Next i

    freeCount = newCount

    PruneFree freeRects, freeCount
End Sub

Private Function PlacementScore(ByRef fr As TFreeRect, ByVal rw As Double, ByVal rh As Double, ByVal fitMode As Long) As Double
    Dim leftoverW As Double
    Dim leftoverH As Double
    Dim shortSide As Double
    Dim longSide As Double
    Dim areaWaste As Double

    leftoverW = fr.w - rw
    leftoverH = fr.h - rh

    shortSide = MinD(leftoverW, leftoverH)
    longSide = MaxD(leftoverW, leftoverH)

    areaWaste = (fr.w * fr.h) - (rw * rh)

    Select Case fitMode

        Case 1
            PlacementScore = shortSide

        Case 2
            PlacementScore = areaWaste

        Case 3
            PlacementScore = longSide

        Case Else
            PlacementScore = shortSide

    End Select
End Function

' --------------------------------------------------------------------
' VISUAL ALIGNMENT
'
' Internal nesting still uses CorelDRAW mathematical Y:
'     y = 0 is mathematical bottom.
'
' But when rendered visually, we flip Y.
'
' Therefore:
'     visual TOP edge      -> internal y
'     visual BOTTOM edge   -> internal y + h
'
' This is the important V3 correction.
' --------------------------------------------------------------------

Private Function AlignmentPenalty(ByRef placed() As TPlaced, ByVal placedCount As Long, ByVal x As Double, ByVal y As Double, ByVal w As Double, ByVal h As Double) As Double

    Dim i As Long

    Dim leftDist As Double
    Dim visualTopDist As Double

    Dim bestLeft As Double
    Dim bestTop As Double

    Dim candidateVisualTop As Double
    Dim existingVisualTop As Double

    If placedCount <= 0 Then
        AlignmentPenalty = 0#
        Exit Function
    End If

    bestLeft = 1E+30
    bestTop = 1E+30

    ' Visual TOP corresponds to internal y.
    candidateVisualTop = y

    For i = 1 To placedCount

        leftDist = AbsD(x - placed(i).x)

        ' IMPORTANT:
        ' use y, not y + h, for visual top alignment
        existingVisualTop = placed(i).y

        visualTopDist = AbsD(candidateVisualTop - existingVisualTop)

        If leftDist < bestLeft Then
            bestLeft = leftDist
        End If

        If visualTopDist < bestTop Then
            bestTop = visualTopDist
        End If

    Next i

    If bestLeft <= ALIGN_TOLERANCE Then
        bestLeft = 0#
    End If

    If bestTop <= ALIGN_TOLERANCE Then
        bestTop = 0#
    End If

    AlignmentPenalty = bestLeft + bestTop
End Function

Private Function IsBetterPlacement(ByVal score As Double, ByVal alignScore As Double, ByVal tieY As Double, ByVal tieX As Double, ByVal bestScore As Double, ByVal bestAlign As Double, ByVal bestY As Double, ByVal bestX As Double) As Boolean

    If score < bestScore - EPS Then
        IsBetterPlacement = True
        Exit Function
    End If

    If AbsD(score - bestScore) <= EPS Then

        If alignScore < bestAlign - EPS Then
            IsBetterPlacement = True
            Exit Function
        End If

        If AbsD(alignScore - bestAlign) <= EPS Then

            If tieY < bestY - EPS Then
                IsBetterPlacement = True
                Exit Function
            End If

            If AbsD(tieY - bestY) <= EPS Then

                If tieX < bestX - EPS Then
                    IsBetterPlacement = True
                    Exit Function
                End If

            End If

        End If

    End If

    IsBetterPlacement = False
End Function

Private Function FindBestPlacement(ByRef freeRects() As TFreeRect, ByVal freeCount As Long, ByVal reqW As Double, ByVal reqH As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef placed() As TPlaced, ByVal placedCount As Long, ByRef bestX As Double, ByRef bestY As Double, ByRef bestW As Double, ByRef bestH As Double, ByRef bestRot As Boolean) As Boolean

    Dim i As Long

    Dim rw As Double
    Dim rh As Double

    Dim score As Double
    Dim alignScore As Double

    Dim bestScore As Double
    Dim bestAlign As Double

    Dim tieY As Double
    Dim tieX As Double
    Dim bestTieY As Double
    Dim bestTieX As Double

    Dim found As Boolean

    bestScore = 1E+30
    bestAlign = 1E+30
    bestTieY = 1E+30
    bestTieX = 1E+30

    found = False

    For i = 1 To freeCount

        rw = reqW
        rh = reqH

        If rw <= freeRects(i).w + EPS And rh <= freeRects(i).h + EPS Then

            score = PlacementScore(freeRects(i), rw, rh, fitMode)

            alignScore = AlignmentPenalty(placed, placedCount, freeRects(i).x, freeRects(i).y, rw, rh)

            tieY = freeRects(i).y
            tieX = freeRects(i).x

            If IsBetterPlacement(score, alignScore, tieY, tieX, bestScore, bestAlign, bestTieY, bestTieX) Then

                bestScore = score
                bestAlign = alignScore
                bestTieY = tieY
                bestTieX = tieX

                bestX = freeRects(i).x
                bestY = freeRects(i).y

                bestW = rw
                bestH = rh

                bestRot = False

                found = True

            End If

        End If

        If allowRotation Then

            rw = reqH
            rh = reqW

            If rw <= freeRects(i).w + EPS And rh <= freeRects(i).h + EPS Then

                score = PlacementScore(freeRects(i), rw, rh, fitMode)

                alignScore = AlignmentPenalty(placed, placedCount, freeRects(i).x, freeRects(i).y, rw, rh)

                tieY = freeRects(i).y
                tieX = freeRects(i).x

                If IsBetterPlacement(score, alignScore, tieY, tieX, bestScore, bestAlign, bestTieY, bestTieX) Then

                    bestScore = score
                    bestAlign = alignScore
                    bestTieY = tieY
                    bestTieX = tieX

                    bestX = freeRects(i).x
                    bestY = freeRects(i).y

                    bestW = rw
                    bestH = rh

                    bestRot = True

                    found = True

                End If

            End If

        End If

    Next i

    FindBestPlacement = found
End Function

' --------------------------------------------------------------------
' PACK ONE ROLL
' This version uses an explicit order.
' That allows the local search to change the nesting sequence.
' --------------------------------------------------------------------

Private Sub PackOneBinOrdered(ByRef items() As TBanner, ByRef remaining() As Long, ByVal n As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef placed() As TPlaced, ByRef placedCount As Long, ByRef outIdx() As Long, ByRef outCount As Long)

    Dim freeRects() As TFreeRect
    Dim freeCount As Long

    Dim k As Long
    Dim rid As Long

    Dim reqW As Double
    Dim reqH As Double

    Dim bestX As Double
    Dim bestY As Double
    Dim bestW As Double
    Dim bestH As Double
    Dim bestRot As Boolean

    ReDim placed(1 To n)
    ReDim outIdx(1 To n)

    placedCount = 0
    outCount = 0

    ReDim freeRects(1 To 1)

    freeCount = 1

    freeRects(1).x = 0#
    freeRects(1).y = 0#
    freeRects(1).w = rollWidth
    freeRects(1).h = maxHeight

    For k = 1 To n

        rid = remaining(k)

        reqW = items(rid).OrigW + 2# * items(rid).margin
        reqH = items(rid).OrigH + 2# * items(rid).margin

        If FindBestPlacement(freeRects, freeCount, reqW, reqH, allowRotation, fitMode, placed, placedCount, bestX, bestY, bestW, bestH, bestRot) Then

            placedCount = placedCount + 1

            placed(placedCount).rid = rid
            placed(placedCount).x = bestX
            placed(placedCount).y = bestY
            placed(placedCount).w = bestW
            placed(placedCount).h = bestH
            placed(placedCount).Rotated = bestRot

            PlaceAndSplit freeRects, freeCount, bestX, bestY, bestW, bestH

        Else

            outCount = outCount + 1
            outIdx(outCount) = rid

        End If

    Next k
End Sub

Private Sub PackMultiRollWithOrder(ByRef items() As TBanner, ByVal n As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef order() As Long, ByRef rolls() As TRoll, ByRef rollCount As Long, ByRef notPlaced As Long)

    Dim remaining() As Long
    Dim nextRemaining() As Long

    Dim placed() As TPlaced
    Dim outIdx() As Long

    Dim remainingCount As Long
    Dim outCount As Long
    Dim placedCount As Long

    Dim i As Long
    Dim safety As Long

    rollCount = 0
    notPlaced = 0

    If n <= 0 Then Exit Sub

    ReDim rolls(1 To MAX_ROLLS)
    ReDim remaining(1 To n)

    For i = 1 To n
        remaining(i) = order(i)
    Next i

    remainingCount = n

    Do While remainingCount > 0

        safety = safety + 1

        If safety > MAX_ROLLS Then
            notPlaced = remainingCount
            Exit Do
        End If

        PackOneBinOrdered items, remaining, remainingCount, rollWidth, maxHeight, allowRotation, fitMode, placed, placedCount, outIdx, outCount

        If placedCount <= 0 Then
            notPlaced = remainingCount
            Exit Do
        End If

        rollCount = rollCount + 1

        rolls(rollCount).placedCount = placedCount

        ReDim rolls(rollCount).placed(1 To placedCount)

        For i = 1 To placedCount
            rolls(rollCount).placed(i) = placed(i)
        Next i

        rolls(rollCount).UsedHeight = CalcPlacedHeight(placed, placedCount)

        If outCount <= 0 Then
            remainingCount = 0
            Exit Do
        End If

        ReDim nextRemaining(1 To outCount)

        For i = 1 To outCount
            nextRemaining(i) = outIdx(i)
        Next i

        ReDim remaining(1 To outCount)

        For i = 1 To outCount
            remaining(i) = nextRemaining(i)
        Next i

        remainingCount = outCount

    Loop
End Sub

Private Function CalcPlacedHeight(ByRef placed() As TPlaced, ByVal placedCount As Long) As Double

    Dim i As Long
    Dim h As Double

    h = 0#

    For i = 1 To placedCount
        h = MaxD(h, placed(i).y + placed(i).h)
    Next i

    CalcPlacedHeight = h
End Function

Private Function CalcMaterialUsed(ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rollWidth As Double) As Double

    Dim r As Long
    Dim total As Double

    total = 0#

    For r = 1 To rollCount
        total = total + rollWidth * rolls(r).UsedHeight
    Next r

    CalcMaterialUsed = total
End Function

Private Function CalcTrueArea(ByRef items() As TBanner, ByRef rolls() As TRoll, ByVal rollCount As Long) As Double

    Dim r As Long
    Dim i As Long
    Dim rid As Long
    Dim total As Double

    total = 0#

    For r = 1 To rollCount

        For i = 1 To rolls(r).placedCount

            rid = rolls(r).placed(i).rid

            total = total + items(rid).OrigW * items(rid).OrigH

        Next i

    Next r

    CalcTrueArea = total
End Function

Private Function CalcWaste(ByRef items() As TBanner, ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rollWidth As Double) As Double

    Dim material As Double
    Dim trueArea As Double

    material = CalcMaterialUsed(rolls, rollCount, rollWidth)
    trueArea = CalcTrueArea(items, rolls, rollCount)

    If material <= EPS Then

        CalcWaste = 1#

    Else

        CalcWaste = (material - trueArea) / material

    End If
End Function

Private Function CalcRightWaste(ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rollWidth As Double) As Double

    Dim r As Long
    Dim i As Long

    Dim rightEdge As Double
    Dim maxRightEdge As Double

    Dim waste As Double
    Dim worstWaste As Double

    worstWaste = 0#

    For r = 1 To rollCount

        maxRightEdge = 0#

        For i = 1 To rolls(r).placedCount

            rightEdge = rolls(r).placed(i).x + rolls(r).placed(i).w

            maxRightEdge = MaxD(maxRightEdge, rightEdge)

        Next i

        waste = rollWidth - maxRightEdge

        If waste < 0# Then
            waste = 0#
        End If

        worstWaste = MaxD(worstWaste, waste)

    Next r

    CalcRightWaste = worstWaste
End Function

' --------------------------------------------------------------------
' VISUAL ALIGNMENT SCORE
'
' Left = x
' Visual top = internal y
'
' So this measures alignment as it will actually appear in CorelDRAW.
' --------------------------------------------------------------------

Private Function CalcAlignmentScore(ByRef rolls() As TRoll, ByVal rollCount As Long) As Double

    Dim r As Long
    Dim i As Long
    Dim j As Long

    Dim score As Double

    Dim leftDist As Double
    Dim topDist As Double

    Dim candidateVisualTop As Double
    Dim otherVisualTop As Double

    Dim bestLeft As Double
    Dim bestTop As Double

    For r = 1 To rollCount

        For i = 1 To rolls(r).placedCount

            bestLeft = 1E+30
            bestTop = 1E+30

            candidateVisualTop = rolls(r).placed(i).y

            For j = 1 To rolls(r).placedCount

                If i <> j Then

                    leftDist = AbsD(rolls(r).placed(i).x - rolls(r).placed(j).x)

                    otherVisualTop = rolls(r).placed(j).y

                    topDist = AbsD(candidateVisualTop - otherVisualTop)

                    bestLeft = MinD(bestLeft, leftDist)
                    bestTop = MinD(bestTop, topDist)

                End If

            Next j

            If bestLeft <= ALIGN_TOLERANCE Then
                bestLeft = 0#
            End If

            If bestTop <= ALIGN_TOLERANCE Then
                bestTop = 0#
            End If

            If bestLeft < 1E+20 Then
                score = score + bestLeft
            End If

            If bestTop < 1E+20 Then
                score = score + bestTop
            End If

        Next i

    Next r

    CalcAlignmentScore = score
End Function

Private Function PackScore(ByRef items() As TBanner, ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal notPlaced As Long, ByVal rollWidth As Double, ByRef rightWaste As Double, ByRef alignmentScore As Double, ByRef materialUsed As Double) As Double

    Dim excessRight As Double

    rightWaste = CalcRightWaste(rolls, rollCount, rollWidth)
    alignmentScore = CalcAlignmentScore(rolls, rollCount)
    materialUsed = CalcMaterialUsed(rolls, rollCount, rollWidth)

    If notPlaced > 0 Then
        PackScore = 1E+30 + CDbl(notPlaced) * 1E+25
        Exit Function
    End If

    excessRight = rightWaste - MAX_RIGHT_WASTE

    If excessRight < 0# Then
        excessRight = 0#
    End If

    PackScore = excessRight * 100000000# + materialUsed + alignmentScore * 0.01 + CDbl(rollCount) * 0.0001
End Function

Private Function EvaluateOrderScore(ByRef items() As TBanner, ByVal n As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef order() As Long, ByRef outRollCount As Long, ByRef outNotPlaced As Long, ByRef outRightWaste As Double, ByRef outAlignment As Double, ByRef outMaterial As Double) As Double

    Dim testRolls() As TRoll

    Dim score As Double

    PackMultiRollWithOrder items, n, rollWidth, maxHeight, allowRotation, fitMode, order, testRolls, outRollCount, outNotPlaced

    score = PackScore(items, testRolls, outRollCount, outNotPlaced, rollWidth, outRightWaste, outAlignment, outMaterial)

    EvaluateOrderScore = score
End Function

' --------------------------------------------------------------------
' TOP SEED STORAGE
' Keeps the best few initial V2 layouts for local optimization.
' --------------------------------------------------------------------

Private Sub AddSeed(ByRef seedOrders() As Long, ByRef seedScores() As Double, ByRef seedWidths() As Double, ByRef seedFits() As Long, ByRef seedSorts() As Long, ByRef seedCount As Long, ByVal maxSeeds As Long, ByRef candidateOrder() As Long, ByVal n As Long, ByVal candidateScore As Double, ByVal candidateWidth As Double, ByVal candidateFit As Long, ByVal candidateSort As Long)

    Dim pos As Long
    Dim i As Long
    Dim j As Long

    If maxSeeds <= 0 Then Exit Sub

    pos = 0

    For i = 1 To maxSeeds

        If candidateScore < seedScores(i) Then
            pos = i
            Exit For
        End If

    Next i

    If pos = 0 Then Exit Sub

    If seedCount < maxSeeds Then
        seedCount = seedCount + 1
    End If

    For i = seedCount To pos + 1 Step -1

        seedScores(i) = seedScores(i - 1)
        seedWidths(i) = seedWidths(i - 1)
        seedFits(i) = seedFits(i - 1)
        seedSorts(i) = seedSorts(i - 1)

        For j = 1 To n
            seedOrders(i, j) = seedOrders(i - 1, j)
        Next j

    Next i

    seedScores(pos) = candidateScore
    seedWidths(pos) = candidateWidth
    seedFits(pos) = candidateFit
    seedSorts(pos) = candidateSort

    For j = 1 To n
        seedOrders(pos, j) = candidateOrder(j)
    Next j
End Sub

' --------------------------------------------------------------------
' LOCAL SEARCH
'
' 1. Adjacent swaps
' 2. Long-distance swaps
' 3. Reinsert moves
' 4. 3-object permutations
'
' Each successful improvement is kept immediately.
' --------------------------------------------------------------------

Private Sub OptimizeOrder(ByRef items() As TBanner, ByVal n As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef order() As Long, ByRef finalScore As Double)

    Dim currentScore As Double
    Dim testScore As Double

    Dim currentRight As Double
    Dim currentAlign As Double
    Dim currentMaterial As Double

    Dim testRollCount As Long
    Dim testNotPlaced As Long

    Dim testRight As Double
    Dim testAlign As Double
    Dim testMaterial As Double

    Dim i As Long
    Dim j As Long

    Dim moveCount As Long
    Dim passNo As Long

    Dim improved As Boolean

    currentScore = EvaluateOrderScore(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, testRollCount, testNotPlaced, currentRight, currentAlign, currentMaterial)

    finalScore = currentScore

    For passNo = 1 To MAX_LOCAL_PASSES

        improved = False

        ' ------------------------------------------------------------
        ' PHASE A: Adjacent swaps
        ' ------------------------------------------------------------

        For i = 1 To n - 1

            SwapLong order, i, i + 1

            testScore = EvaluateOrderScore(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)

            If testScore < currentScore - EPS Then

                currentScore = testScore
                improved = True

            Else

                SwapLong order, i, i + 1

            End If

        Next i

        ' ------------------------------------------------------------
        ' PHASE B: Long-distance swaps
        ' ------------------------------------------------------------

        moveCount = 0

        For i = 1 To n - 2

            For j = i + 2 To n

                moveCount = moveCount + 1

                If moveCount > MAX_PAIR_MOVES Then Exit For

                SwapLong order, i, j

                testScore = EvaluateOrderScore(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)

                If testScore < currentScore - EPS Then

                    currentScore = testScore
                    improved = True

                Else

                    SwapLong order, i, j

                End If

            Next j

            If moveCount >= MAX_PAIR_MOVES Then Exit For

        Next i

        ' ------------------------------------------------------------
        ' PHASE C: Reinsert
        ' ------------------------------------------------------------

        moveCount = 0

        For i = 1 To n

            For j = 1 To n

                If i <> j Then

                    moveCount = moveCount + 1

                    If moveCount > MAX_REINSERT_MOVES Then Exit For

                    MoveItemOrder order, i, j, n

                    testScore = EvaluateOrderScore(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)

                    If testScore < currentScore - EPS Then

                        currentScore = testScore
                        improved = True

                        i = j

                    Else

                        MoveItemOrder order, j, i, n

                    End If

                End If

            Next j

            If moveCount >= MAX_REINSERT_MOVES Then Exit For

        Next i

        ' ------------------------------------------------------------
        ' PHASE D: 3-object destroy/repair
        '
        ' Try several permutations of each small neighborhood.
        ' ------------------------------------------------------------

        moveCount = 0

        For i = 1 To n - 2

            If moveCount >= MAX_TRIPLE_MOVES Then Exit For

            ' A B C -> A C B
            SwapLong order, i + 1, i + 2

            moveCount = moveCount + 1

            testScore = EvaluateOrderScore(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)

            If testScore < currentScore - EPS Then
                currentScore = testScore
                improved = True
            Else
                SwapLong order, i + 1, i + 2
            End If

            If moveCount >= MAX_TRIPLE_MOVES Then Exit For

            ' A B C -> B A C
            SwapLong order, i, i + 1

            moveCount = moveCount + 1

            testScore = EvaluateOrderScore(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)

            If testScore < currentScore - EPS Then
                currentScore = testScore
                improved = True
            Else
                SwapLong order, i, i + 1
            End If

            If moveCount >= MAX_TRIPLE_MOVES Then Exit For

            ' A B C -> C B A
            SwapLong order, i, i + 2

            moveCount = moveCount + 1

            testScore = EvaluateOrderScore(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)

            If testScore < currentScore - EPS Then
                currentScore = testScore
                improved = True
            Else
                SwapLong order, i, i + 2
            End If

        Next i

        If Not improved Then Exit For

    Next passNo

    finalScore = currentScore
End Sub

Private Sub MoveShapeToBottomLeft(ByVal sh As Shape, ByVal targetX As Double, ByVal targetY As Double)

    Dim bx As Double
    Dim by As Double
    Dim bw As Double
    Dim bh As Double

    sh.GetBoundingBox bx, by, bw, bh, False

    sh.Move targetX - bx, targetY - by
End Sub

' --------------------------------------------------------------------
' APPLY RESULT TO CORELDRAW
'
' IMPORTANT V3:
'
' Internal nesting:
'     y = 0     -> visual TOP of roll
' after visual conversion
'
' CorelDRAW actual page:
'     pageTop -> visual top
'
' Formula:
'     targetY =
'         rollTop
'         - internalY
'         - footprintHeight
'         + margin
'
' This fixes the previous top/bottom inversion.
' --------------------------------------------------------------------

Private Sub ApplyNestingToObjects(ByRef items() As TBanner, ByRef sourceShapes() As Shape, ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rollWidth As Double)

    Dim totalHeight As Double
    Dim rollOffsetY As Double

    Dim r As Long
    Dim i As Long
    Dim rid As Long

    Dim margin As Double

    Dim targetX As Double
    Dim targetY As Double

    Dim pageLeft As Double
    Dim pageBottom As Double
    Dim pageTop As Double
    Dim rollTop As Double

    Dim sh As Shape

    totalHeight = 0#

    For r = 1 To rollCount

        totalHeight = totalHeight + rolls(r).UsedHeight

        If r < rollCount Then
            totalHeight = totalHeight + ROLL_GAP
        End If

    Next r

    If totalHeight <= EPS Then
        totalHeight = 10#
    End If

    ActivePage.SizeWidth = rollWidth
    ActivePage.SizeHeight = totalHeight

    pageLeft = ActivePage.LeftX
    pageBottom = ActivePage.BottomY
    pageTop = ActivePage.TopY

    rollOffsetY = 0#

    For r = 1 To rollCount

        rollTop = pageTop - rollOffsetY

        For i = 1 To rolls(r).placedCount

            rid = rolls(r).placed(i).rid

            Set sh = sourceShapes(rid)

            margin = items(rid).margin

            If rolls(r).placed(i).Rotated Then
                sh.Rotate 90#
            End If

            targetX = pageLeft + rolls(r).placed(i).x + margin

            targetY = rollTop - rolls(r).placed(i).y - rolls(r).placed(i).h + margin

            MoveShapeToBottomLeft sh, targetX, targetY

        Next i

        rollOffsetY = rollOffsetY + rolls(r).UsedHeight

        If r < rollCount Then
            rollOffsetY = rollOffsetY + ROLL_GAP
        End If

    Next r

    ActiveDocument.ClearSelection

    For r = 1 To rollCount

        For i = 1 To rolls(r).placedCount

            rid = rolls(r).placed(i).rid

            sourceShapes(rid).CreateSelection

        Next i

    Next r

End Sub

Private Sub ParseWidthList(ByVal txt As String, ByRef widths() As Double, ByRef widthCount As Long)

    Dim parts() As String
    Dim i As Long
    Dim v As Double

    widthCount = 0

    parts = Split(txt, ",")

    ReDim widths(1 To UBound(parts) + 1)

    For i = LBound(parts) To UBound(parts)

        If Len(Trim$(parts(i))) > 0 Then

            v = Val(Trim$(parts(i)))

            If v > 0# Then

                widthCount = widthCount + 1
                widths(widthCount) = v

            End If

        End If

    Next i

    If widthCount <= 0 Then

        ReDim widths(1 To 1)

    Else

        ReDim Preserve widths(1 To widthCount)

    End If
End Sub

Private Function SortModeName(ByVal mode As Long) As String

    Select Case mode

        Case 1
            SortModeName = "Area Descending"

        Case 2
            SortModeName = "Width Descending"

        Case 3
            SortModeName = "Height Descending"

        Case 4
            SortModeName = "Short Side Descending"

        Case 5
            SortModeName = "Long Side Descending"

        Case 6
            SortModeName = "Aspect Ratio Descending"

        Case Else
            SortModeName = "Unknown"

    End Select
End Function

Private Function FitModeName(ByVal mode As Long) As String

    Select Case mode

        Case 1
            FitModeName = "BSSF"

        Case 2
            FitModeName = "BAF"

        Case 3
            FitModeName = "BLSF"

        Case Else
            FitModeName = "Unknown"

    End Select
End Function

Public Sub RunNesting_BannerCorelDRAW()

    Dim doc As Document
    Dim sr As ShapeRange
    Dim sh As Shape

    Dim items() As TBanner
    Dim sourceShapes() As Shape

    Dim rolls() As TRoll
    Dim candidateRolls() As TRoll

    Dim candidateOrder() As Long
    Dim workOrder() As Long

    Dim seedOrders() As Long
    Dim seedScores() As Double
    Dim seedWidths() As Double
    Dim seedFits() As Long
    Dim seedSorts() As Long

    Dim n As Long
    Dim i As Long
    Dim j As Long

    Dim oldUnit As Long

    Dim margin As Double
    Dim rollText As String

    Dim widths() As Double
    Dim widthCount As Long

    Dim rotateAnswer As VbMsgBoxResult
    Dim allowRotation As Boolean

    Dim maxHeight As Double
    Dim minNeeded As Double

    Dim candidateWidth As Double
    Dim bestWidth As Double

    Dim candidateSortMode As Long
    Dim candidateFitMode As Long

    Dim bestSortMode As Long
    Dim bestFitMode As Long

    Dim candidateRollCount As Long
    Dim candidateNotPlaced As Long

    Dim bestRollCount As Long
    Dim bestNotPlaced As Long

    Dim candidateScore As Double
    Dim bestScore As Double

    Dim candidateMaterial As Double
    Dim bestMaterial As Double

    Dim candidateWaste As Double
    Dim bestWaste As Double

    Dim candidateRightWaste As Double
    Dim bestRightWaste As Double

    Dim candidateAlignment As Double
    Dim bestAlignment As Double

    Dim optimizedScore As Double

    Dim seedCount As Long

    Dim bx As Double
    Dim by As Double
    Dim bw As Double
    Dim bh As Double

    Dim sumSide As Double
    Dim maxMargin As Double

    Dim msg As String

    ' ------------------------------------------------------------
    ' CHECK DOCUMENT
    ' ------------------------------------------------------------

    If ActiveDocument Is Nothing Then

        MsgBox "Tidak ada document CorelDRAW aktif.", vbExclamation, "Auto Nesting"

        Exit Sub

    End If

    Set doc = ActiveDocument

    Set sr = ActiveSelectionRange

    If sr Is Nothing Then

        MsgBox "Pilih object/banner terlebih dahulu.", vbExclamation, "Auto Nesting"

        Exit Sub

    End If

    If sr.count <= 0 Then

        MsgBox "Pilih minimal 1 object/banner terlebih dahulu.", vbExclamation, "Auto Nesting"

        Exit Sub

    End If

    n = sr.count

    oldUnit = doc.Unit

    doc.Unit = cdrCentimeter

    ReDim items(1 To n)
    ReDim sourceShapes(1 To n)

    i = 0

    For Each sh In sr

        i = i + 1

        Set sourceShapes(i) = sh

        sh.GetBoundingBox bx, by, bw, bh, False

        If bw <= EPS Or bh <= EPS Then

            doc.Unit = oldUnit

            MsgBox "Object nomor " & CStr(i) & " memiliki bounding box tidak valid.", vbCritical, "Auto Nesting"

            Exit Sub

        End If

        items(i).Label = "Object " & CStr(i)

        items(i).OrigW = bw
        items(i).OrigH = bh

        items(i).margin = 0#

    Next sh

    ' ------------------------------------------------------------
    ' MARGIN
    ' ------------------------------------------------------------

    margin = Val(InputBox("Margin / clearance per sisi (cm):", "Auto Nesting - Margin", "0"))

    If margin < 0# Then
        margin = 0#
    End If

    For i = 1 To n
        items(i).margin = margin
    Next i

    ' ------------------------------------------------------------
    ' ROLL WIDTH
    ' ------------------------------------------------------------

    rollText = InputBox("Masukkan daftar lebar roll dalam cm." & vbCrLf & "Contoh: 150,200,250,300", "Auto Nesting - Roll Width", "109,159,219,259,319")

    If Len(Trim$(rollText)) = 0 Then

        doc.Unit = oldUnit

        MsgBox "Lebar roll tidak diberikan.", vbExclamation, "Auto Nesting"

        Exit Sub

    End If

    ParseWidthList rollText, widths, widthCount

    If widthCount <= 0 Then

        doc.Unit = oldUnit

        MsgBox "Daftar lebar roll tidak valid.", vbCritical, "Auto Nesting"

        Exit Sub

    End If

    ' ------------------------------------------------------------
    ' ROTATION
    ' ------------------------------------------------------------

    rotateAnswer = MsgBox("Izinkan object diputar 90°?", vbYesNo + vbQuestion, "Auto Nesting - Rotation")

    allowRotation = (rotateAnswer = vbYes)

    ' ------------------------------------------------------------
    ' HEIGHT / MINIMUM WIDTH
    ' ------------------------------------------------------------

    sumSide = 0#
    maxMargin = 0#

    For i = 1 To n

        sumSide = sumSide + MaxD(items(i).OrigW, items(i).OrigH)

        maxMargin = MaxD(maxMargin, items(i).margin)

    Next i

    maxHeight = sumSide + maxMargin * (n + 2) + 100#

    minNeeded = 0#

    For i = 1 To n

        If allowRotation Then

            minNeeded = MaxD(minNeeded, MinD(items(i).OrigW, items(i).OrigH) + 2# * items(i).margin)

        Else

            minNeeded = MaxD(minNeeded, items(i).OrigW + 2# * items(i).margin)

        End If

    Next i

    ' ------------------------------------------------------------
    ' INITIAL V2 MULTI-START
    '
    ' Keep best few seeds for local optimization.
    ' ------------------------------------------------------------

    ReDim seedOrders(1 To MAX_LOCAL_SEEDS, 1 To n)
    ReDim seedScores(1 To MAX_LOCAL_SEEDS)
    ReDim seedWidths(1 To MAX_LOCAL_SEEDS)
    ReDim seedFits(1 To MAX_LOCAL_SEEDS)
    ReDim seedSorts(1 To MAX_LOCAL_SEEDS)

    For i = 1 To MAX_LOCAL_SEEDS
        seedScores(i) = 1E+30
    Next i

    seedCount = 0

    bestScore = 1E+30
    bestMaterial = 1E+30
    bestWaste = 1#
    bestRightWaste = 1E+30
    bestAlignment = 1E+30
    bestWidth = 0#
    bestRollCount = 0
    bestNotPlaced = n

    bestSortMode = 1
    bestFitMode = 1

    For j = 1 To widthCount

        candidateWidth = widths(j)

        If candidateWidth + EPS >= minNeeded Then

            For candidateSortMode = 1 To 6

                BuildInitialOrder items, n, candidateSortMode, candidateOrder

                For candidateFitMode = 1 To 3

                    PackMultiRollWithOrder items, n, candidateWidth, maxHeight, allowRotation, candidateFitMode, candidateOrder, candidateRolls, candidateRollCount, candidateNotPlaced

                    candidateScore = PackScore(items, candidateRolls, candidateRollCount, candidateNotPlaced, candidateWidth, candidateRightWaste, candidateAlignment, candidateMaterial)

                    If candidateNotPlaced = 0 Then
                        candidateWaste = CalcWaste(items, candidateRolls, candidateRollCount, candidateWidth)
                    Else
                        candidateWaste = 1#
                    End If

                    AddSeed seedOrders, seedScores, seedWidths, seedFits, seedSorts, seedCount, MAX_LOCAL_SEEDS, candidateOrder, n, candidateScore, candidateWidth, candidateFitMode, candidateSortMode

                    If candidateScore < bestScore Then

                        bestScore = candidateScore

                        bestWidth = candidateWidth

                        bestRollCount = candidateRollCount
                        bestNotPlaced = candidateNotPlaced

                        bestSortMode = candidateSortMode
                        bestFitMode = candidateFitMode

                        bestMaterial = candidateMaterial
                        bestWaste = candidateWaste
                        bestRightWaste = candidateRightWaste
                        bestAlignment = candidateAlignment

                    End If

                Next candidateFitMode

            Next candidateSortMode

        End If

    Next j

    ' ------------------------------------------------------------
    ' LOCAL OPTIMIZATION
    '
    ' Run on several best V2 seeds.
    ' This is where swap/reinsert/manual-style search happens.
    ' ------------------------------------------------------------

    For i = 1 To seedCount

        CopyOrderFromSeed seedOrders, i, n, workOrder

        optimizedScore = 1E+30

        OptimizeOrder items, n, seedWidths(i), maxHeight, allowRotation, seedFits(i), workOrder, optimizedScore

        PackMultiRollWithOrder items, n, seedWidths(i), maxHeight, allowRotation, seedFits(i), workOrder, candidateRolls, candidateRollCount, candidateNotPlaced

        candidateScore = PackScore(items, candidateRolls, candidateRollCount, candidateNotPlaced, seedWidths(i), candidateRightWaste, candidateAlignment, candidateMaterial)

        If candidateNotPlaced = 0 Then
            candidateWaste = CalcWaste(items, candidateRolls, candidateRollCount, seedWidths(i))
        Else
            candidateWaste = 1#
        End If

        If candidateScore < bestScore Then

            bestScore = candidateScore

            bestWidth = seedWidths(i)

            bestRollCount = candidateRollCount
            bestNotPlaced = candidateNotPlaced

            bestSortMode = seedSorts(i)
            bestFitMode = seedFits(i)

            bestMaterial = candidateMaterial
            bestWaste = candidateWaste
            bestRightWaste = candidateRightWaste
            bestAlignment = candidateAlignment

            ReDim candidateOrder(1 To n)

            For j = 1 To n
                candidateOrder(j) = workOrder(j)
            Next j

        End If

    Next i

    ' ------------------------------------------------------------
    ' FALLBACK / FINAL REPACK
    ' ------------------------------------------------------------

    If bestWidth <= EPS Or bestRollCount <= 0 Then

        doc.Unit = oldUnit

        msg = "Tidak ditemukan konfigurasi roll yang feasible."
        msg = msg & vbCrLf & vbCrLf
        msg = msg & "Minimum roll width: "
        msg = msg & Format$(minNeeded, "0.00")
        msg = msg & " cm"

        MsgBox msg, vbCritical, "Auto Nesting"

        Exit Sub

    End If

    ' If candidateOrder contains optimized order use it.
    ' Otherwise build the original V2 order.
    If Not IsArrayInitialized(candidateOrder) Then
        BuildInitialOrder items, n, bestSortMode, candidateOrder
    End If

    PackMultiRollWithOrder items, n, bestWidth, maxHeight, allowRotation, bestFitMode, candidateOrder, rolls, bestRollCount, bestNotPlaced

    bestMaterial = CalcMaterialUsed(rolls, bestRollCount, bestWidth)

    bestWaste = CalcWaste(items, rolls, bestRollCount, bestWidth)

    bestRightWaste = CalcRightWaste(rolls, bestRollCount, bestWidth)

    bestAlignment = CalcAlignmentScore(rolls, bestRollCount)

    ' ------------------------------------------------------------
    ' APPLY TO ACTUAL COREL DRAW OBJECTS
    ' ------------------------------------------------------------

    ApplyNestingToObjects items, sourceShapes, rolls, bestRollCount, bestWidth

    doc.Unit = oldUnit

    ' ------------------------------------------------------------
    ' REPORT
    ' ------------------------------------------------------------

    msg = "AUTO NESTING V3 SELESAI"
    msg = msg & vbCrLf & vbCrLf

    msg = msg & "Object: "
    msg = msg & CStr(n)

    msg = msg & vbCrLf
    msg = msg & "Roll width: "
    msg = msg & Format$(bestWidth, "0.00")
    msg = msg & " cm"

    msg = msg & vbCrLf
    msg = msg & "Jumlah roll: "
    msg = msg & CStr(bestRollCount)

    msg = msg & vbCrLf
    msg = msg & "Tidak ditempatkan: "
    msg = msg & CStr(bestNotPlaced)

    msg = msg & vbCrLf
    msg = msg & "Material digunakan: "
    msg = msg & Format$(bestMaterial, "0.00")
    msg = msg & " cm2"

    msg = msg & vbCrLf
    msg = msg & "Waste estimasi: "
    msg = msg & Format$(bestWaste * 100#, "0.00")
    msg = msg & "%"

    msg = msg & vbCrLf
    msg = msg & "Waste kanan maksimum: "
    msg = msg & Format$(bestRightWaste, "0.00")
    msg = msg & " cm"

    msg = msg & vbCrLf

    If bestRightWaste <= MAX_RIGHT_WASTE + EPS Then
        msg = msg & "Right waste status: OK"
    Else
        msg = msg & "Right waste status: > 10 cm"
    End If

    msg = msg & vbCrLf
    msg = msg & "Visual alignment score: "
    msg = msg & Format$(bestAlignment, "0.00")

    msg = msg & vbCrLf
    msg = msg & "Seed sort: "
    msg = msg & SortModeName(bestSortMode)

    msg = msg & vbCrLf
    msg = msg & "Fitness: "
    msg = msg & FitModeName(bestFitMode)

    msg = msg & vbCrLf & vbCrLf
    msg = msg & "Local optimization: SWAP + REINSERT + 3-OBJECT REARRANGE"

    MsgBox msg, vbInformation, "Auto Nesting V3"

End Sub

Private Sub CopyOrderFromSeed(ByRef seedOrders() As Long, ByVal seedNo As Long, ByVal n As Long, ByRef order() As Long)

    Dim i As Long

    ReDim order(1 To n)

    For i = 1 To n
        order(i) = seedOrders(seedNo, i)
    Next i
End Sub

Private Function IsArrayInitialized(ByRef arr() As Long) As Boolean

    Dim lb As Long
    Dim ub As Long

    On Error GoTo NotInitialized

    lb = LBound(arr)
    ub = UBound(arr)

    If ub >= lb Then
        IsArrayInitialized = True
    Else
        IsArrayInitialized = False
    End If

    Exit Function

NotInitialized:
    IsArrayInitialized = False
End Function