24 June 2010

Deleting elements from a dynamic array

In my blog "Initialising Dynamic Arrays" I mentioned I have been writing some unit tests that needed numerous repetative array initialisation operations. Well, one of the other common operations I found myself writing was the deletion of items from dynamic arrays. So I decided to find a generic way of doing this.

Assuming we know the index of the item to be deleted we need the equivalent of Delphi's built-in Delete procedure for strings. If you read the previous post you won't be surprised to learn that I decided to further extend the Generics.Collections.TArray class by adding to the TArrayEx class I introduced there.

My first attempt emulates Delphi's Delete procedure by deleting the array element in-place: i.e. it updates the array passed as a parameter. Unsurprisingly the method is called DeleteInPlace. Here's how it goes:

type
  TArrayEx = class(TArray)
  public
    ...
    class procedure DeleteInPlace<T>(var A: TArray<T>; const Index: Integer);
  end;

...

class procedure TArrayEx.DeleteInPlace<T>(var A: TArray<T>;
  const Index: Integer);
var
  IdxA: Integer;
begin
  Assert((Index >= Low(A)) and (Index <= High(A)));
  for IdxA := Index to Pred(High(A)) do
    A[IdxA] := A[Succ(IdxA)];
  SetLength(A, Length(A) - 1);
end;

This uses a common algorithm. It just copies all array elements above the index of the deleted item down one place then shrinks the array by one element.

Next I decided it would also be useful to be able to construct a new array that contained a copy of a given array with the specified element removed. Continuing my startlingly inspired naming plan I called this method Delete. Here it is:

type
  TArrayEx = class(TArray)
  public
    ...
    class function Delete<T>(const A: array of T; const Index: Integer):
      TArray<T>;
  end;

...

class function TArrayEx.Delete<T>(const A: array of T; const Index: Integer):
  TArray<T>;
var
  IdxSrc, IdxRes: Integer;
begin
  Assert((Index >= Low(A)) and (Index <= High(A)));
  SetLength(Result, Length(A) - 1);
  IdxRes := Low(Result);
  for IdxSrc := Low(A) to High(A) do
  begin
    if IdxSrc <> Index then
    begin
      Result[IdxRes] := A[IdxSrc];
      Inc(IdxRes);
    end;
  end;
end;

This is pretty self-explanatory. It simply creates a new array of the required size and copies all the array elements to it, except for the one that is to be deleted.

I could have implemented Delete in terms of DeleteIinPlace like this, using CloneArray from the previous post:

class function TArrayEx.Delete<T>(const A: array of T; const Index: Integer):
  TArray<T>;
var
  IdxSrc, IdxRes: Integer;
begin
  Assert((Index >= Low(A)) and (Index <= High(A)));
  Result := CloneArray<T>(A);
  DeleteInPlace<T>(Result, Index);
end;

But I decided against this to avoid looping through the array 1.5 times on average instead of once. (CloneArray loops through the array once and DeleteInPlace loops through half the array on average.)

OK, I'll come clean. I actually wrote Delete first and then DeleteInPlace after I found the compiler wouldn't accept it as an overload of Delete, but the story goes better the way I told it!
Does anyone know why the compiler won't accept that methods with different return types (or no return types) have different signatures anyway? Leave a comment if you know please.

23 June 2010

Initialising dynamic arrays

When writing some unit tests a while ago I found myself needing to initialise some dynamic arrays with test data. It would be nice if we could do something like this:

var
  A: array of Integer;
begin
  A := (1,2,3,4);  // !! WRONG
end;

but we can't. So I decided to write some functions to initialise dynamic arrays to the contents of another array, be it a constant, a literal or another dynamic array.

The result was a set of overloaded routines, one for each data type I needed to handle, for example for Integer and string arrays I had:

function CloneArray(const A: array of Integer): TIntegerDynArray; overload;
var
  Idx: Integer;
begin
  SetLength(Result, Length(A));
  for Idx := Low(A) to High(A) do
    Result[Idx - Low(A)] := A[Idx];
end;

function CloneArray(const A: array of string): TStringDynArray; overload;
var
  Idx: Integer;
begin
  SetLength(Result, Length(A));
  for Idx := Low(A) to High(A) do
    Result[Idx - Low(A)] := A[Idx];
end;

Noticing how similar these functions were - only the first line differs - I decided to try a generic approach. Since I didn't want to parameterise both the type of the array (e.g. the TIntegerDynArray return value) and the array element (e.g. Integer) I first decided to change the return values of the functions to use the TArray<T> type defined in the System unit. So the function prototypes got changed to

function CloneArray(const A: array of Integer): TArray<Integer>; overload;

and

function CloneArray(const A: array of string): TArray<string>; overload;

The implementation of the routines did not need changing. It seemed clear how to parameterise the routines: just replace the Integer or string types with T, like this:

function CloneArray<T>(const A: array of T): TArray<T>;

Wrong! At this point I learned that you can't parameterise global routines, as my blog entry "Being dim #2: No generic global procedures" explains. I needed to make the CloneArray routine a class method of some suitable class. Rather than create a new class I cast around and decided to extend the TArray class defined in the Generics.Collections unit.

type
  TArrayEx = class(TArray)
  public
    class function CloneArray<T>(const A: array of T): TArray<T>;
  end;

...

class function TArrayEx.CloneArray<T>(const A: array of T): TArray<T>;
var
  Idx: Integer;
begin
  SetLength(Result, Length(A));
  for Idx := Low(A) to High(A) do
    Result[Idx - Low(A)] := A[Idx];
end;

Don't confuse Generics.Collections.TArray with System.TArray<T> - the first is a class, the second a generic dynamic array type.

CloneArray assumes that straighforward assignment of array elements is what we want. For example if the array elements are objects, just the object pointer is copied. If you need the object's fields to be physically copied this simplistic approach won't work.

I'll close this post with an example of use. Here's a code fragment that initialises string and integer arrays:

var
  IA: TArray<Integer>;
  SA: TArray<string>;
begin
  IA := TArrayEx.CloneArray<Integer>([1,2,3,5,7,11]);
  SA := TArrayEx.CloneArray<string>(['bonnie', 'clyde']);
end;

22 June 2010

Being dim #2: No generic global procedures

The other day I was writing some unit tests and needed some helper functions to look up some array elements of in arrays of different base types. I had several overloaded functions to do the job, like this:

function IndexOf(const Item: string; const A: array of string): Integer; overload;
function IndexOf(const Item: Integer; const A: array of Integer): Integer; overload;

Oh, I thought, generics are a way round this, so I replaced the overloaded functions with something like

function IndexOf<T>(const Item: T; const A: array of T): Integer;

only to be get compiler error 2530: Type parameters not allowed on global procedure or function. Now, I didn't know that and I'm sharing it in case some of you didn't either.

And the solution? I sorted it by using a static class to hold the code, i.e.

type
  TSomeClass = class(TObject)
  public
    class function IndexOf<T>(const Item: T; const A: array of T): Integer;
  end;

This works fine.

I've not provided implementation details of any of this code since the details are not important in this context.

Being dim #1: Array and set enumerators

One of my favourite additions to Delphi over the past years has been the for..in construct and the associated enumerators. I just love the way we can do

var
  Ch: Char;
  S: string;
begin
  S := 'Some text';
  for Ch in S do
    // Do something with Ch
end;

So how come I missed that enumerators work on sets and arrays? I'm mentioning this here just in case it's slipped past anyone else, and in case you can tell me about any other enumerators I might have missed!

Since forever I've being having to do stuff like this for arrays and sets:

const
  cMyArray: array[1..4] of Byte = (51, 60, 80, 81);
  cMySet: set of Byte = [50, 51, 80, 81, 40, 30, 32];
var
  I: Integer;
  B: Byte;
begin
  for B := Low(Byte) to High(Byte) do
    if B in cMySet then
      // Do stuff with B
  for I := Low(cMyArray) to High(cMyArray) do
    // Do stuff my cMyArray[I]
end;

When all along I could have been doing:

const
  cMyArray: array[1..4] of Byte = (51, 60, 80, 81);
  cMySet: set of Byte = [50, 51, 80, 81, 40, 30, 32];
var
  Item: Byte;
begin
  for Item in cMySet do
    // Do stuff with Item
  for Item in cMyArray do
    // Do stuff with Item
end;

Duh! A refactoring I will go!