------------------------------------------------------------------------------
--                                                                          --
--                         GNAT LIBRARY COMPONENTS                         --
--                                                                          --
--         A D A . C O N T A I N E R S . S T A B L E _ S O R T I N G        --
--                                                                          --
--                                 B o d y                                  --
--                                                                          --
--                     Copyright (C) 1995-2021, AdaCore                     --
--                                                                          --
-- GNAT is free software;  you can  redistribute it  and/or modify it under --
-- terms of the  GNU General Public License as published  by the Free Soft- --
-- ware  Foundation;  either version 3,  or (at your option) any later ver- --
-- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
-- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
--                                                                          --
-- As a special exception under Section 7 of GPL version 3, you are granted --
-- additional permissions described in the GCC Runtime Library Exception,   --
-- version 3.1, as published by the Free Software Foundation.               --
--                                                                          --
-- You should have received a copy of the GNU General Public License and    --
-- a copy of the GCC Runtime Library Exception along with this program;     --
-- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
-- <http://www.gnu.org/licenses/>.                                          --
--                                                                          --
-- GNAT was originally developed  by the GNAT team at  New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc.      --
--                                                                          --
------------------------------------------------------------------------------

package body Ada.Containers.Stable_Sorting is
   package body List_Descriptors is
      procedure Doubly_Linked_List_Sort (List : List_Descriptor) is

         Empty  : constant List_Descriptor := (Nil, Nil, 0);

         function Merge_Sort (Arg : List_Descriptor) return List_Descriptor;
         --  Sort list of given length using MergeSort; length must be >= 2.
         --  As required by RM, the sort is stable.

         ----------------
         -- Merge_Sort --
         ----------------

         function Merge_Sort (Arg : List_Descriptor) return List_Descriptor
         is
            procedure Split_List
              (Unsplit : List_Descriptor; Part1, Part2 : out List_Descriptor);
            --  Split list into two parts for divide-and-conquer.
            --  Unsplit.Length must be >= 2.

            function Merge_Parts
              (Part1, Part2 : List_Descriptor) return List_Descriptor;
            --  Merge two sorted lists, preserving sorted property.

            ----------------
            -- Split_List --
            ----------------

            procedure Split_List
              (Unsplit : List_Descriptor; Part1, Part2 : out List_Descriptor)
            is
               Rover : Node_Ref := Unsplit.First;
               Bump_Count : constant Count_Type := (Unsplit.Length - 1) / 2;
            begin
               for Iter in 1 .. Bump_Count loop
                  Rover := Next (Rover);
               end loop;

               Part1 := (First  => Unsplit.First,
                         Last   => Rover,
                         Length => Bump_Count + 1);

               Part2 := (First => Next (Rover),
                         Last  => Unsplit.Last,
                         Length => Unsplit.Length - Part1.Length);

               --  Detach
               Set_Next (Part1.Last, Nil);
               Set_Prev (Part2.First, Nil);
            end Split_List;

            -----------------
            -- Merge_Parts --
            -----------------

            function Merge_Parts
              (Part1, Part2 : List_Descriptor) return List_Descriptor
            is
               procedure Detach_First (Source   : in out List_Descriptor;
                                       Detached : out Node_Ref);
               --  Detach the first element from a non-empty list and
               --  return the detached node via the Detached parameter.

               ------------------
               -- Detach_First --
               ------------------

               procedure Detach_First (Source   : in out List_Descriptor;
                                       Detached : out Node_Ref) is
               begin
                  Detached := Source.First;

                  if Source.Length = 1 then
                     Source := Empty;
                  else
                     Source := (Next (Source.First),
                                Source.Last,
                                Source.Length - 1);

                     Set_Prev (Next (Detached), Nil);
                     Set_Next (Detached, Nil);
                  end if;
               end Detach_First;

               P1     : List_Descriptor := Part1;
               P2     : List_Descriptor := Part2;
               Merged : List_Descriptor := Empty;

               Take_From_P2 : Boolean;
               Detached     : Node_Ref;

            --  Start of processing for Merge_Parts

            begin
               while (P1.Length /= 0) or (P2.Length /= 0) loop
                  if P1.Length = 0 then
                     Take_From_P2 := True;
                  elsif P2.Length = 0 then
                     Take_From_P2 := False;
                  else
                     --  If the compared elements are equal then Take_From_P2
                     --  must be False in order to ensure stability.

                     Take_From_P2 := P2.First < P1.First;
                  end if;

                  if Take_From_P2 then
                     Detach_First (P2, Detached);
                  else
                     Detach_First (P1, Detached);
                  end if;

                  if Merged.Length = 0 then
                     Merged := (First | Last => Detached, Length => 1);
                  else
                     Set_Prev (Detached, Merged.Last);
                     Set_Next (Merged.Last, Detached);
                     Merged.Last := Detached;
                     Merged.Length := Merged.Length + 1;
                  end if;
               end loop;
               return Merged;
            end Merge_Parts;

         --  Start of processing for Merge_Sort

         begin
            if Positive (Arg.Length) < 2 then
               --  already sorted
               return Arg;
            end if;

            declare
               Part1, Part2 : List_Descriptor;
            begin
               Split_List (Unsplit => Arg, Part1 => Part1, Part2 => Part2);

               Part1 := Merge_Sort (Part1);
               Part2 := Merge_Sort (Part2);

               return Merge_Parts (Part1, Part2);
            end;
         end Merge_Sort;

      --  Start of processing for Sort

      begin
         if List.Length > 1 then
            --  If a call to the formal "<" op references the container
            --  during sorting, seeing an empty container seems preferable
            --  to seeing an internally inconsistent container.
            --
            Update_Container (Empty);

            Update_Container (Merge_Sort (List));
         end if;
      end Doubly_Linked_List_Sort;
   end List_Descriptors;
end Ada.Containers.Stable_Sorting;