forked from kanwei/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 1
/
History.txt
176 lines (107 loc) · 3.87 KB
/
History.txt
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
=== Jan 3, 2009
* Levenshtein distance in C
=== April 3, 2009
* Finished C refactorization of SplayTree
=== March 28, 2009
* Implemented SplayTree in C
* Made recursively_free_nodes methods static to fix a SEGFAULT
* Improved CBst
* Moved to Markdown for README
* 0.2.0 release
=== January 19, 2009
* kd-tree for points in multi-dimensional space
=== November 25, 2008
* Checked in gnufied's C BST
=== November 13, 2008
* Removed #each for Hash and Priority Queue (Feature)
=== September 15, 2008
* Added comb sort
* Benchmark work on sorting algorithms
=== September 1, 2008
* Switched to Hanna rdoc template
* RBTree#isred now private
=== August 20, 2008
* Implemented Knuth-Morris-Pratt substring algorithm
=== August 15, 2008
* Updated README to reflect progress
=== August 10, 2008
* Implemented mergesort, insertion_sort, shell_sort, quicksort
=== August 8, 2008
* Implemented bubble_sort, selection_sort, heapsort
=== August 5, 2008
* Started Algorithms portion
* Implemented Search#binary_search
=== July 20, 2008
* Iterate over trees iteratively instead of recursively
* Implemented Deque in C
=== July 15, 2008
* Refactored namespaces, thank you Austin Ziegler!
=== July 14, 2008
* Use alias_method instead of alias
* Found and fixed RBTree#delete bug (finally!)
* Refactored Trie, SuffixArray, SplayTreeMap
=== July 13, 2008
* Refactored Deque
* Implemented Deque#reverse_each (like Array's)
=== July 12, 2008
* Reformatted some specs to be more idiomatic (Thank you Federico Builes)
=== July 10, 2008
* Added algorithm complexity information for all Containers
* Implemented Trie for string representation
* Implmented SuffixArray for fast substring search
* Fixed memory leak in CRBTree
* Updated Manifest and algorithms.rb to match progress
=== July 9, 2008
* Implemented Deque
* Stack and Queue now use Deque
* Fixed issues with CRBTree's #empty? and delete methods
=== July 8, 2008
* Can now iterate over a heap
* Renamed #contains_key -> has_key? since it's more idiomatic
* Implented #change_key and #delete for Heap
* Priority Queue is now implemented with the new Fibonacci Heap
* Removed old Priority Queue code as a result
* Heap: fixed #delete bug not checking if item exists, #has_key? bug
for not returning boolean
* Heap: value field is now optional and defaults to the key if not specified
* More refactoring of RBTreeMap (both Ruby and C)
=== July 7, 2008
* Heap is now implemented with a Fibonacci Heap, not a binomial heap
=== July 4, 2008
* Implemented SplayTreeMap
* Heap now uses kind_of? to check for other heaps when doing #merge
* Renamed some Heap methods for consistency with the rest of the library
* RBTreeMap#contains? -> contains_key?
* Refactored RBTreeMap to be more object-oriented
* More documentation for RBTreeMap
=== July 3, 2008
* Added documentation for Stack and Queue
=== June 24, 2008
* Imported Brian Amberg's priority queue implementation
* Now uses Echoe to build gem
* Gem builds for the first time
=== June 18, 2008
* Can now enumerate over RBTreeMap
=== June 17, 2008
* RBTreemap#delete now returns deleted value
* Added delete method to C implementation
=== June 16, 2008
* Implemented delete methods for RBTreeMap
=== June 14, 2008
* Renamed the data structures module to "Containers"
* Removed dependence on stdbool.h
* Renamed RBTree to RBTreeMap
=== June 13, 2008
* Implemented Sedgewick's Left Leaning Red Black Tree in C!
=== June 12, 2008
* Implemented Sedgewick's Left Leaning Red Black Tree
=== June 10, 2008
* Implemented merge! for other heaps and heap initialization from an array
* Implemented Queue
=== June 9, 2008
* Finished binomial heap implementation
=== June 8, 2008
* Added Stack
* Working on heap
=== April 20
* Accepted to Google Summer of Code!