assoc-heap


Vocabulary
assoc-heaps

Word description
A data structure containing an assoc and a heap to get certain properties with better time constraints at the expense of more space and complexity. For instance, a hashtable and a heap can be combined into one assoc-heap to get a sorted data structure with O(1) lookup. Operations on assoc-heap may update both the assoc and the heap or leave them out of sync if it's advantageous.

Definition
IN: assoc-heaps

TUPLE: assoc-heap assoc heap ;


Methods
USING: accessors assoc-heaps heaps ;

M: assoc-heap heap-empty? heap>> heap-empty? ;


USING: accessors assoc-heaps heaps ;

M: assoc-heap heap-peek heap>> heap-peek ;


USING: accessors assoc-heaps heaps ;

M: assoc-heap heap-pop heap>> heap-pop ;


USING: accessors assoc-heaps assocs heaps kernel ;

M: assoc-heap heap-push*
pick over assoc>> key?
[ 3drop f ]
[ [ assoc>> swapd set-at ] [ heap>> heap-push* ] 3bi ] if ;