| 81 | }; |
| 82 | |
| 83 | static void ConstructTree(TDistrTree* res, const TVector<TTreeConnectorCost>& links, int nodeCount, float sendTime) //treeNodeCost) |
| 84 | { |
| 85 | if (links.empty() || nodeCount == 1) { |
| 86 | res->FinalNodeId = 0; |
| 87 | return; |
| 88 | } |
| 89 | TDistrTreeConstructor treeConstr(nodeCount); |
| 90 | |
| 91 | for (int i = 0; i < links.ysize(); ++i) { |
| 92 | const TTreeConnectorCost& tc = links[i]; |
| 93 | int g1 = treeConstr.GetParent(tc.Vec1); |
| 94 | int g2 = treeConstr.GetParent(tc.Vec2); |
| 95 | if (g1 == g2) |
| 96 | continue; // already connected |
| 97 | |
| 98 | const TDistrTree& gg1 = treeConstr.Group[g1]; |
| 99 | const TDistrTree& gg2 = treeConstr.Group[g2]; |
| 100 | Y_ASSERT(tc.Cost > gg1.MaxPing && tc.Cost > gg2.MaxPing); |
| 101 | float flatConnectionCost = |
| 102 | (gg1.Children.ysize() + gg2.Children.ysize() - 1) * sendTime + |
| 103 | tc.Cost + |
| 104 | Max(gg1.Cost, gg2.Cost); |
| 105 | |
| 106 | float g1total = CalcTreeCost(gg1, sendTime); |
| 107 | float g2total = CalcTreeCost(gg2, sendTime); |
| 108 | float newNodeCost = sendTime + tc.Cost + Max(g1total, g2total); |
| 109 | |
| 110 | int newGroupId; |
| 111 | TDistrTree& newGroup = treeConstr.AddTree(&newGroupId); |
| 112 | if (flatConnectionCost <= newNodeCost) { |
| 113 | // make flat marge |
| 114 | newGroup.Children = gg1.Children; |
| 115 | newGroup.Children.insert(newGroup.Children.end(), gg2.Children.begin(), gg2.Children.end()); |
| 116 | std::sort(newGroup.Children.begin(), newGroup.Children.end(), TDistrTreeCmpCost(sendTime)); |
| 117 | newGroup.Cost = Max(gg1.Cost, gg2.Cost); |
| 118 | newGroup.MaxPing = tc.Cost; |
| 119 | } else { |
| 120 | // make hierarchical merge |
| 121 | newGroup.Children.push_back(gg1); |
| 122 | newGroup.Children.push_back(gg2); |
| 123 | std::sort(newGroup.Children.begin(), newGroup.Children.end(), TDistrTreeCmpCost(sendTime)); |
| 124 | newGroup.Cost = Max(g1total, g2total); |
| 125 | newGroup.MaxPing = tc.Cost; |
| 126 | } |
| 127 | treeConstr.Group2parent[g1] = newGroupId; |
| 128 | treeConstr.Group2parent[g2] = newGroupId; |
| 129 | } |
| 130 | *res = treeConstr.Group[treeConstr.GetParent(0)]; |
| 131 | } |
| 132 | |
| 133 | static void ConstructTreeLimitBranching(TDistrTree* res, const TVector<TTreeConnectorCost>& links, int nodeCount, int maxBranching) { |
| 134 | if (links.empty() || nodeCount == 1) { |
no test coverage detected