I work with graphs quite a lot and it is natural to use Tables to hold nodes. The key is the ID and the node may be an object that at minimum holds the indexes of its parents / children. For topologically sorted directed acyclical graphs (DAGs) I find myself using OrderedTable quite a lot and here I find myself missing features that Seq has, but that haven't been added to OrderedTable. On more than one occasion I have wanted access by index, pop() or reverse(). For example right now I want to do a consuming breath first search on a DAG and add nodes under certain conditions, so naturally I would want to do something like:
var candidates: OrderedTable[int, node] = nodes
while candidates.len > 0:
let candidate = candidates.pop()
do_some_work(node)
if ...:
candidates.add(node(...))
Anyway is this planned? Or am I missing some good reason why these methods aren't supported?
proc find[A, B](self: OrderedTable[A, B], item: B): tuple[found: bool, key: A] =
for (k, v) in self.pairs():
if item == v:
return (true, k)
proc reversed[T: OrderedTable](self: T): T =
let keys = self.keys().toSeq()
for k in reversed(keys):
result[k] = self[k]A table, the general programming, doesn't have a concept of indexes so accessing by index doesn't make so much sense.
I'm not sure if you want to find by key or value. For key you can use in. For value you can use @sls1005's answer.
It seems your ids are sequential, so you could use a seq. Tables are useful for quick access of the value based on the key, but your indexes are sequential integers, a seq would be much faster.
Instead of indexes of parents and children, you can use references to them with the ref keyword.
For breadth first each I would definitely use a seq because you don't need to randomly access them, you just need the "top" of the stack
@sls1005 I know, I use sort to topologically sort and actually also to reverse Tables. Pop does not remove the first key/value in a ordered table, so not exactly the use case I desire.
@ynfle No, indexing makes sense for anything ordered. Obviously you can reasonably talk about for example the first entry in any ordered object, regardless if it is table or something else.
As for using a seq of ref, you are assuming the keys are int AND they are sequential. Therefore your suggestion won't work most of the time.
Also explaining things everyone knows like the in operator and seq being fast seems to suggest you think I have no idea what I am doing. This is not the case.
And finally, as I said I work with graphs quite a lot and your last sentence includes unreasonable assumptions, but I wont get into details as I don't want to discuss it.
I'm pretty sure they're suggesting (and that's what I'd suggest too) that you do something like this:
type
Node[T] = ref object
payload: T
parents: seq[T]
children: seq[T]
var graph: seq[Node]
Then you don't need any kind of table.
For unordered things, std/sets.HashSet has an unkeyed pop which I use in suggest, but OrderedSet does not. So, these may not be good answers.
If order and key sparsity and out-of-the-box table-like operation is truly needed, my generally more full-featured adix/lptabz also has an unkeyed (aka iteration order) pop, and a compact-ordered mode like Python since 3.6 (but a bit more efficient). The ordered mode is insert-order not key-order and I pop/delete the fast way (by swapping with the end of the array) the way Nim's del works (not its`delete`). So, once you start popping the order starts getting permuted. This may or may not matter to you. If it does not, this is an answer.
There is actually a key-ordered table-like thing in adix/btree that has a bare minimum of functionality, but could be more optimized for special key types like strings. That can maintain any order at all, but is slower than a hash-based approach due to indirections/more work. There are other btree libs around, too, (including one in compiler/) but I don't think any others even support bulk loading never mind rank-based access.
If none of this is quite right, there is very little special about libraries in Nim vs just doing your own module compared to many prog langs. The right analogy is much more C++ template libraries than Python libs. So, you can probably also do your own minimal table in a couple hundred lines of code that will be as efficient (or more since you are tuning it to your specific needs) and mostly drop-in compatible. compactdict may be the closest starting point to your needs if you are new to Nim and wanted to start with simple-ish code and you know what you are doing. It's been >3 years since its last update, but its test suite seems to still work.
Sorry for the length, but hopefully something here will help you or some future you-like entity. I'm bullish about the 2nd & 4th paragraphs. :-)