Evlan
Set
Last updated at 2005/07/10 22:46:11 PDT by Temporal

This is "evlan.org/utility/Set", a module implementing a data structure which represents an immutable set. It wraps a sorted array.

```# Evlan API - Standard library for the Evlan programming language
# Copyright (C) 2002-2005 Kenton Varda
# <http://www.evlan.org>
#
# (Note:  This license is temporary, and will change to something more
# friendly once I have decided how exactly I want Evlan licensed.)
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version
# 2 of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
# General Public License for more details.
#
# You should have received a copy of the GNU Library General Public
# License along with this program; if not, write to the Free
# Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
# MA 02111-1307, USA
# ====================================================================

Set where
Sort = import "Sort"

#This module implements a data structure representing an immutable
#set.  In many cases, this is more efficient than using a
#MutableSet.
Set = object of
#Constructs a set containing the given array of elements.
#isBefore is a function which takes two elements and returns
#true if the first element comes before the second in sorted
#order or false otherwise.  If isBefore(a, b) and isBefore(b, a)
#both return false, then a and b match.
#
#This constructor is O(n lg n) as the elements must be sorted.
#If you know that they will already be sorted, call
#makeAlreadySorted() instead.
make = (elements, isBefore) => result where
result = makeAlreadySorted(Sort.sort(elements, isBefore), isBefore)

#Represents an empty set.
empty = object of
isEmpty = true
find = key => Maybe.empty
findDefault = (key, default) => default
contains = key => false
toArray = () => {}

#Like make(), but assumes that the elements are in sorted order.
#This is faster, as the elements would otherwise be sorted
#first.  This constructor is O(1).
makeAlreadySorted = (sortedElements, isBefore) => result where
find = (start, end, key) => result where
index = Sort.binarySearch(sortedElements, element => isBefore(element, key))
result =
if index == sortedElements.size
or isBefore(key, sortedElements[index])
then Maybe.empty
else Maybe.make(sortedElements[index])
result =
if sortedElements.size == 0
then empty
else object of    #interface defined here
isEmpty = false
find = key => \find(0, sortedElements.size, key)
findDefault = (key, default) => result where
findResult = find(key)
result = if findResult.isEmpty then default else findResult.value
contains = key => not find(key).isEmpty
toArray = () => sortedElements

#The following functions are operations which may be performed
#on a set.  They are not methods of a set because they are
#independent of the set's implementation.  These are slow (O(n))
#and should be avoided.  If you want to be able to efficiently
#modify the contents of a set, use MutableSet instead.

#Insert the given key into the set.  isBefore must be the same
#comparison function originally used to construct the set.  If
#the key already exists in the set, the old value will be
#replaced.
insert = (set, key, isBefore) => result where
items = set.toArray()
index = Sort.binarySearch(items, element => isBefore(element, key))
newParts =
if index < items.size and not isBefore(key, items[index])
then array of
Array.getInterval(items, 0, index)
{key}
Array.getInterval(items, index+1, items.size)
else array of
Array.getInterval(items, 0, index)
{key}
Array.getInterval(items, index, items.size)
result = makeAlreadySorted(Array.join(newParts), isBefore)

#Finds the value in the set matching the given key, calls
#updateItem on it, and replaces the value with the result.  The
#result must have the same position in sorted order as its
#original value.  isBefore must be the same comparison function
#originally used to construct the set.  If no value matching the
#key exists in the set, the set is unchanged.
update = (set, key, updateItem, isBefore) => result where
items = set.toArray()
index = Sort.binarySearch(items, element => isBefore(element, key))
newParts = array of
Array.getInterval(items, 0, index)
{updateItem(items[index])}
Array.getInterval(items, index+1, items.size)
result =
if index < items.size and not isBefore(key, items[index])
then makeAlreadySorted(Array.join(newParts), isBefore)
else set

#Removes the value matching the given key from the set, if one
#is found.  isBefore must be the same comparison function
#originally used to construct the set.
remove = (set, key, isBefore) => result where
items = set.toArray()
index = Sort.binarySearch(items, element => isBefore(element, key))
newParts = array of
Array.getInterval(items, 0, index)
Array.getInterval(items, index+1, items.size)
result =
if index < items.size and not isBefore(key, items[index])
then makeAlreadySorted(Array.join(newParts), isBefore)
else set```
evlan.org © Copyright 2003-2005 Kenton Varda
Powered by Io Community Manager, Evlan, and FreeBSD