/**
 * Interface to ATerm's IndexedSets.
 *
 * @since   0.11
 * @author  Martin Bravenboer <martin.bravenboer@gmail.com>
 */
module collection/set/indexed

/**
 * IndexedSet representations
 */
signature
  constructors
    IndexedSet : ImplDep -> IndexedSet

/**
 * IndexedSet construction and deconstruction
 */
strategies

  /**
   * Creates a new set with default initial size and maximum load.
   *
   * @type  _ -> IndexedSet
   */
  new-iset =
    new-iset(|117,75)

  /**
   * Creates a new set with specified initial size and maximum load.
   *
   * @param  Int, Initial size of internal storage
   * @param  Int, 0-100.
   * @type   _ -> IndexedSet
   */
  new-iset(|initial_size, max_load) =
    prim("SSL_indexedSet_create", initial_size, max_load); !IndexedSet(<id>)

  /**
   * Releases all memory occupied by the set.
   * A destroyed set can no longer be used.
   *
   * @type  IndexedSet -> IndexedSet
   */
  iset-destroy =
    ?IndexedSet(set); prim("SSL_indexedSet_destroy", set); !IndexedSet(<id>)

  /**
   * Removes all elements from the set.
   *
   * @type  IndexedSet -> IndexedSet
   */
  iset-clear =
    ?IndexedSet(set); prim("SSL_indexedSet_reset", set); !IndexedSet(<id>)

/**
 * IndexedSet operations
 */
strategies

  /**
   * Adds elem to the set.
   *
   * If the elem is already in the set, then on_old is applied to
   * its index.
   *
   * @param  Int -> a
   * @type   IndexedSet -> (Int | a )
   */
  iset-add(on_old|elem) =
    ?IndexedSet(set); prim("SSL_indexedSet_put", on_old | set, elem)

  /**
   * Ensures that elem is in the set.
   *
   * @type IndexedSet -> IndexedSet
   */
  iset-add(|elem) =
    ?set; iset-add(id|elem); !set

  /**
   * Ensures that all elems in the specified list are in the set.
   *
   * @type IndexedSet -> IndexedSet
   */
  iset-addlist(|lst) =
    ?set; <map({ elem: ?elem; <iset-add(|elem)> set })> lst; !set

  /**
   * Fails if elem is not in the set.
   *
   * @type  IndexedSet -> IndexedSet
   */
  iset-contains(|elem) =
    where(iset-get-index(|elem))

  /**
   * Removes elem from set.
   *
   * If the elements is not in the set, then this strategy does not fail.
   *
   * @type  IndexedSet -> IndexedSet
   */
  iset-remove(|elem) =
    ?IndexedSet(set); prim("SSL_indexedSet_remove", set, elem); !IndexedSet(<id>)
  
  /**
   * Returns all elements of the set.
   *
   * @type  IndexedSet(a) -> List(a)
   */
  iset-elements =
    ?IndexedSet(set); prim("SSL_indexedSet_elements", set)


  /**
   * Unites a set with another.
   *
   * @param  IndexedSet
   * @type   IndexedSet -> IndexedSet
   */
  iset-union(|set2) =
    ?set1
  ; where(<iset-elements; map({ elem: ?elem; <iset-add(|elem)> set1 })> set2)

  /**
   * Intersects a set with another.
   *
   * @param  IndexedSet
   * @type   IndexedSet -> IndexedSet
   */
  iset-isect(|set2) =
    ?set1
  ; where(iset-elements
          ; map({ elem:
                  ?elem
                ; (<iset-contains(|elem)> set2
                   <+ <iset-remove(|elem)> set1)
                }))

  /**
   * Checks whether one set is a subset of another.
   *
   * @param  IndexedSet
   * @type   IndexedSet -> IndexedSet
   */
  iset-subset(|set2) =
    ?set1
  ; where(<iset-elements; map({ elem: ?elem; <iset-contains(|elem)> set1 })> set2)

  /**
   * Checks whether a set has equal contents as another.
   *
   * @param  IndexedSet
   * @type   IndexedSet -> IndexedSet
   */
  iset-eq(|set2) =
    ?set1
  ; where(iset-subset(|set2))
  ; where(<iset-subset(|set1)> set2)
  
  /**
   * Applies s to the elements of a Set until it no more elements are added to this set.
   *
   * @param a -> List(a)
   * @type  Set(A) -> Set(A)
   */
  iset-fixpoint(s) =
    ?set@IndexedSet(_)
    ; repeat(
        where(
          iset-elements
        ; list-some(
            s
          ; list-some({new:
              ?new
            ; <iset-add(fail|new)> set
            })
          )
        )
      )

/**
 * Low-level set strategies (having knowledge of an index)
 */
strategies

  /**
   * Gets the index of elem in the set.
   *
   * Fails if elem is not in the set.
   *
   * @type  IndexedSet -> Int
   */
  iset-get-index(|elem) =
    ?IndexedSet(set); prim("SSL_indexedSet_getIndex", set, elem)

  /**
   * Gets the element at index in the set.
   *
   * Always provide a valid index: behaviour is undefined if the index
   * is not in the set.
   *
   * @type  IndexedSet -> Int
   */
  iset-get-elem(|index) =
    ?IndexedSet(set); prim("SSL_indexedSet_getElem", set, index)