Javascript – Best Data structure for implementation of dependent drop-downs

data structuresjavascripttrie

I want to implement dependent drop-down feature on a web page in my website containing the following drop-downs:

User's group name
Group events (dependent drop-down)
Locations (dependent drop-down)

Now, what I want is according to the selected option in the first drop-down that is group name (the other two will be disabled until it is selected), the list of events is displayed; only those values relevant to the selected group name should occur. Similarly, the values of locations should be in relevance to the group name and the event selected. Not only this, but I also want the design to be irrelevant of the level of dependencies or the current order (group name->events->locations). Even if I wish to add timings as another level of dependency, the design should incorporate it.

Now, in all the related questions to this problem tables are used to store data in databases like:

However, I wish to consider the following alternatives:

Trie: Since the order in which the attributes are selected is
defined, we could use a trie to store all possible combinations of
the list of values in each drop-down dependent on each other. Using
prefix search, we could retrieve the values of the next drop-down,
according to value selected in the previous one.
Table: similar to one used in above, we can store it in database but
then the number of levels of dependencies are not really fixed and
can increase in future. How do I handle that? (Assuming I don't want
to modify the schema every time this happens)
Graph: We could also store the possible combinations in a directed
graph and based on the values selected we can display all the next
adjacent nodes int he next dependent drop-down.

Which of these is a best approach, keeping in mind future extensibility or changes? Or any other suggestions for data structures are also welcomed. Please explain with proper design in detail considering complexity in mind.

Best Answer

You're almost certainly overthinking this. Your quest for an ideal data structure is a solution in search of a problem.

Look carefully at the example you gave. All three of those dropdowns have a different data source, and they imply a relational structure. Just by looking at the names of your dropdowns, I know that you have three tables: Groups, Events and Locations, each having primary keys and foreign keys that associate the tables with each other.

Three tables in a relational database is the ideal data structure for your scenario.

If you need a data representation that can be used in a web page, create a ViewModel object, but in non-trivial applications, it's often necessary to AJAX in the list for a particular dropdown, based on the selection provided by the user in the previous dropdown. The lists can be too large to embed in the actual web page.

Related Solutions

Design – How do we keep dependent data structures up to date

I think your scenarios are discussing variations on the Observer Pattern. Each original node (“subject”) has (at least) the following two methods:

registerObserver(observer) – adds a dependent node to the list of observers.
notifyObservers() – calls x.notify(this) on each observer

And each dependent node (“observer”) has a notify(original) method. Comparing your scenarios:

The notify method immediately rebuilds a dependent subtree.
The notify method sets a flag, the recomputation happens after each set of updates.
The notifyObservers method is smart and only notifies those observers whose constraints are invalidated. This would probably use the Visitor Pattern, so that the dependent nodes can offer a method that decides this.
(this pattern has no relation to brute-force rebuilding)

As the first three ideas are just variations on the observer pattern, their design will have similar complexity (as it happens, they are actually ordered in increasing complexity – I'd think №1 is the most simple to implement).

I can think of one enhancement: building the dependent trees lazily. Each dependent node would then have a boolean flag that is either set to valid or invalid. Each accessor method would check this flag and, if necessary, recalculate the subtree. The difference to №2 is that recalculation happens on access, not upon change. This would probably result in fewest computations, but can lead to significant difficulties if the type of a node would have to change upon access.

I would also like to challenge the need for multiple dependent trees. For example, I always structure my parsers in a way that they immediately emit an AST. Information that is only relevant during construction of this tree doesn't have to be stored in any permanent data structure. Likewise, you can also choose your objects in such a way that the AST has an interpretation as a control flow graph.

For a real-life example, the compiler part inside the perl interpreter does this: The AST is built bottom-up, during which some nodes are constant-folded away. In a second run, the nodes are connected in execution order, during which some nodes are skipped by optimizations. The result is very fast parsing (and few allocations), but very limited optimizations. It should be noted that while such a design is possible, it is probably not something you should strive for: It is a ~~calculated trade-off~~ complete violation of the Single-Responsibility Principle.

If you do actually need multiple trees, then you should also consider whether they really have to be built simultaneously. In the majority of cases, a parse tree is constant after the parse. Likewise, an AST will probably stay constant after macros are resolved and AST-level optimizations have been executed.

Designing online exam

A database table for your questions might look like this:

QuestionID          PK
Question            Text
Difficulty          Int

Keep track of the questions already asked and answered in another table:

StudentID           FK
TestID              FK
QuestionID          FK
AnswerID            FK  (assumes multiple choice)

Possible answers to questions (multiple choice):

AnswerID            PK
QuestionID          FK
Answer              Text
IsTheCorrectAnswer  boolean

Best Answer

Related Solutions

Design – How do we keep dependent data structures up to date

Designing online exam

Related Topic