VIRTUAL COMPOSITIONS

1 . A computer-implemented method comprising:

receiving a request to compute a virtual disjunction over three or more tiered arrays;

repeatedly comparing respective ranges of contiguously set indexes in the arrays until the end of all of the arrays is reached, including:

determining a smallest start index n0 among current ranges of the arrays, wherein the smallest start index n0 is the first set index in a range [n0,n1],

determining whether any of other arrays have overlapping ranges that extend the range [n0,n1] in the virtual conjunction,

updating n1 for each other array having an overlapping range that extends the current range,

outputting the range [n0,n1] the updated value for n1, and

determining a next range starting at or after n1+2 for each of the arrays.

2 . The method of claim 1 , further comprising:

determining that the end of a first array of the three or more arrays has been reached; and

in response, removing the first array from the computation of the virtual disjunction.

3 . A computer-implemented method comprising:

receiving a request to compute a virtual conjunction over three or more tiered arrays;

repeatedly comparing respective ranges of contiguously set indexes in the arrays until the end of one of the arrays is reached, including:

determining a smallest start index n0 among current ranges of the arrays, wherein the smallest start index n0 is the first set index in a range [n0,n1],

determining whether any of other arrays have non-overlapping ranges that reduce the range [n0,n1] in the virtual conjunction,

updating n0 and n1 for each other array having a non-overlapping range,

outputting the range [n0,n1] if not empty using the updated values for n0 and n1, and

determining a next range starting at or after n1+2 for each of the arrays.

4 . A computer-implemented method comprising:

receiving a request to compute a virtual conjunction between two tiered arrays A and B;

repeatedly comparing pairs of ranges of contiguous indexes by updating a next range of contiguous indexes from A or B, including:

for each pair of ranges [a0,a1] and [b0,b1], wherein [a0,a1] is a range of the pair of ranges having a smaller or equal first value:

whenever a1>=b0 and b1<=a1, outputting [b0,b1] and identifying the next pair of ranges as [a0,a1] and a next contiguous range from B starting at or after b1+2,

whenever a1>=b0 and b1>a1, outputting [b0,a1] and identifying the next pair of ranges as [b0,b1] and a next contiguous range from A starting at or after a1+2.

5 . The method of claim 4 , wherein whenever a1<b0, identifying the next pair of ranges as [b0,b1] and a next contiguous range from A starting at or after a1+2.

6 . A computer-implemented method comprising:

receiving a request to compute a virtual disjunction between two tiered arrays A and B;

repeatedly comparing pairs of ranges of contiguous indexes by updating a next range of contiguous indexes from A or B, including:

for each pair of ranges [a0,a1] and [b0,b1], wherein [a0,a1] is a range of the pair of ranges having a smaller (or equal) first value:

set a0 as start of next range,

whenever b0>a1+1, outputting [a0, a1] and identifying the next pair of ranges as [b0,b1] and a next contiguous range from A starting at or after after a1+2.

7 . The method of claim 6 , wherein whenever b0<=a1+1, outputting [a0,b1] and identifying the next pair of ranges as [b0,b1] and the next contiguous range from A after b1+2 .

8 . The method of claim 6 , wherein whenever b0>a1+1 and b1<=a1, identifying the next pair of ranges as [a0,a1] and a next contiguous range from B after a1+2.

9 . A computer-implemented method comprising:

receiving a request to compute a nested virtual composition between a first tiered array and a second tiered array, wherein the nested virtual composition specifies a first virtual composition between the first tiered array and an inverse of the second tiered array; and

computing the nested virtual composition including repeatedly comparing ranges of contiguously set indexes in the first tiered array with ranges of contiguously set indexes generated by computing the inverse of the second tiered array.

10 . The method of claim 9 , wherein computing the nested virtual composition comprises computing the nested virtual composition without generating an array representing the result of the inverse of the second array.

11 . The method of claim 9 , wherein computing the nested virtual composition comprises computing the nested virtual composition without generating an array representing the nested virtual composition.

12 . The method of claim 9 , wherein each tiered array has a plurality of tiers, wherein each non-default element of each tier is a reference to a catalog at a lower tier except for a bottom-most tier of the tiered array that stores non-default values, wherein the request specifies a start index.

13 . The method of claim 9 , wherein the nested virtual composition is “A and not B.”

14 . The method of claim 9 , wherein the nested virtual composition is “B or not A.”

15 . A computer-implemented method comprising:

receiving a request to compute a nested virtual composition between at least three tiered arrays, wherein the nested virtual composition specifies a first virtual composition between two of the tiered arrays and a second virtual composition between a third tiered array and the first virtual composition; and

computing the nested virtual composition including repeatedly comparing ranges of contiguously set indexes in the third tiered array with ranges of contiguously set indexes generated by computing the second virtual composition.

16 . The method of claim 15 , wherein computing the nested virtual composition comprises computing the nested virtual composition without generating an array representing the result of the second virtual composition.

17 . The method of claim 15 , wherein computing the nested virtual composition comprises computing the nested virtual composition without generating an array representing the nested virtual composition.

18 . The method of claims 15 , wherein each tiered array has a plurality of tiers, wherein each non-default element of each tier is a reference to a catalog at a lower tier except for a bottom-most tier of the tiered array that stores non-default values, wherein the request specifies a start index.

19 . A computer-implemented method comprising:

receiving a request to determine whether two tiered arrays have any non-default indexes in common;

determining whether respective top-level catalogs have any non-default values in common;

comparing a first pair of mid-level catalogs that were both referenced by respective top-level catalogs to determine whether the first pair has any non-default values in common;

comparing each pair of bottom-level catalogs that were both referenced by the first pair of mid-level catalogs to determine whether the pair of bottom-level catalogs have any non-default values in common; and

upon determining that at least one pair of bottom-level catalogs has at least one non-default index in common, providing an indication that the arrays share at least one non-default index.

20 . The method of claim 19 , wherein providing the indication comprises bypassing all other comparisons between catalogs having non-default values.

21 . The method of claim 19 , wherein each tiered array has a plurality of tiers, wherein each non-default element of each tier is a reference to a catalog at a lower tier except for a bottom-most tier of the tiered array that stores non-default values.

22 . A computer-implemented method comprising:

receiving a request to determine whether two tiered arrays have any non-default indexes in common, wherein each tiered array has a plurality of tiers, wherein each non-default element of each tier is a reference to a catalog at a lower tier except for a bottom-most tier of the tiered array that stores non-default values;

determining that respective top-level catalogs of the tiered arrays do not have any non-default values in common; and

in response, providing an indication that the tiered arrays do not have any non-default indexes in common.

23 . The method of claim 22 , wherein providing the indication comprises bypassing all other comparisons between catalogs having non-default values.

24 . A computer-implemented method comprising:

receiving a request to count indexes having non-default values in a virtual bitwise composition corresponding to an operation between two tiered arrays;

receiving a plurality of ranges of indexes corresponding to the virtual bitwise composition; and

computing a sum of the plurality of ranges of indexes as the count of non-default values in the virtual bitwise composition.

25 . The method of claim 24 , wherein computing the sum comprising computing the sum without constructing a tiered array that represents the virtual bitwise composition.

26 . A computer-implemented method comprising:

receiving a request to count indexes within a given range of indexes represented by a tiered array;

computing a sum of counts of indexes with which a non-default value is associated over catalogues fully contained within the given range by means of metadata including for each catalogue, this count

adding to the sum, a range-based count of indices with which a non-default value is associated, in the portions of the given range at its start and end that partially overlap the range of indices represented by the containing catalogue.

27 . A computer-implemented method comprising:

receiving a request to find the ith index having a non-default value in a virtual composition comprising a plurality of ranges of contiguously set indexes having non-default values;

initializing a range [a,b], wherein a is a minimum index and b is a maximum index;

repeatedly bisecting the range until the total count in the bisected range is 1, including:

computing a total count of indexes between a and b,

computing c as a midpoint between a and b,

computing a count of indexes m between a and c,

if m>=i, setting the bisected range [a,b] to be a range from c+1 to b, subtracting m from the total count, and subtracting m from i, and

if m<i, setting the bisected range [a,b] to be a range from a to c, and setting the total count as m; and

providing the index a in response to the request when the total count is 1.

28 . The method of claim 27 , wherein the virtual composition represents dependencies between two software elements in a project.

29 . The method of claim 27 , wherein the request is a request to display the ith dependency between two software elements in a project.

30 . The method of claim 27 , wherein the virtual composition represents a logical operation between two tiered arrays, each tiered array having a plurality of tiers, wherein each non-default element of each tier is a reference to a catalog at a lower tier except for a bottom-most tier of the tiered array that stores non-default values.

31 . A computer-implemented method comprising:

receiving a request to find the ith index having a non-default value in a tiered array, wherein the tiered array has a plurality of tiers, wherein each non-default element of each tier is a reference to a catalog at a lower tier except for a bottom-most tier of the tiered array that stores non-default values;

obtaining auxiliary data for the tiered array that includes a minimum set index and a maximum set index and for each catalog, a count of set indexes within the catalog;

initializing a range [a,b], wherein a is the minimum set index and b is the maximum set index;

repeatedly bisecting the range until the range fits within a single catalog, including:

computing a total count of indexes between a and b using the counts of set indexes within each catalog,

computing c as a midpoint between a and b,

computing a count of indexes m between a and c using the counts of set indexes within each catalog,

if m>=i, setting the bisected range [a,b] to be a range from c+1 to b, subtracting m from the total count, and subtracting m from i, and

if m<i, setting the bisected range [a,b] to be a range from a to c, and setting the total count as m; and

when the range [a,b] fits within a single catalog, performing a linear search within the catalog to find ith index of the tiered array; and

providing the ith index in response to the request.

32 . The method of claim 31 , wherein the request is a request to display the ith dependency between two software elements in a project.