• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 299
  • Last Modified:

search near in Delphi Dictionary or other list

I need to maintain a list of key-values, where the key is a date and the value a double. Now, if I search for a date which is not in the list, I need the value of the first next date available in the list. I am trying to use a dictionary, but i don't mind. I need a list in memory and I'm looking for a simple way to do that.

And I know looping through the list, that is an option, but what I'm looking for is like TTable.FindNearest, but than in memory ...
0
DuriPro
Asked:
DuriPro
  • 4
  • 3
1 Solution
 
Emmanuel PASQUIERFreelance Project ManagerCommented:
whatever the way you implement the list, you'll have to do a dichotomic search : by its nature dichotomic search always find the nearest value (before and after the one you look for), until both ends of the search range are the same (if the value exists). If the value does not exists, then you have both nearest existing values, the one before and the one after.

A dichotomic search can only work with sorted values, in your case sorted by date (which can be seen as an integer)

for the implementation of this, I would recommend using TObjectList that will hold the list of TDateValue object (your key/value data type)

Here would be the (simplified) interface of all this :
TDateValue =class (TObject)
 Date:Integer;
 Value:Double;
end;

TDateValueList=class(TObjectList)
private
  function  GetDateValueByIndex(i:integer):TDateValue;
public
  
  procedure AddKeyValue(D:TDate;Val:Double); // Always use this to add values in your list, not TObjectList methods
  function FindDateOrNearestNext(D:TDate):Integer; // Returns INDEX of exact date or nearest position (next)
  property KeyValues[i:integer]:TDateValue read GetDateValueByIndex;
end;

Open in new window


Is that what you are after ?
Do you need help implementing Dichotomic search or is it the first time you heard the word ?
0
 
DuriProAuthor Commented:
Wow, that sounds great and is exactly what I'm looking for. And I need some help with that Dichotomic search indeed .... Would you help me some further with the public procedure and public function please ?
0
 
Emmanuel PASQUIERFreelance Project ManagerCommented:
stay tuned, I'll do it later tonight
0
Cloud Class® Course: Python 3 Fundamentals

This course will teach participants about installing and configuring Python, syntax, importing, statements, types, strings, booleans, files, lists, tuples, comprehensions, functions, and classes.

 
Emmanuel PASQUIERFreelance Project ManagerCommented:
Hi, here it is, I made a unit to implement a generic dichotomic search list
It also includes your specific key/value object implementation, so that you can see how to implement your own key/value list using the root classes

I made also a sample project using this unit
Dichotomic.zip
0
 
Emmanuel PASQUIERFreelance Project ManagerCommented:
Small update in the sample application
* I forgot to free the list on form destroy
* I now update listbox selected item after adding a key/value
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, Spin, ComCtrls, Dichotomic;

type
  TForm1 = class(TForm)
    lbDicho: TListBox;
    btnFill: TButton;
    btnAdd: TButton;
    DateTimePicker: TDateTimePicker;
    edtValue: TSpinEdit;
    btnLocate: TButton;
    Label1: TLabel;
    LocateResult: TMemo;
    procedure FormCreate(Sender: TObject);
    procedure btnFillClick(Sender: TObject);
    procedure btnAddClick(Sender: TObject);
    procedure btnLocateClick(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
  private
    { Déclarations privées }
    _DichoList:TKeyDateWithDoubleList;
    procedure UpdateDichoList;
  public
    { Déclarations publiques }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
begin
 _DichoList:=TKeyDateWithDoubleList.Create;
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
 _DichoList.Free;
end;

procedure TForm1.UpdateDichoList;
var
 i:integer;
begin
 With lbDicho.Items do
  begin
   BeginUpdate;
   Clear;
   for i := 0 to _DichoList.Count-1  do With TKeyDateWithDouble(_DichoList.KeyObject[i]) do
    Add(DateToStr(Date)+' | '+FloatToStr(Value));
   Add(''); // Add one dummy line, just to be able to select it
   EndUpdate;
  end;
end;

procedure TForm1.btnAddClick(Sender: TObject);
begin
 _DichoList.Add(DateTimePicker.DateTime,edtValue.Value/10);
 UpdateDichoList;
 lbDicho.ItemIndex:=_DichoList.LocatedIndex;
end;

procedure TForm1.btnFillClick(Sender: TObject);
var
 i:integer;
begin
 for i := 1 to 10 do
  _DichoList.Add(DateTimePicker.DateTime+Random(365)-180,Random(1000)/10);
 UpdateDichoList;
end;

procedure TForm1.btnLocateClick(Sender: TObject);
begin
 LocateResult.Clear;
 if _DichoList.Locate(DateTimePicker.DateTime) then
  begin
   LocateResult.Lines.Add(Format('Found @%d',[_DichoList.LocatedIndex]));
  end Else
  begin
   LocateResult.Lines.Add('Not Found.');
   if _DichoList.LocatedIndex>0
    then LocateResult.Lines.Add('Nearest Prev Date '+DateToStr(TKeyDateWithDouble(_DichoList.KeyObject[_DichoList.LocatedIndex-1]).Date))
    Else LocateResult.Lines.Add('No Nearest Prev Date');
   if _DichoList.LocatedIndex<_DichoList.Count
    then LocateResult.Lines.Add('Nearest Next Date '+DateToStr(_DichoList.LocatedObject.Date))
    Else LocateResult.Lines.Add('No Nearest Next Date');
  end;
 lbDicho.ItemIndex:=_DichoList.LocatedIndex;
end;

end.

Open in new window

0
 
DuriProAuthor Commented:
Thank you so much for all your effort ! For me it is a more advanced topic so I'm currently studying your code. It does exactly what I want and I will rewrite it (so I understand better) in my application.

Thanks a lot !!
Arthur
0
 
DuriProAuthor Commented:
THANKS !!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Cloud Class® Course: Microsoft Exchange Server

The MCTS: Microsoft Exchange Server 2010 certification validates your skills in supporting the maintenance and administration of the Exchange servers in an enterprise environment. Learn everything you need to know with this course.

  • 4
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now