EasyList for Delphi and Freepascal

EasyList for Delphi and Freepascal version 1.6

Author: Amine Moulay Ramdane.

Description:

This is EasyList, EasyList looks like a TList and it is implemented with a dynamic array, and it also uses my powerful Parallel Sort Library to sort the array to be able to find an element with a binary search. Please take a look at the demo called test.pas to know how to use it, also you can take a look at the source code of EasyList to know how it is implemented.

The first parameter of the constructor is the compare method used by my inside powerful parallel sorting algorithm , the second parameter is the method that permits the binary search to get the value from the dynamic array of the EasyList, the third parameter of the constructor is a boolean value to set EasyList to be thread-safe, if you set it to true it will be not thread-safe, if you set it to false EasyList will be thread-safe and it will use my invention that is my scalable RWLock (scalable Multiple-Readers-Exclusive-Writer Lock) that is powerful and that is Starvation-free and fair, please look at the source code to understand more, the fourth parameter of the constructor is the number of cores that you set for my powerful parallel sorting (read below about it).

You can add an item with the Add() method.

You can efficiently add an item and maintain a sorted array in an ascending order with AddSorted().

You can set the methods that permit the sorting algorithm and the binary search to read the value from the dynamic array of the EasyList by using SetCompareAndGetValueFuncs() method.

Also you can set the order of the sorting by using the SetOrder() method, you can set the parameter of SetOrder() method to ctAscend for ascending order or ctDescend for descending order. And you can sort using the Sort() method.

And if Find() method doesn't find the Item, it will return -1.

And if FindThisOrFirstGreater() method doesn't find the Item it will return -1.

Both Find() and FindThisOrFirstGreater() use a binary search, so they have a log(n) time complexity and they are very fast.

FindThisOrFirstGreater() is useful when you want to construct an SQL command like the following:

Select FROM Product

WHERE UnitPrice > 50

So you have to execute FindThisOrFirstGreater() method of EasyList and it will sort the dynamic array in ascending order if it isn't sorted in ascending order, and it will find the Item of UnitPrice of 50 or the First Item of greater than UnitPrice of 50 , and after that it is easy to construct this SQL command.

Also you can delete an item with the Delete() method, if the delete() method fails, it will return -1.

Also you can clear all items by using the Clear() method.

Also you can get the number of items in EasyList by using the Count() method.

Also you can set the inside dynamic-array of EasyList object by using the SetArray() method, you can pass it another dynamic-array from outside TEasyList object.

Also you can get the inside dynamic-array by using the GetArray() method.

I have also updated the Grow() method and it is now as fast as C++ GCC STL implementation that uses x = 2, read here to understand why you have to set it like that:

How fast should your dynamic arrays grow?

https://lemire.me/blog/2013/02/06/how-fast-should-your-dynamic-arrays-grow/

Here is my new Grow() method:

-----------------------------

procedure TEasyList.Grow;

var

Delta: Integer;

begin

if length(myArray) > 64 then

Delta := length(myArray) * 2

else

if length(myArray) > 8 then

Delta := 16

else

Delta := 4;

SetLength(myArray,length(myArray) + Delta);

end;

-----------------------------

Read more in the following about my Powerful Parallel Library that is used by my EasyList:

Parallel Sort Library that supports Parallel Quicksort, Parallel HeapSort and Parallel MergeSort on Multicores systems.

Parallel Sort Library uses my Thread Pool Engine and sort many array parts - of your array - in parallel using Quicksort or HeapSort or MergeSort and after that it finally merge them - with the merge() procedure -

In the previous parallelsort version i have parallelized only the sort part, but in this new parallelsort version i have parallelized also the merge procedure part and it gives better performance.

My new parallel sort algorithm has become more cache-aware, and i have done some benchmarks with my new parallel algorithm and it has given up to 5X scalability on a Quadcore when sorting strings, other than that i have cleaned more the code and i think my parallel Sort library has become a more professional and industrial parallel Sort library , you can be confident cause i have tested it thoroughly and no bugs have showed , so i hope you will be happy with my new Parallel Sort library. Notice also in the source code that my Mergesort uses insertion sort like in a Timsort manner, so it is efficient.

I have implemented a Parallel hybrid divide-and-conquer merge algorithm that performs 0.9-5.8 times better than sequential merge, on a quad-core processor, with larger arrays outperforming by over 5 times. Parallel processing combined with a hybrid algorithm approach provides a powerful high performance result.

My algorithm of finding the median of Parallel merge of my Parallel Sort Library is O(log(min(|A|,|B|))), where |A| is the size of A.

Why are we finding the median in the parallel algorithm ?

Here is my idea of finding the median that is O(log(min(|A|,|B|))) to understand better:

Let's assume we want to merge sorted arrays X and Y. Select X[m] median element in X. Elements in X[ .. m-1] are less than or equal to X[m].

Using binary search find index k of the first element in Y greater than X[m]. Thus Y[ .. k-1] are less than or equal to X[m] as well.

Elements in X[m+1..] are greater than or equal to X[m] and Y[k .. ] are greater. So merge(X, Y) can be defined as concat(merge(X[ .. m-1], Y[ .. k-1]), X[m], merge(X[m+1.. ], Y[k .. ])), now we can recursively in parallel do merge(X[ .. m-1], Y[ .. k-1]) and merge(X[m+1 .. ], Y[k .. ]) and then concat results.

I have added a TWildCard class so that to work with wildcards, please take a look at the filespec.pas file inside the zip file so that to understand how it works, and here is how you can work with wildcards:

**********************

var wildcard:TWildCard;

str:string;

begin

str:='Amine.jpg';

wildcard:=TWildCard.create;

if wildcard.samefile('A*?g',str1,true) then writeln('Ok!');

end;

*********************

When the third parameter of samefile() method of TWildCard class is true, samefile() will be case-sensitive.

You can learn how to use Standard Wildcards from here :

https://tldp.org/LDP/GNU-Linux-Tools-Summary/html/x11655.htm

You can go to download the zip files by clicking on the following web link:

https://drive.google.com/drive/folders/1KSPywDf28LPY0F4Rx2QT9lmBuEwyJZ-i?usp=sharing

Language: FPC Pascal v3.02+ / Delphi tokyo+

http://www.freepascal.org/

Required FPC switches: -O3 -Sd

-Sd for delphi mode....

- Platform: Windows,Linux (x86)