Sounds like this solution would best be implemented with an undo-tree, but also a linear history mapping with pointers to that tree - the linear history would just log movement within the tree over time e.g. undo-redo would just be a backwards-forwards movement.
That's exactly what you get with undo-tree. The regular undo/redo commands continue working as normal, but you can also manually browse the tree if things get too nonlinear for you.
