Module CondenseList

A module to take orderable data (which may not be continuous) and condense it into one or more dense lists, with one such list per specified division.

To instantiate this module, you need to provide at least one predicate that specifies the sparse index of a given item. Items can be segmented into separate lists via another predicate which specifies the division of each item.

The sparse index (which may have gaps) is used to determine the ordering of the items in the condensed list. Once the condensed list is created, the items in the list will automatically be assigned a dense index (which has no gaps).

For instance, to create a condensed list of variables defined in every file, create predicates that specify the line number of the variable as the sparse index, and the file of the variable as the division:

  int getLineNumber(File file) { result = file.getLocation().getStartLine() }
  File getFile(Variable var) { result = var.getLocation().getFile() }

  class Entry = Condense<Variable, getLineNumber/1>::GroupBy<File, getFile/1>::ListEntry;

  from Entry entry
  select entry, entry.getDivision(), entry.getItem(), entry.getDenseIndex(), entry.getNext(),
      entry.getPrev()

To get a list of all items without a division, use the class CondenseList<...>::Global::ListEntry.

This module will produce incorrect results if the sparse index contains duplicates for the selected division.