How to implement complexed custom sort?

Not that it helps with your sorting question, but I have done two chess libs in Elixir…

The second is a translated from Erlang and generates all possible moves. Maybe it helps

My AVLTree implementation with custom sorting function: GitHub - japplegame/avl_tree: Pure Elixir AVL tree implementation · GitHub

Thanks, but this is just an example for a more generic question… Sorting your nested structs in ways you desire to.
But I’m gonna have fun with those repos!

Giving a custom function to (e.g. Enum.sort/3) was what I first considered, but it doesn’t help when you want to sort nested structs…
But anyway, I like your AVLTree! It is very simple. Thanks!

And I’ve kind of came up with some way: implementing a custom sort Protocol may do.

defprotocol ChessSorter do
  @spec asc(any, any) :: boolean
  def asc(_, _)
end

defmodule Coordinate do
  defstruct [:x, :y]

  defimpl ChessSorter, for: __MODULE__ do
    def asc(%{x: x1, y: y1}, %{x: x2, y: y2}) when x1 == x2, do: y1 <= y2
    def asc(%{x: x1}, %{x: x2}), x1 <= x2
  end
end

defmodule Piece do
  defstruct [:type]

  defimpl ChessSorter, for: __MODULE__ do
    @types %{
      Pawn => 1,
      Knight => 2,
      Bishop => 3,
      Rook => 4,
      Queen => 5,
      King => 6,
    }

    def asc(%{type: t1}, %{tpe: t2}), do: @types[t1] <= @types[t2]
  end
end

defmodule Fighter
  defstruct [ :owner, :piece, :position ]

  defimpl ChessSorter, for: __MODULE__ do
    def asc(
          %{owner: o1, piece: p2, position: pos1},
          %{owner: o2, piece: p2, position: pos2}
        )
        when o1 == o2 and p1 == p2,
        do: ChessSorter.asc(pos1, pos2)

    def asc(%{owner: o1, piece: p2}, %{owner: o2, piece: p2}) when o1 == o2,
      do: ChessSorter.asc(p1, p2)

    def asc(%{owner: :opponent}, %{owner: :player}), do: false
    def asc(%{owner: :player}, %{owner: :opponent}), do: true
  end
end

And then : fighters |> Enum.sort(&ChessSorter.asc/2). So this recursively does sorting down to basic Kernel.<= s.

But I am afraid this may be veery slow. Is it?

Elixir’s sorting function is stable. This means that you can first sort the whole list of fighters on the least-important condition, then on the second-least important condition , etc. and finally on the most important condtion, and they will end up in the order you’d expect.

So in your case

fighters
|> Enum.sort_by(fn fighter -> fighter.position end)
|> Enum.sort_by(fn fighter -> fighter.piece.type end)
|> Enum.sort_by(fn fighter -> fighter.owner end)

And, by taking advantage of the fact that tuples are ordered elementwise (we look at the next element only if the current element is equal), we could write it like this instead as well:

fighters
|> Enum.sort_by(fn fighter -> {fighter.owner, fighter.piece.type, fighter.position} end)

However, this will not give the answer you’d like yet, because many things are represented by symbols, which by default are sorted alphabetically (whereas you’d like the given order King > Queen > Bishop > ... and player > opponent. The translation functions you wrote for your custom sorter would indeed be a solution to this.

It is possible to automate that a little, by creating a map of the numerically ordered equivalents (like piece_type_ordering = piece_types |> Enum.with_index |> Enum.into(%{})), which you’d want to generate at compile time, so you can just write a function then that will turn a given thing into their ordering.

I think a protocol like the following might make sense:

defprotocol Orderable
  @doc """ 
   Turns the given structure into something that can be compared and sorted in the desired order.
   """
  @spec orderable(any) :: any
  orderable(_)
end

whose implementation for e.g. %Piece would simply return the number that is stored for the given type’s symbol key.

And for %Fighter, it would return e.g.

def orderable(fighter)
  import Orderable
  {orderable(fighter.owner), orderable(fighter.piece), fighter.position}
end

Wow, this is amazing how minimum the code could be. It was a whole new study for me. Thanks for the information!!

With Orderable protocol you also can use AVLTree like this:

AVLTree.new(fn a, b -> Orderable.orderable(a) < Orderable.orderable(b))

All inserted elements will be automatically sorted.

@japplegame Interesting! I wrote a library a while back to build and work with Priority Queues called prioqueue, which abstracts away the implementation details of how this queue is maintained, and lets you plug in your own. I think making an AVLTree implementation would be a great idea! When will you upload AVLTree to Hex.PM?

@ndac_todoroki Glad to be able to help. I guess the Orderable protocol could be wrapped in a library, since I think it is rather common to want to do this kind of stuff. We might even provide built-in implementations for common ordered enumerables that call Orderable.orderable for all their contained elements… Let me conjure up something!

Done! The orderable library has been built, tested, documented and published.