Class Models for Lua

# Ordered Set

## `loop.collection.OrderedSet`

Class of objects that store a set of values arranged in a particular order. As a usual set, it does not allow duplicates and checks for containment efficiently. The values are stored like a linked list, therefore the sequence can only be iterated in a single direction, i.e. cannot get the previous value. Insertions and removals at any point of the sequence are done efficiently. This class is useful for storing a large set of values without repetitions that are organized in a particular order and accepts frequent insertions and removals at any point of the sequence during iterations.

Stores each value of the set by mapping it to its successor. Therefore, all values are stored as mapped keys. The only exception is the last value that provides no successor. Each instance maps two special values, one to the first value of the sequence and other to the last value. Instances behave like linked lists that does not allow repeated values.

## Behavior

### Fields

`firstkey`: userdata
  Special value used as the key that maps the first value of the set.

### Methods

`contains(value)`
  Return true if a `value` belongs to the set or false otherwise.
`empty()`
  Return true if there is no value inserted in the set or false otherwise.
`first()`
  Returns the first value of the set.
`insert(value [, previous])`
  Inserts `value` in the set after the value `previous`. If `previous` is not provided then `value` is inserted as the last value of the set. `value` is returned if successfully inserted. If `previous` does not belong to the set or `value` is already inserted then the call has no effect and no value is returned.
`last()`
  Returns the last value of the set.
`popfront()`
  Removes the first value of the set and then returns it. If the set is empty this function has no effect.
`previous(value [, start])`
  Searches for the previous value of `value` starting from `start`. If `start` is not provided the search is done through the entire set. If `value` is the first value of the set then the special key that holds the first value is returned. If `value` is found in the set, its previous value is returned, otherwise no value is returned.
`pushback(value)`
  Adds `value` to the end of the set. `value` is returned if successfully added. If `value` is already inserted then the call has no effect and no value is returned.
`pushfront(value)`
  Adds `value` to the start of the set. `value` is returned if successfully added. If `value` is already inserted then the call has no effect and no value is returned.
`remove(value [, start])`
  Searches for `value` and removes it from the set starting the search after the value of `start`. If `start` is not provided the search is done through the entire set. The removed value is returned or no value is returned if `value` is not found.
`replace(old, new [, start])`
  Searches for value `old` and replaces it by value `new` starting the search after the value of `start`. If `start` is not provided the search is done through the entire set. The replaced value is returned or no value is returned if `old` is not found or if `new` already belongs to the set.
`sequence()`
  Returns an iterator for use with the `for` statement of Lua. The `for` variables receive the current value and the previous value, respectively.

## Remarks

- Instances cannot store the name of class members as strings. To do so, use the class operations over an empty table like in the following example:

      OrderedSet = require "loop.collection.OrderedSet"
      set = {}
      OrderedSet.insert(set, "first")
      OrderedSet.insert(set, "insert")
      OrderedSet.insert(set, "last")
      OrderedSet.insert(set, "previous")
      OrderedSet.insert(set, "sequence")
      for word in OrderedSet.sequence(set) do
        io.write(word, " ")
      end

- This class provides operations of some traditional data structures as aliases of its methods.
  Set operations
    - `add(value)` alias for `pushback(value)`
  Stack operations
    - `push(value)` alias for `pushfront(value)`
    - `pop()` alias for `popfront()`
    - `top()` alias for `first()`
  Queue operations
    - `enqueue(value)` alias for `pushback(value)`
    - `dequeue()` alias for `popfront()`
    - `head()` alias for `first()`
    - `tail()` alias for `last()`

## Examples

### Broad-first and depth-first searches for directed graphs.

    local oo         = require "loop.base"
    local OrderedSet = require "loop.collection.OrderedSet"

    local function inbroad(queue, head)
      head = queue[head]
      if head then
        for _, node in ipairs(head) do
          queue:enqueue(node)
        end
        return head
      end
    end
    function broadsearch(node)
      queue = OrderedSet()
      queue:enqueue(node)
      return inbroad, queue, OrderedSet.firstkey
    end

    local function indepth(stack, top)
      top = stack[top]
      if top then
        for _, node in ipairs(top) do
          stack:insert(node, top)
        end
        return top
      end
    end
    function depthsearch(node)
      stack = OrderedSet()
      stack:push(node)
      return indepth, stack, OrderedSet.firstkey
    end

    Node = oo.class()

    function Node:goesto(...)
      for i=1, select("#", ...) do
        self[#self + 1] = select(i, ...)
      end
    end

    A = Node{ name = "A" }
    B = Node{ name = "B" }
    C = Node{ name = "C" }
    D = Node{ name = "D" }

    A:goesto(B,C)
    B:goesto(D)
    C:goesto(D)
    D:goesto(A)

    io.write("broad-first search:")
    for node in broadsearch(A) do
      io.write(" ", node.name)
    end
    print()

    io.write("depth-first search:")
    for node in depthsearch(A) do
      io.write(" ", node.name)
    end
    print()

Copyright (C) 2004-2008 Tecgraf, PUC-Rio

This project is currently being maintained by Tecgraf at PUC-Rio.