unit ArrayEx;

interface

uses
  Generics.Defaults, Generics.Collections, System.SyncObjs, System.SysUtils;

type
  // Типы компаратора
  TCompareResult = (crLess,crEqual,crMore);
  TCompareMode = (cmAscending, cmDescending);
  // Типы функций пользовательского компаратора
  TCompareValue<T> = reference to function(const Item1,Item2: T): TCompareResult;

  // -------------------------------------------------------------------------
  // ------------------- TArrayEx (Расширенный массив) -----------------------
  // -------------------------------------------------------------------------

  {$REGION 'TArrayEx'}

  TArrayEx<T> = record
  public
    // Доступ к элементам напрямую (unsafe)
    Items      : array of T;
    // Пользовательский Тэг
    Tag        : integer;
    // Признак необходимости освобождать элементы при удалении
    DoFreeData : Boolean;
    FEnumInit  : string;
  private
    var
      FIndexMod     : integer;                      // Размер индекса
      FIndexArray   : array of array of integer;    // Элементы индекса
      FComparer     : IEqualityComparer<T>;         // Компаратор

    function GetItems(Index: integer): T; inline;
    procedure SetItems(Index: integer; const Value: T); inline;
    procedure QuickSortA(const Comparer: IComparer<T>; L, R: Integer);
    procedure QuickSortB(L, R: Integer; CompareEvt: TCompareValue<T>; Less, More: TCompareResult);
    function GetIndexMod: integer; inline;
    procedure SetIndexMod(Value: integer); inline;
    procedure HashClear(NewIndexMod: integer); inline;
    procedure HashAdd(const Value: T; Index: integer); inline;
    function GetHash(const Value: T): integer; inline;
    procedure SetIndex(Index: Integer; const Value: T); inline;
    procedure SetCount(const Value: integer); inline;
    function GetCount: integer; inline;
    function GetHigh: integer; inline;
    procedure SetHigh(const Value: integer); inline;
    function GetLow: integer; inline;
    procedure FreeElement(Num: integer); inline;
  public
    // Конструкторы
    constructor Create(DoFreeData: boolean);

    // Доступ к элементам по умолчанию
    property Elements[Index: integer]: T read GetItems write SetItems; default;

    // Очистка массива
    procedure Clear; overload;

    // Добавление элемента(ов) в конец
    function Add(Value: T): integer; overload; inline;
    function Add(Values: array of T): integer; overload;
    function AddUnique(Value: T): integer;

    // Вставка элемента по индексу
    procedure Insert(Index: integer; Value: T); overload; inline;
    procedure Insert(Index: integer; Values: array of T); overload;

    // Удаление элемента по индексу
    procedure Delete(Index: integer); inline;
    procedure DeleteRange(Index, Count: integer); inline;

    // Создание индекса по массиву
    procedure CreateIndex(IndexMod: integer = -1);
    // Уничтожение индекса по массиву
    procedure DropIndex;

    // Кол-во элементов массива
    property Count: integer read GetCount write SetCount;
    // Индекс нижнего элемента массива
    property Low: integer read GetLow;
    // Индекс верхнего элемента массива
    property High: integer read GetHigh write SetHigh;

    // Поиск значения(ий) в массиве
    function Exists(Value: T): boolean; overload;
    function Exists(Values: array of T; NeedAllValues: boolean = False): boolean; overload;
    // Индекс(ы) значения в массиве
    function IndexOf(Value: T): integer;
    function IndexesOf(Value: T): TArrayEx<integer>;

    // Сортировка
    procedure Sort(Comparer: IComparer<T> = nil); overload;
    procedure Sort(CompareEvt: TCompareValue<T>; Mode: TCompareMode = cmAscending); overload;

    // Сериализатор в строку
    function ToString: string; overload;
    function ToString(Delimeter : string): string; overload;

    class operator Add(const A,B: TArrayEx<T>): TArrayEx<T>; overload;
    class operator Add(const A: TArrayEx<T>; const B: array of T): TArrayEx<T>; overload;
    class operator Add(const A: array of T; const B: TArrayEx<T>): TArrayEx<T>; overload;
    class operator Implicit(const A: TArrayEx<T>): TArray<T>;
    class operator Equal(const A,B: TArrayEx<T>): Boolean;
    class operator NotEqual(const A,B: TArrayEx<T>): Boolean;
  end;
  {$ENDREGION}


implementation

uses TypInfo, Math, RTTI;

{ TArrayEx }

procedure TArrayEx<T>.SetCount(const Value: integer);
begin
  System.SetLength(Items,Value);
  if GetIndexMod>0 then begin
    CreateIndex(Value);
  end;
end;

procedure TArrayEx<T>.SetHigh(const Value: integer);
begin
  System.SetLength(Items,Value-1);
  if GetIndexMod>0 then begin
    CreateIndex(Value-1);
  end;
end;

procedure TArrayEx<T>.SetIndex(Index: Integer; const Value: T);
begin
  if GetIndexMod<=0 then Exit;

  if Index>=GetIndexMod then begin
    CreateIndex(Index*2);
  end else begin
    HashAdd(Value,Index);
  end;
end;

function TArrayEx<T>.GetIndexMod: integer;
begin
  if Length(FIndexArray)=0 then begin
    FIndexMod:=0;
    FComparer:=TEqualityComparer<T>.Default;
  end;
  Result:=FIndexMod;
end;

procedure TArrayEx<T>.SetIndexMod(Value: integer);
begin
  FIndexMod:=Value;
  SetLength(FIndexArray,FIndexMod);
end;

function TArrayEx<T>.Add(Value: T): integer;
begin
  Result:=Length(Items);
  System.SetLength(Items,Result+1);
  Items[Result]:=Value;

  SetIndex(Result,Value);
end;

function TArrayEx<T>.Add(Values: array of T): integer;
var
  i: Integer;
begin
  Result:=Length(Items);
  System.SetLength(Items,Result+Length(Values));
  for i:=0 to System.High(Values) do begin
    Items[Result]:=Values[i];
    SetIndex(Result,Values[i]);
  end;
end;

procedure TArrayEx<T>.Delete(Index: integer);
var
  i: Integer;
begin
  if (Index<0) or (Index>High) then Exit;

  if DoFreeData and (PTypeInfo(TypeInfo(TValue)).Kind=tkClass) then begin
    FreeElement(Index);
  end;

  for i:=Index+1 to High do begin
    Items[i-1]:=Items[i];
  end;
  System.SetLength(Items,Length(Items)-1);

  CreateIndex(GetIndexMod);
end;

procedure TArrayEx<T>.DeleteRange(Index, Count: integer);
var
  i: Integer;
begin
  if (Count<1) or (Index<0) or (Index+Count>High) then Exit;

  if DoFreeData and (PTypeInfo(TypeInfo(TValue)).Kind=tkClass) then begin
    for i:=Index to Index+Count-1 do begin
      FreeElement(i);
    end;
  end;

  for i:=Index+Count to High do begin
    Items[i-Count]:=Items[i];
  end;
  System.SetLength(Items,Length(Items)-Count);

  CreateIndex(GetIndexMod);
end;

procedure TArrayEx<T>.DropIndex;
begin
  HashClear(0);
end;

function TArrayEx<T>.IndexesOf(Value: T): TArrayEx<integer>;
var
  i,j,m    : integer;
begin
  m:=GetIndexMod;

  if m=0 then begin
    CreateIndex;
    m:=GetIndexMod;
  end;

  m:=Abs(GetHash(Value) mod m);

  Result.Clear;
  for i:=0 to System.High(FIndexArray[m]) do begin
    if FComparer.Equals(Items[FIndexArray[m,i]],Value) then begin
      Result.Add(FIndexArray[m,i]);
    end;
  end;
  Result.Sort;
end;

function TArrayEx<T>.IndexOf(Value: T): integer;
var
  i,j,m    : integer;
begin
  m:=GetIndexMod;

  if m=0 then begin
    CreateIndex;
    m:=GetIndexMod;
  end;

  m:=Abs(GetHash(Value) mod m);
  for i:=0 to System.High(FIndexArray[m]) do
    if FComparer.Equals(Items[FIndexArray[m,i]],Value) then begin
      Exit(FIndexArray[m,i]);
    end;
  Result:=-1;
end;


procedure TArrayEx<T>.Insert(Index: integer; Values: array of T);
var
  i: Integer;
begin
  if (Index<0) or (Index>Count) then Exit;

  System.SetLength(Items,Length(Items)+length(Values));
  for i:=High downto Index+length(Values) do begin
    Items[i]:=Items[i-length(Values)];
  end;

  for i:=Index to System.High(Values) do begin
    Items[Index+i]:=Values[i];
  end;

  CreateIndex(GetIndexMod);
end;

function TArrayEx<T>.GetItems(Index: integer): T;
begin
  Result:=Items[Index];
end;

function TArrayEx<T>.GetLow: integer;
begin
  Result:=0;
end;

procedure TArrayEx<T>.HashClear(NewIndexMod: integer);
begin
  System.SetLength(FIndexArray,0);
  SetIndexMod(NewIndexMod);
end;

function TArrayEx<T>.GetCount: integer;
begin
  Result:=Length(Items);
end;

function TArrayEx<T>.GetHash(const Value: T): integer;
begin
  Result:=TEqualityComparer<T>.Default.GetHashCode(Value);
end;

function TArrayEx<T>.GetHigh: integer;
begin
  Result:=System.High(Items);
end;

procedure TArrayEx<T>.HashAdd(const Value: T; Index: integer);
var
  n,m     : integer;
begin
  try
    m:=Abs(GetHash(Value) mod GetIndexMod);
    n:=length(FIndexArray[m]);
  except
  end;

  System.SetLength(FIndexArray[m],n+1);
  FIndexArray[m,n]:=Index;
end;

procedure TArrayEx<T>.FreeElement(Num: integer);
begin
  try
    PObject(@Items[num])^.Free;
    Items[num]:=Default(T);
  except
  end;
end;

procedure TArrayEx<T>.Clear;
var
  i: Integer;
begin
  if DoFreeData and (PTypeInfo(TypeInfo(TValue)).Kind=tkClass) then begin
    for i:=0 to High do begin
      FreeElement(i);
    end;
  end;
  System.SetLength(Items,0);
  HashClear(GetIndexMod);
end;

constructor TArrayEx<T>.Create(DoFreeData: boolean);
begin
  Clear;
  DoFreeData:=DoFreeData;
end;

procedure TArrayEx<T>.CreateIndex(IndexMod: integer = -1);
var
  i : integer;
const
  DefaultIndexSize = 64;
begin
  if IndexMod=-1 then begin
    IndexMod:=DefaultIndexSize;
    if Count=0 then begin
      IndexMod:=DefaultIndexSize;
    end else begin
      IndexMod:=Count;
    end;
  end;
  HashClear(IndexMod);

  if IndexMod>0 then begin
    for i:=Low to High do begin
      HashAdd(Items[i],i);
    end;
  end;
end;

procedure TArrayEx<T>.Insert(Index: integer; Value: T);
var
  i: Integer;
begin
  if (Index<0) or (Index>Count) then Exit;

  System.SetLength(Items,Length(Items)+1);
  for i:=High downto Index+1 do begin
    Items[i]:=Items[i-1];
  end;
  Items[Index]:=Value;

  CreateIndex(GetIndexMod);
end;

procedure TArrayEx<T>.SetItems(Index: integer; const Value: T);
begin
  if (Index<0) or (Index>High) then Exit;
  Items[Index]:=Value;
end;

procedure TArrayEx<T>.QuickSortA(const Comparer: IComparer<T>; L, R: Integer);
var
  I, J: Integer;
  pivot, temp: T;
begin
  if (Length(Items) = 0) or ((R - L) <= 0) then
    Exit;
  repeat
    I := L;
    J := R;
    pivot := Items[L + (R - L) shr 1];
    repeat
      while Comparer.Compare(Items[I], pivot) < 0 do
        Inc(I);
      while Comparer.Compare(Items[J], pivot) > 0 do
        Dec(J);
      if I <= J then
      begin
        if I <> J then
        begin
          temp := Items[I];
          Items[I] := Items[J];
          Items[J] := temp;
        end;
        Inc(I);
        Dec(J);
      end;
    until I > J;
    if L < J then
      QuickSortA(Comparer, L, J);
    L := I;
  until I >= R;
end;

procedure TArrayEx<T>.Sort(Comparer: IComparer<T> = nil);
var
  OIndexMod: integer;
begin
  OIndexMod:=GetIndexMod;
  if OIndexMod>0 then DropIndex;

  if Comparer=nil then Comparer:=TComparer<T>.Default;
  QuickSortA(Comparer, 0, High);

  if OIndexMod>0 then CreateIndex(OIndexMod);
end;

procedure TArrayEx<T>.QuickSortB(L, R: Integer; CompareEvt: TCompareValue<T>; Less, More: TCompareResult);
var
  I, J: Integer;
  pivot, temp: T;
begin
  if (Length(Items) = 0) or ((R - L) <= 0) then
    Exit;
  repeat
    I := L;
    J := R;
    pivot := Items[L + (R - L) shr 1];
    repeat
      while CompareEvt(Items[I], pivot) = crLess do
        Inc(I);
      while CompareEvt(Items[J], pivot) = crMore do
        Dec(J);
      if I <= J then
      begin
        if I <> J then
        begin
          temp := Items[I];
          Items[I] := Items[J];
          Items[J] := temp;
        end;
        Inc(I);
        Dec(J);
      end;
    until I > J;
    if L < J then
      QuickSortB(L, J, CompareEvt, Less, More);
    L := I;
  until I >= R;
end;

procedure TArrayEx<T>.Sort(CompareEvt: TCompareValue<T>; Mode: TCompareMode = cmAscending);
var
  OIndexMod: integer;
  Less,More: TCompareResult;
begin
  OIndexMod:=GetIndexMod;
  if OIndexMod>0 then DropIndex;

  if not Assigned(CompareEvt) then Exit;

  case Mode of
    cmAscending: begin
      Less:=crLess;
      More:=crMore;
    end;
    cmDescending: begin
      Less:=crMore;
      More:=crLess;
    end;
  end;

  QuickSortB(Low,High,CompareEvt,Less,More);

  if OIndexMod>0 then CreateIndex(OIndexMod);
end;

function TArrayEx<T>.ToString(Delimeter: string): string;
var
  i : Integer;
  n : integer;
  s : string;
begin
  Result:='';
  for i:=Low to High do begin
    if (Result<>'') then begin
      s:=Delimeter+TValue.From<T>(Items[i]).ToString;
    end else begin
      s:=TValue.From<T>(Items[i]).ToString;
    end;

    n:=Length(Result);
    SetLength(Result,n+length(s));
    Move(s[1],Result[n+1],Length(s)*SizeOf(Char));
  end;
end;

function TArrayEx<T>.ToString: string;
begin
  Result:=ToString(';');
end;

function TArrayEx<T>.Exists(Value: T): boolean;
begin
  Result:=IndexOf(Value)>=0;
end;

function TArrayEx<T>.Exists(Values: array of T; NeedAllValues: boolean = False): boolean;
var
  i: Integer;
begin
  Result:=NeedAllValues;

  for i:=0 to System.High(Values) do begin
    if NeedAllValues then begin
      if IndexOf(Values[i])<0 then Exit(False);
    end else begin
      if IndexOf(Values[i])>=0 then Exit(True);
    end;
  end;
end;

class operator TArrayEx<T>.Add(const A, B: TArrayEx<T>): TArrayEx<T>;
begin
  Result.Clear;

  SetLength(Result.Items,A.Count+B.Count);
  Move(A.Items[0],Result.Items[0],A.Count*SizeOf(T));
  Move(B.Items[0],Result.Items[A.Count],B.Count*SizeOf(T));
  if length(A.FIndexArray)>0 then begin
    Result.CreateIndex;
  end;
end;


class operator TArrayEx<T>.Add(const A: TArrayEx<T>; const B: array of T): TArrayEx<T>;
begin
  Result.Clear;

  SetLength(Result.Items,A.Count+length(B));
  Move(A.Items[0],Result.Items[0],A.Count*SizeOf(T));
  Move(B[0],Result.Items[A.Count],length(B)*SizeOf(T));
  if length(A.FIndexArray)>0 then begin
    Result.CreateIndex;
  end;
end;

class operator TArrayEx<T>.Add(const A: array of T; const B: TArrayEx<T>): TArrayEx<T>;
begin
  Result.Clear;

  SetLength(Result.Items,length(A)+B.Count);
  Move(A[0],Result.Items[0],length(A)*SizeOf(T));
  Move(B.Items[0],Result.Items[length(A)],B.Count*SizeOf(T));
  if length(B.FIndexArray)>0 then begin
    Result.CreateIndex;
  end;
end;

function TArrayEx<T>.AddUnique(Value: T): integer;
begin
  Result:=IndexOf(Value);
  if Result<0 then begin
    Result:=Add(Value);
  end;
end;

class operator TArrayEx<T>.Implicit(const A: TArrayEx<T>): TArray<T>;
begin
  SetLength(Result,A.Count);
  Move(A.Items[0],Result[0],A.Count*SizeOf(T));
end;

class operator TArrayEx<T>.Equal(const A, B: TArrayEx<T>): Boolean;
var
  i        : integer;
  Comparer : IEqualityComparer<T>;
begin
  if length(A.Items)<>length(B.Items) then Exit(False);
  Comparer:=TEqualityComparer<T>.Default;

  for i:=0 to System.High(A.Items) do begin
    if Comparer.Equals(A.Items[i],B.Items[i]) then Exit(False);
  end;
  Result:=True;
end;

class operator TArrayEx<T>.NotEqual(const A, B: TArrayEx<T>): Boolean;
begin
  Result:=not (A=B);
end;

end.