Tree-like queues

Question

I'm implementing a interpreter-like project for which I need a strange little scheduling queue. Since I'd like to try and avoid wheel-reinvention I was hoping someone could give me references to a similar structure or existing work. I know I can simply instantiate multiple queues as I go along, I'm just looking for some perspective by other people who might have better ideas than me ;)

I envision that it might work something like this: The structure is a tree with a single root. You get a kind of "insert_iterator" to the root and then push elements onto it (e.g. a and b in the example below). However, at any point you can also split the iterator into multiple iterators, effectively creating branches. The branches cannot merge into a single queue again, but you can start popping elements from the front of the queue (again, using a kind of "visitor_iterator") until empty branches can be discarded (at your discretion).

            x -> y -> z
a -> b -> { g -> h -> i -> j }
            f -> b

Any ideas? Seems like a relatively simple structure to implement myself using a pool of queues but I'm following the "think first, code later" strategy :)

Thanks

EDIT: I thought I'd add some extra background info. It's not relevant for the problem, but I thought it might help to clarify my objectives a bit. Very roughly the idea behind this structure is that it is basically used to scheduling computations... A branch can end in either a COMMIT or a ROLLBACK. If any of x -> ..., g -> ... or f -> ... ends in a COMMIT, then

a -> b

is executed in sequence as well as the branch that ended in COMMIT. E.g.

x -> y -> z -> COMMIT

However, a -> b will only be executed once when at least one of the branches are committed. If all three of the branches end in ROLLBACK then the entire tree is discarded including the initial events a -> b.

Thanks for the great answers so far! I'll review them in detail as soon as I get home again.

Answer 1

The Boost Graph Library contains a data structure called a disjoint set which models the structure you need here (an interlinked group of sets).

Another way to think of this data structure is as a Forest. A forest is a disjoint union of trees.