1.1 --- a/core.sql	Sun Sep 30 00:56:01 2012 +0200
     1.2 +++ b/core.sql	Sun Sep 30 12:59:07 2012 +0200
     1.3 @@ -7,7 +7,7 @@
     1.4  BEGIN;
     1.5  
     1.6  CREATE VIEW "liquid_feedback_version" AS
     1.7 -  SELECT * FROM (VALUES ('2.2.0', 2, 2, 0))
     1.8 +  SELECT * FROM (VALUES ('2.1.0', 2, 1, 0))
     1.9    AS "subquery"("string", "major", "minor", "revision");
    1.10  
    1.11  
    1.12 @@ -329,11 +329,6 @@
    1.13  COMMENT ON COLUMN "session"."lang"              IS 'Language code of the selected language';
    1.14  
    1.15  
    1.16 -CREATE TYPE "schulze_variant" AS ENUM ('absolute_strength', 'tuple_strength', 'partial_tie_breaking', 'tie_breaking_with_negative_strength');
    1.17 -
    1.18 -COMMENT ON TYPE "schulze_variant" IS 'Variant of schulze method, which differ by complexity; greater values have a higher complexity';
    1.19 -
    1.20 -
    1.21  CREATE TABLE "policy" (
    1.22          "id"                    SERIAL4         PRIMARY KEY,
    1.23          "index"                 INT4            NOT NULL,
    1.24 @@ -361,7 +356,6 @@
    1.25          "indirect_majority_non_negative" INT4   NOT NULL DEFAULT 0,
    1.26          "no_reverse_beat_path"          BOOLEAN NOT NULL DEFAULT TRUE,
    1.27          "no_multistage_majority"        BOOLEAN NOT NULL DEFAULT FALSE,
    1.28 -        "schulze_variant"     "schulze_variant" NOT NULL DEFAULT 'tie_breaking_with_negative_strength',
    1.29          CONSTRAINT "timing" CHECK (
    1.30            ( "polling" = FALSE AND
    1.31              "admission_time" NOTNULL AND "discussion_time" NOTNULL AND
    1.32 @@ -677,13 +671,13 @@
    1.33  COMMENT ON COLUMN "initiative"."negative_votes"         IS 'Calculated from table "direct_voter"';
    1.34  COMMENT ON COLUMN "initiative"."direct_majority"        IS 'TRUE, if "positive_votes"/("positive_votes"+"negative_votes") is strictly greater or greater-equal than "direct_majority_num"/"direct_majority_den", and "positive_votes" is greater-equal than "direct_majority_positive", and ("positive_votes"+abstentions) is greater-equal than "direct_majority_non_negative"';
    1.35  COMMENT ON COLUMN "initiative"."indirect_majority"      IS 'Same as "direct_majority", but also considering indirect beat paths';
    1.36 -COMMENT ON COLUMN "initiative"."schulze_rank"           IS 'Schulze-Ranking';
    1.37 -COMMENT ON COLUMN "initiative"."better_than_status_quo" IS 'TRUE, if initiative has a schulze-ranking better than the status quo';
    1.38 -COMMENT ON COLUMN "initiative"."worse_than_status_quo"  IS 'TRUE, if initiative has a schulze-ranking worse than the status quo';
    1.39 +COMMENT ON COLUMN "initiative"."schulze_rank"           IS 'Schulze-Ranking without tie-breaking';
    1.40 +COMMENT ON COLUMN "initiative"."better_than_status_quo" IS 'TRUE, if initiative has a schulze-ranking better than the status quo (without tie-breaking)';
    1.41 +COMMENT ON COLUMN "initiative"."worse_than_status_quo"  IS 'TRUE, if initiative has a schulze-ranking worse than the status quo (without tie-breaking)';
    1.42  COMMENT ON COLUMN "initiative"."reverse_beat_path"      IS 'TRUE, if there is a beat path (may include ties) from this initiative to the status quo';
    1.43  COMMENT ON COLUMN "initiative"."multistage_majority"    IS 'TRUE, if either (a) this initiative has no better rank than the status quo, or (b) there exists a better ranked initiative X, which directly beats this initiative, and either more voters prefer X to this initiative than voters preferring X to the status quo or less voters prefer this initiative to X than voters preferring the status quo to X';
    1.44  COMMENT ON COLUMN "initiative"."eligible"               IS 'Initiative has a "direct_majority" and an "indirect_majority", is "better_than_status_quo" and depending on selected policy the initiative has no "reverse_beat_path" or "multistage_majority"';
    1.45 -COMMENT ON COLUMN "initiative"."winner"                 IS 'Winner is the "eligible" initiative with best "schulze_rank" and in case of unresolved ties with lowest "id"';
    1.46 +COMMENT ON COLUMN "initiative"."winner"                 IS 'Winner is the "eligible" initiative with best "schulze_rank" and in case of ties with lowest "id"';
    1.47  COMMENT ON COLUMN "initiative"."rank"                   IS 'Unique ranking for all "admitted" initiatives per issue; lower rank is better; a winner always has rank 1, but rank 1 does not imply that an initiative is winner; initiatives with "direct_majority" AND "indirect_majority" always have a better (lower) rank than other initiatives';
    1.48  
    1.49  
    1.50 @@ -3854,47 +3848,22 @@
    1.51    IS 'Closes the voting on an issue, and calculates positive and negative votes for each initiative; The ranking is not calculated yet, to keep the (locking) transaction short.';
    1.52  
    1.53  
    1.54 -CREATE FUNCTION "impossible_defeat_strength"()
    1.55 -  RETURNS INT8
    1.56 -  LANGUAGE 'plpgsql' IMMUTABLE AS $$
    1.57 -    BEGIN
    1.58 -      RETURN -1::INT8 << 63;
    1.59 -    END;
    1.60 -  $$;
    1.61 -
    1.62 -COMMENT ON FUNCTION "impossible_defeat_strength"() IS 'An INT8 value lower than any other value returned by function "defeat_strength"(INT4, INT4)';
    1.63 -
    1.64 -
    1.65  CREATE FUNCTION "defeat_strength"
    1.66 -  ( "schulze_variant_p" "schulze_variant",
    1.67 -    "positive_votes_p" INT4,
    1.68 -    "negative_votes_p" INT4 )
    1.69 +  ( "positive_votes_p" INT4, "negative_votes_p" INT4 )
    1.70    RETURNS INT8
    1.71    LANGUAGE 'plpgsql' IMMUTABLE AS $$
    1.72      BEGIN
    1.73 -      IF "schulze_variant_p" >= 'tuple_strength'::"schulze_variant" THEN
    1.74 -        IF "positive_votes_p" > "negative_votes_p" THEN
    1.75 -          RETURN ("positive_votes_p"::INT8 << 31) - "negative_votes_p"::INT8;
    1.76 -        ELSIF "positive_votes_p" = "negative_votes_p" THEN
    1.77 -          RETURN 0::INT8;
    1.78 -        ELSE
    1.79 -          IF "schulze_variant_p" >= 'tie_breaking_with_negative_strength'::"schulze_variant" THEN
    1.80 -            RETURN "positive_votes_p"::INT8 - ("negative_votes_p"::INT8 << 31);
    1.81 -          ELSE
    1.82 -            RETURN "impossible_defeat_strength"();
    1.83 -          END IF;
    1.84 -        END IF;
    1.85 +      IF "positive_votes_p" > "negative_votes_p" THEN
    1.86 +        RETURN ("positive_votes_p"::INT8 << 31) - "negative_votes_p"::INT8;
    1.87 +      ELSIF "positive_votes_p" = "negative_votes_p" THEN
    1.88 +        RETURN 0;
    1.89        ELSE
    1.90 -        IF "positive_votes_p" > "negative_votes_p" THEN
    1.91 -          RETURN "positive_votes_p"::INT8;
    1.92 -        ELSE
    1.93 -          RETURN 0::INT8;
    1.94 -        END IF;
    1.95 +        RETURN -1;
    1.96        END IF;
    1.97      END;
    1.98    $$;
    1.99  
   1.100 -COMMENT ON FUNCTION "defeat_strength"("schulze_variant", INT4, INT4) IS 'Calculates defeat strength (INT8!) of a pairwise defeat primarily by the absolute number of votes for the winner and secondarily by the absolute number of votes for the loser. A tie has a strength of zero.';
   1.101 +COMMENT ON FUNCTION "defeat_strength"(INT4, INT4) IS 'Calculates defeat strength (INT8!) of a pairwise defeat primarily by the absolute number of votes for the winner and secondarily by the absolute number of votes for the loser';
   1.102  
   1.103  
   1.104  CREATE FUNCTION "calculate_ranks"("issue_id_p" "issue"."id"%TYPE)
   1.105 @@ -3904,17 +3873,11 @@
   1.106        "issue_row"         "issue"%ROWTYPE;
   1.107        "policy_row"        "policy"%ROWTYPE;
   1.108        "dimension_v"       INTEGER;
   1.109 -      "vote_matrix"       INT4[][];     -- absolute votes
   1.110 -      "direct_matrix"     INT8[][];     -- direct defeat strength
   1.111 -      "path_matrix"       INT8[][];     -- defeat strength of best path
   1.112 -      "compare_matrix"    BOOLEAN[][];  -- binary relation to create schulze-rank
   1.113 -      "forbidden_matrix"  BOOLEAN[][];  -- forbidden links for tie-breaking
   1.114 -      "modified_matrix"   INT8[][];     -- defeat strength after tie-breaking
   1.115 +      "vote_matrix"       INT4[][];  -- absolute votes
   1.116 +      "matrix"            INT8[][];  -- defeat strength / best paths
   1.117        "i"                 INTEGER;
   1.118        "j"                 INTEGER;
   1.119        "k"                 INTEGER;
   1.120 -      "m"                 INTEGER;
   1.121 -      "n"                 INTEGER;
   1.122        "battle_row"        "battle"%ROWTYPE;
   1.123        "rank_ary"          INT4[];
   1.124        "rank_v"            INT4;
   1.125 @@ -3954,16 +3917,15 @@
   1.126        IF "i" != "dimension_v" OR "j" != "dimension_v" + 1 THEN
   1.127          RAISE EXCEPTION 'Wrong battle count (should not happen)';
   1.128        END IF;
   1.129 -      -- Store defeat strengths in "path_matrix" using "defeat_strength"
   1.130 +      -- Store defeat strengths in "matrix" using "defeat_strength"
   1.131        -- function:
   1.132 -      "direct_matrix" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]);
   1.133 +      "matrix" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]);
   1.134        "i" := 1;
   1.135        LOOP
   1.136          "j" := 1;
   1.137          LOOP
   1.138            IF "i" != "j" THEN
   1.139 -            "direct_matrix"["i"]["j"] := "defeat_strength"(
   1.140 -              "policy_row"."schulze_variant",
   1.141 +            "matrix"["i"]["j"] := "defeat_strength"(
   1.142                "vote_matrix"["i"]["j"],
   1.143                "vote_matrix"["j"]["i"]
   1.144              );
   1.145 @@ -3975,7 +3937,6 @@
   1.146          "i" := "i" + 1;
   1.147        END LOOP;
   1.148        -- Find best paths:
   1.149 -      "path_matrix" := "direct_matrix";
   1.150        "i" := 1;
   1.151        LOOP
   1.152          "j" := 1;
   1.153 @@ -3984,13 +3945,13 @@
   1.154              "k" := 1;
   1.155              LOOP
   1.156                IF "i" != "k" AND "j" != "k" THEN
   1.157 -                IF "path_matrix"["j"]["i"] < "path_matrix"["i"]["k"] THEN
   1.158 -                  IF "path_matrix"["j"]["i"] > "path_matrix"["j"]["k"] THEN
   1.159 -                    "path_matrix"["j"]["k"] := "path_matrix"["j"]["i"];
   1.160 +                IF "matrix"["j"]["i"] < "matrix"["i"]["k"] THEN
   1.161 +                  IF "matrix"["j"]["i"] > "matrix"["j"]["k"] THEN
   1.162 +                    "matrix"["j"]["k"] := "matrix"["j"]["i"];
   1.163                    END IF;
   1.164                  ELSE
   1.165 -                  IF "path_matrix"["i"]["k"] > "path_matrix"["j"]["k"] THEN
   1.166 -                    "path_matrix"["j"]["k"] := "path_matrix"["i"]["k"];
   1.167 +                  IF "matrix"["i"]["k"] > "matrix"["j"]["k"] THEN
   1.168 +                    "matrix"["j"]["k"] := "matrix"["i"]["k"];
   1.169                    END IF;
   1.170                  END IF;
   1.171                END IF;
   1.172 @@ -4004,132 +3965,6 @@
   1.173          EXIT WHEN "i" = "dimension_v";
   1.174          "i" := "i" + 1;
   1.175        END LOOP;
   1.176 -      -- initial calculation of binary relation:
   1.177 -      "compare_matrix" := array_fill(NULL::BOOLEAN, ARRAY["dimension_v", "dimension_v"]);
   1.178 -      "i" := 1;
   1.179 -      LOOP
   1.180 -        "j" := 1;
   1.181 -        LOOP
   1.182 -          IF "i" != "j" THEN
   1.183 -            IF "path_matrix"["i"]["j"] > "path_matrix"["j"]["i"] THEN
   1.184 -              "compare_matrix"["i"]["j"] = TRUE;
   1.185 -              "compare_matrix"["j"]["i"] = FALSE;
   1.186 -            ELSIF "path_matrix"["i"]["j"] < "path_matrix"["j"]["i"] THEN
   1.187 -              "compare_matrix"["i"]["j"] = FALSE;
   1.188 -              "compare_matrix"["j"]["i"] = TRUE;
   1.189 -            END IF;
   1.190 -          END IF;
   1.191 -          EXIT WHEN "j" = "dimension_v";
   1.192 -          "j" := "j" + 1;
   1.193 -        END LOOP;
   1.194 -        EXIT WHEN "i" = "dimension_v";
   1.195 -        "i" := "i" + 1;
   1.196 -      END LOOP;
   1.197 -      -- tie-breaking:
   1.198 -      IF "policy_row"."schulze_variant" >= 'partial_tie_breaking'::"schulze_variant" THEN
   1.199 -        "modified_matrix"  := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]);
   1.200 -        "forbidden_matrix" := array_fill(NULL::BOOLEAN, ARRAY["dimension_v", "dimension_v"]);
   1.201 -        "m" := 1;
   1.202 -        LOOP
   1.203 -          "n" := "m" + 1;
   1.204 -          LOOP
   1.205 -            IF "compare_matrix"["m"]["n"] ISNULL THEN
   1.206 -              "i" := 1;
   1.207 -              LOOP
   1.208 -                "j" := 1;
   1.209 -                LOOP
   1.210 -                  IF "i" != "j" THEN
   1.211 -                    "forbidden_matrix"["i"]["j"] := FALSE;
   1.212 -                    "modified_matrix"["i"]["j"] := "path_matrix"["i"]["j"];
   1.213 -                  END IF;
   1.214 -                  EXIT WHEN "j" = "dimension_v";
   1.215 -                  "j" := "j" + 1;
   1.216 -                END LOOP;
   1.217 -                EXIT WHEN "i" = "dimension_v";
   1.218 -                "i" := "i" + 1;
   1.219 -              END LOOP;
   1.220 -              LOOP
   1.221 -                "i" := 1;
   1.222 -                LOOP
   1.223 -                  "j" := 1;
   1.224 -                  LOOP
   1.225 -                    IF "i" != "j" THEN
   1.226 -                      -- TODO: Bug here. This can cause other links to be forbidden, which should not be forbidden:
   1.227 -                      IF "modified_matrix"["m"]["n"] = "direct_matrix"["i"]["j"] THEN
   1.228 -                        "forbidden_matrix"["i"]["j"] := TRUE;
   1.229 -                      END IF;
   1.230 -                    END IF;
   1.231 -                    EXIT WHEN "j" = "dimension_v";
   1.232 -                    "j" := "j" + 1;
   1.233 -                  END LOOP;
   1.234 -                  EXIT WHEN "i" = "dimension_v";
   1.235 -                  "i" := "i" + 1;
   1.236 -                END LOOP;
   1.237 -                "i" := 1;
   1.238 -                LOOP
   1.239 -                  "j" := 1;
   1.240 -                  LOOP
   1.241 -                    IF "i" != "j" THEN
   1.242 -                      IF "forbidden_matrix"["i"]["j"] THEN
   1.243 -                        "modified_matrix"["i"]["j"] := "impossible_defeat_strength"();
   1.244 -                      ELSE
   1.245 -                        "modified_matrix"["i"]["j"] := "direct_matrix"["i"]["j"];
   1.246 -                      END IF;
   1.247 -                    END IF;
   1.248 -                    EXIT WHEN "j" = "dimension_v";
   1.249 -                    "j" := "j" + 1;
   1.250 -                  END LOOP;
   1.251 -                  EXIT WHEN "i" = "dimension_v";
   1.252 -                  "i" := "i" + 1;
   1.253 -                END LOOP;
   1.254 -                "i" := 1;
   1.255 -                LOOP
   1.256 -                  "j" := 1;
   1.257 -                  LOOP
   1.258 -                    IF "i" != "j" THEN
   1.259 -                      "k" := 1;
   1.260 -                      LOOP
   1.261 -                        IF "i" != "k" AND "j" != "k" THEN
   1.262 -                          IF "modified_matrix"["j"]["i"] < "modified_matrix"["i"]["k"] THEN
   1.263 -                            IF "modified_matrix"["j"]["i"] > "modified_matrix"["j"]["k"] THEN
   1.264 -                              "modified_matrix"["j"]["k"] := "modified_matrix"["j"]["i"];
   1.265 -                            END IF;
   1.266 -                          ELSE
   1.267 -                            IF "modified_matrix"["i"]["k"] > "modified_matrix"["j"]["k"] THEN
   1.268 -                              "modified_matrix"["j"]["k"] := "modified_matrix"["i"]["k"];
   1.269 -                            END IF;
   1.270 -                          END IF;
   1.271 -                        END IF;
   1.272 -                        EXIT WHEN "k" = "dimension_v";
   1.273 -                        "k" := "k" + 1;
   1.274 -                      END LOOP;
   1.275 -                    END IF;
   1.276 -                    EXIT WHEN "j" = "dimension_v";
   1.277 -                    "j" := "j" + 1;
   1.278 -                  END LOOP;
   1.279 -                  EXIT WHEN "i" = "dimension_v";
   1.280 -                  "i" := "i" + 1;
   1.281 -                END LOOP;
   1.282 -                IF "modified_matrix"["m"]["n"] > "modified_matrix"["n"]["m"] THEN
   1.283 -                  "compare_matrix"["m"]["n"] := TRUE;
   1.284 -                  "compare_matrix"["n"]["m"] := FALSE;
   1.285 -                  EXIT;
   1.286 -                ELSIF "modified_matrix"["m"]["n"] < "modified_matrix"["n"]["m"] THEN
   1.287 -                  "compare_matrix"["m"]["n"] := FALSE;
   1.288 -                  "compare_matrix"["n"]["m"] := TRUE;
   1.289 -                  EXIT;
   1.290 -                ELSIF "modified_matrix"["m"]["n"] = "impossible_defeat_strength"() THEN
   1.291 -                  EXIT;
   1.292 -                END IF;
   1.293 -              END LOOP;
   1.294 -            END IF;
   1.295 -            EXIT WHEN "n" = "dimension_v";
   1.296 -            "n" := "n" + 1;
   1.297 -          END LOOP;
   1.298 -          EXIT WHEN "m" = "dimension_v" - 1;
   1.299 -          "m" := "m" + 1;
   1.300 -        END LOOP;
   1.301 -      END IF;
   1.302        -- Determine order of winners:
   1.303        "rank_ary" := array_fill(NULL::INT4, ARRAY["dimension_v"]);
   1.304        "rank_v" := 1;
   1.305 @@ -4144,7 +3979,7 @@
   1.306                IF
   1.307                  "i" != "j" AND
   1.308                  "rank_ary"["j"] ISNULL AND
   1.309 -                "compare_matrix"["j"]["i"]
   1.310 +                "matrix"["j"]["i"] > "matrix"["i"]["j"]
   1.311                THEN
   1.312                  -- someone else is better
   1.313                  EXIT;
   1.314 @@ -4204,7 +4039,7 @@
   1.315            "better_than_status_quo" = "rank_ary"["i"] < "rank_ary"["dimension_v"],
   1.316            "worse_than_status_quo"  = "rank_ary"["i"] > "rank_ary"["dimension_v"],
   1.317            "multistage_majority"    = "rank_ary"["i"] >= "rank_ary"["dimension_v"],
   1.318 -          "reverse_beat_path"      = "path_matrix"["dimension_v"]["i"] >= 0,
   1.319 +          "reverse_beat_path"      = "matrix"["dimension_v"]["i"] >= 0,
   1.320            "eligible"               = FALSE,
   1.321            "winner"                 = FALSE,
   1.322            "rank"                   = NULL  -- NOTE: in cases of manual reset of issue state