OrderedList.frink

View or download OrderedList.frink in plain text format


use binarySearch.frink

/** NOTE:  Frink now has an internal OrderedList implementation, so this is
    obsolete.

    This class represents an ordered list, which is a list that enforces
    a certain order on its elements at insertion.  It can be created with a
    comparison function which determines how items are placed into the list. */

class OrderedList
{
   /** The default comparision function. */
   class var defaultComparisonFunction = {|a,b|  a <=> b}

   /** The comparison function that will be used to compare items. */
   var comparisonFunction

   /** The ordered data stored in a normal array. */
   var orderedData = new array

   /** Construct an OrderedList with the default comparison function. */
   new[] :=
   {
      comparisonFunction = defaultComparisonFunction
   }
   
   /** Construct an OrderedList with the specified comparision function.  The
       comparison function should take two arguments */

   new[compareFunction] :=
   {
      comparisonFunction = compareFunction
   }

   /** Inserts a new value, ordered, into the list. */
   insert[value] :=
   {
      insertBefore = getIndex[value]
      orderedData.insert[insertBefore, value]
   }

   /** Returns the index of the item to insert before.  if the item is found
       anywhere in this list, this returns the index of one of the matching
       items in the list.  If the item is not found in the list, this still
       returns the index before which it should be inserted. */

   getIndex[item] := binarySearch[orderedData, item, comparisonFunction]

   /** Returns the number of items in the list. */
   getItemCount[] := length[orderedData]

   /** Returns the specified item in the list, by index. */
   getItem[index] := orderedData@index

   /** Removes the specified index from the list (and returns its value.) */
   removeIndex[index] := orderedData.remove[index]

   /** Pops the first item from the list and returns it. */
   popFirst[] := orderedData.popFirst[]

   /** Pops the last item from the list and returns it. */
   popLast[] := orderedData.pop[]
}


View or download OrderedList.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 17646 days, 9 hours, 38 minutes ago.