Lifo

Last In, First Out: implementations of mutable and immutable stacks in pure Ruby.

• Installation
• Available stacks
• Usage
  • Lifo::Stack
    • Pushing and popping
    • Empty stacks
    • Iterating, copying and comparing
  • Lifo::ImmutableStack
    • What does "immutable" mean?
    • Creating a stack
    • Pushing values
    • Looking at the top value
    • Removing the top value
    • Empty stacks
    • Keeping old versions ("undo")
    • Iterating and converting
    • Comparing stacks
    • A caveat: the values themselves
• Development
• Contributing
• License
• Code of Conduct

Install the gem and add to the application's Gemfile by executing:

bundle add lifo

If bundler is not being used to manage dependencies, install the gem by executing:

gem install lifo

Both are Enumerable, yield their values from top to bottom, and share the core method names (push, push_all, push_all_reverse, pop, peek, size, empty?), but they differ in what those methods do. Only Lifo::Stack also offers clear and pop(n).

Because pop means something different in each class, do not swap one for the other without checking every call site.

Each stack is documented in its own section below. Load the gem with require "lifo" to make all of them available.

Use Lifo::Stack when you want a plain, cheap stack that you modify in place, like an Array used with push and pop. It is backed by an Array, so push and pop run in (amortized) constant time and nothing is copied.

require "lifo"

stack = Lifo::Stack.new(1, 2)   # values are pushed in order, like push_all
stack << 3
stack # => #<Lifo::Stack [3, 2, 1] (top first)>

stack.peek # => 3
stack.pop  # => 3
stack.size # => 2

push (alias <<) puts a value on top. push_all pushes several values, so the last one ends up on top, while push_all_reverse puts the first one on top. All of them modify the stack and return it, so calls can be chained. push_all_reverse needs a finite collection, such as an Array or a Range.

stack = Lifo::Stack.new
stack.push(1).push(2)          # => #<Lifo::Stack [2, 1] (top first)>
stack.push_all([3, 4])         # => #<Lifo::Stack [4, 3, 2, 1] (top first)>
stack.push_all_reverse([5, 6]) # => #<Lifo::Stack [5, 6, 4, 3, 2, 1] (top first)>

pop removes and returns the top value, just like Array#pop. This is the opposite of Lifo::ImmutableStack#pop, which returns a new stack. pop(n) removes the top n values and returns them as an array with the former top value last, like Array#pop(n). That order means push_all puts them back:

stack = Lifo::Stack.new(1, 2, 3)

removed = stack.pop(2) # => [2, 3]
stack                  # => #<Lifo::Stack [1] (top first)>

stack.push_all(removed)
stack                  # => #<Lifo::Stack [3, 2, 1] (top first)>

Like Array#pop(n), it returns fewer values if the stack is smaller and never raises for that. Anything other than a non-negative Integer raises ArgumentError.

clear removes all values and returns the stack.

pop returns nil on an empty stack instead of raising, while peek raises Lifo::EmptyStackError. Since a stack may also hold nil values, use empty? to tell an empty stack apart from a popped nil:

stack = Lifo::Stack.new

stack.pop  # => nil
stack.peek # raises Lifo::EmptyStackError: cannot peek into an empty stack

value = stack.pop unless stack.empty?

Lifo::Stack is Enumerable and yields its values from top to bottom, so map, select, include?, first, to_a and friends work as expected. Methods like map return plain arrays, not stacks.

stack = Lifo::Stack.new(1, 2, 3)

stack.to_a                      # => [3, 2, 1]
stack.map { |value| value * 2 } # => [6, 4, 2]
stack.first                     # => 3

• dup (and clone) create an independent copy: pushing to or popping from one does not affect the other. The values themselves are not copied.
• == compares contents and is only true for another Lifo::Stack holding equal values in the same order. In particular, a Lifo::Stack is never equal to a Lifo::ImmutableStack.
• Since a stack can change, it does not define hash or eql? and should not be used as a Hash key. Use a Lifo::ImmutableStack for that.
• It is not safe to modify from several threads at once without your own locking.

Use Lifo::ImmutableStack when you want to pass stacks around freely, keep earlier versions, or share them between threads without worrying about anything changing unexpectedly.

With Ruby's built-in Array, push and pop change the array you call them on:

array = [1, 2]
array.push(3)
array # => [1, 2, 3]  (the original was modified)

An immutable data structure is never modified after it has been created. Instead, every operation leaves the original untouched and returns a new value:

require "lifo"

empty = Lifo::ImmutableStack.new
one   = empty.push(1)

empty # => #<Lifo::ImmutableStack [] (top first)>
one   # => #<Lifo::ImmutableStack [1] (top first)>

Note that empty is still empty after calling push. The most common mistake when starting out is to throw away the return value:

stack = Lifo::ImmutableStack.new
stack.push(1)        # Wrong: the new stack is discarded
stack.size           # => 0

stack = stack.push(1) # Right: keep the new stack
stack.size           # => 1

Why bother? Since nothing can change behind your back, you can hand a stack to any part of your program (or to another thread) without worrying that someone else modifies it. You also get "undo" for free: just keep the old version around. Despite the copying semantics, push and pop are cheap (constant time), because a new stack shares its contents with the old one instead of duplicating them.

stack = Lifo::ImmutableStack.new

stack.empty? # => true
stack.size   # => 0

Unlike Lifo::Stack.new, the constructor takes no values. To start with some, use push_all or push_all_reverse (see below).

push returns a new stack with the value on top. << is an alias, so calls can be chained:

stack = Lifo::ImmutableStack.new.push(1).push(2).push(3)
stack # => #<Lifo::ImmutableStack [3, 2, 1] (top first)>

stack = Lifo::ImmutableStack.new << "a" << "b"
stack # => #<Lifo::ImmutableStack ["b", "a"] (top first)>

To push many values at once, use push_all (the last value ends up on top) or push_all_reverse (the first value ends up on top):

base = Lifo::ImmutableStack.new.push(0)

base.push_all([1, 2, 3])         # => #<Lifo::ImmutableStack [3, 2, 1, 0] (top first)>
base.push_all_reverse([1, 2, 3]) # => #<Lifo::ImmutableStack [1, 2, 3, 0] (top first)>

push_all_reverse needs a finite collection, such as an Array or a Range.

peek returns the top value without removing it:

stack = Lifo::ImmutableStack.new.push(1).push(2)

stack.peek # => 2
stack.size # => 2 (nothing was removed)

pop returns a new stack without the top value. It does not return the removed value, so use peek first if you need it:

stack = Lifo::ImmutableStack.new.push(1).push(2).push(3)

top       = stack.peek # => 3
remaining = stack.pop  # => #<Lifo::ImmutableStack [2, 1] (top first)>

stack # => #<Lifo::ImmutableStack [3, 2, 1] (top first)>  (unchanged)

Calling peek or pop on an empty stack raises Lifo::EmptyStackError (a subclass of Lifo::Error). Check with empty? first if you are not sure:

stack = Lifo::ImmutableStack.new

stack.peek # raises Lifo::EmptyStackError: cannot peek into an empty stack
stack.pop  # raises Lifo::EmptyStackError: cannot pop from an empty stack

stack = stack.pop unless stack.empty?

Because operations never modify a stack, every earlier version stays valid. Branching off from a common starting point is safe:

history = Lifo::ImmutableStack.new.push("draft 1").push("draft 2")

edited   = history.push("draft 3")
reverted = history.pop

edited.to_a   # => ["draft 3", "draft 2", "draft 1"]
history.to_a  # => ["draft 2", "draft 1"]
reverted.to_a # => ["draft 1"]

ImmutableStack is Enumerable and yields its values from top to bottom, so all the usual methods like map, select, include?, first, sum and to_a are available:

stack = Lifo::ImmutableStack.new.push_all([1, 2, 3])

stack.each { |value| puts value } # prints 3, 2, 1
stack.to_a                        # => [3, 2, 1]
stack.map { |value| value * 2 }   # => [6, 4, 2]
stack.include?(2)                 # => true
stack.first(2)                    # => [3, 2]
stack.sum                         # => 6

Methods like map return plain arrays, not stacks. To get a stack back, push the result again:

doubled = Lifo::ImmutableStack.new.push_all_reverse(stack.map { |value| value * 2 })
doubled # => #<Lifo::ImmutableStack [6, 4, 2] (top first)>

Two stacks are equal (==, eql?) when they hold equal values in the same order. They can therefore be used as Hash keys or in a Set:

a = Lifo::ImmutableStack.new.push(1).push(2)
b = Lifo::ImmutableStack.new.push(1).push(2)

a == b             # => true
a.equal?(b)        # => false (two distinct objects)
{ a => :found }[b] # => :found

Hashing looks at every value, and so does comparing two stacks of the same size, so both take time proportional to the size of the stack. Stacks of different sizes are told apart immediately. A Lifo::ImmutableStack is never equal to a Lifo::Stack, even if they hold the same values.

The stack itself is frozen, but the values you put into it are not copied or frozen. If you push a mutable object, such as an Array or a String, changing that object afterwards changes what the stack contains:

list  = [1]
stack = Lifo::ImmutableStack.new.push(list)

list << 2
stack.peek # => [1, 2]

To be fully immutable, push frozen values (for example list.freeze, or "text".freeze) or values that are immutable anyway, like numbers and symbols.

After checking out the repo, run bin/setup to install dependencies. Then, run bundle exec rake to run everything CI runs:

When you change a public method, update its YARD comment in lib/ and its signature in sig/ along with the code.

To experiment with the code, run bin/console for an interactive prompt.

To install this gem onto your local machine, run bundle exec rake install. To release a new version, update the version number in version.rb, and then run bundle exec rake release, which will create a git tag for the version, push git commits and the created tag, and push the .gem file to rubygems.org.

Bug reports and pull requests are welcome on GitHub at https://github.com/leoarnold/lifo. This project is intended to be a safe, welcoming space for collaboration, and contributors are expected to adhere to the code of conduct.

The gem is available as open source under the terms of the MIT License.

Everyone interacting in the Lifo project's codebases, issue trackers, chat rooms and mailing lists is expected to follow the code of conduct.