Typescript Generics and the Typescript Math Toolkit Priority Queue

My spare time development is currently focused on the Typescript Math Toolkit data structures library.  The goal of this development is to provide a library suitable for various algorithms in the toolkit as well as supporting demos.  As of this post, the Linked List is already on Github and I just finished the Priority Queue.

I enjoyed having access to Templates in C++ (now called Generics in C# and Typescript).  The availability of Generics in Typescript allows the creation of a single class that accommodates multiple data types.  The specific implementation of the Priority Queue also illustrates some more advanced features of Typescript, so I thought it would be worthy of a more detailed blog post.

The TSMT Priority Queue is based on my past usage of a priority queue over the years.  It consists of an array of prioritizable items, each of which has three properties, a priority, a timestamp, and a data reference.  If we allow the data to be of arbitrary type, the contract may be specified in a simple interface.

export interface IPrioritizable<T>
{
  priority: Number;     // priority, integer>= 0
  timestamp: Number;    // optional timestamp, expected to be an integer >= 0
  data: T;              // arbitrary, but constructable data type such as Object or a Class
}

A prioritizable item implements this interface. In my past usage, data associated with the prioritizable item was an Object or class, such as

class PItem 
{
  protected _name: string  = "name";
  protected _id: number    = 0;
  protected _value: number = 0;

  constructor() {}

  // accessors/mutators removed to save space

  public computeValue(someData: Object): void
  {
    // compute value from supplied data
  }
}

I would construct the data along with the item and set the data reference in the prioritizable item. A discussion with a couple of developers interested in using this Priority Queue yielded a different use case. They wanted the option of constructing the data type when the prioritizable item was constructed. They would access and set the data at a later point in the application.

While not the way I would approach the problem, it was a use case I wanted to at least try to support in the alpha release. This led to the following implementation of the Prioritizable class.

export class Prioritizable<T> implements IPrioritizable<T>
{
  protected _priority: number;
  protected _timestamp: number;
  
  protected _data: T;

/**
 * Construct a new Prioritizable item
 * 
 * @param TConstructor : { new (): T }  (optional) Reference to a constructable object
 * 
 * @return Nothing Constructs the supplied data type (if provided) and sets the internal data reference.  Priority and timestamp are initialized to zero.
 */
  constructor( TConstructor?: { new (): T } )
  {
    this._priority  = 0;
    this._timestamp = 0;

    // pre-construct the data type?
    if (TConstructor)
      this._data = new TConstructor();
  }

/**
 * Access the priority
 * 
 * @return number Current priority value
 */
  public get priority(): number
  {
    return this._priority;
  }

/**
 * Assign the priority
 * 
 * @param value: number Priority value (must be greater than or equal to zero) - expected to be integer, but this is not currently enforced
 * 
 * @return Nothing Assigns the priority if the input is a valid number
 */
  public set priority(value: number)
  {
    if (!isNaN(value) && value === value && value >= 0)
      this._priority = value;
  }

/**
 * Access the timestamp value
 * 
 * @return number Current timestamp value
 */
  public get timestamp(): number
  {
    return this._timestamp;
  }

/**
 * Assign the timestamp value
 * 
 * @param value: number Timestamp value (must be greater than or equal to zero) - expected to be integer, but this is not currently enforced
 * 
 * @return Nothing Assigns the timestamp if the input is a valid number
 */
  public set timestamp(value: number)
  {
    if (!isNaN(value) && value === value && value >= 0)
      this._timestamp = value;
  }

/**
 * Access the data item
 * 
 * @return T Direct reference to the data item; the data is not currently required to be cloneable, so a direct reference is provided.  Use this method with caution.
 */
  public get data(): T
  {
    return this._data;
  }

/**
 * Assign the data item
 * 
 * @param value: T Reference to a data value of type T
 * 
 * @return Nothing Directly assigns the supplied reference to the internal data value.  Use caution to not make further modifications to the supplied value.
 */
  public set data(value: T)
  {
    if (value)
      this._data = value;
  }
}

The constructor is rather unusual and requires an optional constructable object to be passed. For example,

let __pObject: Prioritizable<Object> = new Prioritizable<Object>(Object);

(creates new prioritizable item with Object data, constructs a new Object, and sets the internal data reference)

let __pObject: Prioritizable<Object> = new Prioritizable<Object>();

(creates new prioritizable item with Object data; internal data reference is null and must be set later using mutator)

This implementation allows both use cases to be implemented, but is currently experimental.

Suppose a class, PItem, is available that represents the data to be associated with a prioritizable item. My preferred use case to add items to the queue is:

let queue: TSMT$PriorityQueue<PItem> = new TSMT$PriorityQueue<PItem>();
let item1: Prioritizable<PItem>      = new Prioritizable<PItem>();
let pItem1: PItem                    = new PItem();

item1.priority  = 1;
item1.timestamp = 1001;
item1.data      = pItem1;

.
.
.

queue.addItem(item1);

The TSMT Priority Queue uses priority as a default, primary sort key. A timestamp value (typically another integer greater than or equal to zero) may be used as a secondary key. A type alias is defined with the priority queue,

 export type SortType = 'priority' | 'timestamp';

Sort criteria are specified by a mutator that accepts an array of SortType values. A type guard is also used to ensure validity of each individual item in the mutator. A type guard is a runtime check to ensure validity of a passed type since there is no runtime checking after export to JS. The syntax uses a return type that is a predicate, which evaluates to a boolean, as shown in this internal method,

 protected __isSortType(value: string, acceptable: Array): value is SortType

Usage is illustrated in the setCriteria mutator

valid = valid && this.__isSortType(criteria[i], values);

The TSMT Priority Queue supports addition and removal of items, removal of the first/last item in the queue, and clearing of the queue. By default, a sort is performed on each addition to the queue. The sort may be delayed by use of the delay mutator. Lazy validation is used in the class, so sorting may be delayed until calling a method that requires the queue to be in sorted order.

A generous set of specs is provided with the source distribution on Github and this is probably the best way to become familiar with using the priority queue. Even if you do not directly use the code, I hope you can borrow some of the Tyepscript techniques used in its development.

Enjoy!

 

Comments are closed.