{ http://www.awitness.org/delphi_pascal_tutorial/index.html This unit demos a way to use an indexing array to quickly find things on sorted linked list when people want to find something in a phone book , say 'Ben' they jump to the letter B and then to Be and begin looking there This code does the same thing storing indexed pointers to positions on the sorted alphabetical array ie a aa ab ac ... b ba bc bd etc etc When a search must be made a quick calculation is made based on the first two letters of the search word (don't use the search code to search for one letter) and the result of this quick calculation is the position in the array of the pointer pointing to that particular section of the linked list (the array would point to 'be' if we were looking for Ben) First hit the open button to read words in from a text file use plain text if you want to avoid garbage words the read text function is just a quick way to build up a lot of entries on the linked list so there is something to index and search for the read text function ignores punctuation so wasn't becomes two words wasn and then the letter t is also recognized as a word - the code thinks that words start with a letter and end with anything other than a letter and has not been taught to recognize punctuation when the text file is read the words are output in the memo (just so you know that something is going on and also a debug for the text reading code) at the same time each word is put onto a sorted linked list and the array index is updated if Ben was pointed by the 'be' pointer of the array and Bean was input then Bean would become the new pointer in 'be' replacing Ben because Bean is less than Ben (when you do a search for 'be' entries you want to start at the lowest 'be' entry on the list) when the text file has been read, the words inserted on the sorted linked list and the array index updated, you can punch the debug button to print out both the array index and the sorted linked list to text files - this is simply debugging code to make sure that both codes are working properly you do a quick telephone book like look up for a word on the linked list by typing it into the edit box and hitting the search button the search function calculates which page to flip to in the 'telephone book' and then sends the pointer and the following pointer to a quick search function the search function would search from 'be' to 'bf' for any 'be' entry rather than starting from the beginning of the linked list or going right to the end of the sorted list and quickly either find the pointer to the entry and report back that it didn't exist a second field is included in the record where a random number is inserted when Ben is found on the list his 'number' is also reported this is just a demo of how records can have an indexing field and then corresponding fields of data in the record (the index field in this example is the string and the additional data field is the random number) With a few modifications this code could also be adapted to quickly insert items on the linked list. This has not been implemented at the moment (it just occurred to me). For example to insert 'Ben' on the list we could begin a search for the insertion point at 'Be'. If the pointer to 'Be' on the array is 'nil' then we step back on the array until we find a pointer that is not nil (let's say there was an entry for 'ba'). If the 'be' entry is greater than the current 'be' entry we can pass the 'be' pointer (the pointer to lowest 'be' element currently on the list) however if the added 'be' entry is less than the current 'be' entry on the list then we must pass a pointer to a previous entry (for example 'ba') since we require a previous pointer to attach an item to a sorted linked list (in this example the new lower 'be' element would be attached to the last 'ba' element - the previous pointer - and before the 'be' element that was previously the lowest element indexed under 'be' making the newly inserted 'be' element now the lowest 'be' element on the list. As the code is currently implemented it starts right at the bottom of the list with the head. Time could then be saved both on the searching and on the insertion into the sorted list by using the array. } unit Unit1; interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; type PtrAlphaRecord = ^LinkedListElementAlphaRecord; {a pointer to a record} LinkedListElementAlphaRecord = record {the kind of record pointed to} aword : string; anumber : integer; nextlink : PtrAlphaRecord; end; TForm1 = class(TForm) Button1: TButton; Memo1: TMemo; OpenDialog1: TOpenDialog; Edit1: TEdit; Button2: TButton; Button3: TButton; Label1: TLabel; Label2: TLabel; Label3: TLabel; Label4: TLabel; Label5: TLabel; Label6: TLabel; procedure FormCreate(Sender: TObject); procedure Button1Click(Sender: TObject); procedure ReadText; procedure Parseline(var line : string); function SortedLinkedListInsert(s:string; head:PtrAlphaRecord):PtrAlphaRecord; procedure UpdateArrayIndex(Linkpoint, Previous : PtrAlphaRecord); procedure Button3Click(Sender: TObject); {the debug button} procedure debugarrayindex; procedure Button2Click(Sender: TObject); function SearchIndexedLinkedList(s : string; start, finish : PtrAlphaRecord):PtrAlphaRecord; private { Private declarations } public { Public declarations } end; var Form1: TForm1; f : textfile; Head, linkpoint : PtrAlphaRecord; {head of linked list, and a pointer to a newly inserted record} AIndex : array[0..701] of PtrAlphaRecord; { a aa ab ac ... b ba bc ...z za} {there are 26 letters of the alphabet normally if someone was to look up 'ben' on even an extremely long list they would jump straight to 'be' and start looking for ben there this is called the divide and conquer strategy and allows people to look up names even in a database as large as a phone book quickly the array contains pointers to a sorted linked list of alphabetical words with the array holding 26 elements for each letter of the alphabet example ba bb bc bd be etc etc there are no words starting with 'bz' so some of the place holders in the array will never be used and will always be nil. The array would point to the first occurence of a word starting with 'be' on a sorted linked list if a word starting with 'be' actually existed (oltherwise the be pointer in the array would be nil and given that this was the first 'be' to be inserted, the search for the spot to insert 'be' would start at the first non nil entry in the array before 'be' (indicating a position on the linked list) and once inserted the pointer to the newly inserted 'be' would be placed in the placeholder for 'be' in the array index structure} implementation {$R *.DFM} procedure TForm1.FormCreate(Sender: TObject); var i : integer; begin New(Head); {head of the linked list, new creates a new record not a new pointer} Head^.aword := ''; {lowest element on the list a nothing string} Head^.nextlink := nil; {intialize first linked list pointer to nil} {initialize all pointers in index array to nil} for i := 0 to 701 do AIndex[i] := nil; Randomize; {initialize random number generator} end; procedure TForm1.Button1Click(Sender: TObject); begin {step 1 create a long linked list structure by reading words from plain text files and inserting them onto a sorted linked list} If OpenDialog1.Execute then begin AssignFile(f, OpenDialog1.FileName); Reset(f); ReadText; {read all the words in the text file} Closefile(f); end; end; procedure TForm1.ReadText; {scan through text file a non letter character is encountered consider it the end of a word {for example punctuation a space etc) this is just a quick way to get lots of words onto a sorted linked list} var line : string; begin While not eof(f) do begin Readln(f, line); Parseline(Line); end; end; {pluck each word out of the line of text} procedure TForm1.Parseline(var line : string); var s : string; i, j, z, len : integer; k : char; x : PtrAlphaRecord; begin i := 0; j := 0; len := length(line); If len = 0 then exit; i := 0; repeat If i + 1 > len then exit; repeat {if its not a letter increment i} i := i + 1; k := Line[i]; z := ord(k); until (i = len) or (((z >= ord('a')) and (z <= ord('z'))) or ((z >= ord('A')) and (z <= ord('Z')))); If i = len then exit; {found a valid letter, now scan to the end of the word which starts at i and will end at j } j := i; repeat j := j + 1; k := Line[j]; z := ord(k); until (j = len) or (z < ord('A')) or ((z > ord('Z')) and (z < ord('a'))) or (z > ord('z')); k := Line[j]; z := ord(k); {don't include periods at end of line etc} If ((z < ord('A')) or ((z > ord('Z')) and (z < ord('a'))) or (z > ord('z'))) then s := copy(line, i, j - i) else s := copy(line, i , j - i + 1); {insert s into sorted linked list} If s <> '' then begin memo1.lines.append(s); {visual debugging code for words} x := SortedLinkedListInsert(s, head); {now use x pointer returned to insert a 'number' into the number field of the list record} If x <> nil then x^.anumber := Random(100000); end; i := j; until (i = len); end; function TForm1.SortedLinkedListInsert(s:string; head:PtrAlphaRecord):PtrAlphaRecord; var Previous:PtrAlphaRecord; found, dupe:boolean; begin found:=false; dupe := false; Previous:=nil; result := nil; repeat {when current string is less than list item this is where to insert} If lowercase(s) < lowercase(head^.aword) then found:=true; {no duplicates} If lowercase(s) = lowercase(head^.aword) then dupe := true; If (lowercase(s) > lowercase(head^.aword)) then begin Previous:=Head; head:=head^.nextlink; {keep going till found item greater than} end; until (found) or (head=nil) or (dupe); {found, end of list, duplicate} If not dupe then begin {reject duplicates} new(linkpoint); {create a new record} linkpoint^.aword := s; {insert the string} Linkpoint^.nextlink:=Previous^.nextlink; {point to next on list} Previous^.nextlink:=linkpoint; {point to newly inserted string} Result:=Linkpoint; UpdateArrayIndex(Linkpoint, Previous); {do the index} end; end; procedure TForm1.UpdateArrayIndex(Linkpoint, Previous : PtrAlphaRecord); var c, c2: char; index : integer; s : string[1]; begin {calculate the correct position on the array index for the newly inserted record the array consists of 702 index entries (which are pointers to a linked list element each letter of the alphabet has 26 positions associated with it for example a aa ab ac ... az b ba bb bc ... and so on by finding the first two letters of the newly inserted string or the first letter if it is a string of 1 a mathematical calculation indicates which array index applies to that entry for example bread would apply to the array element corresponding to br if br is nil then bread is the first example of an element on the list starting with br so the pointer to bread is put into the array index at that point if br is not nil then if the previous pointer contains a string with br in it which is less than the currently inserted value no change must be made to the index array for example if the new value is bread and the previous word was brad brad is already a lower element that bread so no change is made to the index array for the br value since it must point to the lowest element for words starting with br - the procedure simply exits without making any changes however if the word being inserted was bread and the previous pointer contained a word whose first two letters were anything less than br then even if a previously instance of br (such as broad for example) was holding the br index position in the array the array must be pointed to bread since bread is now obviously the lowest element in the list of words starting with br so in this case the array is updated to point to bread and if for example it was pointing to broad before this is simply overwritten with a new pointer to bread to keep the array index list pointing to the lowest element with the letters 'br' } If Length(LinkPoint^.aword) = 1 then begin {if length is one must be a single letter since the insertion routine rejects duplicates it must be the first instance of that single letter insert a pointer to it in the array index} s := uppercase(Linkpoint^.aword[1]); c := s[1]; {array is indexed a aa ab ... az b ba bc ... etc} Index := ((ord(c) - 65) * 27); AIndex[Index] := Linkpoint; exit; {procedure} end; {get first two chars from newly inserted string} s := uppercase(Linkpoint^.aword[1]); c := s[1]; s := uppercase(Linkpoint^.aword[2]); c2 := s[1]; index := ((ord(c) - 65) * 27) + (ord(c2) - 64) ; {if the entry index for these two letters is nil then this is the first} If AIndex[Index] = nil then begin AIndex[Index] := Linkpoint; exit; {procedure} end; {if the previous entry contains the same two first letters as the current entry and its value is less than the newly inserted entry then it already holds a lower position than the current and either the previous entry or one before it is the index array entry for those two letters so exit and do nothing to the array index} If (lowercase(copy(Previous^.aword, 1, 2)) = lowercase(copy(LinkPoint^.aword, 1, 2))) and ((lowercase(Previous^.aword)) < (lowercase(LinkPoint^.aword))) then exit; {procedure} {since we know that the previous entry is not the same two letters and less than the current, and we know that the slot in the array index was not nil then since the previous entry is less than the new entry {by definition a link is inserted on a sorted linked list right after the first entry encountered which is less than the entry inserted) it means that we must update the index array by replacing its index with the current entry which is now the lowest entry for those two letters} AIndex[Index] := LinkPoint; end; {don't push this button until text file has been read the code prints out what the array indexing pointers are pointing to and then points out the alpha sorted linked list to allow visual checking of the accuracy of the code} procedure TForm1.Button3Click(Sender: TObject); {debug index code} begin debugarrayindex; end; procedure TForm1.debugarrayindex; var i : integer; x : PtrAlphaRecord; j : integer; fa : textfile; begin i := 0; AssignFile(fa, 'h:\arraytest\aindex.txt'); rewrite(fa); j := 64; repeat if AIndex[i] <> nil then Writeln(fa, 'Index : ' + IntToStr(i) + ' ' + chr(j) + ' : ' + Aindex[i]^.aword); If AIndex[i] = nil then Writeln(fa, 'Index : ' + IntToStr(i) + ' ' + chr(j) + ' : ' + 'nil'); i := i + 1; j := j + 1; If j = (ord('Z') + 1) then j := 64; until (i = 702); CloseFile(fa); Assignfile(fa, 'h:\arraytest\alinklist.txt'); Rewrite(fa); If head^.nextlink <> nil then begin x := head^.nextlink; repeat Writeln(fa, x^.aword); x := x^.nextlink; until (x = nil); end; CloseFile(fa); ShowMessage('dun'); end; procedure TForm1.Button2Click(Sender: TObject); {do a quick indexed search of the linked list items} var s:string; c, c2 : char; index : integer; x : PtrAlphaRecord; begin If Edit1.Text = '' then exit; s := uppercase(Edit1.Text); c := s[1]; c2 := s[2]; index := ((ord(c) - 65) * 27) + (ord(c2) - 64) ; {debugging code} If AIndex[Index] <> nil then ShowMessage(s + ' : ' + AIndex[Index]^.aword) else ShowMessage(s + ' : No entry for that letter combo'); If Index <> 701 then x := SearchIndexedLinkedList(s, Aindex[Index], AIndex[Index + 1]) else x := SearchIndexedLinkedList(s, Aindex[Index], nil); If x = nil then ShowMessage('That entry was not found on the list') else ShowMessage(x^.aword + ' was found on the list' + chr(13) + ' and the number is ' + InttoStr(x^.anumber)); end; {the array index contains pointers to elements on the linked list if we are searching for Ben we pass the string Ben the pointer to 'be' and the pointer to 'bf' we start searching from 'be' and when we reach 'bf' we stop and report unsuccessful search or we find ben and return its pointer} function TForm1.SearchIndexedLinkedList(s : string; start, finish : PtrAlphaRecord):PtrAlphaRecord; begin Result := nil; if start <> nil then begin repeat If start <> nil then If uppercase(start^.aword) = s then Result := start else start := start^.nextlink; until ((start = finish) or (Result <> nil)); end; end; end.