Cấu trúc dữ liệu cho Double Elmination Tournament

Question

Tôi đang trong quá trình chuyển đổi phần mềm Tournament Organizer, cho phép tạo và thao tác các giải đấu Double Elimination, sử dụng mẫu thiết kế MVVM để có thể dễ dàng kiểm tra hơn. Trong khi làm như vậy, tôi đang tách ra khỏi 'mô hình' từ một số mã trong giao diện người dùng trực tiếp thao tác cấu trúc khung.

Đây sẽ là lần lặp thứ ba của phần mềm mà tôi đã viết để xử lý các giải đấu. Đầu tiên được viết bằng PHP và lưu trữ dữ liệu trong cơ sở dữ liệu. Phiên bản thứ hai là phiên bản WPF mà tôi đã tạo, và nó lưu trữ dữ liệu trong bộ nhớ, và sau đó serializes nó vào một tệp XML. Tuy nhiên, trong cả hai phiên bản, có những khía cạnh của việc thực hiện mà tôi cảm thấy không sạch sẽ, và dường như họ phá vỡ luật DRY.

Nếu bạn đang tạo cấu trúc dữ liệu từ đầu để xử lý các dấu ngoặc kép, bạn sẽ làm như thế nào?

Lưu ý rằng không cần phải tự động tạo các dấu ngoặc theo thuật toán (tải từ một loại bỏ đôi được tạo trước với 4/8/16/32 người là cách tôi đang thực hiện ngay bây giờ), chỉ là trường hợp sử dụng chính của việc thiết lập người chiến thắng của trận đấu và 'tiến' họ qua khung.

Chỉnh sửa: Để làm rõ, cấu trúc dữ liệu cần xử lý các giải đấu loại bỏ đôi, vì vậy có khả năng, người thắng cuộc trong một trận đấu có thể sẽ cạnh tranh với người thua cuộc khác.

Answer 1

Giải pháp của tôi cho điều này là có hai bộ cấu trúc dữ liệu. Một cho phần khung và một cho ghế.

class Match 
{ 
    string Id; 
    MatchSeat red; 
    MatchSeat blue; 
    MatchSeat winner; 
    MatchSeat loser; 
} 

class MatchSeat 
{ 
    string Id; 
    Entry Entry; 
} 

Sau đó, để thiết lập, tôi đã thực hiện một số chức năng trợ giúp lấy thông tin khung và xây dựng cấu trúc.

{ "1", "seed1", "seed4", "W1", "L1" }, 
{ "2", "seed2", "seed3", "W2", "L2" }, 
{ "3", "W1", "W2", "W3", "L3" }, 
{ "4", "L1", "L2", "W4", "L4" }, 
{ "5", "W4", "L3", "W5", "L5" }, 
{ "F", "W3", "W5", "WF", "WF" } 

Sau đó, khi hạt giống và người thắng cuộc/kẻ thua cuộc được điền, giá trị chỉ được đặt ở một nơi.

Answer 2

Điều gì về một cây nhị phân đầy đủ nơi vòng đầu tiên bắt đầu tại các nút lá và sau đó di chuyển lên.

Answer 3

Vì vậy, ở điểm kết thúc, bạn có 64 đội. Vì vậy, có một bộ sưu tập, bằng cách nào đó, của 64 đội.

Nhưng chúng được ghép nối và đối với mỗi cặp, có một người chiến thắng. Và trong khung giữa, người chiến thắng thực sự nổi lên từ một khung, vì vậy tôi nghĩ rằng đối tượng khung của bạn thực sự trông giống như:

public class Bracket 
{ 
    Team winner; //if this is null or whatever, then we don't have a winner yet 
    Bracket topBracket; 
    Bracket bottomBracket; 
} 

... và khi bạn đang instantiating đầu của bạn, bạn sẽ chỉ để lại hai sub-Brackets null, chỉ với một người chiến thắng.

Để xử lý loại bỏ hai lần, có một khung thứ hai, là một khung giảm giá. Sẽ tốt hơn nếu bạn có thể tự động xử lý việc thêm người thua cuộc vào khung này (thiết kế khung bắt đầu bằng 32, người chơi xuống 16, thêm vào 16 người thua từ khung chiến thắng vòng 2, v.v.) nhưng đó là tất cả việc triển khai. Cấu trúc dữ liệu không cần phải thay đổi để phù hợp với điều đó, bạn chỉ cần thêm chúng.

Answer 4

Tôi chỉ nhận thấy câu hỏi này trong thanh bên của một câu hỏi tôi đã về, và nghĩ rằng tôi muốn kêu vang trong:

Tôi đang trong quá trình phát triển một tính năng Tournament API đầy đủ, và tôi open- tìm nguồn cung ứng nó.

Nó chưa tạo ra các giải đấu loại trừ kép, nhưng cấu trúc dữ liệu cho các giải đấu loại trực tiếp gần đây đã được sửa đổi để hỗ trợ cấu trúc cây hai lần.

http://tournaments.codeplex.com/