Jump to content
Mike Torrettinni

Advice on searching within nested records

Recommended Posts

Posted (edited)

I would appreciate any suggestions on how to improve or make this easier:

 

I have quite complicated (nested) data structure to find references. For example:

 

// this is just example

type
  TSubSubSubItem = record
    ID: integer;
    Name: string;
    Disabled: boolean;
    Amount: integer;
    OrdersNo: string;
  end;

  TSubSubItem = record
    ID: integer;
    Name: string;
    SubSubSubItems: TList<TSubSubSubItem>;
  end;

  TSubItem = record
    ID: integer;
    Name: string;
    SubSubItems: TList<TSubSubItem>;
  end;

  TMainData = record
    ID: integer;
    SubItemsA,
    SubItemsB: TList<TSubItem>;
  end;

var MainData: TList<TMainData>;

And if I want to find all Disabled SubSubSubItems, this is how I would do it:

 

procedure FindAllDisabled(var aDisabledItems: TList<...>);
var
  i, j, k, l: Integer;
begin
  for i := 0 to MainData.Count - 1 do
    if MainData[i].SubItemsA <> nil then
      for j := 0 to MainData[i].SubItemsA.Count - 1 do
        if MainData[i].SubItemsA[j].SubSubItems <> nil then
          for k := 0 to MainData[i].SubItemsA[j].SubSubItems.Count - 1 do
            if MainData[i].SubItemsA[j].SubSubItems[k].SubSubSubItems <> nil then
              for l := 0 to MainData[i].SubItemsA[j].SubSubItems[k].SubSubSubItems.Count - 1 do
                if MainData[i].SubItemsA[j].SubSubItems[k].SubSubSubItems[l].Disabled then
                  //  save record and all parents to disabled record

end;

 

This method will return all Disabled SubSubSubItems. If I then need all SubSubSubItems with Amount > 0, I would set new method or use the same and combine last IF with parameter to eother search Disabled or Amount > 0.

This is very simple example, I have a real life cases where Disabled property can be at any nested level from 2-6. This is becoming very complex and unreadable and repeated similar For loops.

 

Any suggestions how I can simplify search of values in nested record? The problem is that for each found item, I need full 'parent tree', so I can report to users where in details this item is found.

 

Edited by Mike Torrettinni
Fixed.

Share this post


Link to post

I think database is another layer that I don't need at this point. And as far as I know you can't nest records, right? They would be separate tables with keys - this defeats the nested records benefits.

 

Share this post


Link to post
4 minutes ago, Mike Torrettinni said:

this defeats the nested records benefits

You're not nesting records.

 

TList<T> doesn't contain a list of T. It contains a pointer to a list of T.

Share this post


Link to post

If you could drop the records and use classes instead you could do something like this (very incomplete - I'm in a rush):

 

type
  TItem = class
  private type
    TPredicate = function(AItem: TItem): boolean;
  private
    FItems: TList<TItem>;
    FDisabled: boolean;
  public
    function Find(Predicate: TPredicate): boolean; virtual;
    property Disabled: boolean read FDisabled write FDisabled;
  end;

function TItem.Find(Predicate: TPredicate): boolean;
var
  Child: TItem;
begin
  if (not Predicate(Self)) then
    Exit(False);

  for Child in FItems do
    if (not Child.Find(Predicate)) then
      Exit(False);

  Result := True;
end;

var
  Item: TItem;
  Result: TList<TItem>;
begin
  if (Item.Find(
    function(AItem: TItem): boolean
    begin
      if (AItem.Disabled) then
        Result.Add(AItem);
      Result := True;
    end)) then
  begin
    ...Result contains list of disabled items...
  end;
end;

 

Share this post


Link to post
Just now, Anders Melander said:

You're not nesting records.

 

TList<T> doesn't contain a list of T. It contains a pointer to a list of T.

Maybe 'nesting' is not the right word, but the structure of records than can only be accessed by through Parent records... or can I just access directly SubSubSubItems of MainData.ID = 1 and SubItemsA.ID = 12 and SubSubItems.Id=2?

Is there another word for this, instead of nested records?

Share this post


Link to post

I think the word is Tree , https://en.wikipedia.org/wiki/Nested_set_model

 

As Andres suggested, as your code is already there and you like records then just add record method to let each item return its disabled list ( or adding it to supplied list/ record), such code will be more clear and easier to extend, e.g. to enable specific item anywhere

Share this post


Link to post
Posted (edited)
2 minutes ago, Kas Ob. said:

As Andres suggested, as your code is already there and you like records then just add record method to let each item return its disabled list ( or adding it to supplied list/ record), such code will be more clear and easier to extend, e.g. to enable specific item anywhere 

Aha, thanks, I think now I better understand his suggestion.

Edited by Mike Torrettinni

Share this post


Link to post
54 minutes ago, Kas Ob. said:

just add record method to let each item return its disabled list

OK, this is for when you have Parent and Child list, and Result = Disabled Child list, for a Parent (like Andreas class). How would that work if it is like my example, where I need to to know for each Disabled Item, all the Parents and Parent.Parent and Parent.Parent.Parent?

 

Share this post


Link to post

Something like this

type
  TSubSubSubItem = record
    ID: integer;
    Name: string;
    Disabled: boolean;
    Amount: integer;
    OrdersNo: string;
  end;

  TSubSubItem = record
    ID: integer;
    Name: string;
    SubSubSubItems: TList<TSubSubSubItem>;
  public
    procedure GetDisabled(var List: TList<TSubSubSubItem>);
  end;

  TSubItem = record
    ID: integer;
    Name: string;
    SubSubItems: TList<TSubSubItem>;
  public
    procedure GetDisabled(var List: TList<TSubSubSubItem>);
  end;

  TMainData = record
    ID: integer;
    SubItemsA, SubItemsB: TList<TSubItem>;
  public
    procedure GetDisabled(var List: TList<TSubSubSubItem>);
  end;

var
  MainData: TList<TMainData>;
  
  
  
  implementation

procedure FindAllDisabled(var aDisabledItems: TList<TSubSubSubItem>);
var
  i, j, k, l: Integer;
begin
  for i := 0 to MainData.Count - 1 do
    if MainData[i].SubItemsA <> nil then
      for j := 0 to MainData[i].SubItemsA.Count - 1 do
        if MainData[i].SubItemsA[j].SubSubItems <> nil then
          for k := 0 to MainData[i].SubItemsA[j].SubSubItems.Count - 1 do
            if MainData[i].SubItemsA[j].SubSubItems[k].SubSubSubItems <> nil then
              for l := 0 to MainData[i].SubItemsA[j].SubSubItems[k].SubSubSubItems.Count
                - 1 do
                if MainData[i].SubItemsA[j].SubSubItems[k].SubSubSubItems[l].Disabled then
                  //  save record and all parents to disabled record



end;

procedure FindAllDisabled2(var aDisabledItems: TList<TSubSubSubItem>);
var
  Item:TMainData;
begin
  for Item in MainData do
    Item.GetDisabled(aDisabledItems);
end;

{ TSubSubItem }

procedure TSubSubItem.GetDisabled(var List: TList<TSubSubSubItem>);
var
  Item: TSubSubSubItem;
begin
  for Item in SubSubSubItems do
    if Item.Disabled then
      List.Add(Item);
end;

{ TSubItem }

procedure TSubItem.GetDisabled(var List: TList<TSubSubSubItem>);
var
  Item: TSubSubItem;
begin
  for Item in SubSubItems do
    Item.GetDisabled(List);
end;

{ TMainData }

procedure TMainData.GetDisabled(var List: TList<TSubSubSubItem>);
var
  Item: TSubItem;
begin
  for Item in SubItemsA do
    Item.GetDisabled(List);
  for Item in SubItemsB do
    Item.GetDisabled(List);
end;

Now you see the difference between FindAllDisabled and FindAllDisabled2  

Share this post


Link to post

I'm back.

The point of my example was that, provided you use classes, you can generalize the tree structure and the function that traverses the tree. And you can delegate the operation to perform on each node to the caller via the predicate function.

 

In your example you'd examine the Disabled value of the node and store the node in a list on match. The return value of the predicate specifies if the search should continue or stop. E.g. if you wanted to just test if the tree contains any node that match a certain criteria, the you'd return False on the first match. If Find returns False then you know there was a match.

 

For each level in the tree you would specialize the generalization for that level to add the necessary data members.

 

 

 

Share this post


Link to post
Posted (edited)

OK, I think I got it now! New concept to me.

 

Just wanted to show you how I have solved similar concept in the past:

I would have no nested record, but I would have (similar to DB) a separate Array for each record, so the TSubSubSubItem would be:

 

TSubSubSubItem = record
  // key or location info
  MainDataID: integer;
  SubItemID: integer;
  SubSubItemID: integer;
  SubSubSubItemID: integer;
  // SubSubSub item details
  Disabled: boolean;
  Amount: integer;
  OrdersNo: string;
 end;
 
var AllSubSubSubItems : TArray<TSubSubSubItem>;

And in this case I just find all Disabled items and get all references by Key details. Easy, but the list is separated and Key has to be maintained. While 'nested' or tree like structure, is strict.

And with data in separate arrays I can access directly any item - I can't do that in tree structure.

Edited by Mike Torrettinni
Spelling.

Share this post


Link to post

What you really want is to separate the iteration over the data structure from the action that you perform on each item. Otherwise you end up with massive duplication of code.

 

Also, this data structure seems pretty unlikely to be the right way to represent any data structure I can imagine. 

Share this post


Link to post
6 minutes ago, David Heffernan said:

Also, this data structure seems pretty unlikely to be the right way to represent any data structure I can imagine. 

What do you mean, the tree like structure (nested records) or my last example?

Share this post


Link to post

Any data structure that encodes depth in a static name is surely the wrong solution. Have you read any books on data structures? 

Share this post


Link to post
Just now, David Heffernan said:

Have you read any books on data structures

No, any recommendations? I don't have time to read now, but I can put in on my ToRead list, or at least Amazon Wish list.

 

2 minutes ago, David Heffernan said:

Any data structure that encodes depth in a static name is surely the wrong solution

I follow this rule for another example, but that is a lot less complicated and is more for presentation layer. For complex structure, I can't see that far, yet.

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×