Method and computing device for maintaining dependencies among reference elements
The disclosure is generally directed to a method and computing device for maintaining dependencies among multiple reference elements (e.g., formulas of a table or spreadsheet). In various embodiments, prior to a reevaluation operation carried out on the reference elements, a computing device receives an input of a reference element via a user interface (e.g., receives a user's input of a formula), assigns the reference element to a group based on the dependency between the reference element and one or more other reference elements, and assigns the reference element to a location within a dependency graph to which the other reference elements are assigned. In response to an event that requires at least one of the reference elements to be reevaluated, the computing device reevaluates each group of reference elements in sequence a group at a time.
1. A method for maintaining dependencies among a plurality of formulas, each formula of the plurality of formulas being associated with a cell of a table that includes a plurality of cells, the method, performed by a computing processor, comprising:
prior to an event requiring recalculation of the table:
maintaining an interval-based dependency graph in a computer memory such that each node of the graph is associated with at least one of the plurality of cells and each node of the graph represents a range of cells of the table on which a formula of the at least one cell depends;
maintaining a range tree such that each node of the range tree is associated with the location of the cell within the table;
assigning each of the plurality of formulas to a group, such that no formula of any group is dependent upon any other formula of the group, and each formula is assigned to only one group;
receiving an input of a formula in the table;
analyzing the received formula to identify which of the plurality of cells the received formula depends upon;
searching the range tree to identify which of the depended-upon cells contain formulas;
recursively searching the dependency graph to identify which of the cells of the plurality of cells of the table depend, either directly or indirectly, upon the received formula;
based on the results of the range tree search and on the results of the recursive dependency graph search, assigning each cell of the plurality of cells to a group such that no cell of a group is dependent on another cell of a group, and each cell of the plurality is assigned to only one group;
in response to an event requiring the reevaluation of one or more of the formulas of the plurality, reevaluating the formulas sequentially by group according to the group to which their respective cells are assigned, such; and
displaying the result of the reevaluation on the table on a display device.
2. The method of claim 1 , wherein the dependency graph is one of a plurality of dependency graphs, each dependency graph of the plurality representing a dimension of the table.
3. The method of claim 1 , wherein reevaluating the formulas sequentially by group comprises reevaluating each formula of each group in a separate thread of execution in parallel with reevaluating at least one other formula of the group.
4. The method of claim 1 , further comprising:
repeatedly searching the dependency graph to identify other formulas of the plurality of formulas that depend either directly or indirectly on a given first formula of the plurality of formulas;
determining the criticality of the given first formula based on the total number of identified formulas; and
visually indicating the determined criticality of the given first formula on the display device.
5. A computing device comprising a computing processor, wherein the computing processor carries out a method for maintaining dependencies among a plurality of formulas, each formula of the plurality of formulas being associated with a cell of a table that includes a plurality of cells, the method comprising:
prior to an event requiring recalculation of the table;
maintaining an interval-based dependency graph in a computer memory such that each node of the graph is associated with at least one of the plurality of cells and each node of the graph represents a range of cells of the table on which a formula of the at least one cell depends;
maintaining a range tree such that each node of the range tree is associated with the location of the cell within the table;
assigning each of the plurality of formulas to a group, such that no formula of any group is dependent upon any other formula of the group, and each formula is assigned to only one group;
receiving an input of a formula in the table;
analyzing the received formula to identify which of the plurality of cells the received formula depends upon;
searching the range tree to identify which of the depended-upon cells contain formulas;
recursively searching the dependency graph to identify which of the cells of the plurality of cells of the table depend, either directly or indirectly, upon the received formula;
based on the results of the range tree search and on the results of the recursive dependency graph search, assigning each cell of the plurality of cells to a group such that no cell of a group is dependent on another cell of a group, and each cell of the plurality is assigned to only one group;
in response to an event requiring the reevaluation of one or more of the formulas of the plurality, reevaluating the formulas sequentially by group according to the group to which their respective cells are assigned, such; and
displaying the result of the reevaluation on the table on a display device.
6. The computing device of claim 5 , wherein the dependency graph is one of a plurality of dependency graphs, each dependency graph of the plurality representing a dimension of the table.
7. The computing device of claim 5 , wherein reevaluating the formulas sequentially by group comprises reevaluating each formula of each group in a separate thread of execution in parallel with reevaluating at least one other formula of the group.
8. The computing device of claim 5 , wherein the method further comprises:
repeatedly searching the dependency graph to identify other formulas of the plurality of formulas that depend either directly or indirectly on a given first formula of the plurality of formulas;
determining the criticality of the given first formula based on the total number of identified formulas; and
visually indicating the determined criticality of the given first formula on the display device.