Zallafar's Queue Array

From Gwen Morse's Wiki
Revision as of 21:26, 23 July 2010 by Eachna (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
;;
;; From Zallafar of Lusternia (Tim Fredenburg)
;;

###########################################################
#
# QUEUES
#
###########################################################

# TinyFugue doesn't provide any data structures so we fabricate our own.
# These "queues" end up being used as arrays, lists, etc.


###########################################################
# Prioritized queue
#
# The first field in each item is a number, a priority.  The items in the
# queue are sorted by priority, highest to lowest.
# The rest of the fields are the item itself.

# The arguments are the queue name, the priority, and the item.
# The item may have multiple fields.
# Returns the position in the queue that the item went into.
# Macro is invisible to make mecho output more understandable.
/def -i pqueueAdd = \
       /set pqueueAddSpot=1 %; \
       /while ( pqueueAddSpot <= queueSize( {1} ) ) \
               /eval /set pqueueAddQueueItem=$[queueAt( {1}, pqueueAddSpot)] %; \
;               /eval /echo %pqueueAddSpot %pqueueAddQueueItem %; \
               /if ( $( /phigher %{2} %pqueueAddQueueItem ) ) /break %; /endif %; \
               /eval /set pqueueAddSpot=$[pqueueAddSpot + 1] %; \
       /done %; \
;       /eval /echo Goes in spot %pqueueAddSpot %; \
       /queueInsert %{1} %pqueueAddSpot %{-1}

; This macro is used so that in calling it we get the item parsed into its
; separate fields.  Then {2} will be only the item's priority.
; Uses > rather then >= so that the item added first has higher priority in a tie.
/def -i phigher = /result  {1} > {2}
       

###########################################################
# Sorted queue
#
# When squeueAdd is called it will use the defined comparison routine to
# determine where to insert the new item in the queue.  The comparison
# routine must be named <queuename>Compare.  It will be passed two
# strings, new item and existing item, and must return >0 for greater than,
# 0 for equal, and <0 for less than.
#
# Sorts low to high, with a new equal item coming after other equal items.

# The arguments are the queue name, the item to add.
# The item may have multiple fields.
# Returns the position in the queue that the item went into.
# Macro is invisible to make mecho output more understandable.
/def squeueAdd = \
       /let spot=1 %; \
       /while ( spot <= queueSize( {1} ) ) \
               /let existingItem=$[queueAt( {1}, spot)] %; \
               /let compareFunc=%{1}Compare %; \
               /eval /test %{compareFunc}( {-1}, {existingItem} ) %; \
               /if ( {?} < 0 ) /break %; /endif %; \
               /let spot=$[spot + 1] %; \
       /done %; \
       /queueInsert %{1} %spot %{-1}

/def stringCompare = /return $[ strcmp( {1}, {2} ) ]

/def testCompare = /stringCompare $( /field1 %1 ) $( /field1 %2 ) %; /return {?}


###########################################################
# Queues
#
# A queue is just a series of global variables.  E.g.:
#       queueHerbsThing1
#       queueHerbsThing2
#       ...
# Push means to add at the end of the queue.
# Pop means to remove from the front of the queue.
# The name of the queue ("Herbs" in the example) must always be specified.
#       queuePush( "Herbs", "calamus" )
#       queuePush( "Herbs", "horehound" )
#       queueSize( "Herbs" )
#       queuePop( "Herbs" )
# It's OK to use a queue without ever having declared it ahead of time.
# In fact, there is no way to declare a queue.

# Arguments are queue name and thing to push.
# Returns number of items in queue.
# Macro is invisible to make mecho output more understandable.
/def -i queuePush = \
       /eval /eval /set queue%{1}Size $$[{queue%{1}Size} + 1] %; \
       /eval /eval /set queue%{1}Thing%%{queue%{1}Size} %{-1} %; \
       /return queue%{1}Size

# Arguments are queue name and any number of things to push.
/def -i queuePushMany = \
       /set queuePushManyWhich 2 %; \
       /while ( queuePushManyWhich <= {#} ) \
               /eval /queuePush %1 %%{%queuePushManyWhich} %; \
               /set queuePushManyItem=$[queueAt( {1}, queuePushManyWhich )] %; \
               /set queuePushManyWhich $[ queuePushManyWhich + 1 ] %; \
       /done

# Push an item onto the front of a queue (where it will be the first popped).
; Args: queue name, item
/def queuePushFront = /queueInsert %1 1 ${-1}

# Args: queue name, regexp to parse items, # of Pn to sort on, comparison func, item
# This is probably best called as a function, to avoid some quoting issues.
# E.g. /test queuePushSorted( "xx", "(\\d+)", 1, "sortDecreasing", "299" )
/def -i queuePushSorted = \
;/echo regexp |%2| %; \
       /test regmatch( {2}, {-4} ) %; \
;/echo result %?, P1 %P1 %; \
       /eval /test set( "queuePushValue=%%P%3" ) %; \
;/echo queuePushValue %queuePushValue %; \
       /set queuePushSpot=1 %; \
       /while ( queuePushSpot <= queueSize( {1} ) ) \
               /eval /test set( "queuePushQueueItem=$[queueAt( {1}, queuePushSpot)]" ) %; \
               /test regmatch( {2}, {queuePushQueueItem} ) %; \
               /eval /test set( "queuePushItemValue=%%P%3" ) %; \
               /if ( $( /%4 %queuePushValue %queuePushItemValue ) ) /break %; /endif %; \
               /eval /set queuePushSpot=$[queuePushSpot + 1] %; \
       /done %; \
       /queueInsert %{1} %queuePushSpot %{-4}

/def -i sortIncreasing = /result {1} < {2}
/def -i sortDecreasing = /result {1} > {2}

; This macro is used so that in calling it we get the item parsed into its
; separate fields.  Then {2} will be only the item's priority.
; Uses > rather then >= so that the item added first has higher priority in a tie.
/def -i phigher = /result  {1} > {2}

# Argument is the queue name.
# Returns the number of items in the queue.
# Macro is invisible to make mecho output more understandable.
/def -i queueSize = \
       /eval /eval /set queueSizeSize $$[{queue%{1}Size} + 0] %; \
       /return {queueSizeSize}

# Argument is the queue name.
# Removes the first item from the queue and returns it.
# Macro is invisible to make mecho output more understandable.
/def -i queuePop = \
       /if ( queueSize( {1} ) <= 0 ) \
               /echo POPPING EMPTY QUEUE %1 %; \
               /return "" %; \
       /endif %; \
       /eval /eval /set queueThingPopped  %%{queue%{1}Thing1} %; \
       /if ( queueSize( {1} ) > 1 ) \
               /eval /for which 1 $[queueSize( {1} ) - 1] \
                       /eval /set queue%{1}Thing%%%which %%%%queue%{1}Thing$$$[which + 1] %; \
       /endif %; \
       /eval /eval /set queue%{1}Size $$[{queue%{1}Size} - 1] %; \
       /result "%queueThingPopped"

# Argument is the queue name.
# Macro is invisible to make mecho output more understandable.
/def -i queueFlush = \
       /eval /set queue%{1}Size 0

# Arguments are the queue name and the spot in the queue to return.
# Queue locations are numbered from 1.
# Macro is invisible to make mecho output more understandable.
/def -i queueAt = \
       /if /test {2} < 1  | {2} > queue%{1}Size %; /then /result "" %; /endif %; \
       /eval /set queueThingAt %%{queue%{1}Thing%{2}} %; \
       /result {queueThingAt}

# Arguments are the queue name, the spot to put the item and the
# item itself.  The current item at that spot and all following items
# are moved back one spot in the queue.
# Macro is invisible to make mecho output more understandable.
/def -i queueInsert = \
       /if ( {2} <= 0 ) \
               /echo INVALID INSERTION POINT %2, FOR QUEUE %1 %; \
               /return %; \
       /endif %; \
       /if ( {2} > queueSize( {1} ) + 1 ) \
               /echo INSERTION AT %2 BEYOND END OF QUEUE %1 %; \
               /return %; \
       /endif %; \
       /if ( queueSize( {1} ) >= {2} ) \
               /eval /for which %{2} $[queueSize( {1} )] \
                       /eval /set \
                               queue%{1}Thing$$$[%{2} + queueSize( "%{1}" ) - which + 1] \
                               %%%%queue%{1}Thing$$$[{2} + queueSize( "%{1}" ) - which] %; \
;                               queue%{1}Thing$$$[%{2} + queueSize( "%{1}" ) - %%%which + 1] \
;                               %%%%queue%{1}Thing$$$[%{2} + queueSize( "%{1}" ) - %%%which] %; \
       /endif %; \
       /eval /eval /set queue%{1}Thing%{2} %{-2} %; \
       /eval /eval /set queue%{1}Size $$[{queue%{1}Size} + 1]

# Arguments are the queue name, the spot of the existing the item and the
# new value for the item.
# Macro is invisible to make mecho output more understandable.
/def -i queueReplace = \
       /if ( {2} <= 0 ) \
               /echo INVALID REPLACEMENT POINT %2, FOR QUEUE %1 %; \
               /return %; \
       /endif %; \
       /if ( {2} > queueSize( {1} ) ) \
               /echo REPLACEMENT AT %2 BEYOND END OF QUEUE %1 %; \
               /return %; \
       /endif %; \
       /eval /eval /set queue%{1}Thing%{2} %{-2} %; \

# Arguments: queue name, the spot of the existing the item, desired field in
# item,  the new value for the field.
# Macro is invisible to make mecho output more understandable.
/def -i queueReplaceField = \
       /if ( {2} <= 0 ) \
               /echo INVALID REPLACEMENT POINT %2, FOR QUEUE %1 %; \
               /return %; \
       /endif %; \
       /if ( {2} > queueSize( {1} ) ) \
               /echo REPLACEMENT AT %2 BEYOND END OF QUEUE %1 %; \
               /return %; \
       /endif %; \
       /eval /set replaceFieldItem %%{queue%{1}Thing%{2}} %; \
       /set replaceFieldItem $(/replaceField %3 %4 %replaceFieldItem) %; \
       /eval /eval /set queue%{1}Thing%{2}=%replaceFieldItem

# Arguments: field number, new field value, all fields of item.
# Result: entire item with field replaced
/def -i replaceField = \
       /if ( {1} <= 0  |  {1} > {#} - 2 ) \
               /echo -e BAD FIELD NUMBER %1 FOR REPLACEFIELD %{*} %; \
               /result "" %; \
       /endif %; \
; Walk through each field, concatenating.  Swap in the new field as we go.
       /set replaceFieldWhich 3 %; \
       /while ( replaceFieldWhich <= {#} ) \
               /eval /set replaceFieldField %%{%replaceFieldWhich} %; \
; Swap in new value for field.
               /if ( replaceFieldWhich - 2 == {1} ) \
                       /set replaceFieldField %2 %; \
               /endif %; \
; Don't add a space separator for the first field.
               /if ( replaceFieldWhich == 3 ) \
                       /set replaceFieldResult %replaceFieldField %; \
; All subsequent fields are prefaced by a space.
               /else \
                       /set replaceFieldResult $[strcat( replaceFieldResult, " ", replaceFieldField )] %; \
               /endif %; \
               /set replaceFieldWhich $[replaceFieldWhich + 1] %; \
       /done %; \
       /result {replaceFieldResult}

# Arguments are the queue name, and the spot to delete the item from.
# All following items are moved forward one spot in the queue.
# Macro is invisible to make mecho output more understandable.
/def -i queueRemove = \
       /if ( {2} <= 0 ) \
               /echo INVALID REMOVAL POINT %2, FOR QUEUE %1 %; \
               /return %; \
       /endif %; \
       /if ( {2} > queueSize( {1} )  ) \
               /echo REMOVAL AT %2 BEYOND END OF QUEUE %1 %; \
               /return %; \
       /endif %; \
       /eval /eval /set queueThingRemoved  %%{queue%{1}Thing%{2}} %; \
       /if ( queueSize( {1} ) > {2} ) \
               /eval /for which %{2} $[queueSize( {1} ) - 1] \
                       /eval /set \
                               queue%{1}Thing%%%which \
                               %%%%queue%{1}Thing$$$[which + 1] %; \
;                               %%%%queue%{1}Thing$$$[%%%which + 1] %; \
       /endif %; \
       /eval /eval /set queue%{1}Size $$[{queue%{1}Size} - 1] %; \
       /return {queueThingRemoved}

# Searches a specific field of queue items for a matching string.
# Args: queue name, field number, string to find
# Returns item number of first matching entry, or zero on no match.
# Macro is invisible to make mecho output more understandable.
/def -i queueFindField = \
       /set findQueueSpot=1 %; \
       /eval /set findQueueLength $[queueSize( {1} )] %; \
       /while ( findQueueSpot <= findQueueLength ) \
               /eval /set findQueueItem=$[queueAt( {1}, findQueueSpot)] %; \
;               /eval /echo %findQueueSpot %findQueueItem %; \
               /eval /set findField $( /findItemField %2 %findQueueItem ) %; \
               /if ( findField =~ {3} ) \
                       /return findQueueSpot %; \
               /endif %; \
               /eval /set findQueueSpot=$[findQueueSpot + 1] %; \
       /done %; \
       /return 0

# Searches items of a queue for a matching string.
# Args: queue name, string to find
# Returns item number of first matching entry, or zero on no match.
# Macro is invisible to make mecho output more understandable.
/def -i queueFind = \
       /let spot=1 %; \
       /let qsize $[queueSize( {1} )] %; \
       /while ( spot <= qsize ) \
               /let item=$[queueAt( {1}, spot )] %; \
;               /echo %spot %item matches? %{-1} %; \
               /if ( item =~ {-1} ) \
                       /return spot %; \
               /endif %; \
               /let spot=$[spot + 1] %; \
       /done %; \
       /return 0

/def findItemField = /eval /result {$[{1} + 1]}

# Args: queue name, field number, string to find
# Returns count of matching items in queue.
# Note that called with same arguments as queueFindField.
# Macro is invisible to make mecho output more understandable.
/def -i queueCount = \
       /set countCount 0 %; \
       /set countQueueSpot=1 %; \
       /eval /set countQueueLength $[queueSize( {1} )] %; \
       /while ( countQueueSpot <= countQueueLength ) \
               /eval /set countQueueItem=$[queueAt( {1}, countQueueSpot)] %; \
;               /eval /echo %countQueueSpot %countQueueItem %; \
               /eval /set countField=$( /findItemField %2 %countQueueItem ) %; \
               /if ( countField =~ {3} ) \
                       /eval /set countCount=$[countCount + 1] %; \
               /endif %; \
               /eval /set countQueueSpot=$[countQueueSpot + 1] %; \
       /done %; \
       /return countCount


# Argument is the queue name.
# Macro is invisible to make mecho output more understandable.
/def -i queueDump = \
       /eval /for which 1 $[queueSize( {1} )] \
               /eval /_echo %%%%queue%{1}Thing%%%which

# Call a macro for each item in a queue.  Queue walked in forward direction.
; Args: queue name, macro to call with each item
; Arguments to the called macro: item number, item.
; Macro returns true to continue looping, false to stop.
/def -i queueForEach = \
       /let queueForEachWhich 1 %; \
       /let queueForEachSize $[ queueSize( {1} ) ] %; \
       /while ( queueForEachWhich <= queueForEachSize ) \
               /let queueForEachItem=$[queueAt( {1}, queueForEachWhich )] %; \
               /test %2( queueForEachWhich, {queueForEachItem} ) %; \
               /if ( ! {?} ) /break %; /endif %; \
               /let queueForEachWhich $[ queueForEachWhich + 1 ] %; \
       /done

# Call a macro for each item in a queue.  Queue walked in reverse direction.
; Args: queue name, macro to call with each item
; Arguments to the called macro: item number, item.
; Macro returns true to continue looping, false to stop.
/def -i queueForEachReverse = \
       /let queueForEachWhich $[ queueSize( {1} ) ] %; \
       /while ( queueForEachWhich >= 1 ) \
               /let queueForEachItem=$[queueAt( {1}, queueForEachWhich )] %; \
               /test %2( queueForEachWhich, {queueForEachItem} ) %; \
               /if ( ! {?} ) /break %; /endif %; \
               /let queueForEachWhich $[ queueForEachWhich - 1 ] %; \
       /done

; Simple macro to use with queueForEach to show each item in a queue.
/def queueEchoItem = /echo %{2} %; /return 1

# Convert a queue to a single string of all the items in the queue.
; Args: queue, var to get list
/def -i queueAsList = \
       /set queueAsListList=%2 %; \
       /set %queueAsListList= %; \
       /queueForEach %1 queueAsListAdd
/def queueAsListAdd = \
       /eval /set %queueAsListList %%{%queueAsListList} %{2} %; \
       /return 1

# Convert a queue to a single string of all the items in the queue, with each item
# delimited by a bar.
; Args: queue, var to get list
/def -i queueAsDelimitedList = \
       /set queueAsDelimitedListList=%2 %; \
       /set %queueAsDelimitedListList=| %; \
       /queueForEach %1 queueAsDelimitedListAdd
/def queueAsDelimitedListAdd = \
       /eval /set %queueAsDelimitedListList %%{%queueAsDelimitedListList}%{2}| %; \
       /return 1

# Make a copy of a queue.
; Args: queue to copy, queue to be the copy
/def -i queueCopy = \
       /set queueCopyDestination %2 %; \
       /queueFlush %queueCopyDestination %; \
       /queueForEach %1 queueCopyOne
/def queueCopyOne = \
       /queuePush %queueCopyDestination %2 %; \
       /return 1

# Parse out fields of a line.
/def field1 = /result {1}
/def field2 = /result {2}