CPAchecker implements a PersistentStack based on the PathCopyingPersistentTreeMap. This should be moved into this repository, as others can benefit from it. But since a stack (and a queue) are just special views on a deque, we can just implement a PersistentDeque and get a queue and stack out of the deque, increasing our set of persistent data-structures in a thought out way.
The PersistentDeque can be based on the PathCopyingPersistentTreeMap, like in CPAchecker, or may be based on other starting points, for example the PersistentLinkedList, to optimize the implementation.
Much more optimal solution(s) can be found for example in Implementing Persistent O(1) Stacks and Queues in R by Shawn T. O'Neil. Looking at the R code, we could try to translate the concept to Java with our PersistentLinkedList rather quickly i think.
CPAchecker implements a
PersistentStackbased on thePathCopyingPersistentTreeMap. This should be moved into this repository, as others can benefit from it. But since a stack (and a queue) are just special views on a deque, we can just implement aPersistentDequeand get a queue and stack out of the deque, increasing our set of persistent data-structures in a thought out way.The
PersistentDequecan be based on thePathCopyingPersistentTreeMap, like in CPAchecker, or may be based on other starting points, for example thePersistentLinkedList, to optimize the implementation.Much more optimal solution(s) can be found for example in Implementing Persistent O(1) Stacks and Queues in R by Shawn T. O'Neil. Looking at the R code, we could try to translate the concept to Java with our
PersistentLinkedListrather quickly i think.