iteratable

Documentation

Overview

Package iteratable implements iteratable container data structures.

Set is a speical purpose set type, suitable mainly for implementing algorithms around scanners, parsers, etc. These kinds of algorihms are often more straightforward to describe as set constructions and operations.

Unusually, all set operations are destructive!

BSD License

Copyright (c) 2017–20, Norbert Pillmayer

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of this software nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Index

• Constants
• type Order
• type Set
  • func NewSet(size int) *Set
  • func (s *Set) Add(item interface{})
  • func (s *Set) Contains(item interface{}) bool
  • func (s *Set) Copy() *Set
  • func (s *Set) Difference(other *Set) *Set
  • func (s *Set) Each(mapper func(interface{}))
  • func (s *Set) Empty() bool
  • func (s *Set) Equals(other *Set) bool
  • func (s *Set) Exhaust()
  • func (s *Set) First() interface{}
  • func (s *Set) FirstMatch(predicate func(interface{}) bool) interface{}
  • func (s *Set) Intersection(other *Set) *Set
  • func (s *Set) Item() interface{}
  • func (s *Set) Iterate(exhaust bool)
  • func (s *Set) IterateOnce()
  • func (s *Set) Len() int
  • func (s *Set) Less(i, j int) bool
  • func (s *Set) Next() bool
  • func (s *Set) Remove(item interface{}) interface{}
  • func (s *Set) Size() int
  • func (s *Set) Sort(order Order) *Set
  • func (s *Set) Stagnates() bool
  • func (s *Set) Subset(predicate func(interface{}) bool) *Set
  • func (s *Set) Swap(i, j int)
  • func (s *Set) Take() interface{}
  • func (s *Set) Union(other *Set) *Set
  • func (s *Set) Values() []interface{}

Constants

const (
	Once         bool = false
	Exhaustively bool = true
)

If a set is set up for exhaustion, the iteration will return items until no more items are in the set, otherwise it will iterate over each item once.

Types

type Order

type Order func(x, y interface{}) bool

Order is a comparator used for sorting the elements of a set. It should return true, if x < y for a given interpretation of '<'.

type Set

type Set struct {
	// contains filtered or unexported fields
}

Set is a speical purpose set type, suitable mainly for implementing algorithms around scanners, parsers, etc. These kinds of algorihms are often more straightforward to describe as set constructions and operations.

func NewSet

func NewSet(size int) *Set

NewSet creates a new iteratable set. Clients may provide initial elements and an estimation for the capacity needed.

func (*Set) Add

func (s *Set) Add(item interface{})

Add adds a new item to a set, if it is not already present. If an once-iteration has already read item, and the item is added again to the set, the once-iteration will not process the item again. For an exhaust-iteration, the added item is put at the end of the list.

func (*Set) Contains

func (s *Set) Contains(item interface{}) bool

Contains returns true, if item is contained in the set, false otherwise.

func (*Set) Copy

func (s *Set) Copy() *Set

Copy makes a copy of a set.

func (*Set) Difference

func (s *Set) Difference(other *Set) *Set

Difference returns s without the elements contained in other, too.

func (*Set) Each

func (s *Set) Each(mapper func(interface{}))

Each applies a mapper function to each element in the set.

func (*Set) Empty

func (s *Set) Empty() bool

Empty returns true, if the set contains items, false otherwise.

func (*Set) Equals

func (s *Set) Equals(other *Set) bool

Equals returns true if both sets contain the same elements.

func (*Set) Exhaust

func (s *Set) Exhaust()

Exhaust is a shortcut for Iterate(true). The iteration will return items until no more items are in the set.

func (*Set) First

func (s *Set) First() interface{}

First returns the first (random) element of a set, or nil.

func (*Set) FirstMatch

func (s *Set) FirstMatch(predicate func(interface{}) bool) interface{}

FirstMatch is a more efficient shortcut for S.Copy().Subset(...).First(), i.e. it finds a random element in S with a given condition. The condition is given as a boolean function. If it is nil, it is treated as "any".

func (*Set) Intersection

func (s *Set) Intersection(other *Set) *Set

Intersection returns the common elements of two given sets.

func (*Set) Item

func (s *Set) Item() interface{}

Item returns the item at the currenct iteration position, if any.

func (*Set) Iterate

func (s *Set) Iterate(exhaust bool)

Iterate sets up a set for iteration.

We do not use a separate iterator type, thus effectively locking a set to a single client at a time. However, for succinct implementations of certain algorithms, this way it's much more straightfoward to read and understand. Moreover, we allow for modification of the set while it is being iterated.

So, with

var S iteratable.Set{...}

we could write iterator code something like this:

iter := S.Iterator()
for iter.Next() {
     item := iter.Item()
}

but instead, we rather write

S.InterateOnce()                 S.Exhaust()
for S.Next() {                   for S.Next() {
     item := S.Item()                 item := S.Take()
}                                }

This may seem like a neglectable difference, even violating established OO practice (and in a certain way it is), but some algorithms are easier to follow without having iterators all over the place, which are used within a single function anyway.

If exhaust is set, the iteration will return items until no more items are in the set, otherwise it will iterate over each item once.

func (*Set) IterateOnce

func (s *Set) IterateOnce()

IterateOnce is a shortcut for Iterate(false). Will iterate over each item once.

func (*Set) Len

func (s *Set) Len() int

Len is for sort.interface; not intended for public use.

func (*Set) Less

func (s *Set) Less(i, j int) bool

Swap is for sort.interface; not intended for public use.

func (*Set) Next

func (s *Set) Next() bool

Next moves the iteration cursor by one position. It returns true, if an item is available at the new position.

func (*Set) Remove

func (s *Set) Remove(item interface{}) interface{}

Remove removes an item from a set, if present. It will return the item if it was found, nil otherwise.

func (*Set) Size

func (s *Set) Size() int

Size returns the number of items in the set.

func (*Set) Sort

func (s *Set) Sort(order Order) *Set

Sort sorts the elements of a set according to a given order. It returns the input set with elements sorted (not a copy).

func (*Set) Stagnates

func (s *Set) Stagnates() bool

Stagnates signals that every item in the set has been scheduled at least once for re-consideration.

func (*Set) Subset

func (s *Set) Subset(predicate func(interface{}) bool) *Set

Subset removes all elements of a set not fulfilling a condition. The condition is given as a boolean function. If it is nil, s is returned unchanged.

func (*Set) Swap

func (s *Set) Swap(i, j int)

Swap is for sort.interface; not intended for public use.

func (*Set) Take

func (s *Set) Take() interface{}

Take returns the item at the current iteration position, if any. The item is removed from the set.

func (*Set) Union

func (s *Set) Union(other *Set) *Set

Union merges the elements of two sets.

func (*Set) Values

func (s *Set) Values() []interface{}

Values returns all items of a set.