- Joined
- Nov 7, 2014
- Messages
- 571
JASS:
library Set
//! novjass
General notes:
This is an attempt to implement a struct for working with sets.
References:
sets: https://en.wikipedia.org/wiki/Set_theory
union: https://en.wikipedia.org/wiki/Union_(set_theory)
intersection: https://en.wikipedia.org/wiki/Intersection_(set_theory)
difference: https://en.wikipedia.org/wiki/Complement_(set_theory)#Relative_complement
symmetric difference: https://en.wikipedia.org/wiki/Symmetric_difference
API:
// for brevity when `a` is mentioned it is the same as the Set represented by the `this` argument of the methods
// creates an empty set
static method create takes nothing returns thistype
// destroys the set
static method destroy takes nothing returns nothing
// the number of elements in the set
readonly integer size
// returns the i'th element of `a`, i must be in the range: 1 <= i <= `a`.size
method operator[] takes integer i returns integer
// adds the element `e` to the set `a`, returns `a`
method add takes integer e returns thistype
// removes the element `e` from the set `a`, returns `a`
method remove takes integer e returns thistype
// returns true if the element `e` is in the set `a`
method has takes integer e returns boolean
// returns true if `b` has all the elements of `a` or more, i.e `a` is a subset of (<=, less than or equal to, le) `b`
method le takes Set b returns boolean
// returns true if `b` has all the elements of `a` and more, i.e `a` is a strict subset of (<, less than, lt) `b`
method lt takes Set b returns boolean
// returns the union of `a` and `b`, i.e the set that contains the elements that are either in `a`, `b` or both
method union takes Set b returns Set
// returns the intersection of `a` and `b`, i.e the set that contains the elements that are both in `a` and in `b`
method intersection takes Set b returns Set
// returns the set difference of `a` and `b`, i.e the set that contains the elements that are in `a` and not in `b`
method diff takes Set b returns Set
// returns the symmetric difference of `a` and `b`, i.e the set that contains the elements that are in `a` or `b` but not both
method sym_diff takes Set b returns Set
// returns a string representation of the set
method to_string takes nothing returns string
//! endnovjass
globals
private hashtable ht = InitHashtable()
endglobals
struct Set
readonly integer size = 0
//
// the default create method is sufficient
//
method destroy takes nothing returns nothing
call FlushChildHashtable(ht, 3 * this)
call FlushChildHashtable(ht, 3 * this + 1)
call FlushChildHashtable(ht, 3 * this + 2)
call this.deallocate()
endmethod
static if DEBUG_MODE then
private static method panic takes string s returns nothing
call BJDebugMsg("|cffFF0000" + "thistype" + " error: " + s + "|r")
if 1 / 0 == 1 then // we report the error and stop the script from running any further
endif
endmethod
endif
method operator[] takes integer i returns integer
debug if not (1 <= i and i <= this.size) then
debug call panic("attempt to access the " + I2S(i) + "th element of Set(" + I2S(this) + ") but size is " + I2S(this.size))
debug endif
return LoadInteger(ht, 3 * this + 1, i)
endmethod
method add takes integer e returns thistype
local integer elems = 3 * this
if HaveSavedInteger(ht, elems, e) then
return this
endif
call SaveInteger(ht, elems, e, 1)
set this.size = this.size + 1
call SaveInteger(ht, 3 * this + 1, this.size, e)
call SaveInteger(ht, 3 * this + 2, e, this.size)
return this
endmethod
method remove takes integer e returns thistype
local integer elems
local integer list
local integer pos
local integer e_pos
local integer last_e
set elems = 3 * this
if not HaveSavedInteger(ht, elems, e) then
return this
endif
call RemoveSavedInteger(ht, elems, e)
set list = 3 * this + 1
set pos = 3 * this + 2
set e_pos = LoadInteger(ht, pos, e)
set last_e = LoadInteger(ht, list, this.size)
call SaveInteger(ht, list, e_pos, last_e)
call SaveInteger(ht, pos, last_e, e_pos)
call RemoveSavedInteger(ht, pos, e)
call RemoveSavedInteger(ht, list, this.size)
set this.size = this.size - 1
return this
endmethod
method has takes integer e returns boolean
return HaveSavedInteger(ht, 3 * this, e)
endmethod
method le takes thistype b returns boolean
local thistype a = this
local integer a_list = 3 * a + 1
local integer count = a.size
local integer i
set i = 1
loop
exitwhen i > count
if not b.has(LoadInteger(ht, a_list, i)) then
return false
endif
set i = i + 1
endloop
return true
endmethod
method lt takes thistype b returns boolean
return b.size > this.size and this.le(b)
endmethod
method union takes thistype b returns thistype
local thistype a = this
local thistype result = allocate()
local integer list
local integer count
local integer i
set list = 3 * a + 1
set count = a.size
set i = 1
loop
exitwhen i > count
call result.add(LoadInteger(ht, list, i))
set i = i + 1
endloop
set list = 3 * b + 1
set count = b.size
set i = 1
loop
exitwhen i > count
call result.add(LoadInteger(ht, list, i))
set i = i + 1
endloop
return result
endmethod
method intersection takes thistype b returns thistype
local thistype a = this
local thistype result = allocate()
local integer list
local integer count
local integer i
local integer e
set list = 3 * a + 1
set count = a.size
set i = 1
loop
exitwhen i > count
set e = LoadInteger(ht, list, i)
if b.has(e) then
call result.add(e)
endif
set i = i + 1
endloop
set list = 3 * b + 1
set count = b.size
set i = 1
loop
exitwhen i > count
set e = LoadInteger(ht, list, i)
if a.has(e) then
call result.add(e)
endif
set i = i + 1
endloop
return result
endmethod
method diff takes thistype b returns thistype
local thistype a = this
local thistype result = allocate()
local integer list
local integer count
local integer i
local integer e
set list = 3 * a + 1
set count = this.size
set i = 1
loop
exitwhen i > count
set e = LoadInteger(ht, list, i)
if not b.has(e) then
call result.add(e)
endif
set i = i + 1
endloop
return result
endmethod
method sym_diff takes thistype b returns thistype
local thistype a = this
local thistype result = allocate()
local integer list
local integer count
local integer i
local integer e
set list = 3 * a + 1
set count = a.size
set i = 1
loop
exitwhen i > count
set e = LoadInteger(ht, list, i)
if not b.has(e) then
call result.add(e)
endif
set i = i + 1
endloop
set list = 3 * b + 1
set count = b.size
set i = 1
loop
exitwhen i > count
set e = LoadInteger(ht, list, i)
if not a.has(e) then
call result.add(e)
endif
set i = i + 1
endloop
return result
endmethod
method to_string takes nothing returns string
local string s
local integer count = this.size
local integer i
if count <= 0 then
return "{}"
endif
set s = "{ " + I2S(this[1])
set i = 2
loop
exitwhen i > count
set s = s + ", " + I2S(this[i])
set i = i + 1
endloop
set s = s + " }"
return s
endmethod
endstruct
endlibrary
