{**********************************************************************
Copyright (C) 2009 by Salvatore Licciardi

Web http://www.webalice.it/turylicciardi    eMail turylicciardi@tiscali.it

 This program is free software: you can redistribute it and/or modify it under
 the terms of the GNU General Public License as published by the Free Software
 Foundation, version 3 of the License.
 This program is distributed in the hope  that it will be useful , but WITHOUT
 ANY WARRANTY without even the implied warranty  of MERCHANTABILITY or FITNESS
 FOR A PARTICULAR PURPOSE.
 See the GNU General Public License for more details. You should have received
 a copy of the GNU General Public License along with this program. If not, see
 http://www.gnu.org/licenses/

 **********************************************************************}

unit LDU_PCH;  {oggetto di lista dinamica unidirezionale di puntatori di carattere}
{$MODE ObjFpc}
interface

uses strings;

type   Tipo=PChar;    {sinonimo per la generica informazione}

type   ptrx=^nodo;

       nodo=record
         info:Tipo;    {generica informazione}
         next:ptrx;    {puntatore unidirezionale: necessario , occupa 4 byte}
         {....         altri dati}
         end;

type  ListaDinamicaUnidirezionale=object
       public
        l:ptrx;
        constructor init;
        destructor destroy;

        {Input}
        function input_iniziale(valore:Tipo):pointer;
        function input_finale(valore:Tipo):pointer;
        function input_dopo_indirizzo(l3:pointer; valore:Tipo):pointer;
        function input_ennesimo(valore:Tipo; ennesimo:longint):pointer;
        {Cacellazioni}
        function cancella_iniziale:pointer;
        function cancella_finale:pointer;
        function cancella_dopo_indirizzo(l2:pointer; quantita:longint):pointer;
        function cancella_ennesimo(ennesimo,quantita:longint):pointer;
        function cerca_e_cancella(valore:Tipo; ennesimo:longint):longint; {ritorna la posizione dove era}
        function Aggiorna(valore1:Tipo; ennesimo:longint; valore2:Tipo):longint; {ritorna la posizione dove aggiornato}
        function Aggiorna_ennesimo(ennesimo:longint; valore:Tipo):longint; {ritorna la posizione dove aggiornato}
        {Altro}
        function inserisci(var destinazione:ListaDinamicaUnidirezionale; inizio_dest,inizio_orig,quantita:longint):longint;
        function inserisci_da(var destinazione:ListaDinamicaUnidirezionale;
                              inizio_dest:longint; inizio_orig:pointer; quantita:longint):longint;
        function NumElementi:longint;
        procedure stampa;

       private
        elementi:longint;
       end;

{Ricerche}
function get_iesimo(l2:pointer; iesimo:longint; var valido:boolean):Tipo;
function posizione(l2:pointer; valore:Tipo):longint;
function cerca_ennesimo(l2:pointer; ennesimo:longint):pointer;
function cerca_ennesimo_valore(l2:pointer; ennesimo:longint; valore:Tipo):pointer;
function cerca_ennesimo_valore_precedente(l2:pointer; ennesimo:longint; valore:Tipo):pointer;
function Count(l2:pointer; valore:Tipo):longint;
function cerca_valore(l2:pointer; valore:Tipo):pointer;

implementation

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function MemAvail:longint;  { a partire da FPC 1.9.6 }
begin
memAvail:=high(longint);
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.NumElementi:longint;
begin
NumElementi:=elementi;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.cancella_iniziale:pointer;
var nuovo:ptrx;
begin
if l=nil then
         begin
         cancella_iniziale:=nil;
         Exit;
         end;
nuovo:=l;
l:=l^.next;
cancella_iniziale:=l;
dispose(nuovo);
dec(elementi);
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.cancella_finale:pointer;
var ora,prec,prec2:ptrx;
begin
prec2:=nil;
prec:=nil;
ora:=l;
while ora<>nil do
      begin
      prec2:=prec;
      prec:=ora;
      ora:=ora^.next;
      end;
if prec2=nil then                  {c'era un solo elemento}
         begin
         l:=cancella_iniziale;
         cancella_finale:=l;       {l, dovrebbe essere sempre =nil}
         Exit;
         end;
dispose(prec);
prec2^.next:=nil;
dec(elementi);
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.cancella_ennesimo(ennesimo,quantita:longint):pointer;
var ll,lll:ptrx;
begin
if (quantita<1)or(ennesimo<1) then
   begin
   cancella_ennesimo:=nil;
   Exit;
   end;

if ennesimo=1 then
   begin
   while quantita>0 do
         begin
         l:=ListaDinamicaUnidirezionale.cancella_iniziale;
         if l=nil then Break;
         dec(quantita);
         end;
   cancella_ennesimo:=l;
   Exit;
   end;

cancella_ennesimo:=l;
ll:=l;
while ennesimo>2 do  {mi posiziono una locazione prima}
      begin
      ll:=ll^.next;
      if ll=nil then
                begin
                cancella_ennesimo:=nil; {lista meno lunga di quanto doveva essere}
                Exit;
                end;
      dec(ennesimo);
      end;
while quantita>0 do
      begin
      lll:=ll^.next;
      if lll=nil then break;
      ll^.next:=lll^.next;
      dispose(lll);
      dec(elementi);
      dec(quantita);
      end;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.cancella_dopo_indirizzo(l2:pointer; quantita:longint):pointer;
var ll,l3:ptrx;
begin
if quantita<1 then
   begin
   cancella_dopo_indirizzo:=nil;
   Exit;
   end;
cancella_dopo_indirizzo:=l;
l3:=l2;
while quantita>0 do
      begin
      ll:=l3^.next;
      if ll=nil then Break;
      l3^.next:=ll^.next;
      dispose(ll);
      dec(elementi);
      dec(quantita);
      end;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.input_iniziale(valore:Tipo):pointer;
var nuovo:ptrx;
begin
if MemAvail<SizeOf(nodo) then
                         begin
                         input_iniziale:=nil;
                         Exit;
                         end;
new(nuovo);
nuovo^.info:=valore;
nuovo^.next:=l;
l:=nuovo;
input_iniziale:=l;
inc(elementi);
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.input_ennesimo(valore:Tipo; ennesimo:longint):pointer;
var ll,nuovo:ptrx;
    err:boolean;
begin
if (ennesimo<1)or(MemAvail<SizeOf(nodo)) then
                         begin
                         input_ennesimo:=nil;
                         Exit;
                         end;
if ennesimo=1 then
              begin
              input_ennesimo:=input_iniziale(valore);
              Exit;
              end;
ll:=l;
err:=false;
while ennesimo>2 do
      begin
      if Err then
             begin
             input_ennesimo:=nil;
             Exit;
             end;
      ll:=ll^.next;
      if ll=nil then Err:=true;
      dec(ennesimo);
      end;
new(nuovo);
nuovo^.info:=valore;
nuovo^.next:=ll^.next;
ll^.next:=nuovo;
input_ennesimo:=nuovo;
inc(elementi);
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function cerca_valore(l2:pointer; valore:Tipo):pointer;
var l3:ptrx;
begin
cerca_valore:=nil;
l3:=l2;
while l3<>nil do
     if StrComp(l3^.info,valore)<>0 then l3:=l3^.next
                                    else
                                     begin
                                     cerca_valore:=l3;
                                     Exit;
                                     end;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function get_iesimo(l2:pointer; iesimo:longint; var valido:boolean):Tipo;
// 'valido' e' false se il valore di iesimo e' <1 o >num elementi delle lista
var l3:ptrx;
begin
valido:=false;
l3:=l2;
if iesimo<1 then Exit;
while l3<>nil do
     if iesimo>1 then
                  begin
                  l3:=l3^.next;
                  dec(iesimo);
                  end
                 else
                   begin
                   get_iesimo:=l3^.info;
                   valido:=true;
                   Exit;
                   end;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function posizione(l2:pointer; valore:Tipo):longint;
var posiz:longint;
    ll:ptrx;
begin
ll:=l2;
posizione:=0;
posiz:=0;
while ll<>nil do
      begin
      inc(posiz);
      if StrComp(ll^.info,valore)<>0 then ll:=ll^.next
                                     else
                                      begin
                                      posizione:=posiz;
                                      Exit;
                                      end;
      end;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function cerca_ennesimo_valore(l2:pointer; ennesimo:longint; valore:Tipo):pointer;
var l3:ptrx;
begin
l3:=l2;
cerca_ennesimo_valore:=nil;
if ennesimo<1 then Exit;
while ennesimo>0 do
      begin
      l3:=cerca_valore(l3,valore);
      cerca_ennesimo_valore:=l3;
      if l3=nil then Exit;
      l3:=l3^.next;
      dec(ennesimo);
      end;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function cerca_ennesimo(l2:pointer; ennesimo:longint):pointer;
var ll:ptrx;
begin
ll:=l2;
cerca_ennesimo:=nil;
if ennesimo<1 then Exit;
while ennesimo>1 do
      begin
      if ll=nil then Exit;
      ll:=ll^.next;
      dec(ennesimo);
      end;
cerca_ennesimo:=ll;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.input_finale(valore:Tipo):pointer;
var nuovo:ptrx;
begin
if MemAvail<SizeOf(nodo) then
                         begin
                         input_finale:=nil;
                         Exit;
                         end;
if l=nil then
         begin
         new(nuovo);
         l:=nuovo;
         end
        else
         begin
         nuovo:=l;
         while nuovo^.next<>nil do nuovo:=nuovo^.next;
         new(nuovo^.next);
         nuovo:=nuovo^.next;
         end;
nuovo^.info:=valore;
nuovo^.next:=nil;
input_finale:=l;
inc(elementi);
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function Count(l2:pointer; valore:Tipo):longint;
var contatore:longint;
    l3:ptrx;
begin
l3:=l2;
contatore:=0;
while l3<>nil do
      begin
      l3:=cerca_valore(l3,valore);
      if l3=nil then break;
      l3:=l3^.next;
      inc(contatore);
      end;
count:=contatore;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.input_dopo_indirizzo(l3:pointer; valore:Tipo):pointer;
var ll,nuovo:ptrx;
begin
if (l3=nil)or(MemAvail<SizeOf(nodo)) then
                         begin
                         input_dopo_indirizzo:=nil;
                         Exit;
                         end;
ll:=l3;
new(nuovo);
nuovo^.info:=valore;
nuovo^.next:=ll^.next;
ll^.next:=nuovo;
input_dopo_indirizzo:=nuovo;
inc(elementi);
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function cerca_ennesimo_valore_precedente(l2:pointer; ennesimo:longint; valore:Tipo):pointer;
var l3:ptrx;
begin
l3:=l2;
{if (ennesimo<1) then} cerca_ennesimo_valore_precedente:=nil;
if l3<>nil then if StrComp(l3^.info,valore)=0 then dec(ennesimo);
while ennesimo>0 do
      repeat
       if l3<>nil then
          begin
          cerca_ennesimo_valore_precedente:=l3;
          l3:=l3^.next;
          if StrComp(l3^.info,valore)=0 then
                             begin
                             dec(ennesimo);
                             break;
                             end;
          end
         else
          begin
          cerca_ennesimo_valore_precedente:=nil;
          Exit;
          end;
      until false;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

constructor ListaDinamicaUnidirezionale.init;
begin
elementi:=0;
l:=nil;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

destructor ListaDinamicaUnidirezionale.destroy;
begin
while l<>nil do cancella_iniziale;
elementi:=0;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

procedure ListaDinamicaUnidirezionale.stampa;     {*** solo a scopo di test}
var ll:ptrx;
begin
ll:=l;
while ll<>nil do
      begin
      writeln(ll^.info);
      ll:=ll^.next;
      end;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.inserisci(var destinazione:ListaDinamicaUnidirezionale;
         inizio_dest,inizio_orig,quantita:longint):longint;
var inseriti:longint;
    destinaz,origin:ptrx;
begin
if (quantita<1)or(inizio_dest<1)or(inizio_orig<1) then
              begin
              inserisci:=0;
              Exit;
              end;
origin:=l;
destinaz:=destinazione.l;
for inseriti:=1 to inizio_orig-1 do {mi posiziono da dove devo iniziare a copiare}
    if origin<>nil then origin:=origin^.next
                   else
                    begin   {inizio, supera la dimensione}
                    inserisci:=0;
                    Exit;
                    end;
if origin=nil then
              begin   {gia' alla fine}
              inserisci:=0;
              Exit;
              end;
for inseriti:=1 to inizio_dest-2 do {mi posiziono da dove devo iniziare ad incollare}
    if destinaz<>nil then destinaz:=destinaz^.next
                     else
                      begin   {inizio, supera la dimensione}
                      inserisci:=0;
                      Exit;
                      end;
inseriti:=0;

while quantita>0 do
      begin
      if (origin=nil) then Break;
      if inizio_dest>1 then                      {memoria insufficiente}
                        if destinazione.input_dopo_indirizzo(destinaz,origin^.info)=nil then Break
                                                                                        else destinaz:=destinaz^.next
                       else {inizio_orig=1 }     {memoria insufficiente}
                        if destinazione.input_iniziale(origin^.info)=nil then break
                                                                         else
                                                                          begin
                                                                          destinaz:=destinazione.l;
                                                                          inizio_dest:=2;  {basta che non sia 1}
                                                                          end;
      origin:=origin^.next;
      dec(quantita);
      inc(inseriti);
      end;
inserisci:=inseriti;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.inserisci_da(var destinazione:ListaDinamicaUnidirezionale;
         inizio_dest:longint; inizio_orig:pointer; quantita:longint):longint;
var inseriti:longint;
    destinaz,origin:ptrx;
begin
if (quantita<1)or(inizio_dest<1)or(inizio_orig=nil) then
              begin
              inserisci_da:=0;
              Exit;
              end;
origin:=inizio_orig;
destinaz:=destinazione.l;
for inseriti:=1 to inizio_dest-2 do {mi posiziono da dove devo iniziare ad incollare}
    if destinaz<>nil then destinaz:=destinaz^.next
                     else
                      begin   {inizio, supera la dimensione}
                      inserisci_da:=0;
                      Exit;
                      end;
inseriti:=0;
while quantita>0 do
      begin
      if (origin=nil) then Break;
      if inizio_dest>1 then                      {memoria insufficiente}
                        if destinazione.input_dopo_indirizzo(destinaz,origin^.info)=nil then Break
                                                                                        else destinaz:=destinaz^.next
                       else {inizio_orig=1 }     {memoria insufficiente}
                        if destinazione.input_iniziale(origin^.info)=nil then break
                                                                         else
                                                                          begin
                                                                          destinaz:=destinazione.l;
                                                                          inizio_dest:=2;  {basta che non sia 1}
                                                                          end;
      origin:=origin^.next;
      dec(quantita);
      inc(inseriti);
      end;
inserisci_da:=inseriti;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.cerca_e_cancella(valore:Tipo; ennesimo:longint):longint; {ritorna la posizione dove era}
var precedente,l3:ptrx;
    posizione:longint;
begin
posizione:=0;
cerca_e_cancella:=-1;
if ennesimo<1 then exit;
l3:=l;
while l3<>nil do
     begin
     inc(posizione);
     if StrComp(l3^.info,valore)<>0 then
                            begin
                            precedente:=l3;
                            l3:=l3^.next;
                            end
                           else
                            if ennesimo=1 then
                                 begin              {cancella}
                                 if posizione=1 then cancella_iniziale
                                                else cancella_dopo_indirizzo(precedente,1);
                                 cerca_e_cancella:=posizione;
                                 Exit;
                                 end
                                else
                                 begin
                                 precedente:=l3;
                                 l3:=l3^.next;
                                 dec(ennesimo);
                                 end;
     end;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.Aggiorna(valore1:Tipo; ennesimo:longint; valore2:Tipo):longint;
var precedente,l3:ptrx;
    posizione:longint;
begin
posizione:=0;
Aggiorna:=-1;
if ennesimo<1 then exit;
l3:=l;
while l3<>nil do
     begin
     inc(posizione);
     if StrComp(l3^.info,valore1)<>0 then
                            begin
                            precedente:=l3;
                            l3:=l3^.next;
                            end
                           else
                            if ennesimo=1 then
                                 begin    {cancella e inserisce}
                                 cancella_dopo_indirizzo(precedente,1);
                                 input_dopo_indirizzo(precedente,valore2);
                                 Aggiorna:=posizione;
                                 Exit;
                                 end
                                else
                                 begin
                                 precedente:=l3;
                                 l3:=l3^.next;
                                 dec(ennesimo);
                                 end;
     end;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

function ListaDinamicaUnidirezionale.Aggiorna_ennesimo(ennesimo:longint; valore:Tipo):longint;
var precedente,l3:ptrx;
    posizione:longint;
    primo:boolean;
begin
primo:=(ennesimo=1);
posizione:=ennesimo;
Aggiorna_ennesimo:=-1;
if ennesimo<1 then exit;
l3:=l;
precedente:=l;
while l3<>nil do
              begin
              if ennesimo=1 then break;
              precedente:=l3;
              l3:=l3^.next;
              dec(ennesimo);
              end;
if (precedente<>nil)and(ennesimo=1) then
                   begin    {cancella e inserisce}
                   if primo then
                             begin
                             cancella_iniziale;
                             input_iniziale(valore);
                             end
                            else
                             begin
                             cancella_dopo_indirizzo(precedente,1);
                             input_dopo_indirizzo(precedente,valore);
                             end;
                   Aggiorna_ennesimo:=posizione;
                   end;
end;

{+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

end.
