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