------------------------------------------------------------------------------
-- Copyright (C) 2020 by Heisenbug Ltd. (gh+spat@heisenbug.eu)
--
-- This work is free. You can redistribute it and/or modify it under the
-- terms of the Do What The Fuck You Want To Public License, Version 2,
-- as published by Sam Hocevar. See the LICENSE file for more details.
------------------------------------------------------------------------------
pragma License (Unrestricted);
with Ada.Containers.Bounded_Vectors;
package body SPAT.Entity.Tree is
package body Generic_Sorting is
package Cursor_Lists is new
Ada.Containers.Bounded_Vectors (Index_Type => Positive,
Element_Type => Cursor,
"=" => "=");
------------------------------------------------------------------------
-- Sort
--
-- This is a "sort by proxy". The way it works that we first copy the
-- children's cursors into a vector which then gets sorted. After this
-- step, we rearrange the subtree in the order of elements in the
-- vector.
------------------------------------------------------------------------
procedure Sort (Tree : in out T;
Parent : in Cursor) is
Num_Children : constant Ada.Containers.Count_Type :=
Entity.Tree.Child_Count (Parent => Parent);
use type Ada.Containers.Count_Type;
The_List : Cursor_Lists.Vector (Capacity => Num_Children);
begin
if Num_Children < 2 then
-- No elements to sort.
return;
end if;
-- Copy the tree's cursor into The_List.
for C in Tree.Iterate_Children (Parent => Parent) loop
The_List.Append (New_Item => C);
end loop;
-- Sort the list with our tree cursors.
declare
------------------------------------------------------------------
-- Before
--
-- Comparison operator.
------------------------------------------------------------------
function Before (Left : in Cursor;
Right : in Cursor) return Boolean is
(Before -- from the generic instance
(Left => Entity.Tree.Element (Position => Left),
Right => Entity.Tree.Element (Position => Right)));
package Sorting is new
Cursor_Lists.Generic_Sorting ("<" => Before);
begin
Sorting.Sort (Container => The_List);
end;
-- Now rearrange the subtree according to our sorting order.
for C of The_List loop
Tree.Splice_Subtree (Parent => Parent,
Before => Entity.Tree.No_Element,
Position => C);
end loop;
end Sort;
end Generic_Sorting;
end SPAT.Entity.Tree;