Jump to content

Sky Slate Blueberry Blackcurrant Watermelon Strawberry Orange Banana Apple Emerald Chocolate
Photo

List manipulation functions


  • Please log in to reply
28 replies to this topic
Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Lists are important building blocks for maintaining varying length of sequences, like applications, websites, window ID's, etc. AHK offers practically just one simple function for handling them
if Var in MatchList 
if Var not in MatchList
if Var contains MatchList
if Var not contains MatchList
With new user functions we can provide tools for manipulating these comma delimited lists. In the script below I tried to strike a balance between code length and running time. I tested them for function, but there still could be some bugs in it.
ListAdd(item,pos,ByRef list)  ; Add item to the list at pos, < 0 counted from the end
{                             ; ErrorLevel = 1 if pos was truncated, = 0 otherwise
   _list_ = ,%list%,          ; enclose in commas for search
   IfLess pos,0, {            ; pos = -1,-2... counted from right
      _pos := -pos
      StringGetPos chpos, _list_, `,, R%_pos%
   }
   Else IfGreater pos,1, {    ; pos = 2,3... counted from left
      StringGetPos chpos, _list_, `,, L%pos%
      IfEqual chpos,-1, StringLen chpos, _list_
   }                          ; pos = 0, 1 and normal cases ...
   StringLeft leftlist, list, % chpos - 1
   StringTrimLeft rightlist, list, %chpos%
   IfNotEqual rightlist,, SetEnv item, %item%`,
   IfNotEqual  leftlist,, SetEnv item, `,%item%
   list = %leftlist%%item%%rightlist%
}

ListCut(pos, ByRef list)      ; Remove & return item from list at pos, < 0 from end
{
   _list_ = ,%list%,          ; enclose in commas for search
   Transform p1, ABS, pos
   p2 := p1 + 1
   IfGreater pos,-1, {        ; pos > 0 counted from left, pos = 0: empty
      StringGetPos ch1, _list_, `,, L%p1%
      StringGetPos ch2, _list_, `,, L%p2%
   }
   Else IfLess pos,0, {       ; pos < 0 counted from right
      StringGetPos ch2, _list_, `,, R%p1%
      StringGetPos ch1, _list_, `,, R%p2%
   }
   IfGreater ErrorLevel,0, Return   ; nothing found
   StringMid item, list, ch1+1, ch2-ch1-1
   StringLeft leftlist, list, % ch1 - 1
   StringTrimLeft rightlist, list, %ch2%
   IfEqual     rightlist,, SetEnv list, %leftlist%
   Else IfEqual leftlist,, SetEnv list,%rightlist%
   Else SetEnv list, %leftlist%,%rightlist%
   Return %item%
}

ListItem(pos,list)            ; Return item at pos, < 0 from the end
{
   _list_ = ,%list%,          ; enclose in commas for search
   Transform p1, ABS, pos
   p2 := p1 + 1
   IfGreater pos,-1, {        ; pos > 0 counted from left, pos = 0: empty
      StringGetPos ch1, _list_, `,, L%p1%
      StringGetPos ch2, _list_, `,, L%p2%
   }
   Else IfLess pos,0, {       ; pos < 0 counted from right
      StringGetPos ch2, _list_, `,, R%p1%
      StringGetPos ch1, _list_, `,, R%p2%
   }
   IfGreater ErrorLevel,0, Return   ; nothing found
   StringMid item, list, ch1+1, ch2-ch1-1
   Return %item%
}

ListPos(item,list)            ; Return position of 1st  copy of item, 0 if not found
{
   _list_ = ,%list%,          ; enclose in commas for search
   StringGetPos ch, _list_, `,%item%`,
   StringLeft list, _list_, % ch+1
   StringReplace list, list, `,, `,, UseErrorLevel
   Return %ErrorLevel%
}

ListReplace(itm1,itm2,ByRef list) ; Replace all itm1 with itm2 in list, itm2="": delete
{                             ; ErrorLevel = # items replaced
   list = ,%list%,            ; enclose in commas for search
   _it_ = ,%itm2%,
   IfEqual itm2,, SetEnv _it_, `,
   Loop
   {                          ; StringReplace does not delete consecutive items
      StringReplace list, list, `,%itm1%`,, %_it_%, UseErrorLevel
      IfEqual ErrorLevel,0, Break
      cnt += ErrorLevel
   }
   ErrorLevel := cnt
   StringTrimLeft  list, list, 1
   StringTrimRight list, list, 1
}
Split or merge of lists is easy, you don't need functions for them. As the need arises I will add more functions, like sort, or removing duplicates. Any ideas, what else could be useful?

Edit 2006.02.25. The full version is here. There is also an experimental version. It uses the global variable "_" to store the list separator, which can be set to any character, like "_ = `;".

Edit 2006.03.17. Minor bugfix, version 1.5/1.51 uploaded
Edit 2008.12.19. Source moved to AutoHotkey.net

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Here is the second part (less tested).
ListLen(list)                 ; how many items constitute the list

{

   IfEqual list,, Return 0

   StringReplace list, list, `,, `,, UseErrorLevel

   Return ErrorLevel + 1

}



ListSplit(pos,list,ByRef list1,ByRef list2) ; Split list at pos, < 0 counted from end

{       ; pos >=0: list1:=item_1,...,item_pos;   list2:=item_pos+1,...{end}

        ; pos < 0: list1:=item_1,...,item_pos-1; list2:=item_pos,...{end}

   _list_ = ,%list%,          ; enclose in commas for search

   IfLess pos,0, {

      p := 1-pos

      StringGetPos ch, _list_, `,, R%p%

      IfGreater ErrorLevel,0, SetEnv ch, 0

   }

   Else {

      p := 1+pos

      StringGetPos ch, _list_, `,, L%p%

      IfGreater ErrorLevel,0, StringLen ch, _list_

   }

   StringLeft     list1, list,% ch-1

   StringTrimLeft list2, list, %ch%

}



ListPart(pos1,pos2,list)      ; Returns list_pos1,...,list_pos2, pos < 0: from end

{

   _list_ = ,%list%,          ; enclose in commas for search

   IfLess pos1,0, {

      p := 1-pos1

      StringGetPos ch1, _list_, `,, R%p%

      IfGreater ErrorLevel,0, SetEnv ch1, 0

   }

   Else {

      StringGetPos ch1, _list_, `,, L%pos1%

      IfGreater ErrorLevel,0, StringLen ch1, _list_

   }

   IfLess pos2,0, {

      p := -pos2

      StringGetPos ch2, _list_, `,, R%p%

      IfGreater ErrorLevel,0, SetEnv ch2, 0

   }

   Else {

      p := 1+pos2

      StringGetPos ch2, _list_, `,, L%p%

      IfGreater ErrorLevel,0, StringLen ch2, _list_

   }

   StringMid list, list, % ch1+1, % ch2-ch1-1

   Return list

}



ListSort(ByRef list)          ; ByRef wrapper for recursive sort

{

   list := List_Sort(ListLen(list),list)

}



ListMerge(list1,list2)        ; Merge sorted lists

{                             ; If listX = item, insert in the right place

   IfEqual list1,, Return list2

   IfEqual list2,, Return list1

   p1 = 1

   p2 = 1

   i1 := ListItem(1,list1)

   i2 := ListItem(1,list2)

   Loop

   {

      IfLess i1,%i2%, {       ; Ascending <-- change for other order

         list = %list%,%i1%

         p1++

         i1 := ListItem(p1,list1)

         IfNotEqual i1,, Continue

         list := list "," ListPart(p2,-1,list2)

         break                ; list1 is exhausted

      }

      Else {

         list = %list%,%i2%

         p2++

         i2 := ListItem(p2,list2)

         IfNotEqual i2,, Continue

         list := list "," ListPart(p1,-1,list1)

         break                ; list2 is exhausted

      }

   }

   StringTrimLeft list, list, 1

   Return list

}



List_Sort(len,list)           ; Returns Recursive Merge-sorted list

{                             ; No ByRef with recursion in AHK Vers 1.0.31

   IfLess len,2, Return list  ; list of length 0,1 is sorted

   Transform L1, BitShiftRight, len, 1 ; integer halve

   L2 := len - L1

   Return ListMerge(List_Sort(L1,ListPart(1,L1,list)),List_Sort(L2,ListPart(L1+1,-1,list)))

}
Notes for ListSort: The applied algorithm is asymptotically one of the fastest, taking time proportional to n.log(n) for length-n lists. The comparison is done by AHK's internal algorithm, providing ascending sort. If you don't like it, replace the instruction in ListMerge()
IfLess i1,%i2%, {
with
IfGreater i1,%i2%, {
or for a more general way, with
If MyLess(i1,i2)

      {
You have to provide the MyLess(x,y) function, which returns 1 if you consider x < y, and 0 otherwise. For example
MyLess(x,y)

{

   IfGreater x,%y%, Return 1

   Return 0

}
will sort the list descending (6,5,4,3...). Try it with
list = 6,5,3,2,01,4

ListSort(list)

MsgBox %list%
Edit 20050416: the function ListMerge is separated from List_Sort, as it is useful for its own right.

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Here is the third part, removing identical items from lists. The script below is faster than sorting. For each item in the list a local variable is generated, named by the hex representation of the name of the item (which could contain illegal characters for a variable name, like "."). If this name is new, it is the first occurrence of the item, otherwise we cut this item off the list.
Hexify(x)         ; Convert a string to a huge hex number starting with X

{

   StringLen Len, x

   format = %A_FormatInteger%

   SetFormat Integer, H

   hex = X

   Loop %Len%

   {

      Transform y, ASC, %x%   ; ASCII code of 1st char, 15 < y < 256

      StringTrimLeft y, y, 2  ; Remove leading 0x

      hex = %hex%%y%

      StringTrimLeft x, x, 1  ; Remove 1st char

   }

   SetFormat Integer, %format%

   Return hex

}



ListUniq(ByRef list)          ; Remove repeated items from list

{

   list = %list%,

   c = 0

   Loop

   {

      StringGetPos d, list, `,,, %c% ; search from c

      IfLess d,0, {           ; No more ","

         StringTrimRight list, list, 1

         Return

      }

      StringMid item, list, % c+1, % d-c

      hex := Hexify(item)     ; Item might not be a valid name

      IfEqual %hex%,, {       ; 1st occurrence

         %hex% = 1

         c := d + 1

         Continue

      }                       ; Already found

      StringLeft      left, list,% c-1

      StringTrimLeft right, list, %d%

      list = %left%%right%

   }

}
Test it with
list = 0,1,2,1,3,02,4,2,1

ListUniq(list)

MsgBox %list%


Chris
  • Administrators
  • 10727 posts
  • Last active:
  • Joined: 02 Mar 2004
Very nice. Perhaps these list management functions are abstract enough to be a good general-purpose library. If so, they can eventually be consolidated and put into a new "standard includes" folder that can be distributed with AutoHotkey.

To include something from the standard folder, the syntax might enclose the filename in <> such as:
#Include

But no final decision on syntax has been made. Maybe someone will think of something better.

Jon
  • Members
  • 349 posts
  • Last active: Aug 30 2011 08:35 PM
  • Joined: 28 Apr 2004
Nice script, Thanks for putting them together Lazlo. I'm sure I'll be finding them useful in the future.

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Thanks for the nice words. I applied some minor changes (removed unnecessary %'s, partial results; added tests). I'll keep the current version here, as it might become too long for posting.

Invalid User
  • Members
  • 447 posts
  • Last active: Mar 27 2012 01:04 PM
  • Joined: 14 Feb 2005
I was also thinking of putting together a pile of lifunctions for lists and other functions I use often in scripts. My pile-o-functions should include:

Move a list item up one
Move a list item down
Select next item
Select pevious item
Drag and Drop onto list
Remove item from list
Filtering script for mass drag and drop to exclude certain defined files
Move group of selected items up
Move group of selected items down
Remove groups of selected items
Script for adding items to the list via gui button or other means(menu item)
Script to demonstrate two different actions to take upon selecting an item with single click and double clicks

This list is longer in my head but I will work on it.
my lame sig :)

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
What you, Invalid User, describe is mostly the application layer above the low level List function library. They include drag-and-drop addition, making multiple selections in a GUI and acting on them at button press or click, etc. What I could add to the library, are:

Move a list item up/down by a specified number of positions
Move a list item to a new position
Swap 2 items

However, it is not clear how selecting the next/previous item should work. If you mean, returning items from pos+1 or pos-1, it is trivial. If you mean locations relative to the last access point, we need to mark somehow where we were. We must not change the list, and inside a function we don't know the name of a parameter (the list), so we cannot attach a variable to the list, telling the last access point. If there are multiple lists, global variables of fixed names won't help. Hashing the content of the list could give a name for the access point variable, but adding an item to the list invalidates this name. It is also slow, needing a full scan of the list each time we need to find out the location of the last access. If only we could access the memory location or the pointer there where the list is stored...

Mass add: it looks like merging or concatenating lists, and optionally removing repetitions.

Remove items, which contain a specified string: it is a good idea. Useful, for example, to remove files with the extension .bak, .tmp, etc. from a list of files. Especially, when wildcards will be available in AHK.

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
I updated the List functions library List.ahk. The changes are:
; Version 1.1: 2005.04.17

;              Minor cleanups (removed unnecessary %'s, partial results...)

;              Added test code

;              User function Precede is used in ListMerge and ListSort

; Version 1.2: 2005.04.20

;              Change: Removed ByRef in ListAdd and ListReplace to Return list

;              Added ListSwap(pos1,pos2,list) - Swap items at pos1 and pos2

;                    ListMove(pos1,pos2,list) - Move item from pos1 to pos2

;                    ListReloc(pos,ofst,list) - Move item relative to current pos

;                    ListDel(pos,list)        - Delete item, Return list

;                    ListRemove(text,list)    - Remove items containing text

;                    ListKeep(text,list)      - Remove items NOT containing text
The complete list of the implemented List functions is now
ListAdd(item,pos,list)        ; Add item to the list at pos, < 0 counted from the end

ListCut(pos, ByRef list)      ; Remove & return item from list at pos, < 0 from end

ListDel(pos,list)             ; Del item from list at pos, < 0 from end

ListItem(pos,list)            ; Return item at pos, < 0 from the end

ListLen(list)                 ; how many items constitute the list

ListPart(pos1,pos2,list)      ; Returns list_pos1,...,list_pos2, pos < 0: from end

ListPos(item,list)            ; Return position of 1st copy of item, 0 if not found

ListReplace(itm1,itm2,list)   ; Replace all itm1 with itm2 in list, itm2="": delete

ListSplit(pos,list,ByRef lst1,ByRef lst2) ; Split list at pos, < 0 from end

ListSwap(pos1,pos2,list)      ; Returns list with items at pos1 & pos2 swapped

ListMove(pos1,pos2,list)      ; Move item from pos1 to pos2, return new list

ListReloc(pos,ofst,list)      ; Move item relative to its current position

ListRemove(text,list)         ; Remove items containing text

ListKeep(text,list)           ; Remove all items NOT containing text

Precede(x,y)                  ; =1 if x precedes y (used in ListMerge, ListSort)

ListMerge(list1,list2)        ; Merge sorted lists

ListSort(ByRef list)          ; ByRef wrapper for recursive sort

_Sort(len,lst)                ; Returns Recursive Merge-sorted list

Hexify(x)                     ; Convert a string to a huge hex number starting with X

ListUniq(ByRef list)          ; Remove repeated items from list, preserve order

Hash16(x)   ; 16-bit hash related to DJB2 hash(i) = 33*hash(i-1) + x[i]

TEST(A,x)   ; Display expression x and its value: TEST(A_LineNumber,3*a+2)

TEST1(A,x)  ; Display 1 prior line I =, the expression, its value and the new I

TEST2(A,x)  ; Display expression x, its value and 2 ByRef values I and J


toralf
  • Moderators
  • 4035 posts
  • Last active: Aug 20 2014 04:23 PM
  • Joined: 31 Jan 2005
Hi Lazlo,

Very nice and usefull functions.

Something that might be an additional usefull function: ListFillControl(ControlName,GuiID,List)
Ciao
toralf
 
I use the latest AHK version (1.1.15+)
Please ask questions in forum on ahkscript.org. Why?
For online reference please use these Docs.

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Thanks for the suggestion. What should this function do? Replace commas with pipes? It is one line. What else?

I deliberately left out anything GUI related, since this library provides the low level functions, the building blocks for complex applications with GUI's, file I/O, etc. If they use well tested powerful functions, their development will be faster and less error prone.

toralf
  • Moderators
  • 4035 posts
  • Last active: Aug 20 2014 04:23 PM
  • Joined: 31 Jan 2005
You are right, it is just a two line function (StringReplace and GuiControl) Might not be as useful as I thought in the beginning.
Ciao
toralf
 
I use the latest AHK version (1.1.15+)
Please ask questions in forum on ahkscript.org. Why?
For online reference please use these Docs.

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Version 1.3 is uploaded. Two functions are changed
ListRemove(text,opt,list)     ; Remove items containing text. ErrorLevel = #removed items

ListKeep(text,opt,list)       ; Keep only items containing text, ErrorLevel = #kept items
There is a new parameter, opt < 0, = 0, > 0: text searched at the end, anywhere, in the beginning of items, respectively. It is to avoid surprises, like Chief.Executive.Officer is treated like a program having .Exe as a substring. With opt = -1 only those .exe occurrences are processed, which are at the end of the items, like file extensions.

maxinuruguay
  • Members
  • 15 posts
  • Last active: Nov 06 2006 10:24 PM
  • Joined: 09 Dec 2005
Is there anyway for the library to use a different delimiter? Maybe a global variable to set the delimiter. It would really be of great help to me. Thanks.

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
I uploaded an experimental version to http://www.hars.us/SW/List1.ahk. It uses the global variable "_" to store the list separator, which can be set to any character, like "_ = `;". (The semicolon needs to be escaped with the back apostrophe.)