From ed24f78c6123335531512145808ccf1d7e2cc649 Mon Sep 17 00:00:00 2001 From: ktanaka Date: Sat, 16 Apr 2016 16:43:55 +0900 Subject: [PATCH 1/3] fixed types, cpp program errors --- cpp/ArrayQueue.h | 1 - cpp/BinarySearchTree.h | 1 + cpp/BinaryTree.h | 2 +- cpp/SLList.h | 2 +- latex/arrays.tex | 2 +- latex/hashing.tex | 2 +- latex/intro.tex | 2 +- latex/redblack.tex | 4 ++-- 8 files changed, 8 insertions(+), 8 deletions(-) diff --git a/cpp/ArrayQueue.h b/cpp/ArrayQueue.h index 1cab5399..4cb1bd38 100644 --- a/cpp/ArrayQueue.h +++ b/cpp/ArrayQueue.h @@ -34,7 +34,6 @@ ArrayQueue::ArrayQueue() : a(1) { template ArrayQueue::~ArrayQueue() { - delete a; } template diff --git a/cpp/BinarySearchTree.h b/cpp/BinarySearchTree.h index 0e1c3ead..a1d98739 100644 --- a/cpp/BinarySearchTree.h +++ b/cpp/BinarySearchTree.h @@ -148,6 +148,7 @@ bool BinarySearchTree::addChild(Node *p, Node *u) { } else if (comp > 0) { p->right = u; } else { + delete u; return false; // u.x is already in the tree } u->parent = p; diff --git a/cpp/BinaryTree.h b/cpp/BinaryTree.h index 16b83208..8e80a8de 100644 --- a/cpp/BinaryTree.h +++ b/cpp/BinaryTree.h @@ -181,7 +181,7 @@ void BinaryTree::bfTraverse() { ArrayDeque q; if (r != nil) q.add(q.size(),r); while (q.size() > 0) { - Node *u = q.remove(q.size()-1); + Node *u = q.remove(0); if (u->left != nil) q.add(q.size(),u->left); if (u->right != nil) q.add(q.size(),u->right); } diff --git a/cpp/SLList.h b/cpp/SLList.h index 8aa6ffb5..f8d67ca2 100644 --- a/cpp/SLList.h +++ b/cpp/SLList.h @@ -21,7 +21,7 @@ class SLList { T x; Node *next; Node(T x0) { - x = 0; + x = x0; next = NULL; } }; diff --git a/latex/arrays.tex b/latex/arrays.tex index f9fc5729..059433dc 100644 --- a/latex/arrays.tex +++ b/latex/arrays.tex @@ -383,7 +383,7 @@ \subsection{Summary} calls to #resize()#, an #ArrayQueue# supports the operations #add(x)# and #remove()# in $O(1)$ time per operation. Furthermore, beginning with an empty #ArrayQueue#, any sequence of $m$ -#add(i,x)# and #remove(i)# operations results in a total of $O(m)$ +#add(x)# and #remove()# operations results in a total of $O(m)$ time spent during all calls to #resize()#. \end{thm} diff --git a/latex/hashing.tex b/latex/hashing.tex index 6dbf7119..7b7f8068 100644 --- a/latex/hashing.tex +++ b/latex/hashing.tex @@ -816,7 +816,7 @@ \subsection{Hash Codes for Arrays and Strings} $#y#_0,\ldots,#y#_{r'-1}$ be distinct sequences of #w#-bit integers in $\{0,\ldots,2^{#w#}-1\}$. Then \[ - \Pr\{ h(#x#_0,\ldots,#x#_{r-1}) = h(#y#_0,\ldots,#y#_{r-1}) \} + \Pr\{ h(#x#_0,\ldots,#x#_{r-1}) = h(#y#_0,\ldots,#y#_{r'-1}) \} \le \max\{r,r'\}/#p# \enspace . \] \end{thm} diff --git a/latex/intro.tex b/latex/intro.tex index ba8630d6..3b9b93f2 100644 --- a/latex/intro.tex +++ b/latex/intro.tex @@ -554,7 +554,7 @@ \subsection{Asymptotic Notation} A number of useful shortcuts can be applied when using asymptotic notation. First: \[ O(n^{c_1}) \subset O(n^{c_2}) \enspace ,\] -for any $c_1 < c_2$. Second: For any constants $a,b,c > 0$, +for any $c_1 < c_2$. Second: For any constants $a,b > 0, c > 1$, \[ O(a) \subset O(\log n) \subset O(n^{b}) \subset O({c}^n) \enspace . \] These inclusion relations can be multiplied by any positive value, and they still hold. For example, multiplying by $n$ yields: diff --git a/latex/redblack.tex b/latex/redblack.tex index e04f63eb..9a392c15 100644 --- a/latex/redblack.tex +++ b/latex/redblack.tex @@ -398,9 +398,9 @@ \subsection{Addition} satisfies the left-leaning property. In this case we can stop. \codeimport{ods/RedBlackTree.addFixup(u)} -The #insertFixup(u)# method takes constant time per iteration and each +The #addFixup(u)# method takes constant time per iteration and each iteration either finishes or moves #u# closer to the root. Therefore, -the #insertFixup(u)# method finishes after $O(\log #n#)$ iterations in +the #addFixup(u)# method finishes after $O(\log #n#)$ iterations in $O(\log #n#)$ time. \subsection{Removal} From a6eb4cadf8f43340c3009f9a689686dd99d908a9 Mon Sep 17 00:00:00 2001 From: ktanaka Date: Sat, 16 Apr 2016 17:09:17 +0900 Subject: [PATCH 2/3] use array swap instead of assign --- cpp/Algorithms.h | 4 ++-- cpp/ArrayDeque.h | 4 ++-- cpp/ArrayQueue.h | 2 +- cpp/ArrayStack.h | 4 ++-- cpp/BinaryHeap.h | 6 +++--- cpp/ChainedHashTable.h | 4 ++-- cpp/DualArrayDeque.h | 4 ++-- cpp/FastArrayStack.h | 2 +- cpp/LinearHashTable.h | 4 ++-- cpp/SEList.h | 2 +- cpp/array.h | 10 ++++++---- latex/arrays.tex | 6 +++--- 12 files changed, 27 insertions(+), 25 deletions(-) diff --git a/cpp/Algorithms.h b/cpp/Algorithms.h index 3d062aff..a32a0d60 100644 --- a/cpp/Algorithms.h +++ b/cpp/Algorithms.h @@ -147,7 +147,7 @@ void countingSort(array &a, int k) { array b(a.length); for (int i = a.length-1; i >= 0; i--) b[--c[a[i]]] = a[i]; - a = b; + a.swap(b); } void radixSort(array &a) { @@ -162,7 +162,7 @@ void radixSort(array &a) { c[i] += c[i-1]; for (int i = a.length-1; i >= 0; i--) b[--c[(a[i] >> d*p)&((1<::clear() { n = 0; j = 0; array b(1); - a = b; + a.swap(b); } template @@ -65,7 +65,7 @@ void ArrayDeque::resize() { array b(max(1, 2*n)); for (int k = 0; k < n; k++) b[k] = a[(j+k)%a.length]; - a = b; + a.swap(b); j = 0; } diff --git a/cpp/ArrayQueue.h b/cpp/ArrayQueue.h index 4cb1bd38..1b0735de 100644 --- a/cpp/ArrayQueue.h +++ b/cpp/ArrayQueue.h @@ -41,7 +41,7 @@ void ArrayQueue::resize() { array b(max(1, 2*n)); for (int k = 0; k < n; k++) b[k] = a[(j+k)%a.length]; - a = b; + a.swap(b); j = 0; } diff --git a/cpp/ArrayStack.h b/cpp/ArrayStack.h index c4579cd1..c9e29667 100644 --- a/cpp/ArrayStack.h +++ b/cpp/ArrayStack.h @@ -55,7 +55,7 @@ template void ArrayStack::clear() { n = 0; array b(1); - a = b; + a.swap(b); } template @@ -72,7 +72,7 @@ void ArrayStack::resize() { array b(max(2 * n, 1)); for (int i = 0; i < n; i++) b[i] = a[i]; - a = b; + a.swap(b); } template diff --git a/cpp/BinaryHeap.h b/cpp/BinaryHeap.h index cf6b5cb3..cd47e882 100644 --- a/cpp/BinaryHeap.h +++ b/cpp/BinaryHeap.h @@ -52,7 +52,7 @@ template void BinaryHeap::resize() { array b(max(2*n, 1)); std::copy(a+0, a+n, b+0); - a = b; + a.swap(b); } template @@ -62,7 +62,7 @@ void BinaryHeap::sort(array &b) { h.a.swap(--h.n, 0); h.trickleDown(0); } - b = h.a; + b.swap(h.a); b.reverse(); } @@ -134,7 +134,7 @@ BinaryHeap::BinaryHeap() : a(1) { template BinaryHeap::BinaryHeap(array &b) : a(0) { - a = b; + a.swap(b); n = a.length; for (int i = n/2-1; i >= 0; i--) { trickleDown(i); diff --git a/cpp/ChainedHashTable.h b/cpp/ChainedHashTable.h index e2591b36..427625cd 100644 --- a/cpp/ChainedHashTable.h +++ b/cpp/ChainedHashTable.h @@ -56,7 +56,7 @@ void ChainedHashTable::resize() { newTable[hash(x)].add(x); } } - t = newTable; + t.swap(newTable); } template @@ -114,7 +114,7 @@ void ChainedHashTable::clear() { n = 0; d = 1; array b(2); - t = b; + t.swap(b); } } /* namespace ods */ diff --git a/cpp/DualArrayDeque.h b/cpp/DualArrayDeque.h index 1bb1e1fe..b592bd22 100644 --- a/cpp/DualArrayDeque.h +++ b/cpp/DualArrayDeque.h @@ -97,9 +97,9 @@ void DualArrayDeque::balance() { for (int i = 0; i < nb; i++) { ab[i] = get(nf+i); } - front.a = af; + front.a.swap(af); front.n = nf; - back.a = ab; + back.a.swap(ab); back.n = nb; } } diff --git a/cpp/FastArrayStack.h b/cpp/FastArrayStack.h index e514dd1f..a0efe3ea 100644 --- a/cpp/FastArrayStack.h +++ b/cpp/FastArrayStack.h @@ -37,7 +37,7 @@ template void FastArrayStack::resize() { array b(max(1, 2*n)); std::copy(a+0, a+n, b+0); - a = b; + a.swap(b); } template diff --git a/cpp/LinearHashTable.h b/cpp/LinearHashTable.h index 53eb0cbe..41f89e7f 100644 --- a/cpp/LinearHashTable.h +++ b/cpp/LinearHashTable.h @@ -112,7 +112,7 @@ void LinearHashTable::resize() { tnew[i] = t[k]; } } - t = tnew; + t.swap(tnew); } template @@ -121,7 +121,7 @@ void LinearHashTable::clear() { q = 0; d = 1; array tnew(2, null); - t = tnew; + t.swap(tnew); } template diff --git a/cpp/SEList.h b/cpp/SEList.h index 3d055a45..d8aa2c8e 100644 --- a/cpp/SEList.h +++ b/cpp/SEList.h @@ -27,7 +27,7 @@ class SEList { n = 0; j = 0; array z(b+1); - a = z; + a.swap(z); } virtual ~BDeque() { } // C++ Question: Why is this necessary? diff --git a/cpp/array.h b/cpp/array.h index 3980e124..dba924fe 100644 --- a/cpp/array.h +++ b/cpp/array.h @@ -31,11 +31,13 @@ class array { void fill(T x); virtual ~array(); - array& operator=(array &b) { - if (a != NULL) delete[] a; + void swap(array &b) { + T *ta = a; a = b.a; - b.a = NULL; + b.a = ta; + int tl = length; length = b.length; + b.length = tl; return *this; } @@ -88,7 +90,7 @@ template void array::copyOfRange(array &a0, array &a, int i, int j) { array b(j-i); std::copy(a.a, a.a+j-i, b.a); - a0 = b; + a0.swap(b); } template diff --git a/latex/arrays.tex b/latex/arrays.tex index 059433dc..3aa22854 100644 --- a/latex/arrays.tex +++ b/latex/arrays.tex @@ -65,9 +65,9 @@ \chapter{Array-Based Lists} \cppimport{ods/array.array(len)} \cpponly{The elements of an array can be indexed:} \cppimport{ods/array.operator[]} -\cpponly{Finally, when one array is assigned to another, this is just +\cpponly{Finally, when one array is swapped with another, this is just a pointer manipulation that takes constant time:} -\cppimport{ods/array.operator=} +\cppimport{ods/array.swap(b)} \section{#ArrayStack#: Fast Stack Operations Using an Array} \seclabel{arraystack} @@ -132,7 +132,7 @@ \subsection{Growing and Shrinking} The #resize()# method is fairly straightforward; it allocates a new array #b# whose size is $2#n#$ and copies the #n# elements of #a# into -the first #n# positions in #b#, and then sets #a# to #b#. Thus, after a call to #resize()#, $#a.length# = 2#n#$. +the first #n# positions in #b#, and then \javaonly{sets #a# to #b#}\cpponly{swaps #a# with #b#}. Thus, after a call to #resize()#, $#a.length# = 2#n#$. \codeimport{ods/ArrayStack.resize()} From 8a27519b847edf6da94ca4bf0e4ae26794a4622d Mon Sep 17 00:00:00 2001 From: ktanaka Date: Sat, 16 Apr 2016 17:17:30 +0900 Subject: [PATCH 3/3] revert previous PR --- cpp/ArrayQueue.h | 1 + cpp/BinarySearchTree.h | 1 - cpp/BinaryTree.h | 2 +- cpp/SLList.h | 2 +- latex/arrays.tex | 2 +- latex/hashing.tex | 2 +- latex/intro.tex | 2 +- latex/redblack.tex | 4 ++-- 8 files changed, 8 insertions(+), 8 deletions(-) diff --git a/cpp/ArrayQueue.h b/cpp/ArrayQueue.h index 1b0735de..3b32240f 100644 --- a/cpp/ArrayQueue.h +++ b/cpp/ArrayQueue.h @@ -34,6 +34,7 @@ ArrayQueue::ArrayQueue() : a(1) { template ArrayQueue::~ArrayQueue() { + delete a; } template diff --git a/cpp/BinarySearchTree.h b/cpp/BinarySearchTree.h index a1d98739..0e1c3ead 100644 --- a/cpp/BinarySearchTree.h +++ b/cpp/BinarySearchTree.h @@ -148,7 +148,6 @@ bool BinarySearchTree::addChild(Node *p, Node *u) { } else if (comp > 0) { p->right = u; } else { - delete u; return false; // u.x is already in the tree } u->parent = p; diff --git a/cpp/BinaryTree.h b/cpp/BinaryTree.h index 8e80a8de..16b83208 100644 --- a/cpp/BinaryTree.h +++ b/cpp/BinaryTree.h @@ -181,7 +181,7 @@ void BinaryTree::bfTraverse() { ArrayDeque q; if (r != nil) q.add(q.size(),r); while (q.size() > 0) { - Node *u = q.remove(0); + Node *u = q.remove(q.size()-1); if (u->left != nil) q.add(q.size(),u->left); if (u->right != nil) q.add(q.size(),u->right); } diff --git a/cpp/SLList.h b/cpp/SLList.h index f8d67ca2..8aa6ffb5 100644 --- a/cpp/SLList.h +++ b/cpp/SLList.h @@ -21,7 +21,7 @@ class SLList { T x; Node *next; Node(T x0) { - x = x0; + x = 0; next = NULL; } }; diff --git a/latex/arrays.tex b/latex/arrays.tex index 3aa22854..44c2d473 100644 --- a/latex/arrays.tex +++ b/latex/arrays.tex @@ -383,7 +383,7 @@ \subsection{Summary} calls to #resize()#, an #ArrayQueue# supports the operations #add(x)# and #remove()# in $O(1)$ time per operation. Furthermore, beginning with an empty #ArrayQueue#, any sequence of $m$ -#add(x)# and #remove()# operations results in a total of $O(m)$ +#add(i,x)# and #remove(i)# operations results in a total of $O(m)$ time spent during all calls to #resize()#. \end{thm} diff --git a/latex/hashing.tex b/latex/hashing.tex index 7b7f8068..6dbf7119 100644 --- a/latex/hashing.tex +++ b/latex/hashing.tex @@ -816,7 +816,7 @@ \subsection{Hash Codes for Arrays and Strings} $#y#_0,\ldots,#y#_{r'-1}$ be distinct sequences of #w#-bit integers in $\{0,\ldots,2^{#w#}-1\}$. Then \[ - \Pr\{ h(#x#_0,\ldots,#x#_{r-1}) = h(#y#_0,\ldots,#y#_{r'-1}) \} + \Pr\{ h(#x#_0,\ldots,#x#_{r-1}) = h(#y#_0,\ldots,#y#_{r-1}) \} \le \max\{r,r'\}/#p# \enspace . \] \end{thm} diff --git a/latex/intro.tex b/latex/intro.tex index 3b9b93f2..ba8630d6 100644 --- a/latex/intro.tex +++ b/latex/intro.tex @@ -554,7 +554,7 @@ \subsection{Asymptotic Notation} A number of useful shortcuts can be applied when using asymptotic notation. First: \[ O(n^{c_1}) \subset O(n^{c_2}) \enspace ,\] -for any $c_1 < c_2$. Second: For any constants $a,b > 0, c > 1$, +for any $c_1 < c_2$. Second: For any constants $a,b,c > 0$, \[ O(a) \subset O(\log n) \subset O(n^{b}) \subset O({c}^n) \enspace . \] These inclusion relations can be multiplied by any positive value, and they still hold. For example, multiplying by $n$ yields: diff --git a/latex/redblack.tex b/latex/redblack.tex index 9a392c15..e04f63eb 100644 --- a/latex/redblack.tex +++ b/latex/redblack.tex @@ -398,9 +398,9 @@ \subsection{Addition} satisfies the left-leaning property. In this case we can stop. \codeimport{ods/RedBlackTree.addFixup(u)} -The #addFixup(u)# method takes constant time per iteration and each +The #insertFixup(u)# method takes constant time per iteration and each iteration either finishes or moves #u# closer to the root. Therefore, -the #addFixup(u)# method finishes after $O(\log #n#)$ iterations in +the #insertFixup(u)# method finishes after $O(\log #n#)$ iterations in $O(\log #n#)$ time. \subsection{Removal}