## -*- Mode: octave -*-
## christo

## Let X and Y be ranked sets objects. We want to count how far away the
## rankings are.  One simple method is to use the bubble-sort edit
## distance.
##
## Note that the method can be used no matter whether the two sets
## contain exactly the same objects or not.
##
## Finally, while both distances are symmetric, only the latter is a
## true distance!
## D(X,Y)<=D(X,Z) + D(Z,Y)



X=[5 4 3 2 1];
Y=[1 4 2 3];

## method 1 - check relative rankings, disregarding missing values!
## This is is not a true distance, but a bound on the second distance
## It is, never the less, symmtetric
function distance = RankingDistance(X, Y)
  n_swaps = 0;
  flag = true;
  n = length(Y);
  while(flag)
    flag = false;
    for i=1:n-1
      ## if ith element of Y has a larger rank then swap!
      x_i_rank = find(X==Y(i));
      x_in_rank = find(X==Y(i+1));
      ## if the element does not exist then assume it is at the end
      if ((x_i_rank > x_in_rank) || (length(x_i_rank)==0))
        ## do nothing if neither element exists
        if (length(x_in_rank) > 0) 
          tmp = Y(i+1);
          Y(i+1) = Y(i);
          Y(i) = tmp;
          flag = true;
          if (length(x_i_rank)>0) 
            n_swaps++;
          end
        endif
      endif
    end
  endwhile
  distance = n_swaps;
endfunction

## method 2 - add all missing elements at the end of each array
## This is a true distance
function distance = MissingValuesRankingDistance(X, Y)
  n_swaps = 0;
  flag = true;
  nx = length(X);
  ny = length(Y);

  n_adds = 0;
  ## copy elements from X to Y if they do not exist there
  for i=1:nx
    if (sum(Y==X(i)) == 0)
      Y = [Y X(i)];
      n_adds++;
    end
  end

  ## copy elements from Y to X (we only have to do it until ny since the
  ## other new elements were by definition already in X)
  for i=1:ny
    if (sum(X==Y(i)) == 0)
      X = [X Y(i)];
      n_adds++;
    end
  end

  n = length(X);
  assert (n==length(Y));

  while(flag)
    flag = false;
    for i=1:n-1
      ## if ith element of Y has a larger rank then swap!
      x_i_rank = find(X==Y(i));
      x_in_rank = find(X==Y(i+1));
      
      if (x_i_rank > x_in_rank)
        tmp = Y(i+1);
        Y(i+1) = Y(i);
        Y(i) = tmp;
        flag = true;
        n_swaps++;
      endif
    end
  endwhile
  distance = n_swaps + n_adds;
endfunction

printf("Output for:")
X
Y
printf("Ranking distance: %d\n", RankingDistance(X,Y));
printf("Missing value ranking distance: %d\n", MissingValuesRankingDistance(X,Y));

Z =[];
printf("Now Z is the zero ranking in the algebra of rankings.  Addition is concatenation with the removal of spurious elements.\n");
printf("D1(Z,X): %d==%d\n", RankingDistance(X,Z), RankingDistance(Z,X));
printf("D2(Z,X): %d==%d\n", MissingValuesRankingDistance(X,Z), MissingValuesRankingDistance(Z,X));


printf ("Testing\n");
for test=1:80
  X=randperm(ceil(exprnd(10)));
  Y=randperm(ceil(exprnd(10)));
  assert(RankingDistance(X, Y) == RankingDistance(Y, X));
  assert(MissingValuesRankingDistance(X, Y) == MissingValuesRankingDistance(Y, X));
  assert(RankingDistance(X, Y) <= MissingValuesRankingDistance(X,Y));
  
  printf(".");
  fflush(stdout);
end

printf("\nDone!\n");

