1.1 --- a/core.sql	Wed May 21 22:01:43 2014 +0200
     1.2 +++ b/core.sql	Thu May 22 03:27:39 2014 +0200
     1.3 @@ -3894,24 +3894,77 @@
     1.4          "primary"               INT8,
     1.5          "secondary"             INT8 );
     1.6  
     1.7 +COMMENT ON TYPE "link_strength" IS 'TODO';
     1.8 +
     1.9 +
    1.10 +CREATE FUNCTION "find_best_paths"("matrix_d" "link_strength"[][])
    1.11 +  RETURNS "link_strength"[][]
    1.12 +  LANGUAGE 'plpgsql' IMMUTABLE AS $$
    1.13 +    DECLARE
    1.14 +      "dimension_v" INT4;
    1.15 +      "matrix_p"    "link_strength"[][];
    1.16 +      "i"           INT4;
    1.17 +      "j"           INT4;
    1.18 +      "k"           INT4;
    1.19 +    BEGIN
    1.20 +      "dimension_v" := array_upper("matrix_d", 1);
    1.21 +      "matrix_p" := "matrix_d";
    1.22 +      "i" := 1;
    1.23 +      LOOP
    1.24 +        "j" := 1;
    1.25 +        LOOP
    1.26 +          IF "i" != "j" THEN
    1.27 +            "k" := 1;
    1.28 +            LOOP
    1.29 +              IF "i" != "k" AND "j" != "k" THEN
    1.30 +                IF "matrix_p"["j"]["i"] < "matrix_p"["i"]["k"] THEN
    1.31 +                  IF "matrix_p"["j"]["i"] > "matrix_p"["j"]["k"] THEN
    1.32 +                    "matrix_p"["j"]["k"] := "matrix_p"["j"]["i"];
    1.33 +                  END IF;
    1.34 +                ELSE
    1.35 +                  IF "matrix_p"["i"]["k"] > "matrix_p"["j"]["k"] THEN
    1.36 +                    "matrix_p"["j"]["k"] := "matrix_p"["i"]["k"];
    1.37 +                  END IF;
    1.38 +                END IF;
    1.39 +              END IF;
    1.40 +              EXIT WHEN "k" = "dimension_v";
    1.41 +              "k" := "k" + 1;
    1.42 +            END LOOP;
    1.43 +          END IF;
    1.44 +          EXIT WHEN "j" = "dimension_v";
    1.45 +          "j" := "j" + 1;
    1.46 +        END LOOP;
    1.47 +        EXIT WHEN "i" = "dimension_v";
    1.48 +        "i" := "i" + 1;
    1.49 +      END LOOP;
    1.50 +      RETURN "matrix_p";
    1.51 +    END;
    1.52 +  $$;
    1.53 +
    1.54 +COMMENT ON FUNCTION "find_best_paths"("link_strength"[][]) IS 'TODO';
    1.55  
    1.56  
    1.57  CREATE FUNCTION "calculate_ranks"("issue_id_p" "issue"."id"%TYPE)
    1.58    RETURNS VOID
    1.59    LANGUAGE 'plpgsql' VOLATILE AS $$
    1.60      DECLARE
    1.61 -      "issue_row"         "issue"%ROWTYPE;
    1.62 -      "policy_row"        "policy"%ROWTYPE;
    1.63 -      "dimension_v"       INT4;
    1.64 -      "vote_matrix"       INT4[][];  -- absolute votes
    1.65 -      "matrix"            "link_strength"[][];  -- defeat strength / best paths
    1.66 -      "i"                 INT4;
    1.67 -      "j"                 INT4;
    1.68 -      "k"                 INT4;
    1.69 -      "battle_row"        "battle"%ROWTYPE;
    1.70 -      "rank_ary"          INT4[];
    1.71 -      "rank_v"            INT4;
    1.72 -      "initiative_id_v"   "initiative"."id"%TYPE;
    1.73 +      "issue_row"       "issue"%ROWTYPE;
    1.74 +      "policy_row"      "policy"%ROWTYPE;
    1.75 +      "dimension_v"     INT4;
    1.76 +      "matrix_a"        INT4[][];  -- absolute votes
    1.77 +      "matrix_d"        "link_strength"[][];  -- defeat strength (direct)
    1.78 +      "matrix_p"        "link_strength"[][];  -- defeat strength (best path)
    1.79 +      "matrix_t"        "link_strength"[][];  -- defeat strength (tie-breaking)
    1.80 +      "matrix_f"        BOOLEAN[][];  -- forbidden link (tie-breaking)
    1.81 +      "matrix_b"        BOOLEAN[][];  -- final order (who beats who)
    1.82 +      "i"               INT4;
    1.83 +      "j"               INT4;
    1.84 +      "m"               INT4;
    1.85 +      "n"               INT4;
    1.86 +      "battle_row"      "battle"%ROWTYPE;
    1.87 +      "rank_ary"        INT4[];
    1.88 +      "rank_v"          INT4;
    1.89 +      "initiative_id_v" "initiative"."id"%TYPE;
    1.90      BEGIN
    1.91        PERFORM "require_transaction_isolation"();
    1.92        SELECT * INTO "issue_row"
    1.93 @@ -3920,9 +3973,9 @@
    1.94          FROM "policy" WHERE "id" = "issue_row"."policy_id";
    1.95        SELECT count(1) INTO "dimension_v"
    1.96          FROM "battle_participant" WHERE "issue_id" = "issue_id_p";
    1.97 -      -- Create "vote_matrix" with absolute number of votes in pairwise
    1.98 +      -- Create "matrix_a" with absolute number of votes in pairwise
    1.99        -- comparison:
   1.100 -      "vote_matrix" := array_fill(NULL::INT4, ARRAY["dimension_v", "dimension_v"]);
   1.101 +      "matrix_a" := array_fill(NULL::INT4, ARRAY["dimension_v", "dimension_v"]);
   1.102        "i" := 1;
   1.103        "j" := 2;
   1.104        FOR "battle_row" IN
   1.105 @@ -3931,7 +3984,7 @@
   1.106          "winning_initiative_id" NULLS FIRST,
   1.107          "losing_initiative_id" NULLS FIRST
   1.108        LOOP
   1.109 -        "vote_matrix"["i"]["j"] := "battle_row"."count";
   1.110 +        "matrix_a"["i"]["j"] := "battle_row"."count";
   1.111          IF "j" = "dimension_v" THEN
   1.112            "i" := "i" + 1;
   1.113            "j" := 1;
   1.114 @@ -3945,18 +3998,18 @@
   1.115        IF "i" != "dimension_v" OR "j" != "dimension_v" + 1 THEN
   1.116          RAISE EXCEPTION 'Wrong battle count (should not happen)';
   1.117        END IF;
   1.118 -      -- Store defeat strengths in "matrix" using "defeat_strength"
   1.119 -      -- function:
   1.120 -      "matrix" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]);
   1.121 +      -- Store direct defeat strengths in "matrix_d" using "defeat_strength"
   1.122 +      -- and "secondary_link_strength" functions:
   1.123 +      "matrix_d" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]);
   1.124        "i" := 1;
   1.125        LOOP
   1.126          "j" := 1;
   1.127          LOOP
   1.128            IF "i" != "j" THEN
   1.129 -            "matrix"["i"]["j"] := (
   1.130 +            "matrix_d"["i"]["j"] := (
   1.131                "defeat_strength"(
   1.132 -                "vote_matrix"["i"]["j"],
   1.133 -                "vote_matrix"["j"]["i"],
   1.134 +                "matrix_a"["i"]["j"],
   1.135 +                "matrix_a"["j"]["i"],
   1.136                  "policy_row"."defeat_strength"
   1.137                ),
   1.138                "secondary_link_strength"(
   1.139 @@ -3973,34 +4026,94 @@
   1.140          "i" := "i" + 1;
   1.141        END LOOP;
   1.142        -- Find best paths:
   1.143 +      "matrix_p" := "find_best_paths"("matrix_d");
   1.144 +      -- Create partial order:
   1.145 +      "matrix_b" := array_fill(NULL::BOOLEAN, ARRAY["dimension_v", "dimension_v"]);
   1.146        "i" := 1;
   1.147        LOOP
   1.148 -        "j" := 1;
   1.149 +        "j" := "i" + 1;
   1.150          LOOP
   1.151            IF "i" != "j" THEN
   1.152 -            "k" := 1;
   1.153 -            LOOP
   1.154 -              IF "i" != "k" AND "j" != "k" THEN
   1.155 -                IF "matrix"["j"]["i"] < "matrix"["i"]["k"] THEN
   1.156 -                  IF "matrix"["j"]["i"] > "matrix"["j"]["k"] THEN
   1.157 -                    "matrix"["j"]["k"] := "matrix"["j"]["i"];
   1.158 -                  END IF;
   1.159 -                ELSE
   1.160 -                  IF "matrix"["i"]["k"] > "matrix"["j"]["k"] THEN
   1.161 -                    "matrix"["j"]["k"] := "matrix"["i"]["k"];
   1.162 -                  END IF;
   1.163 -                END IF;
   1.164 -              END IF;
   1.165 -              EXIT WHEN "k" = "dimension_v";
   1.166 -              "k" := "k" + 1;
   1.167 -            END LOOP;
   1.168 +            IF "matrix_p"["i"]["j"] > "matrix_p"["j"]["i"] THEN
   1.169 +              "matrix_b"["i"]["j"] := TRUE;
   1.170 +              "matrix_b"["j"]["i"] := FALSE;
   1.171 +            ELSIF "matrix_p"["i"]["j"] < "matrix_p"["j"]["i"] THEN
   1.172 +              "matrix_b"["i"]["j"] := FALSE;
   1.173 +              "matrix_b"["j"]["i"] := TRUE;
   1.174 +            END IF;
   1.175            END IF;
   1.176            EXIT WHEN "j" = "dimension_v";
   1.177            "j" := "j" + 1;
   1.178          END LOOP;
   1.179 -        EXIT WHEN "i" = "dimension_v";
   1.180 +        EXIT WHEN "i" = "dimension_v" - 1;
   1.181          "i" := "i" + 1;
   1.182        END LOOP;
   1.183 +      -- Tie-breaking:
   1.184 +      IF "policy_row"."tie_breaking" != 'simple'::"tie_breaking" THEN
   1.185 +        "m" := 1;
   1.186 +        LOOP
   1.187 +          "n" := "m" + 1;
   1.188 +          LOOP
   1.189 +            IF "matrix_b"["m"]["n"] ISNULL THEN
   1.190 +              "matrix_t" := "matrix_p";
   1.191 +              "matrix_f" := array_fill(FALSE, ARRAY["dimension_v", "dimension_v"]);
   1.192 +              LOOP
   1.193 +                "i" := 1;
   1.194 +                <<forbid_one_link>>
   1.195 +                LOOP
   1.196 +                  "j" := 1;
   1.197 +                  LOOP
   1.198 +                    IF "i" != "j" THEN
   1.199 +                      IF "matrix_d"["i"]["j"] = "matrix_t"["m"]["n"] THEN
   1.200 +                        "matrix_f"["i"]["j"] := TRUE;
   1.201 +                        -- exit for performance reasons,
   1.202 +                        -- as only one link will be found:
   1.203 +                        EXIT forbid_one_link;
   1.204 +                      END IF;
   1.205 +                    END IF;
   1.206 +                    EXIT WHEN "j" = "dimension_v";
   1.207 +                    "j" := "j" + 1;
   1.208 +                  END LOOP;
   1.209 +                  IF "i" = "dimension_v" THEN
   1.210 +                    RAISE EXCEPTION 'Schulze tie-breaking does not compute (should not happen)';
   1.211 +                  END IF;
   1.212 +                  "i" := "i" + 1;
   1.213 +                END LOOP;
   1.214 +                "i" := 1;
   1.215 +                LOOP
   1.216 +                  "j" := 1;
   1.217 +                  LOOP
   1.218 +                    IF "i" != "j" THEN
   1.219 +                      "matrix_t"["i"]["j"] := CASE
   1.220 +                         WHEN "matrix_f"["i"]["j"]
   1.221 +                         THEN (-1::INT8) << 63
   1.222 +                         ELSE "matrix_d"["i"]["j"] END;
   1.223 +                    END IF;
   1.224 +                    EXIT WHEN "j" = "dimension_v";
   1.225 +                    "j" := "j" + 1;
   1.226 +                  END LOOP;
   1.227 +                  EXIT WHEN "i" = "dimension_v";
   1.228 +                  "i" := "i" + 1;
   1.229 +                END LOOP;
   1.230 +                "matrix_t" := "find_best_paths"("matrix_t");
   1.231 +                IF "matrix_t"["m"]["n"] > "matrix_t"["n"]["m"] THEN
   1.232 +                  "matrix_b"["m"]["n"] := TRUE;
   1.233 +                  "matrix_b"["n"]["m"] := FALSE;
   1.234 +                  EXIT;
   1.235 +                ELSIF "matrix_t"["m"]["n"] < "matrix_t"["n"]["m"] THEN
   1.236 +                  "matrix_b"["m"]["n"] := FALSE;
   1.237 +                  "matrix_b"["n"]["m"] := TRUE;
   1.238 +                  EXIT;
   1.239 +                END IF;
   1.240 +              END LOOP;
   1.241 +            END IF;
   1.242 +            EXIT WHEN "n" = "dimension_v";
   1.243 +            "n" := "n" + 1;
   1.244 +          END LOOP;
   1.245 +          EXIT WHEN "m" = "dimension_v" - 1;
   1.246 +          "m" := "m" + 1;
   1.247 +        END LOOP;
   1.248 +      END IF;
   1.249        -- Determine order of winners:
   1.250        "rank_ary" := array_fill(NULL::INT4, ARRAY["dimension_v"]);
   1.251        "rank_v" := 1;
   1.252 @@ -4013,9 +4126,9 @@
   1.253                IF
   1.254                  "i" != "j" AND
   1.255                  "rank_ary"["j"] ISNULL AND
   1.256 -                ( "matrix"["j"]["i"] > "matrix"["i"]["j"] OR
   1.257 +                ( "matrix_b"["j"]["i"] OR
   1.258                    -- tie-breaking by "id"
   1.259 -                  ( "matrix"["j"]["i"] = "matrix"["i"]["j"] AND
   1.260 +                  ( "matrix_b"["j"]["i"] ISNULL AND
   1.261                      "j" < "i" ) )
   1.262                THEN
   1.263                  -- someone else is better