--[[

Copyright 2017 YANG Huan (sy.yanghuan@gmail.com).

Licensed under the Apache License, Version 2.0 (the "License");

you may not use this file except in compliance with the License.

You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software

distributed under the License is distributed on an "AS IS" BASIS,

WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

See the License for the specific language governing permissions and

limitations under the License.

--]]

local System = _G.System

local define = System.define

local throw = System.throw

local div = System.div

local bnot = System.bnot

local trueFn = System.trueFn

local falseFn = System.falseFn

local lengthFn = System.lengthFn

local er = System.er

local InvalidOperationException = System.InvalidOperationException

local NullReferenceException = System.NullReferenceException

local ArgumentException = System.ArgumentException

local ArgumentNullException = System.ArgumentNullException

local ArgumentOutOfRangeException = System.ArgumentOutOfRangeException

local IndexOutOfRangeException = System.IndexOutOfRangeException

local NotSupportedException = System.NotSupportedException

local EqualityComparer = System.EqualityComparer

local Comparer_1 = System.Comparer_1

local IEnumerable_1 = System.IEnumerable_1

local IEnumerator_1 = System.IEnumerator_1

local assert = assert

local select = select

local getmetatable = getmetatable

local setmetatable = setmetatable

local type = type

local table = table

local tinsert = table.insert

local tremove = table.remove

local tmove = table.move

local tsort = table.sort

local pack = table.pack

local unpack = table.unpack

local error = error

local coroutine = coroutine

local ccreate

local cresume

local cyield

if coroutine ~= nil then

ccreate = coroutine.create

cresume = coroutine.resume

cyield = coroutine.yield

end

local null = { GetHashCode = System.zeroFn }

local arrayEnumerator

local arrayFromTable

local versions = setmetatable({}, { __mode = "k" })

System.versions = versions

local function throwFailedVersion()

throw(InvalidOperationException("Collection was modified; enumeration operation may not execute."))

end

local function checkIndex(t, index)

if index < 0 or index >= #t then

throw(ArgumentOutOfRangeException("index"))

end

end

local function checkIndexAndCount(t, index, count)

if t == nil then throw(ArgumentNullException("array")) end

if index < 0 or count < 0 or index + count > #t then

throw(ArgumentOutOfRangeException("index or count"))

end

end

local function wrap(v)

if v == nil then

return null

end

return v

end

local function unWrap(v)

if v == null then

return nil

end

return v

end

local function ipairs(t)

local version = versions[t]

return function (t, i)

if version ~= versions[t] then

throwFailedVersion()

end

local v = t[i]

if v ~= nil then

if v == null then

v = nil

end

return i + 1, v

end

end, t, 1

end

local function eachFn(en)

if en:MoveNext() then

return true, en:getCurrent()

end

return nil

end

local function each(t)

if t == nil then throw(NullReferenceException(), 1) end

local getEnumerator = t.GetEnumerator

if getEnumerator == arrayEnumerator then

return ipairs(t)

end

local en = getEnumerator(t)

return eachFn, en

end

function System.isArrayLike(t)

return type(t) == "table" and t.GetEnumerator == arrayEnumerator

end

function System.isEnumerableLike(t)

return type(t) == "table" and t.GetEnumerator ~= nil

end

function System.toLuaTable(array)

local t = {}

for i = 1, #array do

local item = array[i]

if item ~= null then

t[i] = item

end

end

return t

end

System.null = null

System.Void = null

System.each = each

System.ipairs = ipairs

System.throwFailedVersion = throwFailedVersion

System.wrap = wrap

System.unWrap = unWrap

System.checkIndex = checkIndex

System.checkIndexAndCount = checkIndexAndCount

local Array

local emptys = {}

local function get(t, index)

local v = t[index + 1]

if v == nil then

throw(ArgumentOutOfRangeException("index"))

end

if v ~= null then

return v

end

return nil

end

local function set(t, index, v)

index = index + 1

if t[index] == nil then

throw(ArgumentOutOfRangeException("index"))

end

t[index] = v == nil and null or v

versions[t] = (versions[t] or 0) + 1

end

local function add(t, v)

local n = #t

t[n + 1] = v == nil and null or v

versions[t] = (versions[t] or 0) + 1

return n

end

local function addRange(t, collection)

if collection == nil then throw(ArgumentNullException("collection")) end

local count = #t + 1

if collection.GetEnumerator == arrayEnumerator then

tmove(collection, 1, #collection, count, t)

else

for _, v in each(collection) do

t[count] = v == nil and null or v

count = count + 1

end

end

versions[t] = (versions[t] or 0) + 1

end

local function clear(t)

local size = #t

if size > 0 then

for i = 1, size do

t[i] = nil

end

versions[t] = (versions[t] or 0) + 1

end

end

local function first(t)

local v = t[1]

if v == nil then throw(InvalidOperationException()) end

if v ~= null then

return v

end

return nil

end

local function last(t)

local n = #t

if n == 0 then throw(InvalidOperationException()) end

local v = t[n]

if v ~= null then

return v

end

return nil

end

local function unset()

throw(NotSupportedException("Collection is read-only."))

end

local function fill(t, f, e, v)

while f <= e do

t[f] = v

f = f + 1

end

end

local function buildArray(ArrayT, n, t)

if type(n) == "table" then

t = n

elseif t ~= nil then

for i = 1, n do

if t[i] == nil then

t[i] = null

end

end

else

t = {}

if n > 0 then

local T = ArrayT.__genericT__

local default = T:default()

if default == nil then

fill(t, 1, n, null)

elseif type(default) ~= "table" then

fill(t, 1, n, default)

else

for i = 1, n do

t[i] = T:default()

end

end

end

end

return setmetatable(t, ArrayT)

end

local function indexOf(t, v, startIndex, count)

if t == nil then throw(ArgumentNullException("array")) end

local len = #t

if not startIndex then

startIndex, count = 0, len

elseif not count then

if startIndex < 0 or startIndex > len then

throw(ArgumentOutOfRangeException("startIndex"))

end

count = len - startIndex

else

if startIndex < 0 or startIndex > len then

throw(ArgumentOutOfRangeException("startIndex"))

end

if count < 0 or count > len - startIndex then

throw(ArgumentOutOfRangeException("count"))

end

end

local comparer = EqualityComparer(t.__genericT__).getDefault()

local equals = comparer.EqualsOf

for i = startIndex + 1, startIndex + count do

local item = t[i]

if item == null then item = nil end

if equals(comparer, item, v) then

return i - 1

end

end

return -1

end

local function findIndex(t, startIndex, count, match)

if t == nil then throw(ArgumentNullException("array")) end

local len = #t

if not count then

startIndex, count, match = 0, len, startIndex

elseif not match then

if startIndex < 0 or startIndex > len then

throw(ArgumentOutOfRangeException("startIndex"))

end

count, match = len - startIndex, count

else

if startIndex < 0 or startIndex > len then

throw(ArgumentOutOfRangeException("startIndex"))

end

if count < 0 or count > len - startIndex then

throw(ArgumentOutOfRangeException("count"))

end

end

if match == nil then throw(ArgumentNullException("match")) end

local endIndex = startIndex + count

for i = startIndex + 1, endIndex do

local item = t[i]

if item == null then item = nil end

if match(item) then

return i - 1

end

end

return -1

end

local function copy(sourceArray, sourceIndex, destinationArray, destinationIndex, length, reliable)

if not reliable then

checkIndexAndCount(sourceArray, sourceIndex, length)

checkIndexAndCount(destinationArray, destinationIndex, length)

end

tmove(sourceArray, sourceIndex + 1, sourceIndex + length, destinationIndex + 1, destinationArray)

end

local function removeRange(t, index, count)

local n = #t

if count < 0 or index > n - count then

throw(ArgumentOutOfRangeException("index or count"))

end

if count > 0 then

if index + count < n then

tmove(t, index + count + 1, n, index + 1)

end

fill(t, n - count + 1, n, nil)

versions[t] = (versions[t] or 0) + 1

end

end

local function findAll(t, match)

if t == nil then throw(ArgumentNullException("array")) end

if match == nil then throw(ArgumentNullException("match")) end

local list = {}

local count = 1

for i = 1, #t do

local item = t[i]

if (item == null and match(nil)) or match(item) then

list[count] = item

count = count + 1

end

end

return list

end

local function binarySearch(t, ...)

if t == nil then throw(ArgumentNullException("array")) end

local index, count, v, comparer

local n = select("#", ...)

if n == 1 or n == 2 then

index, count, v, comparer = 0, #t, ...

else

index, count, v, comparer = ...

end

checkIndexAndCount(t, index, count)

local compare

if type(comparer) == "function" then

compare = comparer

elseif comparer == nil then

comparer = Comparer_1(t.__genericT__).getDefault()

compare = comparer.Compare

else

compare = comparer.Compare

end

local lo = index

local hi = index + count - 1

while lo <= hi do

local i = lo + div(hi - lo, 2)

local item = t[i + 1]

if item == null then item = nil end

local order = compare(comparer, item, v);

if order == 0 then return i end

if order < 0 then

lo = i + 1

else

hi = i - 1

end

end

return bnot(lo)

end

local function getSortComp(t, comparer)

local compare

if comparer then

if type(comparer) == "function" then

compare = comparer

else

local Compare = comparer.Compare

if Compare then

compare = function (x, y) return Compare(comparer, x, y) end

else

compare = comparer

end

end

else

comparer = Comparer_1(t.__genericT__).getDefault()

local Compare = comparer.Compare

compare = function (x, y) return Compare(comparer, x, y) end

end

return function(x, y)

if x == null then x = nil end

if y == null then y = nil end

return compare(x, y) < 0

end

end

local function sort(t, comparer)

if #t > 1 then

tsort(t, getSortComp(t, comparer))

versions[t] = (versions[t] or 0) + 1

end

end

local function addOrder(t, v, comparer)

local i = binarySearch(t, v, comparer)

if i >= 0 then return false end

tinsert(t, bnot(i) + 1, v == nil and null or v)

return true

end

local function addOrderRange(t, collection)

if collection == nil then throw(ArgumentNullException("collection")) end

local comparer, n = t.comparer, #t

if collection.GetEnumerator == arrayEnumerator then

for i = 1, #collection do

local v = collection[i]

if v == null then v = nil end

addOrder(t, v, comparer)

end

else

for _, v in each(collection) do

addOrder(t, v, comparer)

end

end

if #t ~= n then

versions[t] = (versions[t] or 0) + 1

end

end

local function exceptWithOrder(t, other)

if other == nil then throw(ArgumentNullException("other")) end

local n = #t

if n == 0 then return end

if t == other then

clear(t)

return

end

local comparer = t.comparer

if other.GetEnumerator == arrayEnumerator then

for i = 1, #other do

local v = other[i]

if v == null then v = nil end

local j = binarySearch(t, 0, n, v, comparer)

if j >= 0 then

tremove(t, j + 1)

end

end

else

for _, v in each(other) do

local i = binarySearch(t, 0, n, v, comparer)

if i >= 0 then

tremove(t, i + 1)

end

end

end

if #t ~= n then

versions[t] = (versions[t] or 0) + 1

end

end

local function intersectWithOrder(t, other)

if other == nil then throw(ArgumentNullException("other")) end

local n = #t

if n == 0 then return end

if t == other then return end

local comparer = t.comparer

local array = arrayFromTable({}, t.__genericT__)

for _, v in each(other) do

local i = binarySearch(t, 0, n, v, comparer)

if i >= 0 then

array[#array + 1] = v == nil and null or v

end

end

clear(t)

addOrderRange(t, array)

end

local function isSubsetOfOrderWithSameEC(t, n, comparer, t1)

local n1 = #t1

for i = 1, n do

local v = t[i]

if v == null then v = nil end

local j = binarySearch(t1, 0, n1, v, comparer)

if j < 0 then

return false

end

end

return true

end

local function checkOrderUniqueAndUnfoundElements(t, n, comparer, other, returnIfUnfound)

if n == 0 then

local numElementsInOther = 0

if other:GetEnumerator():MoveNext() then

numElementsInOther = 1

end

return 0, numElementsInOther

end

local uniqueFoundCount, unfoundCount, mark = 0, 0, {}

for _, v in each(other) do

local i = binarySearch(t, v, comparer)

if i >= 0 then

if not mark[i] then

mark[i] = true

uniqueFoundCount = uniqueFoundCount + 1

end

else

unfoundCount = unfoundCount + 1

if returnIfUnfound then

break

end

end

end

return uniqueFoundCount, unfoundCount

end

local function isProperSubsetOfOrder(t, other)

if other == nil then throw(ArgumentNullException("other")) end

if t == other then return false end

local comparer, n = t.comparer, #t

if System.is(other, System.SortedSet(t.__genericT__)) then

if comparer == other.comparer then

if n >= #other then return false end

return isSubsetOfOrderWithSameEC(t, n, comparer, other)

end

end

local uniqueCount, unfoundCount = checkOrderUniqueAndUnfoundElements(t, n, comparer, other)

return uniqueCount == n and unfoundCount > 0

end

local function isProperSupersetOfOrder(t, other)

if other == nil then throw(ArgumentNullException("other")) end

local n = #t

if n == 0 then return false end

if System.is(other, System.ICollection) then

if other:getCount() == 0 then

return true

end

end

local comparer = t.comparer

if System.is(other, System.SortedSet(t.__genericT__)) then

if comparer == other.comparer then

local n1 = #other

if n1 >= n then return false end

return isSubsetOfOrderWithSameEC(other, n1, comparer, t)

end

end

local uniqueCount, unfoundCount = checkOrderUniqueAndUnfoundElements(t, n, comparer, other, true)

return uniqueCount < n and unfoundCount == 0

end

local function isSubsetOfOrder(t, other)

if other == nil then throw(ArgumentNullException("other")) end

local n = #t

if n == 0 then return true end

local comparer = t.comparer

if System.is(other, System.SortedSet(t.__genericT__)) then

if comparer == other.comparer then

if n > #other then return false end

return isSubsetOfOrderWithSameEC(t, n, comparer, set)

end

end

local uniqueCount, unfoundCount = checkOrderUniqueAndUnfoundElements(t, n, comparer, other)

return uniqueCount == n and unfoundCount >= 0

end

local function isSupersetOfOrder(t, other)

if other == nil then throw(ArgumentNullException("other")) end

if System.is(other, System.ICollection) then

if other:getCount() == 0 then

return true

end

end

local comparer, n = t.comparer, #t

if System.is(other, System.SortedSet(t.__genericT__)) then

if comparer == other.comparer then

local n1 = #other

if n < n1 then return false end

return isSubsetOfOrderWithSameEC(other, n1, comparer, t)

end

end

for _, v in each(other) do

local i = binarySearch(t, v, comparer)

if i < 0 then

return false

end

end

return true

end

local function isOverlapsOrder(t, other)

if other == nil then throw(ArgumentNullException("other")) end

local n = #t

if n == 0 then return false end

if System.is(other, System.ICollection) and other:getCount() == 0 then return false end

local comparer = t.comparer

if System.is(other, System.SortedSet(t.__genericT__)) and comparer == other.comparer then

local c = comparer.Compare

if c(comparer, first(t), last(other)) > 0 or c(comparer, last(t), first(other)) < 0 then

return false

end

end

for _, v in each(other) do

local i = binarySearch(t, v, comparer)

if i >= 0 then

return true

end

end

return false

end

local function equalsOrder(t, other)

if other == nil then throw(ArgumentNullException("other")) end

local comparer, n = t.comparer, #t

if System.is(other, System.SortedSet(t.__genericT__)) and comparer == other.comparer then

local n1 = #other

if n ~= n1 then return false end

local c = comparer.Compare

for i = 1, n do

local v, v1 = t[i], other[i]

if v == null then v = nil end

if v1 == null then v1 = nil end

if c(comparer, v, v1) ~= 0 then

return false

end

end

return true

end

local uniqueCount, unfoundCount = checkOrderUniqueAndUnfoundElements(t, n, comparer, other, true)

return uniqueCount == n and unfoundCount == 0

end

local function symmetricExceptWithOrder(t, other)

if other == nil then throw(ArgumentNullException("other")) end

local n = #t

if n == 0 then

addOrderRange(other)

return

end

if t == other then

clear(t)

return

end

local comparer = t.comparer

for _, v in each(other) do

local i = binarySearch(t, v, comparer)

if i >= 0 then

tremove(t, i + 1)

else

addOrder(t, v, comparer)

end

end

end

local function tryGetValueOrder(t, equalValue)

local i = binarySearch(t, equalValue, t.comparer)

if i >= 0 then

local v = t[i + 1]

if v == null then v = nil end

return true, v

end

return false, t.__genericT__:default()

end

local function checkOrderDictKeyValueObj(t, k, v)

if k == nil then throw(ArgumentNullException("key")) end

local TValue = t.__genericTValue__

if v == nil and TValue:default() ~= nil then throw(ArgumentNullException("value")) end

local TKey = t.__genericTKey__

if not System.is(k, TKey) then

throw(ArgumentException(er.Arg_WrongType(k, TKey.__name__), "key"))

end

if not System.is(v, TValue) then

throw(ArgumentException(er.Arg_WrongType(v, TValue.__name__), "value"))

end

end

local function getOrderDictIndex(t, k, isObj)

if k == nil then throw(ArgumentNullException("key")) end

if isObj and not System.is(k, t.__genericTKey__) then

return -1

end

return binarySearch(t, k, t.keyComparer)

end

local function addOrderDict(t, k, v, keyComparer, T, version)

local i = binarySearch(t, k, keyComparer)

if i >= 0 then

throw(ArgumentException(er.Argument_AddingDuplicate(k)))

end

tinsert(t, bnot(i) + 1, setmetatable({ k, v }, T))

if version then

versions[t] = (versions[t] or 0) + 1

end

end

local function getOrderDict(t, k, isObj)

local i = getOrderDictIndex(t, k)

if i >= 0 then

return t[i + 1][2]

end

if isObj then

return nil

end

throw(System.KeyNotFoundException(er.Arg_KeyNotFoundWithKey(k)))

end

local function setOrderDict(t, k, v)

local i = getOrderDictIndex(t, k)

if i >= 0 then

t[i + 1][2] = v

else

tinsert(t, bnot(i) + 1, setmetatable({ k, v }, t.__genericT__))

versions[t] = (versions[t] or 0) + 1

end

end

local function getViewBetweenOrder(t, lowerValue, upperValue)

local comparer = t.comparer

if comparer:Compare(lowerValue, upperValue) > 0 then

throw(ArgumentException("lowerBound is greater than upperBound"))

end

local n = #t

local i = binarySearch(t, lowerValue, comparer)

if i < 0 then i = bnot(i) end

local s = { comparer = comparer }

if i < n then

local j = binarySearch(t, upperValue, comparer)

if j < 0 then j = bnot(j) - 1 end

if i <= j then

tmove(t, i + 1, j + 1, 1, s)

end

end

return setmetatable(s, System.SortedSet(t.__genericT__))

end

local function heapDown(t, k, n, c)

local j

while true do

j = k * 2

if j <= n and j > 0 then

if j < n and c(t[j], t[j + 1]) > 0 then

j = j + 1

end

if c(t[k], t[j]) <= 0 then

break

end

t[j], t[k] = t[k], t[j]

k = j

else

break

end

end

end

local function heapUp(t, k, n, c)

while k > 1 do

local j = div(k, 2)

if c(t[j], t[k]) <= 0 then

break

end

t[j], t[k] = t[k], t[j]

k = j

end

end

local function heapify(t, c)

local n = #t

for i = div(n, 2), 1, -1 do

heapDown(t, i, n, c)

end

end

local function heapAdd(t, v, c)

local n = #t + 1

t[n] = v

heapUp(t, n, n, c)

end

local function heapPop(t, c)

local n = #t

if n == 0 then return end

local v = t[1]

t[1] = t[n]

t[n] = nil

heapDown(t, 1, n - 1, c)

return v

end

local SortedSetEqualityComparerFn

local SortedSetEqualityComparer = {

__ctor__ = function (this, equalityComparer, comparer)

local T = this.__genericT__

this.comparer = comparer or Comparer_1(T).getDefault()

this.equalityComparer = equalityComparer or EqualityComparer(T).getDefault()

end,

EqualsOf = function (_, x, y)

if x == nil then return y == nil end

if y == nil then return false end

return equalsOrder(x, y)

end,

GetHashCodeOf = function (this, t)

local hashCode = 0

if t ~= nil then

for i = 1, #t do

local v = t[i]

if v == null then v = nil end

hashCode = System.xor(hashCode, System.band(this.equalityComparer:GetHashCodeOf(v), 0x7FFFFFFF))

end

end

return hashCode

end,

EqualsObj = function (this, obj)

if System.is(obj, SortedSetEqualityComparerFn(this.__genericT__)) then

return this.comparer == obj.comparer

end

return false

end,

GetHashCode = function (this)

return System.xor(this.comparer:GetHashCode(), this.equalityComparer:GetHashCode())

end

}

SortedSetEqualityComparerFn = define("System.SortedSetEqualityComparer", function (T)

return {

base = { System.IEqualityComparer_1(T) },

__genericT__ = T

}

end, SortedSetEqualityComparer, 1)

local ArrayEnumerator = define("System.ArrayEnumerator", function (T)

return {

base = { IEnumerator_1(T) }

}

end, {

getCurrent = System.getCurrent,

Dispose = System.emptyFn,

Reset = function (this)

this.index = 1

this.current = nil

end,

MoveNext = function (this)

local t = this.list

if this.version ~= versions[t] then

throwFailedVersion()

end

local index = this.index

local v = t[index]

if v ~= nil then

if v == null then

this.current = nil

else

this.current = v

end

this.index = index + 1

return true

end

this.current = nil

return false

end

}, 1)

arrayEnumerator = function (t, T)

if not T then T = t.__genericT__ end

return setmetatable({ list = t, index = 1, version = versions[t], currnet = T:default() }, ArrayEnumerator(T))

end

local ArrayReverseEnumerable

local function reverseEnumerator(t)

local T = t.__genericT__

return setmetatable({ list = t, index = #t, version = versions[t], currnet = T:default() }, ArrayReverseEnumerable(T))

end

ArrayReverseEnumerable = define("System.ArrayReverseEnumerable", function (T)

return {

base = { IEnumerable_1(T), IEnumerator_1(T) }

}

end, {

getCurrent = System.getCurrent,

Dispose = System.emptyFn,

GetEnumerator = function (this)

return reverseEnumerator(this.list)

end,

Reset = function (this)

this.index = #this.list

this.current = nil

end,

MoveNext = function (this)

local t = this.list

if this.version ~= versions[t] then

throwFailedVersion()

end

local index = this.index

local v = t[index]

if v ~= nil then

if v == null then

this.current = nil

else

this.current = v

end

this.index = index - 1

return true

end

this.current = nil

return false

end

}, 1)

local function reverseEnumerable(t)

return setmetatable({ list = t }, ArrayReverseEnumerable(t.__genericT__))

end

local function checkArrayIndex(index1, index2)

if index2 then

throw(ArgumentException("Indices length does not match the array rank."))

elseif type(index1) == "table" then

if #index1 ~= 1 then

throw(ArgumentException("Indices length does not match the array rank."))

else

index1 = index1[1]

end

end

return index1

end

Array = {

version = 0,

__call = buildArray,

set = set,

get = get,

setCapacity = function (t, len)

if len < #t then throw(ArgumentOutOfRangeException("Value", er.ArgumentOutOfRange_SmallCapacity())) end

end,

ctorList = function (t, ...)

local n = select("#", ...)

if n == 0 then return end

local collection = ...

if type(collection) == "number" then return end

addRange(t, collection)

end,

ctorOrderSet = function(t, ...)

local n = select("#", ...)

if n == 0 then

t.comparer = Comparer_1(t.__genericT__).getDefault()

else

local collection, comparer = ...

if collection == nil then throw(ArgumentNullException("collection")) end

t.comparer = comparer or Comparer_1(t.__genericT__).getDefault()

if collection then

addOrderRange(t, collection)

end

end

end,

ctorOrderDict = function (t, ...)

local n = select("#", ...)

local dictionary, comparer

if n ~= 0 then

dictionary, comparer = ...

if dictionary == nil then throw(ArgumentNullException("dictionary")) end

end

if comparer == nil then comparer = Comparer_1(t.__genericT__).getDefault() end

local c = comparer.Compare

local keyComparer = function (_, p, v)