-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathTODO
78 lines (65 loc) · 2.13 KB
/
TODO
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
Data Structures to Add
* Union-find
* Fibonacci heap
* Hash table
* Bloom filter
* Skip list
DArray
* darray_prepend: reserve extra capacity at the front of
the internal array to amortize the cost of prepending
elements.
* darray_slice: figure out the semantics of slices, and
then add this functionality back.
* Add iterators
* Add other functional programming-like operations (map, reduce, etc.)
SList
* Add sort
* Add merge
* Add concat
* Add iterators
* Add other functional programming-like operations (map, reduce, etc.)
DList
* Add merge
* Add concat
* Add other functional programming-like operations (map, reduce, etc.)
Binary Heap
* Add decrease/increase key
Priority Queue
* Add decrease/increase key
RBTree
* Maintain pointers to min and max nodes to make iterator begin and end
operations O(1)
String
* Add regular expressions
* Make API less clunky
* Add unit tests
Graph
* Keep a separate in-edge list for each node?
* Write unit tests
* Make GraphSearchCtx opaque?
* Maybe separate directed and undirected graphs into different types?
* Add algorithm for strongly connected components
* Change Prim and Dijkstra to use Fibonacci heaps
* Add Kruskal's and Boruvka's MST algorithms when union-find is done
* Investigate and add network flow algorithms (e.g., Ford-Fulkerson)
* Add Floyd-Warshall algorithm for all-pairs shortest path
* Add A* search
Error Handling
* Asserts: add build-time switch to turn asserts off. This
would have to then enable alternate logic that would
gracefully fail instead of blowing up the program.
Memory Management
* Add a slab allocator to enhance memory performance of
data structures
Build System
* Build-time configurations
- Debug
- Different backend implementations for
particular ADTs, e.g., array-based stack
instead of SList-based.
Documentation
* Add doxygen-enabled comments to all files
* Add doxygen step to the build process
Portability
* Test on 64-bit
* Test on Linux, OSX