Here you go. I'll try and add comments to the code later
To summarize the code below: It'll work on any size array with any number of entries in any range. In fact, if you want to change it from int's to double or bytes or whatever you only have to change 2 function parameters. It will sort by the # of times a number has appeared in the array, and returns a key/value data pair that you can use to retrieve the both the numeric value + the number of times that number appeared in the array. Not including the hash table code (since hash tables really should be a standard part of BMAX, imo) and the test code, this is only 63 lines long with liberal whitespace.
First, you'll need to include my THashTable code (newly updated for this challenge...had to add a few functions)
And then here is the actual source code, broken in to a few functions so you can access the data at various stages of the analysis.
The function call to AnalyzeArray() first creates a hash-table with "Key/data" pairs of the format (Number, #OfTimesAppearingInArray)
Next, the function AnalyzeTable() gets all of the entries from the hash table and sorts them and returns the sorted list.
PrintResults then loops through the hash table entry pairs (of type gHashEntry), and prints the "Key/data" pairs.
The function AnalyzeArray just combines all of the above steps and functions into one function. If you trace through this function and the functions it calls it should make things clearer. Note that AnalyzeArray() also returns the sorted result list (as a Tlist), so you can easily get rid of the call to "PrintResults()" in AnalyzeArray (it's really just in there for testing & to display that this works) and then just do whatever you want to the returned list.
Anyhow, here is the code
Note I've included some test data in the code that runs and prints out the results.
The output is as follows for the data shown below
******Be sure to replace the line "Include "Thashtable.bmx" in the above source with the appropriate path of the Hastable code provided above!!******
Lastly, if you just want to get at the values of the "two best" numbers, grab the first 2 entries from the list returned by "AnalyzeArray()" and then cast them to a "gHashEntry" and get their ".name" field - which is a string representation of the number - and then cast it to int, like so
If you want to know how many times the "best" value showed up in the array, you need to access the .obj field of the item in the list (each entry has a .name/.obj field which correspond to the "number/#oftimesappearing" key/data pair).
So to get the # of times the best value appeared we do this
To summarize the code below: It'll work on any size array with any number of entries in any range. In fact, if you want to change it from int's to double or bytes or whatever you only have to change 2 function parameters. It will sort by the # of times a number has appeared in the array, and returns a key/value data pair that you can use to retrieve the both the numeric value + the number of times that number appeared in the array. Not including the hash table code (since hash tables really should be a standard part of BMAX, imo) and the test code, this is only 63 lines long with liberal whitespace.
First, you'll need to include my THashTable code (newly updated for this challenge...had to add a few functions)
''Constructor( capacity:int ) - returns a new Hashtable object with a maximum capacity = to '' the parameter provided. Utilize this function to create '' any and all hashtable objects. '' '' ''InsertEntry(name:string,o:object) - add an object to the table, the name is used to '' to generate an index 0-Capacity, selecting the list. '' multiple entries with the same name are permitted using '' this method. If you want to guarantee that only one '' entry exists per a given name, use the '' insertUniqueName( ) method '' ''insertUniqueName( name:string, o:object) - this method guarantees that the object specified '' will be the only object for that particular name. '' ''insertUniqueNamedObject( name:string, obj:object) - this method guarantees that there will only be '' one copy of the object specified by the obj parameter '' in the hashtable. There may be multiple entries for '' the name however. Using this instead of the '' standard InsertEntry() method when you want to make '' sure the same object (assuming it is the same name) '' is not duplicated in the table. '' ''RemoveNamed(name:string) - Removes all entries with the name specified from the hash table. '' Note, this does not return those objects. '' ''RemoveNamedObject(name:string, obj:object) - removes any entries from the bucket specified by the name '' parameter whose object value matches the object specified '' by the obj parameter. This method lets you quickly remove '' a single object without removing all objects that share the '' same name (such as RemoveNamed() does.) '' ''RemoveObject( obj:object ) - searches every bucket in the hash table for the specified object and removes '' all traces of it from the hash table. Note: This method can be relatively slow '' on large tables, and if possible you should use RemoveNamedObject() instead. '' ''GetEntry:object(name:string) - grab the first entry for a given name. You must cast it back to its original '' type before using it,myobject=myType(GetEntry(name:string)) '' ''GetMultipleEntries:object [](name:string) - returns an array of objects (entries) that match the '' given name parameter. This is useful when you intend '' to store a list of objects with a given name index '' ''Grow( growthsize:int ) - Increases the number of buckets in the hash array by growthsize. '' ''removeAllEntries() - removes all objects from the hash table '' ''removeNamed( name ) removes all entries with the given name from the hash table '' '' '' Regarding Unique Entries '' ------------------------ ''If you want to ensure there is only one entry for a given name key, there are two approaches you can take. ''If you want or need to ensure there is no entry for a given name key before you do an insert - or if there ''is an entry already present you want to handle it in some manner you should ''call getEntry( name ). If this is null, it's safe to insert. If this returns an object calling InsertEntry() ''will insert another entry with the same name. While you can access multiple entries with the same name via ''the method GetMultipleEntries(name), doing so is not ideal if you simply want a single entry per name. ''So the first approach is to call getEntry, and deal with the object returned (if any) and then do your ''insertion. ''The second approach comes into play if you don't need access to any entry that might already be stored ''under the insert name, but simply want to guarantee the entry you are inserting is the only one for ''that name. Calling insertUniqueName(name) will erase any entries already stored under "name" and guarantees that ''there is only one unique entry for the name provided. ''''''''''''''''''''''''''' '' ''HASHTABLE OBJECT '' ''- M.Laurenson/Defoc8 2006 ''- S.Hofslund/SculptureOfSoul 2006 '' ''- major modifications: the introduction of a capacity parameter, getMultipleEntries(), '' insertUniqueName(), insertUniqueNamedObject(), removeNamed(), removeNamedObject(), removeObject(), and '' Grow() methods and the Constructor() function some error checking code, document modification '' as well as a new and much more effective hash algorithm added by S.Hofslund (SculptureOfSoul) '''''''''''''''''''''''''''' Type THashTable Field _table:TList[] Field _capacity:Int ?debug Global _indirectconstruct:Int ? Method New() ?debug Assert _indirectconstruct, "Use THashtable.Constructor() to create a new hash table." ? EndMethod Function Constructor:THashTable( capacity:Int ) ?debug _indirectconstruct = True ? Local retobj:THashTable = New THashTable retobj._capacity=capacity retobj._table=retobj._table[..capacity] For Local n:Int=0 Until capacity retobj._table[n]=New TList Next ?debug _indirectconstruct = False ? Return retobj EndFunction Method Grow( growthsize:Int ) If growthsize <= 0 Return Local oldtable:TList[] oldtable = _table _capacity = (_capacity + growthsize) _table = New TList[_capacity] For Local i:Int = 0 Until _capacity _table[i] = New TList Next 'regenerate indexes for and reinsert all of the old tables entries For Local n:Int = 0 Until oldtable.length For Local entry:gHashEntry = EachIn oldtable[n] InsertEntry( entry.name, entry.obj ) Next Next EndMethod Method genIndex(name:String) Local val:Int=0 Local temp:Int For Local n:Int=0 Until name.length 'the following is commented out because it is neither as fast or as efficient as the one used below ' val:+ (name[n])^2 + (name[n]*(n^2)) + (name[n]Mod 3 * name[n]) val= (val Shl 3) + val + name[n] 'commented out for the same reason ' val:+ (name[n])^(((name.length + 1 - n)Mod 2) + 2) Next 'call Abs on the index because it might be negative (in the case of an integer overflow). Return Abs(val Mod (_capacity ) ) EndMethod Method insertEntry(name:String ,obj:Object) Local index:Int=genIndex(name$) Local entry:gHashEntry=New gHashEntry entry.name=name entry.obj=obj entry.link=_table[index].AddLast(entry) EndMethod 'object must have an overriden compare method! Method insertSortedEntry(name:String,obj:Object,ascending:Int=True) Local index:Int=genIndex(name$) Local entry:gHashEntry=New gHashEntry entry.name=name entry.obj=obj entry.link=_table[index].AddLast(entry) _table[index].Sort(ascending) EndMethod Method sortEntriesNamed(name:String,ascending=True) Local index:Int=genIndex(name) _table[index].sort(ascending) EndMethod Method sortAll(ascending:Int=True) For Local iter:Int=0 Until _table.length _table[iter].sort(ascending) Next EndMethod Method insertUniqueNamedObject( name:String, obj:Object ) Local index:Int = genIndex(name) internal_removeNamedObject( obj, index ) Local entry:gHashEntry = New gHashEntry entry.name = name entry.obj = obj entry.link = _table[index].Addlast(entry) EndMethod Method insertUniqueName(name:String,obj:Object) Local index:Int=genIndex(name$) internal_removeNamed( name, index ) Local entry:gHashEntry=New gHashEntry entry.name=name entry.obj=obj entry.link=_table[index].AddLast(entry) EndMethod Method getEntry:Object(name:String) Local index:Int=genIndex(name) Local link:TLink = _table[index]._head Local entry:Object Rem the old for eachin variety of the loop, replaced below by the hand rolled loop. Uncomment this and comment the the below code to see for yourself the speed difference it makes (only noticeable when doing 1000's of operations though) For Local entry:gHashEntry=EachIn _table[index] If(entry.name=name) Return(entry.obj) EndIf Next EndRem 'Print "_table[index].count() =" + _table[index].count() For Local iter = 0 Until _table[index].count() 'handrolling the loop as it turns out to be much faster than a For..Eachin entry = link._succ._value 'do the keys match? If gHashEntry(entry).name = name Return gHashEntry(entry).obj EndIf link = link._succ 'Return(entry.obj) 'EndIf Next Return Null EndMethod Method getMultipleEntries:Object[](name:String) Local index:Int = genIndex(name) Local retarray:Object[] = New Object[getEntryCount(index)] Local objectcount:Int For Local entry:gHashEntry=EachIn _table[index] If entry.name = name retarray[objectcount] = entry.obj objectcount:+ 1 EndIf Next 'resize the array to objectcount elements. retarray = retarray[..objectcount] Return retarray EndMethod Method getAllEntryPairsAsArray:gHashEntry[]() Local numEntries:Int Local retArray:gHashEntry[] Local entryCount:Int For Local n:Int=0 Until _capacity numEntries:+ getEntryCount(n) Next retArray = New gHashEntry[numEntries] entryCount = 0 For Local iter = 0 Until _capacity For Local entry:gHashEntry = EachIn _table[iter] retArray[entryCount] = entry entryCount:+ 1 Next Next retArray = retArray[..entryCount] Return retArray EndMethod Method getAllEntryPairsAsList:TList() Local retlist:TList = CreateList() For Local iter = 0 Until _capacity For Local entry:gHashEntry = EachIn _table[iter] retlist.addlast(entry) Next Next Return retlist EndMethod Rem The below are leftovers from a variety of tests. I figured someone might find these of interest. Anyhow, except in certain special situations, I found them to be slower than the code I'm using for getMultipleEntries. Feel free to experiment though. Method getMultipleEntries2:Object[](name:String) Local index:Int = genIndex(name) Local objectcount:Int For Local entry:gHashEntry=EachIn _table[index] If entry.name = name objectcount:+ 1 EndIf Next Local retarray:Object[] = New Object[objectcount] objectcount = 0 For Local entry:gHashEntry = EachIn _table[index] If entry.name = name retarray[objectcount] = entry.obj objectcount:+ 1 EndIf Next 'resize the array to objectcount elements. 'MemCopy( retarray, retarray, SizeOf(retarray[0]) * objectcount) 'retarray = retarray[..objectcount] 'above method is faster Return retarray EndMethod EndRem Rem Method getMultipleEntries3:Objwrapper(name:String) Local index:Int = genIndex(name) Local retarray:Object[] = New Object[getEntryCount(index)] Local objectcount:Int Local wrapper:objwrapper = New objwrapper For Local entry:gHashEntry=EachIn _table[index] If entry.name = name retarray[objectcount] = entry.obj objectcount:+ 1 EndIf Next 'resize the array to objectcount elements. 'MemCopy( retarray, retarray, SizeOf(retarray[0]) * objectcount) wrapper.objarray = retarray wrapper.length = retarray.length Return wrapper EndMethod EndRem 'simply a slightly faster version of removeNamed. Faster because the index is provided 'and doesn't need to be generated. This method is called by insertUniqueName Method internal_removeNamed( name:String, index:Int ) For Local entry:gHashEntry = EachIn _table[index] If(entry.name = name) entry.link.Remove() EndIf Next EndMethod Method removeNamed:Int( name:String ) 'returns the # of objects removed Local index:Int = genIndex(name) Local remove_count:Int = 0 For Local entry:gHashEntry = EachIn _table[index] If(entry.name = name) entry.link.Remove() remove_count:+ 1 EndIf Next Return remove_count EndMethod Method internal_removeNamedObject( obj:Object, index:Int ) For Local entry:gHashEntry = EachIn _table[index] If(entry.obj = obj) entry.link.Remove() EndIf Next EndMethod Method removeNamedObject:Int( name:String, obj:Object ) 'returns # removed Local index:Int = genIndex(name) Local remove_count:Int = 0 For Local entry:gHashEntry = EachIn _table[index] If(entry.obj = obj) entry.link.Remove() remove_count:+ 1 EndIf Next Return remove_count EndMethod 'this loops through every bucket in the hash table Method removeObject:Int( obj:Object ) 'returns # removed Local remove_count:Int = 0 For Local iter = 0 Until _table.length For Local entry:gHashEntry = EachIn _table[iter] If entry.obj = obj entry.link.remove() remove_count:+ 1 EndIf Next Next Return remove_count EndMethod Method removeAllEntries() For Local n:Int=0 Until _capacity _table[n].clear() Next EndMethod Method getEntryCount:Int(index:Int) If (index >= 0) And (index < _capacity) Return _table[index].count() EndIf EndMethod EndType Type gHashEntry Field name:String Field obj:Object Field link:TLink Method Compare(pHashEntry:Object) 'Try ?debug Print "gHashEntry.compare called" ? ' Print "Compare result: " + obj.Compare2(gHashEntry(pHashEntry).obj) Return obj.Compare(gHashEntry(pHashEntry).obj) 'Catch ex:Object 'EndTry EndMethod EndType
And then here is the actual source code, broken in to a few functions so you can access the data at various stages of the analysis.
The function call to AnalyzeArray() first creates a hash-table with "Key/data" pairs of the format (Number, #OfTimesAppearingInArray)
Next, the function AnalyzeTable() gets all of the entries from the hash table and sorts them and returns the sorted list.
PrintResults then loops through the hash table entry pairs (of type gHashEntry), and prints the "Key/data" pairs.
The function AnalyzeArray just combines all of the above steps and functions into one function. If you trace through this function and the functions it calls it should make things clearer. Note that AnalyzeArray() also returns the sorted result list (as a Tlist), so you can easily get rid of the call to "PrintResults()" in AnalyzeArray (it's really just in there for testing & to display that this works) and then just do whatever you want to the returned list.
Anyhow, here is the code
Strict Include "THashtable.bmx" Function CreateArrayAnalysisTable:THashTable( array:Int[] ) Local hash:THashtable = THashtable.Constructor( array.length ) Local entry:Object For Local iter = 0 Until array.length entry = hash.getEntry( String(array[iter]) ) If(entry) hash.insertUniqueName( String(array[iter]) , String((Int(String(entry))+1 ))) Else hash.insertentry( String(array[iter]), "1" ) EndIf Next Return hash EndFunction Function AnalyzeTable:TList( hash:THashtable ) Local allEntries:TList allEntries = hash.GetAllEntryPairsAsList() allEntries.Sort(False) Return allEntries EndFunction Function PrintResults( resultlist:TList ) For Local entry:ghashentry = EachIn resultlist Print "Number:" + entry.name + "~t~t~tCount: " + String(entry.obj) Next EndFunction Function AnalyzeArray:TList( array:Int[] ) Local hash:Thashtable Local resultlist:TList hash = CreateArrayAnalysisTable( array ) resultlist = AnalyzeTable( hash ) PrintResults( resultlist ) Return resultlist EndFunction '------------------------------------------------------------------------------------------------- ' TEST DATA AND CODE BELOW '------------------------------------------------------------------------------------------------- Global testarray:Int[] = New Int[9] testarray[0] = 4 testarray[1] = 5 testarray[2] = 6 testarray[3] = 7 testarray[4] = 6 testarray[5] = 5 testarray[6] = 6 testarray[7] = 7 testarray[8] = 8 Global testarray2:Int[] = New Int[12] testarray2[0] = -53 testarray2[1] = 326 testarray2[2] = 53 testarray2[3] = -326 testarray2[4] = 326 testarray2[5] = 32 testarray2[6] = -3 testarray2[7] = -53 testarray2[8] = 0 testarray2[9] = 12 testarray2[10] = -53 testarray2[11] = 32 Print "*********Analyzing TestArray**********" AnalyzeArray( testarray ) Print "**************************************" Print "~n~n~n" Print "*********Analyzing TestArray2*********" AnalyzeArray( testarray2 ) Print "**************************************"
Note I've included some test data in the code that runs and prints out the results.
The output is as follows for the data shown below
Global testarray:Int[] = New Int[9] testarray[0] = 4 testarray[1] = 5 testarray[2] = 6 testarray[3] = 7 testarray[4] = 6 testarray[5] = 5 testarray[6] = 6 testarray[7] = 7 testarray[8] = 8 *********Analyzing TestArray********** Number:6 Count: 3 Number:7 Count: 2 Number:5 Count: 2 Number:8 Count: 1 Number:4 Count: 1 ************************************** Global testarray2:Int[] = New Int[12] testarray2[0] = -53 testarray2[1] = 326 testarray2[2] = 53 testarray2[3] = -326 testarray2[4] = 326 testarray2[5] = 32 testarray2[6] = -3 testarray2[7] = -53 testarray2[8] = 0 testarray2[9] = 12 testarray2[10] = -53 testarray2[11] = 32 *********Analyzing TestArray2********* Number:-53 Count: 3 Number:326 Count: 2 Number:32 Count: 2 Number:53 Count: 1 Number:-326 Count: 1 Number:-3 Count: 1 Number:0 Count: 1 Number:12 Count: 1 **************************************
******Be sure to replace the line "Include "Thashtable.bmx" in the above source with the appropriate path of the Hastable code provided above!!******
Lastly, if you just want to get at the values of the "two best" numbers, grab the first 2 entries from the list returned by "AnalyzeArray()" and then cast them to a "gHashEntry" and get their ".name" field - which is a string representation of the number - and then cast it to int, like so
local resultlist:tlist local bestresult:int local secondbestresult:int resultlist = AnalyzeArray( somearray ) bestresult = int(gHashEntry(resultlist.ValueAtIndex( 0 )).name) secondbestresult = int(gHashEntry(resultlist.ValueAtIndex( 1 )).name)
If you want to know how many times the "best" value showed up in the array, you need to access the .obj field of the item in the list (each entry has a .name/.obj field which correspond to the "number/#oftimesappearing" key/data pair).
So to get the # of times the best value appeared we do this
local resultlist:tlist local bestresult:int local bestresultcount:int resultlist = AnalyzeArray( somearray ) bestresult = int(gHashEntry(resultlist.ValueAtIndex( 0 )).name) bestresultcount = int(gHashEntry(resultlist.ValueAtIndex( 0 )).obj)