{"id":367,"date":"2024-03-31T09:15:00","date_gmt":"2024-03-31T08:15:00","guid":{"rendered":"https:\/\/noiseonthenet.space\/noise\/?p=367"},"modified":"2024-03-31T20:27:07","modified_gmt":"2024-03-31T19:27:07","slug":"stacking-bits","status":"publish","type":"post","link":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/","title":{"rendered":"Stacking bits"},"content":{"rendered":"<div id=\"org43b74ab\" class=\"figure\"> <p><img data-recalc-dims=\"1\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg?ssl=1\" alt=\"daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg\" \/> <\/p> <\/div>\n\n<p> Photo by <a href=\"https:\/\/unsplash.com\/@epicantus?utm_content=creditCopyText&amp;utm_medium=referral&amp;utm_source=unsplash\">Daria Nepriakhina \ud83c\uddfa\ud83c\udde6<\/a> on <a href=\"https:\/\/unsplash.com\/photos\/pile-of-assorted-title-books-xY55bL5mZAM?utm_content=creditCopyText&amp;utm_medium=referral&amp;utm_source=unsplash\">Unsplash<\/a> <\/p>\n\n<p> We are digressing a little from our previous path about trees to meet a data structure which has a deep connection with (binary) trees. <\/p>\n\n<p> I will show a very compact (memory efficient) and fast implementation of a binary stack. <\/p>\n\n<p> In this post I will also show how to use Rust types to implement failures and success as well as some Test Driven Design example. <\/p>\n\n<p> For those who want to have a look to previous posts, you can check <\/p>\n\n<ul class=\"org-ul\">\n<li><a href=\"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-binary-tree-in-rust\/\">Growing a (binary)Tree<\/a><\/li>\n<li><a href=\"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/\">Growing a (sorting) Tree<\/a><\/li>\n<\/ul>\n\n<p> The source code for this post is <a href=\"https:\/\/github.com\/noiseOnTheNet\/post014_piling_up_a_stack\">here<\/a> <\/p>\n<div id=\"outline-container-org7420029\" class=\"outline-2\">\n<h2 id=\"org7420029\">what is a stack<\/h2>\n<div class=\"outline-text-2\" id=\"text-org7420029\">\n<p> A stack is a data structure which allow you to retrieve the last datum you put into. <\/p>\n\n<p> This is very similar to a stack of books on your desk: the most common operations you can do are: <\/p>\n\n<ul class=\"org-ul\">\n<li>to add a book on the top; also known as <code>push<\/code><\/li>\n<li>to look at the topmost book; also known as <code>top<\/code><\/li>\n<li>to remove the topmost book; also known as <code>pop<\/code><\/li>\n<li>to count how many books are in our stack; <code>size<\/code><\/li>\n<\/ul>\n\n<p> It is also known as Last In First Out queue, sometime written with the LIFO achronym. <\/p>\n\n<div id=\"org429d9a0\" class=\"figure\"> <p><img data-recalc-dims=\"1\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/stack_usage.drawio.png?ssl=1\" alt=\"stack_usage.drawio.png\" \/> <\/p> <\/div>\n<\/div>\n<\/div>\n<div id=\"outline-container-org14c2820\" class=\"outline-2\">\n<h2 id=\"org14c2820\">defining a binary stack<\/h2>\n<div class=\"outline-text-2\" id=\"text-org14c2820\">\n<p> Instead of creating a generic stack I&rsquo;d like to focus on a very specific case: a stack which can only hold boolean values. <\/p>\n\n<p> The signature of the api could be as follows <\/p>\n\n<div class=\"org-src-container\">\n<label class=\"org-src-name\"><em><\/em><\/label>\n<pre class=\"src src-rust\" id=\"nil\"><span style=\"color: #5B6268;\">\/\/ <\/span><span style=\"color: #5B6268;\">warning: this code does not compile<\/span>\n<span style=\"color: #51afef;\">struct<\/span> <span style=\"color: #ECBE7B;\">Stack<\/span> <span style=\"color: #51afef;\">{}<\/span>\n\n<span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">push<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #dcaeea;\">stack<\/span> : <span style=\"color: #ECBE7B;\">Stack<\/span>, <span style=\"color: #dcaeea;\">value<\/span>: <span style=\"color: #ECBE7B;\">bool<\/span><span style=\"color: #51afef;\">)<\/span> <span style=\"color: #51afef;\">{}<\/span>\n\n<span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">top<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #dcaeea;\">stack<\/span> : <span style=\"color: #ECBE7B;\">Stack<\/span><span style=\"color: #51afef;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">bool<\/span> <span style=\"color: #51afef;\">{}<\/span>\n\n<span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">pop<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #dcaeea;\">stack<\/span> : <span style=\"color: #ECBE7B;\">Stack<\/span><span style=\"color: #51afef;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">bool<\/span> <span style=\"color: #51afef;\">{}<\/span>\n\n<span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">size<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #dcaeea;\">stack<\/span> : <span style=\"color: #ECBE7B;\">Stack<\/span><span style=\"color: #51afef;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">u32<\/span> <span style=\"color: #51afef;\">{}<\/span>\n<\/pre>\n<\/div>\n\n<p> To start this project I chose to create a library: <\/p>\n\n<div class=\"org-src-container\">\n<label class=\"org-src-name\"><em><\/em><\/label>\n<pre class=\"src src-bash\" id=\"nil\">cargo init --lib .\n<\/pre>\n<\/div>\n<p> This creates a <code>lib.rs<\/code> file in the <code>src<\/code> directory with some example code <\/p>\n\n<p> Rust allow to create a trait implementation for this structure; I will add the minimum code needed to compile it <\/p>\n\n<div class=\"org-src-container\">\n<label class=\"org-src-name\"><em><\/em><\/label>\n<pre class=\"src src-rust\" id=\"nil\"><span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">struct<\/span> <span style=\"color: #ECBE7B;\">Stack0<\/span> <span style=\"color: #51afef;\">{}<\/span>\n\n<span style=\"color: #51afef;\">impl<\/span> <span style=\"color: #ECBE7B;\">Stack0<\/span> <span style=\"color: #51afef;\">{<\/span>\n\n    <span style=\"color: #5B6268;\">\/\/ <\/span><span style=\"color: #5B6268;\">adding also a constructor<\/span>\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">new<\/span><span style=\"color: #c678dd;\">()<\/span> -&gt; <span style=\"color: #ECBE7B;\">Stack0<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #ECBE7B;\">Stack0<\/span> <span style=\"color: #98be65;\">{}<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">push<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">self<\/span>: &amp; <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #ECBE7B;\">Stack0<\/span>, <span style=\"color: #dcaeea;\">value<\/span>: <span style=\"color: #ECBE7B;\">bool<\/span><span style=\"color: #c678dd;\">)<\/span> <span style=\"color: #c678dd;\">{<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">top<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">self<\/span>: &amp; <span style=\"color: #ECBE7B;\">Stack0<\/span><span style=\"color: #c678dd;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">bool<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">true<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">pop<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">self<\/span>: &amp; <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #ECBE7B;\">Stack0<\/span><span style=\"color: #c678dd;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">bool<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">true<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">size<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">self<\/span>: &amp; <span style=\"color: #ECBE7B;\">Stack0<\/span><span style=\"color: #c678dd;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">u32<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #da8548; font-weight: bold;\">1<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"outline-container-org3daaebe\" class=\"outline-2\">\n<h2 id=\"org3daaebe\">test first design<\/h2>\n<div class=\"outline-text-2\" id=\"text-org3daaebe\">\n<p> What laws should this data structure obey? <\/p>\n\n<p> Let&rsquo;s check a few: <\/p>\n\n<ol class=\"org-ol\">\n<li>if I <code>push<\/code> a value, <code>pop<\/code> should return it<\/li>\n<li>if I <code>push<\/code> a value the size should increase by one<\/li>\n<li>also <code>top<\/code> should return the last thing I <code>push<\/code> -ed<\/li>\n<li>after <code>pop<\/code> the size should decrease<\/li>\n<li>a new stack should have size 0<\/li>\n<\/ol>\n\n<p> Rust has a convenient toolkit to create and execute tests: let&rsquo;s add a submodule in our library <\/p>\n\n<div class=\"org-src-container\">\n<label class=\"org-src-name\"><em><\/em><\/label>\n<pre class=\"src src-rust\" id=\"nil\"><span style=\"color: #5B6268;\">\/\/ <\/span><span style=\"color: #5B6268;\">this macro is used by compiler to<\/span>\n<span style=\"color: #5B6268;\">\/\/ <\/span><span style=\"color: #5B6268;\">conditionally compile the next section<\/span>\n<span style=\"color: #51afef; font-weight: bold;\">#<\/span><span style=\"color: #51afef; font-weight: bold;\">[<\/span><span style=\"color: #51afef; font-weight: bold;\">cfg<\/span><span style=\"color: #c678dd; font-weight: bold;\">(<\/span><span style=\"color: #51afef; font-weight: bold;\">test<\/span><span style=\"color: #c678dd; font-weight: bold;\">)<\/span><span style=\"color: #51afef; font-weight: bold;\">]<\/span>\n<span style=\"color: #5B6268;\">\/\/ <\/span><span style=\"color: #5B6268;\">this defines a module within current one<\/span>\n<span style=\"color: #51afef;\">mod<\/span> <span style=\"color: #a9a1e1;\">tests<\/span> <span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #5B6268;\">\/\/ <\/span><span style=\"color: #5B6268;\">this statement imports everithing defined<\/span>\n    <span style=\"color: #5B6268;\">\/\/ <\/span><span style=\"color: #5B6268;\">in the upper module<\/span>\n    <span style=\"color: #51afef;\">use<\/span> <span style=\"color: #51afef;\">super<\/span>::*;\n\n    <span style=\"color: #5B6268;\">\/\/ <\/span><span style=\"color: #5B6268;\">this macro identifies a test<\/span>\n    <span style=\"color: #51afef; font-weight: bold;\">#<\/span><span style=\"color: #c678dd; font-weight: bold;\">[<\/span><span style=\"color: #51afef; font-weight: bold;\">test<\/span><span style=\"color: #c678dd; font-weight: bold;\">]<\/span>\n    <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">empty_when_created<\/span><span style=\"color: #c678dd;\">()<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result<\/span> = <span style=\"color: #ECBE7B;\">Stack0<\/span>::new<span style=\"color: #98be65;\">()<\/span>.size<span style=\"color: #98be65;\">()<\/span>;\n        <span style=\"color: #51afef; font-weight: bold;\">assert_eq!<\/span><span style=\"color: #98be65;\">(<\/span>result, <span style=\"color: #da8548; font-weight: bold;\">0<\/span><span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n\n\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\n\n<p> by executing <\/p>\n\n<div class=\"org-src-container\">\n<label class=\"org-src-name\"><em><\/em><\/label>\n<pre class=\"src src-bash\" id=\"nil\">cargo test\n<\/pre>\n<\/div>\n<p> we will compile the library with the tests and execute them, a report is printed which may look like this: <\/p>\n\n<em><\/em>\n<pre class=\"example\" id=\"nil\">\nrunning 1 test\ntest tests::empty_when_created ... FAILED\n\nfailures:\n\n---- tests::empty_when_created stdout ----\nthread 'tests::empty_when_created' panicked at src\/lib.rs:53:9:\nassertion `left == right` failed\n  left: 1\n right: 0\nnote: run with `RUST_BACKTRACE=1` environment variable to display a backtrace\n\n\nfailures:\n    tests::empty_when_created\n\ntest result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s\n<\/pre>\n\n<p> we can add more tests in the same module: e.g. <\/p>\n\n<div class=\"org-src-container\">\n<label class=\"org-src-name\"><em><\/em><\/label>\n<pre class=\"src src-rust\" id=\"nil\">    <span style=\"color: #51afef; font-weight: bold;\">#<\/span><span style=\"color: #51afef; font-weight: bold;\">[<\/span><span style=\"color: #51afef; font-weight: bold;\">test<\/span><span style=\"color: #51afef; font-weight: bold;\">]<\/span>\n    <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">size_increase_when_push<\/span><span style=\"color: #51afef;\">()<\/span> <span style=\"color: #51afef;\">{<\/span>\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">stack<\/span> = <span style=\"color: #ECBE7B;\">Stack0<\/span>::new<span style=\"color: #c678dd;\">()<\/span>;\n        stack.push<span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">false<\/span><span style=\"color: #c678dd;\">)<\/span>;\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result1<\/span> = stack.size<span style=\"color: #c678dd;\">()<\/span>;\n        stack.push<span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">true<\/span><span style=\"color: #c678dd;\">)<\/span>;\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result2<\/span> = stack.size<span style=\"color: #c678dd;\">()<\/span>;\n        <span style=\"color: #51afef; font-weight: bold;\">assert_eq!<\/span><span style=\"color: #c678dd;\">(<\/span>result2, result1 + <span style=\"color: #da8548; font-weight: bold;\">1<\/span><span style=\"color: #c678dd;\">)<\/span>;\n    <span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"outline-container-orgc74e244\" class=\"outline-2\">\n<h2 id=\"orgc74e244\">managing unwanted status<\/h2>\n<div class=\"outline-text-2\" id=\"text-orgc74e244\">\n<p> Now I have couple of questions <\/p>\n\n<ol class=\"org-ol\">\n<li>What happens when I try to get a book from an empty stack?<\/li>\n<li>Can a stack grow forever? Or can I decide it is too tall to grow?<\/li>\n<\/ol>\n\n<p> Rust uses the <code>Result<\/code> enumeration to express this concept; a <code>Result<\/code> can be either be <code>Ok(some_value)<\/code> or <code>Err(error)<\/code>. <\/p>\n\n<p> Being <code>Result&lt;R, E&gt;<\/code> a generic type, I need to specify both the result type <code>R<\/code> and the error type <code>E<\/code>; the result type will be of course a <code>bool<\/code> while for this example I will choose a simple <code>String<\/code> for the error. <\/p>\n\n<p> The stack API can be now modified to tackle our questions: <\/p>\n\n<div class=\"org-src-container\">\n<label class=\"org-src-name\"><em><\/em><\/label>\n<pre class=\"src src-rust\" id=\"nil\"><span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">struct<\/span> <span style=\"color: #ECBE7B;\">Stack1<\/span> <span style=\"color: #51afef;\">{}<\/span>\n\n<span style=\"color: #51afef;\">impl<\/span> <span style=\"color: #ECBE7B;\">Stack1<\/span> <span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">new<\/span><span style=\"color: #c678dd;\">()<\/span> -&gt; <span style=\"color: #ECBE7B;\">Stack1<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #ECBE7B;\">Stack1<\/span> <span style=\"color: #98be65;\">{}<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">push<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">self<\/span>: &amp; <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #ECBE7B;\">Stack1<\/span>, <span style=\"color: #dcaeea;\">value<\/span>: <span style=\"color: #ECBE7B;\">bool<\/span><span style=\"color: #c678dd;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">Result<\/span><span style=\"color: #c678dd;\">&lt;<\/span><span style=\"color: #ECBE7B;\">bool<\/span>, <span style=\"color: #ECBE7B;\">String<\/span><span style=\"color: #c678dd;\">&gt;{<\/span>\n        <span style=\"color: #ECBE7B;\">Ok<\/span><span style=\"color: #98be65;\">(<\/span>value<span style=\"color: #98be65;\">)<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">top<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">self<\/span>: &amp; <span style=\"color: #ECBE7B;\">Stack1<\/span><span style=\"color: #c678dd;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">Result<\/span><span style=\"color: #c678dd;\">&lt;<\/span><span style=\"color: #ECBE7B;\">bool<\/span>, <span style=\"color: #ECBE7B;\">String<\/span><span style=\"color: #c678dd;\">&gt;<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #ECBE7B;\">Ok<\/span><span style=\"color: #98be65;\">(<\/span><span style=\"color: #51afef;\">true<\/span><span style=\"color: #98be65;\">)<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">pop<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">self<\/span>: &amp; <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #ECBE7B;\">Stack1<\/span><span style=\"color: #c678dd;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">Result<\/span><span style=\"color: #c678dd;\">&lt;<\/span><span style=\"color: #ECBE7B;\">bool<\/span>, <span style=\"color: #ECBE7B;\">String<\/span><span style=\"color: #c678dd;\">&gt;<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #ECBE7B;\">Ok<\/span><span style=\"color: #98be65;\">(<\/span><span style=\"color: #51afef;\">true<\/span><span style=\"color: #98be65;\">)<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">size<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">self<\/span>: &amp; <span style=\"color: #ECBE7B;\">Stack1<\/span><span style=\"color: #c678dd;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">u32<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #da8548; font-weight: bold;\">1<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\n\n<p> and so our tests must be adapted; we need to add two rules and their type signature. <\/p>\n\n<div class=\"org-src-container\">\n<label class=\"org-src-name\"><em><\/em><\/label>\n<pre class=\"src src-rust\" id=\"nil\"><span style=\"color: #51afef; font-weight: bold;\">#<\/span><span style=\"color: #51afef; font-weight: bold;\">[<\/span><span style=\"color: #51afef; font-weight: bold;\">cfg<\/span><span style=\"color: #c678dd; font-weight: bold;\">(<\/span><span style=\"color: #51afef; font-weight: bold;\">test<\/span><span style=\"color: #c678dd; font-weight: bold;\">)<\/span><span style=\"color: #51afef; font-weight: bold;\">]<\/span>\n<span style=\"color: #51afef;\">mod<\/span> <span style=\"color: #a9a1e1;\">tests<\/span> <span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #51afef;\">use<\/span> <span style=\"color: #51afef;\">super<\/span>::*;\n\n    <span style=\"color: #51afef; font-weight: bold;\">#<\/span><span style=\"color: #c678dd; font-weight: bold;\">[<\/span><span style=\"color: #51afef; font-weight: bold;\">test<\/span><span style=\"color: #c678dd; font-weight: bold;\">]<\/span>\n    <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">push_and_pop<\/span><span style=\"color: #c678dd;\">()<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">stack<\/span> = <span style=\"color: #ECBE7B;\">Stack1<\/span>::new<span style=\"color: #98be65;\">()<\/span>;\n        stack.push<span style=\"color: #98be65;\">(<\/span><span style=\"color: #51afef;\">false<\/span><span style=\"color: #98be65;\">)<\/span>;\n        stack.push<span style=\"color: #98be65;\">(<\/span><span style=\"color: #51afef;\">true<\/span><span style=\"color: #98be65;\">)<\/span>;\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result1<\/span> = stack.pop<span style=\"color: #98be65;\">()<\/span>;\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result2<\/span> = stack.pop<span style=\"color: #98be65;\">()<\/span>;\n        <span style=\"color: #51afef; font-weight: bold;\">assert_eq!<\/span><span style=\"color: #98be65;\">(<\/span>result1, <span style=\"color: #ECBE7B;\">Ok<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #51afef;\">true<\/span><span style=\"color: #a9a1e1;\">)<\/span><span style=\"color: #98be65;\">)<\/span>;\n        <span style=\"color: #51afef; font-weight: bold;\">assert_eq!<\/span><span style=\"color: #98be65;\">(<\/span>result2, <span style=\"color: #ECBE7B;\">Ok<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #51afef;\">false<\/span><span style=\"color: #a9a1e1;\">)<\/span><span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef; font-weight: bold;\">#<\/span><span style=\"color: #c678dd; font-weight: bold;\">[<\/span><span style=\"color: #51afef; font-weight: bold;\">test<\/span><span style=\"color: #c678dd; font-weight: bold;\">]<\/span>\n    <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">size_increase_when_push<\/span><span style=\"color: #c678dd;\">()<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">stack<\/span> = <span style=\"color: #ECBE7B;\">Stack1<\/span>::new<span style=\"color: #98be65;\">()<\/span>;\n        stack.push<span style=\"color: #98be65;\">(<\/span><span style=\"color: #51afef;\">false<\/span><span style=\"color: #98be65;\">)<\/span>;\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result1<\/span> = stack.size<span style=\"color: #98be65;\">()<\/span>;\n        stack.push<span style=\"color: #98be65;\">(<\/span><span style=\"color: #51afef;\">true<\/span><span style=\"color: #98be65;\">)<\/span>;\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result2<\/span> = stack.size<span style=\"color: #98be65;\">()<\/span>;\n        <span style=\"color: #51afef; font-weight: bold;\">assert_eq!<\/span><span style=\"color: #98be65;\">(<\/span>result2, result1 + <span style=\"color: #da8548; font-weight: bold;\">1<\/span><span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef; font-weight: bold;\">#<\/span><span style=\"color: #c678dd; font-weight: bold;\">[<\/span><span style=\"color: #51afef; font-weight: bold;\">test<\/span><span style=\"color: #c678dd; font-weight: bold;\">]<\/span>\n    <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">push_and_top<\/span><span style=\"color: #c678dd;\">()<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">stack<\/span> = <span style=\"color: #ECBE7B;\">Stack1<\/span>::new<span style=\"color: #98be65;\">()<\/span>;\n        stack.push<span style=\"color: #98be65;\">(<\/span><span style=\"color: #51afef;\">false<\/span><span style=\"color: #98be65;\">)<\/span>;\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result1<\/span> = stack.top<span style=\"color: #98be65;\">()<\/span>;\n        stack.push<span style=\"color: #98be65;\">(<\/span><span style=\"color: #51afef;\">true<\/span><span style=\"color: #98be65;\">)<\/span>;\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result2<\/span> = stack.top<span style=\"color: #98be65;\">()<\/span>;\n        <span style=\"color: #51afef; font-weight: bold;\">assert_eq!<\/span><span style=\"color: #98be65;\">(<\/span>result1, <span style=\"color: #ECBE7B;\">Ok<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #51afef;\">false<\/span><span style=\"color: #a9a1e1;\">)<\/span><span style=\"color: #98be65;\">)<\/span>;\n        <span style=\"color: #51afef; font-weight: bold;\">assert_eq!<\/span><span style=\"color: #98be65;\">(<\/span>result2, <span style=\"color: #ECBE7B;\">Ok<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #51afef;\">true<\/span><span style=\"color: #a9a1e1;\">)<\/span><span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef; font-weight: bold;\">#<\/span><span style=\"color: #c678dd; font-weight: bold;\">[<\/span><span style=\"color: #51afef; font-weight: bold;\">test<\/span><span style=\"color: #c678dd; font-weight: bold;\">]<\/span>\n    <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">size_decreases_when_pop<\/span><span style=\"color: #c678dd;\">()<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">stack<\/span> = <span style=\"color: #ECBE7B;\">Stack1<\/span>::new<span style=\"color: #98be65;\">()<\/span>;\n        stack.push<span style=\"color: #98be65;\">(<\/span><span style=\"color: #51afef;\">false<\/span><span style=\"color: #98be65;\">)<\/span>;\n        stack.push<span style=\"color: #98be65;\">(<\/span><span style=\"color: #51afef;\">true<\/span><span style=\"color: #98be65;\">)<\/span>;\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result1<\/span> = stack.size<span style=\"color: #98be65;\">()<\/span>;\n        stack.pop<span style=\"color: #98be65;\">()<\/span>;\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result2<\/span> = stack.size<span style=\"color: #98be65;\">()<\/span>;\n        <span style=\"color: #51afef; font-weight: bold;\">assert_eq!<\/span><span style=\"color: #98be65;\">(<\/span>result1, result2 - <span style=\"color: #da8548; font-weight: bold;\">1<\/span><span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef; font-weight: bold;\">#<\/span><span style=\"color: #c678dd; font-weight: bold;\">[<\/span><span style=\"color: #51afef; font-weight: bold;\">test<\/span><span style=\"color: #c678dd; font-weight: bold;\">]<\/span>\n    <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">empty_when_created<\/span><span style=\"color: #c678dd;\">()<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result<\/span> = <span style=\"color: #ECBE7B;\">Stack1<\/span>::new<span style=\"color: #98be65;\">()<\/span>.size<span style=\"color: #98be65;\">()<\/span>;\n        <span style=\"color: #51afef; font-weight: bold;\">assert_eq!<\/span><span style=\"color: #98be65;\">(<\/span>result, <span style=\"color: #da8548; font-weight: bold;\">0<\/span><span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef; font-weight: bold;\">#<\/span><span style=\"color: #c678dd; font-weight: bold;\">[<\/span><span style=\"color: #51afef; font-weight: bold;\">test<\/span><span style=\"color: #c678dd; font-weight: bold;\">]<\/span>\n    <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">empty_does_not_pop<\/span><span style=\"color: #c678dd;\">()<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">stack<\/span> = <span style=\"color: #ECBE7B;\">Stack1<\/span>::new<span style=\"color: #98be65;\">()<\/span>;\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result<\/span> = stack.pop<span style=\"color: #98be65;\">()<\/span>;\n        <span style=\"color: #51afef; font-weight: bold;\">assert_eq!<\/span><span style=\"color: #98be65;\">(<\/span>result, <span style=\"color: #ECBE7B;\">Err<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #98be65;\">\"Empty stack\"<\/span>.into<span style=\"color: #51afef;\">()<\/span><span style=\"color: #a9a1e1;\">)<\/span><span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"outline-container-org063053c\" class=\"outline-2\">\n<h2 id=\"org063053c\">implementing the stack<\/h2>\n<div class=\"outline-text-2\" id=\"text-org063053c\">\n<p> The idea here is to use an integer value to host a sequence of bits, each representing a value pushed in the stack. <\/p>\n\n<p> We can emulate the push behavior by executing a left shift of one and adding 1 only if the input value is <code>true<\/code> <\/p>\n\n<p> The following example is made with a 4 bit value just to make it easier to read <\/p>\n\n<p> e.g. <\/p>\n\n<ol class=\"org-ol\">\n<li>stack status is is <code>0b0001<\/code><\/li>\n<li>stack receive a <code>PUSH true<\/code>\n\n<ol class=\"org-ol\">\n<li>left shift the status; now is <code>0b0010<\/code><\/li>\n<li>add one to the status; now is <code>0b0011<\/code><\/li>\n<\/ol><\/li>\n<li>stack receive a <code>PUSH false<\/code>\n\n<ol class=\"org-ol\">\n<li>left shift the status; now is <code>0b0110<\/code><\/li>\n<\/ol><\/li>\n<\/ol>\n\n<p> the right shift can be used as pop e.g <\/p>\n\n<ol class=\"org-ol\">\n<li>stack status is <code>0b0110<\/code><\/li>\n<li>stack receive a <code>POP<\/code>\n\n<ol class=\"org-ol\">\n<li>evaluate <code>status &amp; 0b0001<\/code> and store the result<\/li>\n<li>right shift the status; now is <code>0b0011<\/code><\/li>\n<li>return the stored result (is now <code>false<\/code>)<\/li>\n<\/ol><\/li>\n<li>stack receive a <code>POP<\/code>\n\n<ol class=\"org-ol\">\n<li>evaluate <code>status &amp; 0b0001<\/code> and store the result<\/li>\n<li>right shift the status; now is <code>0b0001<\/code><\/li>\n<li>return the stored result (is now <code>true<\/code>)<\/li>\n<\/ol><\/li>\n<\/ol>\n\n<p> as <code>0b0000 &gt;&gt; 1 == 0b000<\/code> (shift right 0 returns 0) we need a way to know when our stack is empty; a possible way is to define the empty status equal to <code>0b0001<\/code> <\/p>\n\n<p> I will use an unsigned integer of type <code>usize<\/code> in this example. The number of bytes of this integer depends on the cpu architecture, it may be 64 or 32 in most cases. <\/p>\n\n<p> How can we calculate the size of the stack? we use one bit to mark the start point, so if we count all bits after it we have the result. <\/p>\n\n<p> Rust has two interesting features for this kind of calculation; we know the number of bits of <code>usize<\/code> from the constant <code>usize::BITS<\/code> and the function <code>usize::leading_zeros<\/code> returns the count of the bits before our marker. <\/p>\n\n<p> here is the full implementation: <\/p>\n\n<div class=\"org-src-container\">\n<label class=\"org-src-name\"><em><\/em><\/label>\n<pre class=\"src src-rust\" id=\"nil\"><span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">struct<\/span> <span style=\"color: #ECBE7B;\">Stack1<\/span> <span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #dcaeea;\">stack<\/span>: <span style=\"color: #ECBE7B;\">usize<\/span>\n<span style=\"color: #51afef;\">}<\/span>\n\n<span style=\"color: #51afef;\">impl<\/span> <span style=\"color: #ECBE7B;\">Stack1<\/span> <span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">new<\/span><span style=\"color: #c678dd;\">()<\/span> -&gt; <span style=\"color: #ECBE7B;\">Stack1<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #ECBE7B;\">Stack1<\/span> <span style=\"color: #98be65;\">{<\/span> <span style=\"color: #dcaeea;\">stack<\/span>: <span style=\"color: #da8548; font-weight: bold;\">1<\/span> <span style=\"color: #98be65;\">}<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">push<\/span><span style=\"color: #c678dd;\">(<\/span>&amp; <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #51afef;\">self<\/span>, <span style=\"color: #dcaeea;\">value<\/span>: <span style=\"color: #ECBE7B;\">bool<\/span><span style=\"color: #c678dd;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">Result<\/span><span style=\"color: #c678dd;\">&lt;<\/span><span style=\"color: #ECBE7B;\">bool<\/span>, <span style=\"color: #ECBE7B;\">String<\/span><span style=\"color: #c678dd;\">&gt;{<\/span>\n        <span style=\"color: #51afef;\">self<\/span>.stack = <span style=\"color: #51afef;\">self<\/span>.stack &lt;&lt; <span style=\"color: #da8548; font-weight: bold;\">1<\/span>;\n        <span style=\"color: #51afef;\">if<\/span> value<span style=\"color: #98be65;\">{<\/span>\n            <span style=\"color: #51afef;\">self<\/span>.stack += <span style=\"color: #da8548; font-weight: bold;\">1<\/span>;\n        <span style=\"color: #98be65;\">}<\/span>\n        <span style=\"color: #ECBE7B;\">Ok<\/span><span style=\"color: #98be65;\">(<\/span>value<span style=\"color: #98be65;\">)<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">top<\/span><span style=\"color: #c678dd;\">(<\/span>&amp; <span style=\"color: #51afef;\">self<\/span><span style=\"color: #c678dd;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">Result<\/span><span style=\"color: #c678dd;\">&lt;<\/span><span style=\"color: #ECBE7B;\">bool<\/span>, <span style=\"color: #ECBE7B;\">String<\/span><span style=\"color: #c678dd;\">&gt;<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">if<\/span> <span style=\"color: #51afef;\">self<\/span>.stack == <span style=\"color: #da8548; font-weight: bold;\">1<\/span> <span style=\"color: #98be65;\">{<\/span>\n            <span style=\"color: #51afef;\">return<\/span> <span style=\"color: #ECBE7B;\">Err<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #98be65;\">\"Empty stack\"<\/span>.into<span style=\"color: #51afef;\">()<\/span><span style=\"color: #a9a1e1;\">)<\/span>\n        <span style=\"color: #98be65;\">}<\/span>\n        <span style=\"color: #ECBE7B;\">Ok<\/span><span style=\"color: #98be65;\">(<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #51afef;\">self<\/span>.stack &amp; <span style=\"color: #da8548; font-weight: bold;\">1<\/span><span style=\"color: #a9a1e1;\">)<\/span> == <span style=\"color: #da8548; font-weight: bold;\">1<\/span><span style=\"color: #98be65;\">)<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">pop<\/span><span style=\"color: #c678dd;\">(<\/span>&amp; <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #51afef;\">self<\/span><span style=\"color: #c678dd;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">Result<\/span><span style=\"color: #c678dd;\">&lt;<\/span><span style=\"color: #ECBE7B;\">bool<\/span>, <span style=\"color: #ECBE7B;\">String<\/span><span style=\"color: #c678dd;\">&gt;<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">if<\/span> <span style=\"color: #51afef;\">self<\/span>.stack == <span style=\"color: #da8548; font-weight: bold;\">1<\/span> <span style=\"color: #98be65;\">{<\/span>\n            <span style=\"color: #51afef;\">return<\/span> <span style=\"color: #ECBE7B;\">Err<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #98be65;\">\"Empty stack\"<\/span>.into<span style=\"color: #51afef;\">()<\/span><span style=\"color: #a9a1e1;\">)<\/span>\n        <span style=\"color: #98be65;\">}<\/span>\n        <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result<\/span> = <span style=\"color: #98be65;\">(<\/span><span style=\"color: #51afef;\">self<\/span>.stack &amp; <span style=\"color: #da8548; font-weight: bold;\">1<\/span><span style=\"color: #98be65;\">)<\/span> == <span style=\"color: #da8548; font-weight: bold;\">1<\/span>;\n        <span style=\"color: #51afef;\">self<\/span>.stack = <span style=\"color: #51afef;\">self<\/span>.stack &gt;&gt; <span style=\"color: #da8548; font-weight: bold;\">1<\/span>;\n        <span style=\"color: #ECBE7B;\">Ok<\/span><span style=\"color: #98be65;\">(<\/span>result<span style=\"color: #98be65;\">)<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">size<\/span><span style=\"color: #c678dd;\">(<\/span>&amp; <span style=\"color: #51afef;\">self<\/span><span style=\"color: #c678dd;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">u32<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #ECBE7B;\">usize<\/span>::<span style=\"color: #ECBE7B;\">BITS<\/span> - <span style=\"color: #ECBE7B;\">usize<\/span>::leading_zeros<span style=\"color: #98be65;\">(<\/span><span style=\"color: #51afef;\">self<\/span>.stack<span style=\"color: #98be65;\">)<\/span> - <span style=\"color: #da8548; font-weight: bold;\">1<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"outline-container-org319647d\" class=\"outline-2\">\n<h2 id=\"org319647d\">a last remark on error types and borrow checker rules<\/h2>\n<div class=\"outline-text-2\" id=\"text-org319647d\">\n<p> It may sound strange to have a very compact and fast implementation like this one with an error type like <code>String<\/code>; we are actually using constant strings so a type like <code>&amp;str<\/code> should be enough right? <\/p>\n\n<p> Well, no. <\/p>\n\n<p> If we use a signature like <\/p>\n\n<div class=\"org-src-container\">\n<label class=\"org-src-name\"><em><\/em><\/label>\n<pre class=\"src src-rust\" id=\"nil\"><span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">pop<\/span><span style=\"color: #51afef;\">(<\/span>&amp; <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #51afef;\">self<\/span><span style=\"color: #51afef;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">Result<\/span><span style=\"color: #51afef;\">&lt;<\/span><span style=\"color: #ECBE7B;\">bool<\/span>, &amp; <span style=\"color: #ECBE7B;\">str<\/span><span style=\"color: #51afef;\">&gt;<\/span>;\n<\/pre>\n<\/div>\n<p> we are actually using this lifetime signature <\/p>\n\n<div class=\"org-src-container\">\n<label class=\"org-src-name\"><em><\/em><\/label>\n<pre class=\"src src-rust\" id=\"nil\"><span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">pop<\/span><span style=\"color: #51afef;\">&lt;<\/span>'<span style=\"color: #dcaeea;\">a<\/span><span style=\"color: #51afef;\">&gt;(<\/span>&amp; <span style=\"color: #51afef;\">mut<\/span> '<span style=\"color: #dcaeea;\">a<\/span> <span style=\"color: #51afef;\">self<\/span><span style=\"color: #51afef;\">)<\/span> -&gt; <span style=\"color: #ECBE7B;\">Result<\/span><span style=\"color: #51afef;\">&lt;<\/span><span style=\"color: #ECBE7B;\">bool<\/span>, &amp; '<span style=\"color: #dcaeea;\">a<\/span> <span style=\"color: #ECBE7B;\">str<\/span><span style=\"color: #51afef;\">&gt;<\/span>;\n<\/pre>\n<\/div>\n\n<p> This means that we cannot execute something like <\/p>\n\n<div class=\"org-src-container\">\n<label class=\"org-src-name\"><em><\/em><\/label>\n<pre class=\"src src-rust\" id=\"nil\"><span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result1<\/span> = stack.pop<span style=\"color: #51afef;\">(<\/span><span style=\"color: #51afef;\">true<\/span><span style=\"color: #51afef;\">)<\/span>;\n<span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">result2<\/span> = stack.pop<span style=\"color: #51afef;\">(<\/span><span style=\"color: #51afef;\">true<\/span><span style=\"color: #51afef;\">)<\/span>;\n<\/pre>\n<\/div>\n<p> because the first call <b>may<\/b> return an <code>Err(&amp; 'a str)<\/code> which is like a borrow of a mutable pointer that cannot be done twice. <\/p>\n\n<p> So, can we have a more efficient definition of the error type? Sure we can use an enumeration. <\/p>\n\n<p> But this is for another post. <\/p>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"I will show a very compact (memory efficient) and fast implementation of a binary stack, some Test Driven Design and success types","protected":false},"author":1,"featured_media":389,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","inline_featured_image":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[5],"class_list":["post-367","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-language-learning","tag-rust"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.4 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Stacking bits - Noise On The Net<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Stacking bits - Noise On The Net\" \/>\n<meta property=\"og:description\" content=\"I will show a very compact (memory efficient) and fast implementation of a binary stack, some Test Driven Design and success types\" \/>\n<meta property=\"og:url\" content=\"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/\" \/>\n<meta property=\"og:site_name\" content=\"Noise On The Net\" \/>\n<meta property=\"article:published_time\" content=\"2024-03-31T08:15:00+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-03-31T19:27:07+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"775\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"marco.p.v.vezzoli\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"marco.p.v.vezzoli\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/\"},\"author\":{\"name\":\"marco.p.v.vezzoli\",\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/#\\\/schema\\\/person\\\/88c3a70f2b23480197bc61d6e1e2e982\"},\"headline\":\"Stacking bits\",\"datePublished\":\"2024-03-31T08:15:00+00:00\",\"dateModified\":\"2024-03-31T19:27:07+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/\"},\"wordCount\":875,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/#\\\/schema\\\/person\\\/88c3a70f2b23480197bc61d6e1e2e982\"},\"image\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/i0.wp.com\\\/noiseonthenet.space\\\/noise\\\/wp-content\\\/uploads\\\/2024\\\/03\\\/daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg?fit=1200%2C775&ssl=1\",\"keywords\":[\"Rust\"],\"articleSection\":[\"Language learning\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/\",\"url\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/\",\"name\":\"Stacking bits - Noise On The Net\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/i0.wp.com\\\/noiseonthenet.space\\\/noise\\\/wp-content\\\/uploads\\\/2024\\\/03\\\/daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg?fit=1200%2C775&ssl=1\",\"datePublished\":\"2024-03-31T08:15:00+00:00\",\"dateModified\":\"2024-03-31T19:27:07+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/#primaryimage\",\"url\":\"https:\\\/\\\/i0.wp.com\\\/noiseonthenet.space\\\/noise\\\/wp-content\\\/uploads\\\/2024\\\/03\\\/daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg?fit=1200%2C775&ssl=1\",\"contentUrl\":\"https:\\\/\\\/i0.wp.com\\\/noiseonthenet.space\\\/noise\\\/wp-content\\\/uploads\\\/2024\\\/03\\\/daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg?fit=1200%2C775&ssl=1\",\"width\":1200,\"height\":775},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/stacking-bits\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Stacking bits\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/#website\",\"url\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/\",\"name\":\"Noise On The Net\",\"description\":\"Sharing adventures in code\",\"publisher\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/#\\\/schema\\\/person\\\/88c3a70f2b23480197bc61d6e1e2e982\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/#\\\/schema\\\/person\\\/88c3a70f2b23480197bc61d6e1e2e982\",\"name\":\"marco.p.v.vezzoli\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g\",\"caption\":\"marco.p.v.vezzoli\"},\"logo\":{\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g\"},\"description\":\"Self taught assembler programming at 11 on my C64 (1983). Never stopped since then -- always looking up for curious things in the software development, data science and AI. Linux and FOSS user since 1994. MSc in physics in 1996. Working in large semiconductor companies since 1997 (STM, Micron) developing analytics and full stack web infrastructures, microservices, ML solutions\",\"sameAs\":[\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/\",\"https:\\\/\\\/www.linkedin.com\\\/in\\\/marco-paolo-valerio-vezzoli-0663835\\\/\"],\"url\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/author\\\/marco-p-v-vezzoli\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Stacking bits - Noise On The Net","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/","og_locale":"en_US","og_type":"article","og_title":"Stacking bits - Noise On The Net","og_description":"I will show a very compact (memory efficient) and fast implementation of a binary stack, some Test Driven Design and success types","og_url":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/","og_site_name":"Noise On The Net","article_published_time":"2024-03-31T08:15:00+00:00","article_modified_time":"2024-03-31T19:27:07+00:00","og_image":[{"width":1200,"height":775,"url":"https:\/\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg","type":"image\/jpeg"}],"author":"marco.p.v.vezzoli","twitter_card":"summary_large_image","twitter_misc":{"Written by":"marco.p.v.vezzoli","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/#article","isPartOf":{"@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/"},"author":{"name":"marco.p.v.vezzoli","@id":"https:\/\/noiseonthenet.space\/noise\/#\/schema\/person\/88c3a70f2b23480197bc61d6e1e2e982"},"headline":"Stacking bits","datePublished":"2024-03-31T08:15:00+00:00","dateModified":"2024-03-31T19:27:07+00:00","mainEntityOfPage":{"@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/"},"wordCount":875,"commentCount":0,"publisher":{"@id":"https:\/\/noiseonthenet.space\/noise\/#\/schema\/person\/88c3a70f2b23480197bc61d6e1e2e982"},"image":{"@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg?fit=1200%2C775&ssl=1","keywords":["Rust"],"articleSection":["Language learning"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/","url":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/","name":"Stacking bits - Noise On The Net","isPartOf":{"@id":"https:\/\/noiseonthenet.space\/noise\/#website"},"primaryImageOfPage":{"@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/#primaryimage"},"image":{"@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg?fit=1200%2C775&ssl=1","datePublished":"2024-03-31T08:15:00+00:00","dateModified":"2024-03-31T19:27:07+00:00","breadcrumb":{"@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/#primaryimage","url":"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg?fit=1200%2C775&ssl=1","contentUrl":"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg?fit=1200%2C775&ssl=1","width":1200,"height":775},{"@type":"BreadcrumbList","@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/stacking-bits\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/noiseonthenet.space\/noise\/"},{"@type":"ListItem","position":2,"name":"Stacking bits"}]},{"@type":"WebSite","@id":"https:\/\/noiseonthenet.space\/noise\/#website","url":"https:\/\/noiseonthenet.space\/noise\/","name":"Noise On The Net","description":"Sharing adventures in code","publisher":{"@id":"https:\/\/noiseonthenet.space\/noise\/#\/schema\/person\/88c3a70f2b23480197bc61d6e1e2e982"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/noiseonthenet.space\/noise\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/noiseonthenet.space\/noise\/#\/schema\/person\/88c3a70f2b23480197bc61d6e1e2e982","name":"marco.p.v.vezzoli","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g","caption":"marco.p.v.vezzoli"},"logo":{"@id":"https:\/\/secure.gravatar.com\/avatar\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g"},"description":"Self taught assembler programming at 11 on my C64 (1983). Never stopped since then -- always looking up for curious things in the software development, data science and AI. Linux and FOSS user since 1994. MSc in physics in 1996. Working in large semiconductor companies since 1997 (STM, Micron) developing analytics and full stack web infrastructures, microservices, ML solutions","sameAs":["https:\/\/noiseonthenet.space\/noise\/","https:\/\/www.linkedin.com\/in\/marco-paolo-valerio-vezzoli-0663835\/"],"url":"https:\/\/noiseonthenet.space\/noise\/author\/marco-p-v-vezzoli\/"}]}},"jetpack_featured_media_url":"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/daria-nepriakhina-xY55bL5mZAM-unsplash-reduced.jpg?fit=1200%2C775&ssl=1","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/pdDUZ5-5V","jetpack-related-posts":[],"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/posts\/367","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/comments?post=367"}],"version-history":[{"count":5,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/posts\/367\/revisions"}],"predecessor-version":[{"id":394,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/posts\/367\/revisions\/394"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/media\/389"}],"wp:attachment":[{"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/media?parent=367"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/categories?post=367"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/tags?post=367"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}