-- Bei den Vergleichsangaben sind die Werte fuer die Ueberpruefungen
-- ob die Liste leer ist nicht mit eingerechnet. Genauso sind die
-- Ueberpruefungen fuer die "exit when" Bedingungen nicht mit
-- eingerechnet, da diese nicht fuer den Abgleich der Elemente unter-
-- einander wichtig sind.

with Ada.Text_Io; use Ada.Text_Io;
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io;

procedure Info_Blatt9_Aufgabe5 is

  type Item;
  type Ref_Item is access Item;

  -- Next is right
  -- Prev is left
  type Item is record
    Value: Integer;
    Next: Ref_Item;
    Prev: Ref_Item;
  end record;

  -- returns an empty list
  -- 0 Vergleiche
  function Empty return Ref_Item is
  begin
    return null;
  end Empty;


  -- checks whether a list is empty or not
  -- 1 Vergleich
  function Isempty (List: Ref_Item) return Boolean is
  begin
    return List = null;
  end Isempty;

  -- removes a given element from a list
  -- n Vergleiche bei (if P.Value = Item).
  function Remove (Item: Integer; List: Ref_Item) return Ref_Item is
    P: Ref_Item := List;
  begin
    if List /= null and then List.Prev /= null then
      loop
        if P.Value = Item then
          P.Prev.Next := P.Next;
          P.Next.Prev := P.Prev;
        end if;

        exit when P = List.Prev;

        P := P.Next;
      end loop;
    end if;

    return P;
  end Remove;

  -- prints all member elements of a list
  -- 0 Vergleiche
  procedure Print (List: Ref_Item) is
    P: Ref_Item := List;
  begin
    if List /= null and then List.Prev /= null then
      loop
        Put (P.Value'Img & ",");
        exit when P = List.Prev;
        P := P.Next;
      end loop;
    end if;
  end Print;

  -- checks whether a list contains a given element or not
  -- n Vergleiche bei (P.Value = Item).
  function Contain (Item: Integer; List: Ref_Item) return Boolean is
    P: Ref_Item := List;
  begin
    if List /= null and then List.Prev /= null then
      loop
        if P.Value = Item then
          return true;
        end if;

        exit when P = List.Prev;

        P := P.Next;
      end loop;
    end if;

    return false;
  end Contain;

  -- inserts an element into a list if it isn't already included
  -- 1 Vergleich
  function Enter (Elem: Integer; List: Ref_Item) return Ref_Item is
    List_Next_Item: Ref_Item;
  begin
    if not Contain (Elem, List) and then List /= null then
      List_Next_Item := List.Next;
      List.Next := new Item'(Elem, List_Next_Item, List);
      List_Next_Item.Prev := List.Next;
    elsif not Contain (Elem, List) and List = null then
      List_Next_Item := new Item'(Elem, null, null);
      List_Next_Item.Next := List_Next_Item;
      List_Next_Item.Prev := List_Next_Item;
      return List_Next_Item;
    end if;

    return List;
  end Enter;

  -- calculates the union of two lists
  -- 0 Vergleiche
  function Union (List1, List2: Ref_Item) return Ref_item is
    P: Ref_Item := List1;
    Result: Ref_Item := Empty;
  begin
    if List1 /= null and then List1.Prev /= null then
      loop
        Result := Enter (P.Value, Result);
        exit when P = List1.Prev;
        P := P.Next;
      end loop;
    end if;

    P := List2;

    if List2 /= null and then List2.Prev /= null then
      loop
        Result := Enter (P.Value, Result);
        exit when P = List2.Prev;
        P := P.Next;
      end loop;
    end if;

    return Result;
  end Union;

  -- calculates the intersection of two lists
  -- n Vergleiche
  function Intersection (List1, List2: Ref_Item) return Ref_Item is
    P: Ref_Item := List1;
    Result: Ref_Item := Empty;
  begin
    loop
      if Contain (P.Value, List2) then
        Result := Enter (P.Value, Result);
      end if;

      exit when P = List1.Prev;

      P := P.Next;
    end loop;

    return Result;
  end Intersection;

  Anchor : Ref_Item;
  Anchor2: Ref_Item;
begin
  Anchor := Empty;
  Anchor2 := Empty;

  -- initialize list 1
  Anchor           := new Item'(2, null, null);
  Anchor.Next      := new Item'(3, null, null);
  Anchor.Prev      := new Item'(1, Anchor, Anchor.Next);
  Anchor.Next.Next := Anchor.Prev;
  Anchor.Next.Prev := Anchor;

  -- initialize list 2
  Anchor2           := new Item'(4, null, null);
  Anchor2.Next      := new Item'(5, null, null);
  Anchor2.Prev      := new Item'(6, Anchor2, Anchor2.Next);
  Anchor2.Next.Next := Anchor2.Prev;
  Anchor2.Next.Prev := Anchor2;

  Put_Line ("Dies ist die erste Liste:");
  Print (Anchor);

  New_Line;
  New_Line;

  Put_Line ("Dies ist die zweite Liste:");
  Print (Anchor2);

  New_Line;
  New_Line;

  Put_Line ("Der ersten Liste wurde das Element '4' hinzugefuegt:");
  Anchor := Enter (4, Anchor);
  Print (Anchor);

  New_Line;
  New_Line;

  Put_Line ("Ueberpruefung ob das Element '2' in der ersten Liste ist:");
  Put (Contain (2, Anchor)'Img);

  New_Line;
  New_Line;

  Put_Line ("Ueberpruefung ob die erste Liste leer ist:");
  Put (Isempty (Anchor)'Img);

  New_Line;
  New_Line;

  Put_Line ("Das Element '2' aus der ersten Liste entfernt:");
  Anchor := Remove (2, Anchor);
  Print (Anchor);

  New_Line;
  New_Line;

  Put_Line ("Ueberpruefung ob das Element '2' in der ersten Liste ist:");
  Put (Contain (2, Anchor)'Img);

  New_Line;
  New_Line;

  Put_Line ("Die Vereinigungsmenge beider Listen ist:");
  Print (Union (Anchor, Anchor2));

  New_Line;
  New_Line;

  Put_Line ("Die Schnittmenge beider Listen ist:");
  Print (Intersection (Anchor, Anchor2));
end Info_Blatt9_Aufgabe5;