像CSS這樣的頁面佈局的數據結構漂浮

Question

假設我有自己的標記語言，它允許我使用TextElements和ImageElements的數組。其中的每一個都可以具有「float：left/right/none」和「clear：none/left/right/both」等屬性。此外，非浮動元素可以在浮動元素周圍流動。基本上，所有像CSS浮動佈局。

例如：

Elem1 elem2時 Elem3 Elem4 Elem5 _ Elem6

什麼是用來存儲這些元素，而我解僱他們出最好的數據結構？我需要的東西可以很容易地回答這樣的問題：

• 是否有足夠的空間來適應元素2左側或右側的Element1？
• Element1的頁面座標，原點和大小是多少？

我會基本上存儲如下的結構：

{元素，原點（x，y）時，尺寸（W，H）}

對該每個已經紡出元件數據結構。

有一些像RTrees，QuadTrees等類似的東西，但我想要一些簡單的東西來抽象地表示矩形在頁面上的佈局以供我的佈局算法使用。

注意：我不是在HTML中執行此操作，而是在iOS應用程序中對元素進行佈局，並且由於需要支持早期的iOS版本，因此無法使用iOS 6約束。

謝謝！

Answer 1

我相信一個二進制堆可以用於你想要的工作。 Wikipedia explains binary heaps quite well.

二進制堆有兩個屬性，使得它很好的爲你想要的東西：

1. 它是一個完整的樹，其結構上類似元素的佈局的頁面。
2. 節點的排列方式使得每個節點比其子節點更大（或更少，取決於你想要的）。在你的情況下，「更大」意味着「進一步向左和向上」。

你有一個元素列表，如果沒有浮點數，將按順序排列，根據需要包裝行。因此，在沒有浮點的情況下構建堆只會按照接收順序將樹添加到樹中。

浮動使這變得複雜，因爲它們放置在比它們先前的節點更高的位置（或低於右浮動情況下的節點）。幸運的是，構建一個堆允許通過將新節點冒泡到適當的位置。所以，只要你可以定義一個函數來定義浮點元素相對於它的對等點，這就可以工作。

這就是如果，我不知道，不幸的是，我現在沒有足夠的時間來更徹底地探索這個想法。

無論如何，假設你有一個正確的堆，反覆刪除最頂層的元素應該按照它們應該放置在頁面上的順序來枚舉節點。

我認爲CHDataStructures有一個二進制堆，但我無法驗證，因爲保存文檔的服務器在發佈時似乎處於脫機狀態。

祝你好運，我希望這是有幫助的。