Not actually a hash-table, but an AvgLvlTree, which can be used the same way. The AvgLvlTree unit comes with Lazarus; if you don't have that, you can download avglvltree.pas here:

http://svn.freepascal.org/cgi-bin/viewvc.cgi/trunk/components/lazutils/avglvltree.pas?root=lazarus&view=log

There doesn't seem to be a lot of information available on using regular expressions and hash-tables in Free Pascal, so I decided to post this.

The program reads a text file and counts the number of unique words, and also displays the number of times the most common word was found.

Since TStringToPointerTree actually maps strings to pointers, I wrote some tiny utility functions to handle the casting from integers to pointers and back.

Although I was worried that this tree-structure would be slower than a hash-table, it turned out to be quite fast.

{$mode objfpc}

uses
AvgLvlTree,
regexpr,
classes,
dateutils,

  Sysutils;

const
  file_to_process = 'Bartlett--Quotations.txt';
type
  // string-integer table
  t_si_table = TStringToPointerTree;
  t_si_item = PStringToPointerItem;
procedure si_table_put( table: t_si_table; k: string; v: longint );
begin
  table[ k ] := pointer( v )
end;
function si_table_get( table : t_si_table; key : string ): longint;
begin
  exit( longint( table[ key ] ) )
end;
procedure si_table_inc( table: t_si_table; k: string );
begin
  table[ k ] := pointer( si_table_get( table, k ) + 1 ) ;
end;
function si_table_key( item : t_si_item ): string;
begin
  exit( item^.name )
end;
function si_table_val( item : t_si_item ): longint;
begin
  exit( longint( item^.value ) )
end;
function si_table_new( sensitive : boolean ): t_si_table;
begin
  exit( t_si_table.create( sensitive ) )
end;
var
  table : t_si_table ;
  table_item : t_si_item ;
  line, word : string;
  re : TRegExpr;
  max_count, count : int32;
  lines : TStringList;
  time_1 : TDateTime;
begin
  time_1 := time;
  re := TRegExpr.Create;
  re.Expression := '(?i)[a-z]+' ;  // case-insensitive
  table := si_table_new( true ) ; // true to make it case-sensitive.
  lines := TStringList.Create;
  lines.LoadFromFile( file_to_process );
  for line in lines do  begin
    if re.exec( line ) then  begin
      si_table_inc( table, re.match[0] );
      while re.execNext do
        si_table_inc( table, re.match[0] );
    end;
  end;
  lines.free;
  writeln( 'Unique word count: ', table.count );
  max_count := 0;
  for table_item in table do  begin
    count := si_table_val( table_item );
    if count > max_count then  begin
      word := si_table_key( table_item );
      max_count := count
    end;
  end;
  writeln( 'Commonest word: ', word, ' (', max_count, ')' );
  writeln( 'Elapsed time: ',
           milliSecondsBetween( time_1, time ),
           ' milliseconds.' );
  table.free;
  re.free
end.

Processing the file "Bartlett--Quotations.txt", which is about 319 kilobytes in size, produces this output:

Unique word count: 8911
Commonest word: the (2200)
Elapsed time: 94 milliseconds.

Documentation for TRegExpr can be found here:
http://regexpstudio.com/TRegExpr/Help/tregexpr_interface.html

If I'm not mistaken, see:
http://wiki.lazarus.freepascal.org/AVL_Tree

Thanks,
Reinier

Yes, that was one of the very few good references that I found.

There doesn't seem to be much demand for hash-tables in the Free Pascal community. Hash-tables can be very helpful. I don't see a good way to do what my program does without using associative arrays of some type.

Also, there doesn't seem to be much use of regular expressions.

Anyway, TStringToPointerTree works well and seems very fast to me.

Added an iterator of sorts for regular expressions. This allows

    if re.exec( line ) then  begin
      si_table_inc( table, re.match[0] );
      while re.execNext do
        si_table_inc( table, re.match[0] );
    end;

to be replaced by

    re_each_match( re, line, @count_the_word );

with no loss of speed.

{$mode objfpc}

uses
AvgLvlTree,
regexpr,
classes,
dateutils,

  Sysutils;

const
  file_to_process = 'Bartlett--Quotations.txt';
type
  // string-integer table
  t_si_table = TStringToPointerTree;
  t_si_item = PStringToPointerItem;
procedure si_table_put( table: t_si_table; k: string; v: longint );
begin
  table[ k ] := pointer( v )
end;
function si_table_get( table : t_si_table; key : string ): longint;
begin
  result := longint( table[ key ] )
end;
procedure si_table_inc( table: t_si_table; k: string );
begin
  table[ k ] := pointer( si_table_get( table, k ) + 1 ) ;
end;
function si_table_key( item : t_si_item ): string;
begin
  result := item^.name
end;
function si_table_val( item : t_si_item ): longint;
begin
  result := longint( item^.value )
end;
function si_table_new( sensitive : boolean ): t_si_table;
begin
  result := t_si_table.create( sensitive )
end;
type
  t_regex_proc = procedure( const text : string );
procedure re_each_match( re : TRegExpr;
                         const text: string;
                         proc: t_regex_proc ); overload;
begin
  if re.exec( text ) then  begin
    proc( re.match[0] );
    while re.execNext do
      proc( re.match[0] );
  end;
end;
procedure re_each_match( const re_str, text: string;
                         proc: t_regex_proc ); overload;
var
  re : TRegExpr;
begin
  re := TRegExpr.Create;
  re.Expression := re_str;
  re_each_match( re, text, proc );
  re.free
end;
var
  table : t_si_table ;
  table_item : t_si_item ;
  line, word : string;
  re : TRegExpr;
  max_count, count : int32;
  lines : TStringList;
  time_1 : TDateTime;
procedure count_the_word( const s : string );
begin
  si_table_inc( table, s )
end;
begin
  time_1 := time;
  re := TRegExpr.Create;
  re.Expression := '(?i)[a-z]+' ;  // case-insensitive
  table := si_table_new( true ) ; // true to make it case-sensitive.
  lines := TStringList.Create;
  lines.LoadFromFile( file_to_process );
  for line in lines do
    re_each_match( re, line, @count_the_word );
  lines.free;
  writeln( 'Unique word count: ', table.count );
  max_count := 0;
  for table_item in table do  begin
    count := si_table_val( table_item );
    if count > max_count then  begin
      word := si_table_key( table_item );
      max_count := count
    end;
  end;
  writeln( 'Commonest word: ', word, ' (', max_count, ')' );
  writeln( 'Elapsed time: ',
           milliSecondsBetween( time_1, time ),
           ' milliseconds.' );
  table.free;
  re.free
end.

Thanks. It's a wiki

There doesn't seem to be much demand for hash-tables in the Free Pascal community. Hash-tables can be very helpful.

There are some hash tables in units "contnrs", "dynhasharray" and "stringhashlist".

I don't see a good way to do what my program does without using associative arrays of some type.

Me too.

Also, there doesn't seem to be much use of regular expressions.

Well, I guess Pascal programmers prefer readability over shortness.

Anyway, TStringToPointerTree works well and seems very fast to me.

Me too.

Mattias

http://www.freepascal.org/docs-html/fcl/contnrs/index-4.html

I can't seem to find "dyn" on this page.

TFPStringHashTable won't work for my program because it maps strings to strings, not to pointers or numbers. (I wonder if it has an enumerator.)

I already experimented with TFPDataHashTable. It won't work for this program, because, incredibly, there is no way to iterate over the entries! The people who write these classes need to have a wider experience with using hash-tables. (Become fluent in the tiny language Awk, for example.)

That's why it seemed that I had to download a file from Lazarus and compile it in order to have a good associative array that maps strings to numbers (or pointers).

So, thanks a lot for creating avglvltree. It does the job perfectly.

I think we can agree 100% that 70-character-long regular expressions are nightmarish and should definitely be avoided if at all possible! Trying to decipher one of those could almost drive you crazy.

Regular expressions are an absolute necessity for some applications. The program "grep", for example. The user can't be expected or allowed to write a routine in C or Pascal that selects certain lines, but he can be allowed to supply a regular expression that does that. The same is true for text editors. Any halfway decent editor will let you find a line that contains "foo" followed at some distance by "bar" by searching for "foo.*bar". (Even Microsoft Word lets you do a r.e. search, although they dishonestly call it something else.)

I know that you're saying that a regexpr engine can't do what a full-blown parser can. Very true. But for some tasks they work very well.

Let's say we want to find some dates in a string. The dates will be like either of these patterns:

yyyy-mm-dd
yyyy/mm/dd

In the r.e., \d represents a digit, and [...] is a character class or set. So the r.e. could be

\d\d\d\d[-/]\d\d[-/]\d\d

Testing that on this string

'92011-05-22 1999/12/22--2012-02-28; 2000/09/033 2011-07-05::1988/04/06'

we get

2011-05-22
1999/12/22
2012-02-28
2000/09/03
2011-07-05
1988/04/06

Now let's say that we don't want to include the dates that have an extra digit before the year or after the day. A non-digit character is represented by \D, and the beginning of the string is matched by ^. Alternation or "or" is indicated by |. So we prefix this to the r.e.:

(^|\D)

It says that the date must be at the very beginning of the string or it must be preceded by a non-digit. A $ will match only at the end of the string, so we append this to the r.e.:

(\D|$)

It says that the date must be followed by a non-digit or must be at the very end of the string. At this point the r.e. looks like this:

(^|\D)\d\d\d\d[-/]\d\d[-/]\d\d(\D|$)

And the ouput is this:

1999/12/22-
-2012-02-28;
2011-07-05:
:1988/04/06

The delimiting characters are now included in the match. To solve this, we take advantage of the fact that parentheses in the r.e. not only create a group, but also make a "capture" of what they enclose. So we put them around the part of the pattern that we want to keep, yielding this:

'(^|\D)(\d\d\d\d[-/]\d\d[-/]\d\d)(\D|$)'

Since there are 3 pairs of parentheses in the r.e., there are 3 captures. We want the second one. So we change the program from

  writeln( re.match[0] );

which prints the entire substring that was matched, to

  writeln( re.match[2] );

which prints the second capture. The ouput is now

1999/12/22
2012-02-28
2011-07-05
1988/04/06

Just as it's easier to climb a cliff than to descend it, it's easier to write a regular expression than to read it. So don't worry too much about that aspect.

Remember that a small r.e. can sometimes do the work of quite a few lines of code.

{$mode objfpc}
{$H+}
uses regexpr;
const date_data =
  '92011-05-22 1999/12/22--2012-02-28; 2000/09/033 2011-07-05::1988/04/06';
var
  re : TRegExpr;
begin
  re := TRegExpr.Create;
  re.Expression := '\d\d\d\d[-/]\d\d[-/]\d\d';
  if re.exec( date_data ) then  begin
    writeln( re.match[0] );
    while re.execNext do
      writeln( re.match[0] )
  end;
  writeln;
  re.Expression := '(^|\D)\d\d\d\d[-/]\d\d[-/]\d\d(\D|$)';
  if re.exec( date_data ) then  begin
    writeln( re.match[0] );
    while re.execNext do
      writeln( re.match[0] )
  end;
  writeln;
  re.Expression := '(^|\D)(\d\d\d\d[-/]\d\d[-/]\d\d)(\D|$)';
  if re.exec( date_data ) then  begin
    writeln( re.match[2] );
    while re.execNext do
      writeln( re.match[2] )
  end;
  writeln;
  re.free
end.

Which means you're encouraged to place your contributions, code snippets etc there.
It's of course personal taste, but IMO, code snippets/examples are much better placed there than in a mailing list as they can be more easily updated, formatted and categorized.

The lengthy article + example you posted on regexes is e.g. a perfect candidate IMO....
http://wiki.lazarus.freepascal.org/Regexpr

Just my 2 cents,

thanks,
Reinier

Mattias Gaertner wrote

> Also, there doesn't seem to be much use of regular expressions. Well, I guess Pascal programmers prefer readability over shortness.

They're definitely not a panacea, but where you want to do things like extract the x.y.z version number from e.g 'PostgreSQL 8.4.6 on i686-pc-linux-gnu, compiled by GCC 2.95.3, 32-bit' and 'LI-V2.5.0.26054 Firebird 2.5 Release Candidate 3', using regexes can end up being more readable provided that the comments include examples of what should be matched.

I know that function and variable names should be chosen so as to reduce the need for comments, but I feel that large sections of the programming industry are still biased against them because they have this fixed idea that they introduce overhead in the generated code or can give away trade secrets to the end user. In short, we're still hobbled by the legacy of interpreted BASIC, which is about all that some management types know.

For comparison, here's a C++ program. Unlike the Pascal version, it shows the 20 most common words. Also, it doesn't use a regular expression engine, since I didn't have one.

An associative array that maps strings to integers was simply obtained by:

 unordered_map<string,int> w_table;
// c++  -std=c++11 -o map.exe  map.cpp
#include <unordered_map>
#include <iostream>
#include <fstream>
#include <list>
#include <utility>  // for pair
#include <vector>
#include <algorithm>  // for sort
using namespace std;

// Convert "a-f" to "abcdef".
string gen_cset( string s )
{

  string acc;
  char ch;
  int last = s.size() - 1;
  for (int i = 0; i <= last; i++)
  { ch = s[i];
    if ('-' == ch)
      if ((0 == i) || (last == i))
        acc.push_back( ch );
      else
        for (int j = s[i-1] + 1; j < s[i+1]; j++)
          acc.push_back( j );
    else
      acc.push_back( ch );
  }
  return acc;

}

const string letters = gen_cset( "a-zA-Z" );
list<string> scan_string( string s, string chars )
{
  list<string> lst;
  size_t p, q;
  p = 0;
  while ( p != string::npos )
  { p = s.find_first_of( chars, p );
    if ( p != string::npos )
    { q = s.find_first_not_of( chars, p );
      lst.push_back( s.substr( p, q - p ) );
      p = q;
    }
  }
  return lst;
}
typedef  pair<string,int>  word_and_count;

bool compare_pair( word_and_count a, word_and_count b ) {

  return ( a.second > b.second );

}

int main() {
  unordered_map<string,int> w_table;
  ifstream f_stream ( "Bartlett--Quotations.txt" );
  string line;
  list<string> word_list;
  if ( f_stream.is_open() )
  { while ( f_stream.good() )
    { getline( f_stream, line);
      word_list = scan_string( line, gen_cset("a-zA-Z" ));
      for ( string x: word_list )
        w_table[ x ] += 1;
    }
    f_stream.close();
  }
  cout << "Number of unique words: " << w_table.size() << endl;
  cout << "Most common words:" << endl;
  vector<word_and_count>  pair_vec;
  for ( auto x: w_table )
    pair_vec.push_back( x );
  sort( pair_vec.begin(), pair_vec.end(), compare_pair  );
  word_and_count pr;
  for ( int i = 0; i<20; i++ )
  { pr = pair_vec[i];
    cout << pr.first << " " << pr.second << endl;
  }
  return 0;
}
// Number of unique words: 8911
// Most common words:
// the 2200
// of 1406
// a 1118
// to 1011
// and 975
// in 740
// is 581
// s 510
// Act 484
// Sc 483
// that 454
// The 403
// I 369
// Line 345
// not 333
// his 323
// with 306
// And 303
// be 277
// i 268

If it's C++ and doesn't use regular expressions, is it really relevant here?

Hi,

Actually it's not just hash tables, but tables in general. We have basically two options:
1. Arrays
2. Objects (like TCollection, etc.)

Objects are overkill to me for a lot of things where I want a more raw datatype, and Arrays (Even dynamic ones) are a bit *too* raw. So usually you can repurpose an existing object to do what you want, or write your own, or... add logic to do what you want with arrays.

I think adding native support for table type processing would be a major addition and a lot of people would say it's not Pascal-like. So we have lots of libraries to choose from - which is good, but we always have to take the time to look, evaluate and choose.

Although Pascal is my favorite language, dealing with "internal tables" (with or w/o hashing) is so much easier in ABAP. Still, ABAP does a few things really well, and is a pain for everything else. Pascal, on the other hand, does most things well.

Thank you,
Noah Silva

2013/3/22 S. Fisher

Hi,

I had an entire class on using Regular Expressions (in Java). They actually only look scary or hard to read until you get used to them. Debugging them can be difficult sometimes though. If you search, there are some web pages available that let you check them online in real time. Even though I am fairly expert with them in Java, I don't use them much in Pascal, though.

Thank you,
Noah Silva

2013/3/23 S. Fisher