Standard Library Collections

Contents

..
array.dg
set.dg
stack.dg
intbintree.dg
linkedlist.dg
arraylist.dg

array.dg

Name Type Runtime Heap Used
array_reduce ([?T0] arr, uint size, ((?T0,?T0) ~> ?T0) reducer, ?T0 initial) -> ?T0 O(size * ?) -
array_contains ([?T0] arr, uint size, ?T0 elem) -> bool O(size) -

set.dg

Name Type Runtime Heap Use
set_ctor (?T0 sample) ~> Set<?T0> O(1) +O(1)
set_dtor (Set<?T0> s) -> bool O(1) -O(s.capacity)
set_size (Set<?T0> s) -> uint O(1) -
set_contains (Set<?T0> s, ?T0 x) -> bool O(s.size) -
set_insert (Set<?T0> s, ?T0 x) -> int O(s.size) +O(1)
set_remove (Set<?T0> s, ?T0 x) -> int O(s.size) -O(1)
set_union (Set<?T0> a, Set<?T0> b) -> Set<?T0> O(a.size^2 + b.size^2) +O(a.capacity + b.capacity)
set_cut (Set<?T0> a, Set<?T0> b) -> Set<?T0> O(max(a.size, b.size)^2) +O(min(a.capacity, b.capacity))

stack.dg

Name Type Runtime Heap Use
stack_ctor (uint capacity) ~> Stack<?T0> O(1) +O(1)
stack_dtor (Stack<?T0> s) ~> bool O(1) -O(capacity)
stack_size (Stack<?T0> s) -> uint64 O(1) -
stack_contains (Stack<?T0> s, ?T0 elem) -> bool O(size) -
stack_push (Stack<?T0> s, ?T0 x) -> int throws O(1) +O(1) amortized
stack_peek (Stack<?T0> s) -> ?T0 throws O(1) -
stack_pop (Stack<?T0> s) -> ?T0 throws O(1) -

intbintree.dg

Name Type Runtime Heap Use
intbintree_ctor () ~> IntBinTree O(1)+O(1)
intbintree_dtor (IntBinTree t) ~> bool O(size)-O(size)
intbintree_size(IntBinTree t) -> uint64O(size)-
intbintree_contains (IntBinTree t, int key) -> boolO(size) worst case-
intbintree_insert (IntBinTree t, int key) ~> int O(size) worst case+O(1)
intbintree_visit(IntBinTree t, ((int)->bool) visitor) -> boolO(size) worst case-

linkedlist.dg

Name Type Runtime Heap Use
linkedlist_ctor() ~> LinkedList<?T0>O(1)+O(1)
linkedlist_dtor(LinkedList<?T0> l) ~> boolO(size)-O(l.size)
linkedlist_size (LinkedList<?T0> l) -> uint64 O(1) -
linkedlist_contains(LinkedList<?T0> l, ?T0 value) -> boolO(size)-
linkedlist_push_front(LinkedList<?T0> l, ?T0 value) ~> boolO(1)+O(1)
linkedlist_push_back(LinkedList<?T0> l, ?T0 value) ~> boolO(1)+O(1)
linkedlist_pop_front(LinkedList<?T0> l) ~> ?T0 throwsO(1)-O(1)
linkedlist_pop_back(LinkedList<?T0> l) ~> ?T0 throwsO(1)-O(1)
linkedlist_index_of(LinkedList<?T0> l, ?T0 value) -> intO(size)-

arraylist.dg

Name Type Runtime Heap Use
arraylist_ctor () ~> ArrayList<?T0> O(1) +O(1)
arraylist_dtor (ArrayList<?T0> l) ~> bool O(1) -O(l.capacity)
arraylist_size (ArrayList<?T0> l) -> uint64 O(1) -
arraylist_contains (ArrayList<?T0> l, ?T0 value) -> bool O(size) -
arraylist_insert (ArrayList<?T0> l, ?T0 value) ~> bool O(1) amortized +O(1) amortized
arraylist_at (ArrayList<?T0> l, uint64 index) -> ?T0 O(1) -
arraylist_index_of (ArrayList<?T0> l, ?T0 value) -> int O(size) -
arraylist_clear (ArrayList<?T0> l) -> bool O(1) -