?
Solved

search near in Delphi Dictionary or other list

Posted on 2011-10-19
7
Medium Priority
?
286 Views
Last Modified: 2012-05-12
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
Comment
Question by:DuriPro
  • 4
  • 3
7 Comments
 
LVL 25

Expert Comment

by:epasquier
ID: 36993501
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
 

Author Comment

by:DuriPro
ID: 36993546
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
 
LVL 25

Expert Comment

by:epasquier
ID: 36994304
stay tuned, I'll do it later tonight
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 25

Expert Comment

by:epasquier
ID: 36998577
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
 
LVL 25

Accepted Solution

by:
epasquier earned 500 total points
ID: 36998612
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
 

Author Comment

by:DuriPro
ID: 36998749
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
 

Author Closing Comment

by:DuriPro
ID: 36998753
THANKS !!
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you ever had your Delphi form/application just hanging while waiting for data to load? This is the article to read if you want to learn some things about adding threads for data loading in the background. First, I'll setup a general applica…
Hello everybody This Article will show you how to validate number with TEdit control, What's the TEdit control? TEdit is a standard Windows edit control on a form, it allows to user to write, read and copy/paste single line of text. Usua…
In a question here at Experts Exchange (https://www.experts-exchange.com/questions/29062564/Adobe-acrobat-reader-DC.html), a member asked how to create a signature in Adobe Acrobat Reader DC (the free Reader product, not the paid, full Acrobat produ…
Whether it be Exchange Server Crash Issues, Dirty Shutdown Errors or Failed to mount error, Stellar Phoenix Mailbox Exchange Recovery has always got your back. With the help of its easy to understand user interface and 3 simple steps recovery proced…
Suggested Courses
Course of the Month17 days, 2 hours left to enroll

864 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question