Delphi Programming

and software in general.

Tuesday, November 8, 2011

Compile time ordered vectors

I would like to have support for ordering content of a constant array at compile time.

I would like to have optimized lookup function for such an ordered constant array (binary search, hash index, etc, - whatever fits the purpose) to check if a variable has a match in the ordered constant array. The code generator could inline the lookup function if so was desired.

I guess you can say that I am looking for something like the "in" keyword for sets, but extended to work with any constant array (string, array of enumerable, array of number, or array of other constants such as class type references).

A specification syntax could look something like:
  <arraytype> = {ordered {ascending | descending}} Vector<T>

Implicit methods associated with the type:
  Vector<T>.Contains(const element: T):Boolean;
  Vector<T>.ContainsAny(const array of T):Boolean;
  Vector<T>.ContainsAll(const array of T):Boolean;
  Vector<T>.Include(const element: T);
  Vector<T>.Exclude(const element: T);

Example declaration:
type
  TMyType = ordered ascending Vector<Char>;
const
  InvalidChars : TMyType = ['\', ':', '.', '(', ')']; // I don't want to worry about order here


Example of use:
  if InvalidChars.Contains(SomeCharacter) then ...

Today, I can create singleton objects that are ordered as part of the initialization code, but it becomes a lot of micro management code which isn't optimized for call performance, instead of easy to use code like "element in set" style code.

4 comments:

  1. Your syntax is for sorting, but your use cases are all about set operations. Set operations do not require sorting - sets do require some manner of precomputing, but not display sequence ordering. Its best not to impose an implementation on the interface.

    If you want presorted data, change your use case to show why this would be useful and how you would deal with locale and localization issues.

    If you want set operations on arrays or vectors, lose the "ordered" syntax and just extend the existing "set of" syntax.

    ReplyDelete
  2. Aye, it is a poor example. I'll provide a better one.

    This actually was an old draft post, and it appear to me that I haven't quite completed my train of thought here. My need at the time was related to creating jump tables for handling data streams, partly statically defined at compile time, but revised at run time.

    ReplyDelete
  3. Dynamic jump tables: still a set, not a sort. ;)

    ReplyDelete
  4. Hmm - you've got a point... I'll think a little about it and try from a different angle.

    ReplyDelete