--- /dev/null
+# Nit functional types and Iterator API
+
+This lib provides a common interfaces to represent and call any type of routine.
+This is usefull if you want to build a functional API, where user can pass
+functions. Right now, there's no support for anonymous function or function pointer.
+However, one can build classes that inherit from a functional type to simulate
+a function. Here's an example implementing the famous __map__ function:
+
+~~~
+class MapIntToString
+ super Fun1[Int,String]
+ redef fun call(x) do return x.to_s
+end
+
+redef class Array[E]
+ fun map(mapper: Fun1[E, Object]): Array[Object]
+ do
+ var res = new Array[Object]
+ for ele in self do res.add(mapper.call(ele))
+ return res
+ end
+end
+
+var xs = [1,2,3,4]
+var f = new MapIntToString
+assert xs.map(f) == ["1", "2", "3", "4"]
+~~~
+
+Currently, this style of programming seems tedious, but future update of the langage
+will support function pointer and anonymous function.
+
+Functional API makes it easier to build asynchronous or multithreaded code,
+because representing a pending or future computation using a function requires
+much less code:
+
+~~~nitish
+fun long\_calculation
+do
+ ...
+end
+
+# function pointer
+var thread = new Thread(&long\_calculation)
+thread.start
+thread.wait
+~~~
+
+Finally, this lib provides an entire functional API over the `Iterator` class
+similar to the old `Pipeline` lib.
+
+## Functional Types
+
+There are two fundamental types: `FunX[0..X, RES]` and `ProcX[0..X]`, both inherits
+`Routine`. The `X` represents the arity of the routine, eg :
+
+~~~
+import functional
+
+class A
+
+ # to_s isa `Fun0[String]`.
+ redef fun to_s do return "greeting from A"
+end
+
+# f isa `Fun2[Int,Int,Int]`
+fun f(x: Int, y: Int): Int do return x + y
+
+# g isa `Proc2[Int,Int]`
+fun g(x: Int, y: Int) do print "{x + y}"
+~~~
+
+For a `FunX` type the arity doesn't count the return type.
+
+**Note**: The arity doesn't count the receiver of the current class where the
+method belongs.
+
+## Iterator API
+
+The new `Iterator` API provides all the classical functional style transformation:
+map, for\_each, fold, fold1, flatmap, enumerate, any and all.
+
+Most methods return a new `Iterator`, this allow us to chain them:
+
+~~~nitish
+import functional
+
+fun addone(x: Int): Int do return x + 1
+fun square(x: Int): Int do return x * x
+fun add(x:Int, y: Int): Int do return x + y
+
+var xs = [1,2,3,4,5,6,7,8,9,10]
+
+assert xs.iterator.map(&square).map(&addone).fold(0, &add) == 395
+~~~
+
+Some functions collapse the iterator into one value : `all`, `any`, `fold`,
+`fold1`, `for_each` (void-like).
+
+**Note**: Most of the new methods tries to be lazy. However, `Iterator::order_by`
+consume the entire iterator and `Iterator::filter` might consume the entire iterator.
+
+## Usage
+
+To use the new API you must include in your file `import functional`.
+
+## Notes
+
+- The module `functional::functional_gen` is only used to generate `functional::functional_types`.
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2019 Louis-Vincent Boudreault <lv.boudreault95@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.
+
+# Functional types and functional API for `Iterator`
+module functional
+
+import iter_extras
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2019 Louis-Vincent Boudreault <lv.boudreault95@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.
+
+# This module is only used to generate `functional_types.nit`
+module functional_gen
+
+# Generates of an array of formal type as strings.
+# The size of the array equals the arity of the class.
+fun gen_generics(nargs: Int): Array[String]
+do
+ var args = new Array[String]
+ for i in [0..nargs[ do
+ args.push("A" + i.to_s)
+ end
+ return args
+end
+
+class RoutineTemplate
+ var classname: String
+ var nb_generics: Int
+ var supers: Array[String]
+ var has_return: Bool
+ var annotation = "is abstract"
+
+ redef fun to_s
+ do
+ var generics = gen_generics(nb_generics)
+ var params = new Array[String]
+ for g in generics do
+ params.push(g.to_lower + ": " + g)
+ end
+ var signature = ""
+ if params.length > 0 then signature = "({params.join(",")})"
+ if has_return then
+ signature += ": RESULT"
+ generics.push("RESULT")
+ end
+ var classparam = ""
+ if generics.length > 0 then
+ classparam = "[{generics.join(",")}]"
+ end
+ var superdecls = new Array[String]
+ for s in supers do superdecls.add("\tsuper {s}")
+ var classdef = new Array[String]
+ classdef.add("class {classname}{classparam}")
+ classdef.add("{superdecls.join("\n")}")
+ classdef.add("\tfun call{signature} {annotation}")
+ classdef.add("end")
+ return classdef.join("\n")
+ end
+end
+
+# Writes all functional types
+fun generate_functypes(n: Int, writer: Writer)
+do
+ writer.write("""
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# 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.
+
+# This module provides functional type to represents various function forms.
+# Function types can hold up to 20 arguments. The type `Fun` is for function
+# (input and output) and `Proc` is for procedure (input but no output).
+# This file is automatically generated, do not edit it manually.
+module functional_types
+
+interface Routine
+end
+interface Fun
+ super Routine
+end
+interface Proc
+ super Routine
+end
+""")
+ var templates = new Array[String]
+ for i in [0..n[ do
+ var t1 = new RoutineTemplate("Fun{i}", i, ["Fun"], true)
+ var t2 = new RoutineTemplate("Proc{i}", i, ["Proc"], false)
+ templates.push(t1.to_s)
+ templates.push(t2.to_s)
+ end
+ writer.write(templates.join("\n"))
+end
+
+var fw = new FileWriter.open("functional_types.nit")
+generate_functypes(20, fw)
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# 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.
+
+# This module provides functional type to represents various function forms.
+# Function types can hold up to 20 arguments. The type `Fun` is for function
+# (input and output) and `Proc` is for procedure (input but no output).
+# This file is automatically generated, do not edit it manually.
+module functional_types
+
+interface Routine
+end
+interface Fun
+ super Routine
+end
+interface Proc
+ super Routine
+end
+class Fun0[RESULT]
+ super Fun
+ fun call: RESULT is abstract
+end
+class Proc0
+ super Proc
+ fun call is abstract
+end
+class Fun1[A0,RESULT]
+ super Fun
+ fun call(a0: A0): RESULT is abstract
+end
+class Proc1[A0]
+ super Proc
+ fun call(a0: A0) is abstract
+end
+class Fun2[A0,A1,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1): RESULT is abstract
+end
+class Proc2[A0,A1]
+ super Proc
+ fun call(a0: A0,a1: A1) is abstract
+end
+class Fun3[A0,A1,A2,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2): RESULT is abstract
+end
+class Proc3[A0,A1,A2]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2) is abstract
+end
+class Fun4[A0,A1,A2,A3,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3): RESULT is abstract
+end
+class Proc4[A0,A1,A2,A3]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3) is abstract
+end
+class Fun5[A0,A1,A2,A3,A4,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4): RESULT is abstract
+end
+class Proc5[A0,A1,A2,A3,A4]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4) is abstract
+end
+class Fun6[A0,A1,A2,A3,A4,A5,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5): RESULT is abstract
+end
+class Proc6[A0,A1,A2,A3,A4,A5]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5) is abstract
+end
+class Fun7[A0,A1,A2,A3,A4,A5,A6,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6): RESULT is abstract
+end
+class Proc7[A0,A1,A2,A3,A4,A5,A6]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6) is abstract
+end
+class Fun8[A0,A1,A2,A3,A4,A5,A6,A7,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7): RESULT is abstract
+end
+class Proc8[A0,A1,A2,A3,A4,A5,A6,A7]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7) is abstract
+end
+class Fun9[A0,A1,A2,A3,A4,A5,A6,A7,A8,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8): RESULT is abstract
+end
+class Proc9[A0,A1,A2,A3,A4,A5,A6,A7,A8]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8) is abstract
+end
+class Fun10[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9): RESULT is abstract
+end
+class Proc10[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9) is abstract
+end
+class Fun11[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10): RESULT is abstract
+end
+class Proc11[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10) is abstract
+end
+class Fun12[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11): RESULT is abstract
+end
+class Proc12[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11) is abstract
+end
+class Fun13[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12): RESULT is abstract
+end
+class Proc13[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12) is abstract
+end
+class Fun14[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13): RESULT is abstract
+end
+class Proc14[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13) is abstract
+end
+class Fun15[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14): RESULT is abstract
+end
+class Proc15[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14) is abstract
+end
+class Fun16[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15): RESULT is abstract
+end
+class Proc16[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15) is abstract
+end
+class Fun17[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15,a16: A16): RESULT is abstract
+end
+class Proc17[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15,a16: A16) is abstract
+end
+class Fun18[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,A17,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15,a16: A16,a17: A17): RESULT is abstract
+end
+class Proc18[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,A17]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15,a16: A16,a17: A17) is abstract
+end
+class Fun19[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,A17,A18,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15,a16: A16,a17: A17,a18: A18): RESULT is abstract
+end
+class Proc19[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,A17,A18]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15,a16: A16,a17: A17,a18: A18) is abstract
+end
\ No newline at end of file
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2019 Louis-Vincent Boudreault <lv.boudreault95@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.
+
+# This modules provides a new functional interface for `Iterator`.
+module iter_extras
+
+import functional_types
+import cartesian
+
+redef class Array
+
+ # Sorts an array with a function.
+ #
+ # ~~~~nitish
+ # class Person
+ # var name: String
+ # end
+ #
+ # def get_name(p: Person) do return p.name
+ #
+ # var ps = [new Person("Turing"), new Person("Curry"), new Person("Alfredo")]
+ # ps.sort_with(&get_name)
+ # assert ps[0].name == "Alfredo"
+ # assert ps[1].name == "Curry"
+ # assert ps[2].name == "Turing"
+ # ~~~~
+ fun sort_with(f: Fun1[E, Comparable])
+ do
+ var cmp = new ComparatorWith[E](f)
+ if length > 1 then
+ cmp.quick_sort(self, 0, length - 1)
+ end
+ end
+end
+
+redef interface Iterator[E]
+
+ # Applies a function to every elements
+ #
+ # ~~~~nitish
+ # fun add(x: Int): Int do return x + 1
+ #
+ # var f = &add
+ # var xs = [1,2,3,4,5]
+ # var actual = xs.iterator.map(f).to_a
+ # assert actual == [2,3,4,5,6]
+ # ~~~~
+ fun map(f: Fun1[E,Object]): MapIter[E,Object]
+ do
+ return new MapIter[E,Object](self, f)
+ end
+
+ # Iterator that gives the current count and element as a pair
+ fun enumerate: EnumerateIter[E]
+ do
+ return new EnumerateIter[E](self)
+ end
+
+ # Iterator that filters elements by a predicate
+ #
+ # ~~~~nitish
+ # fun lt10(x: Int): Bool do return x < 10
+ #
+ # var pred = <10
+ # var xs = [1..20]
+ # var actual = xs.iterator.filter(pred).to_a
+ # assert actual == [1..9].to_a
+ # ~~~~
+ fun filter(pred: Fun1[E,Bool]): FilterIter[E]
+ do
+ return new FilterIter[E](self,pred)
+ end
+
+ # Checks if at least one element respects a predicate
+ #
+ # ~~~~nitish
+ # fun eq10(x: Int): Bool do return x == 10
+ #
+ # var pred = &eq10
+ # var xs = [1,2,5,7,9,10,44]
+ # assert xs.iterator.any(pred)
+ # var ys = []
+ # assert not ys.iterator.any(pred)
+ # assert not [1,2,44].iterator.any(pred)
+ # ~~~~
+ fun any(pred: Fun1[E,Bool]): Bool
+ do
+ for x in self do
+ if pred.call(x) then
+ return true
+ end
+ end
+ return false
+ end
+
+ # Checks if all elements respect a predicate
+ #
+ # ~~~~nitish
+ # fun lt10(x: Int): Bool do return x < 10
+ #
+ # var pred = <10
+ # var xs = [1..9]
+ # assert xs.iterator.all(pred)
+ # assert [].iterator.all(pred)
+ # assert not [1..10].iterator.all(pred)
+ # ~~~~
+ fun all(pred: Fun1[E,Bool]): Bool
+ do
+ for x in self do
+ if not pred.call(x) then
+ return false
+ end
+ end
+ return true
+ end
+
+ # Folds an iterator from the left
+ #
+ # ~~~~nitish
+ # fun adder(x: Int, y: Int): Int do return x + y
+ #
+ # var xs = [1..10]
+ # assert xs.iterator.fold(0, &adder) == 55
+ # ~~~~
+ fun fold(acc: Object, f: Fun2[Object, E, Object]): Object
+ do
+ for x in self do
+ acc = f.call(acc, x)
+ end
+ return acc
+ end
+
+ # Folds and apply two element at a time
+ #
+ # ~~~~nitish
+ # fun min_int(x: Int, y: Int): Int
+ # do
+ # if x < y then return x
+ # return y
+ # end
+ #
+ # var xs = [100,423,51,1,-19,55,999,-18]
+ # assert xs.iterator.fold1(&min_int) == -19
+ # ~~~~
+ # REQUIRE : length > 1
+ fun fold1(f: Fun2[E,E,E]): E
+ do
+ var a1 = item
+ next
+ var a2 = item
+ next
+ var res = f.call(a1,a2)
+ for x in self do
+ res = f.call(res, x)
+ end
+ return res
+ end
+
+ # Apply a mutation function over all elements
+ #
+ # ~~~~nitish
+ # class Person
+ # var age: Int
+ # def incr_age
+ # do
+ # age += 1
+ # end
+ # end
+ #
+ # var ps = [new Persone(1), new Person(2), new Person(3)]
+ # var ages = ps.iterator.for_each(&Person::incr_age).map(&Person::age).to_a
+ # assert ages == [2,3,4]
+ # ~~~~
+ fun for_each(f: Proc1[E])
+ do
+ for x in self do
+ f.call(x)
+ end
+ end
+
+ # Maps every element to a nested structure then flattens it
+ #
+ # ~~~~nitish
+ # fun chars_fn(s: String): Iterator[Char]
+ # do
+ # return s.chars.iterator
+ # end
+ # var cs = ["aaa","bbb","ccc"]
+ # assert cs.iterator.flat_map(&chars_fn).to_a.join == "aaabbbccc"
+ # ~~~~
+ fun flat_map(f: Fun1[E, Iterator[Object]]): FlatMapIter[E, Object]
+ do
+ return new FlatMapIter[E, Object](self, f)
+ end
+
+ # Generates an `Iterator` whose elements are sorted by the function
+ # passed in argument.
+ #
+ # ~~~~nitish
+ # class Person
+ # var name: String
+ # end
+ #
+ # def get_name(p: Person) do return p.name
+ #
+ # var ps = [new Person("Turing"), new Person("Curry"), new Person("Alfredo")]
+ # var ordered_names = ps.iterator.order_by(&get_name).map(&get_name).to_a
+ # assert ordered_names == ["Alfredo", "Curry", "Turing"]
+ # ~~~~
+ fun order_by(f: Fun1[E, Comparable]): OrderedIter[E]
+ do
+ return new OrderedIter[E](self, f)
+ end
+
+end
+
+# Base class for all iterators using functional types.
+private abstract class FunIter[OLD,NEW]
+ super Iterator[NEW]
+ var my_iter: Iterator[OLD]
+
+ redef fun next
+ do
+ my_iter.next
+ end
+
+ redef fun start
+ do
+ my_iter.start
+ end
+
+ redef fun finish
+ do
+ my_iter.finish
+ end
+
+ redef fun is_ok
+ do
+ return my_iter.is_ok
+ end
+end
+
+# An iterator that maps each item with `f`.
+class MapIter[A,B]
+ super FunIter[A,B]
+ var f: Fun1[A, B]
+
+ redef fun item
+ do
+ return f.call(my_iter.item)
+ end
+
+end
+
+# An iterator that maps each item to a pair containing the item with its
+# current count.
+class EnumerateIter[E]
+ super FunIter[E, Pair[Int,E]]
+
+ redef fun item
+ do
+ return new Pair[Int,E](0, my_iter.item)
+ end
+end
+
+# An tierator that filter its element by a predicate `pred`.
+class FilterIter[E]
+ super FunIter[E,nullable E]
+ var pred: Fun1[E, Bool]
+
+ redef init
+ do
+ if is_ok and not pred.call(my_iter.item) then next
+ end
+
+ redef fun item
+ do
+ assert is_ok
+ return my_iter.item
+ end
+
+ redef fun next
+ do
+ loop
+ my_iter.next
+ if not is_ok then
+ break
+ end
+ var x = my_iter.item
+ if pred.call(x) then
+ break
+ end
+ end
+ end
+end
+
+# An iterator that maps each item to an iterator and yield
+# each item from it.
+class FlatMapIter[A,B]
+ super FunIter[A,B]
+ var f: Fun1[A, Iterator[B]]
+ protected var inner: nullable Iterator[B] = null
+
+ redef init
+ do
+ try_compute_inner
+ end
+
+ redef fun item
+ do
+ return inner.as(not null).item
+ end
+
+ redef fun is_ok
+ do
+ return inner != null
+ end
+
+ redef fun next
+ do
+ inner.next
+ if not inner.is_ok then
+ super
+ try_compute_inner
+ end
+ end
+
+ # Tries to resolve the inner iterator.
+ # Assigns null to `inner` if it fails.
+ protected fun try_compute_inner
+ do
+ inner = null
+ if not my_iter.is_ok then return
+ var res = f.call(my_iter.item)
+ if res.is_ok then inner = res
+ end
+end
+
+# An iterator that yield each item in order
+class OrderedIter[E]
+ super FunIter[E,E]
+ var f: Fun1[E, Comparable]
+
+ private var sorted_iter: Iterator[E] is noinit
+ private var sorted_arr: Array[E] is noinit
+
+ redef init
+ do
+ sorted_arr = my_iter.to_a
+ sorted_arr.sort_with(f)
+ sorted_iter = sorted_arr.iterator
+ end
+
+ redef fun next
+ do
+ sorted_iter.next
+ end
+
+ redef fun item
+ do
+ return sorted_iter.item
+ end
+
+ redef fun is_ok
+ do
+ return sorted_iter.is_ok
+ end
+
+ redef fun finish
+ do
+ sorted_iter.finish
+ end
+
+ redef fun to_a
+ do
+ return sorted_arr
+ end
+end
+
+# Comparator that use a function provided by the user to compare between elements.
+class ComparatorWith[E]
+ super Comparator
+ redef type COMPARED: E
+
+ var f: Fun1[E, Comparable]
+
+ redef fun compare(a,b)
+ do
+ var x = f.call(a)
+ var y = f.call(b)
+ if x < y then return -1
+ if x > y then return 1
+ return 0
+ end
+end
--- /dev/null
+[package]
+name=functional
+tags=functional,types
+maintainer=Louis-Vincent Boudreault <lv.boudreault95@gmail.com>
+license=Apache-2.0
+desc=Functional type hierarchies and Stream-like API
+[upstream]
+browse=https://github.com/nitlang/nit/tree/master/lib/functional/
+git=https://github.com/nitlang/nit.git
+git.directory=lib/functional/
+homepage=http://nitlanguage.org
+issues=https://github.com/nitlang/nit/issues
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2019 Louis-Vincent Boudreault <lv.boudreault95@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/license/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.
+
+module test_iter_extras is test
+
+import iter_extras
+private import test_utils
+
+redef class Ref[E]
+ redef fun ==(other) do
+ if other isa Ref[E] then
+ return self.item == other.item
+ end
+ return false
+ end
+end
+
+# test cases using `iter_extras::Iterator::map`
+class TestMapIter
+ test
+
+ # test case for an empty `Array` of `Int`
+ fun add_one_on_empty_array is test do
+ var xs = new Array[Int]
+ var actual = xs.iterator.map(add_one).to_a
+ assert actual.is_empty
+ end
+
+ # test case for an `Array` containing one `Int`
+ fun add_one_on_singleton_array is test do
+ var xs = [1]
+ var actual = xs.iterator.map(add_one).to_a
+ assert actual[0] == 2
+ end
+
+ # test case for `Range`, adding one to each elements (1 to 10)
+ fun add_one_on_range_1_to_10 is test do
+ var xs = [1..10]
+ var actual = xs.iterator.map(add_one).to_a
+ var expected = [2,3,4,5,6,7,8,9,10,11]
+ assert actual == expected
+ end
+
+ # test multiple application of map of an `Array[String]`.
+ fun snake_and_upper_strings is test do
+ var cs = ["helloWorld", "worldHello", "testCase"]
+ var actual = cs.iterator.map(snake_case_fn).map(upper_fn).to_a
+ var expected = ["HELLO_WORLD", "WORLD_HELLO", "TEST_CASE"]
+ assert actual == expected
+ end
+end
+
+# test cases using `iter_extras::Iterator::for_each`
+class TestForEach
+ test
+
+ fun add_one_to_all is test do
+ var xs = new Array[Ref[Int]]
+ var expected = new Array[Ref[Int]]
+ for i in [1..10] do
+ var r1 = new Ref[Int](i)
+ var r2 = new Ref[Int](i+1)
+ xs.push(r1)
+ expected.push(r2)
+ end
+ xs.iterator.for_each(add_one_proc)
+ assert xs == expected
+ end
+
+ fun for_each_empty_array is test do
+ var xs = new Array[Ref[Int]]
+ xs.iterator.for_each(add_one_proc)
+ assert xs.is_empty
+ end
+
+ fun for_each_on_singleton_array is test do
+ var r1 = new Ref[Int](1)
+ var r2 = new Ref[Int](2)
+ var xs = [r1]
+ xs.iterator.for_each(add_one_proc)
+ assert r1 == r2
+ assert xs == [r2]
+ end
+end
+
+# test cases using `iter_extras::Iterator::filter`
+class TestFilterIter
+ test
+
+ # test case for an empty `Array`
+ fun filter_empty_array is test do
+ var xs = new Array[Int]
+ var lt10 = lower_than_fn(10)
+ var actual = xs.iterator.filter(lt10).to_a
+ assert actual.is_empty
+ end
+
+ # test case for a `Range` whose elements doesn't match the predicate
+ fun filter_nomatch is test do
+ var xs = [1..10]
+ var lt0 = lower_than_fn(0)
+ var actual = xs.iterator.filter(lt0).to_a
+ assert actual.is_empty
+ end
+
+ # test case for a `Range` whose elements match 50% of a given predicate
+ fun filter_half_match_on_range_1_to_10 is test do
+ var xs = [1..10]
+ var lt6 = lower_than_fn(6)
+ var actual = xs.iterator.filter(lt6).to_a
+ var expected = [1,2,3,4,5]
+ assert actual == expected
+ end
+
+ # test case for an `Array` whose last element is the only matching element
+ # for a given predicate
+ fun only_last_element_is_a_letter is test do
+ var xs = "123a"
+ var actual = xs.iterator.filter(is_letter_fn).to_a.join
+ assert actual == "a"
+ end
+
+ # test case for a `String` containing mixed alphanumeric characters
+ fun only_letters is test do
+ var cs = "aaa123b4bb3333c1c32c"
+ assert cs.iterator.filter(is_letter_fn).to_a.join == "aaabbbccc"
+ end
+
+ # test case for a `String` containing only one letter in the middle
+ fun has_any_letter_true is test do
+ var cs = "12345a12345"
+ assert cs.iterator.any(is_letter_fn)
+ end
+
+ # test case for an empty `String` that should not contain any letter
+ fun empty_string_has_no_letter is test do
+ var cs = ""
+ assert not cs.iterator.any(is_letter_fn)
+ end
+
+ # test case for a `String` representing a number, should not have any letter
+ fun numeric_string_has_no_letter is test do
+ var cs = "123456"
+ assert not cs.iterator.any(is_letter_fn)
+ end
+end
+
+# test cases using `iter_extras::Iterator::flat_map`
+class TestFlatMapIter
+ test
+
+ # test case for combining three `String`
+ fun combine_aaa_bbb_ccc_to_aaabbbccc is test do
+ var cs = ["aaa","bbb","ccc"]
+ assert cs.iterator.flat_map(chars_fn).to_a.join == "aaabbbccc"
+ end
+
+ fun combine_empty_strings is test do
+ var cs = ["", ""]
+ assert cs.iterator.flat_map(chars_fn).to_a.join == ""
+ end
+
+ fun flat_map_over_empty_array is test do
+ var cs = new Array[String]
+ assert cs.iterator.flat_map(chars_fn).to_a.join == ""
+ end
+end
+
+# test cases using `iter_extras::Iterator::fold`
+class TestFoldIter
+ test
+
+ fun sum_an_empty_array is test do
+ var xs = new Array[Int]
+ var actual = xs.iterator.fold(0, sum_fn)
+ assert actual == 0
+ end
+
+ fun sum_1_to_10 is test do
+ var xs = [1..10]
+ var actual = xs.iterator.fold(0, sum_fn)
+ assert actual == 55
+ end
+
+ fun fold_one_element is test do
+ var xs = [1]
+ var actual = xs.iterator.fold(0, sum_fn)
+ assert actual == xs[0]
+ end
+end
+
+# test cases using `iter_extras::Iterator::fold1`
+class TestFold1Iter
+ test
+
+ fun find_min_in_mixed_array is test do
+ var xs = [45,424,11,43,7,5,8,9,1,-100]
+ var actual = xs.iterator.fold1(min_int_fn)
+ assert actual == -100
+ end
+
+ fun fold1_with_2_elements is test do
+ var xs = [0,-100]
+ var actual = xs.iterator.fold1(min_int_fn)
+ assert actual == -100
+ end
+end
+
+# test cases using `iter_extras::Iterator::order_by`
+class TestOrderedIter
+ test
+
+ fun order_empty_list_of_numbers is test do
+ var xs = new Array[Int]
+ var actual = xs.iterator.order_by(id_int).to_a
+ assert actual == xs
+ end
+
+ fun order_list_of_ints is test do
+ var xs = [5,4,3,2,1]
+ var actual = xs.iterator.order_by(id_int).to_a
+ var expected = [1,2,3,4,5]
+ assert actual == expected
+ end
+
+ fun order_singleton_list_of_ints is test do
+ var xs = [1]
+ var actual = xs.iterator.order_by(id_int).to_a
+ assert actual == xs
+ end
+
+ fun order_list_of_strings_by_alphabetical_order is test do
+ var xs = ["louis", "florian", "alexis", "jean", "alexandre"]
+ var actual = xs.iterator.order_by(id_str).to_a
+ var expected = ["alexandre", "alexis", "florian", "jean", "louis"]
+ assert actual == expected
+ end
+
+ fun order_list_of_strings_by_length is test do
+ var xs = ["louis", "florian", "alexis", "jean", "alexandre"]
+ var actual = xs.iterator.order_by(str_len).to_a
+ var expected = ["jean", "louis", "alexis", "florian", "alexandre"]
+ assert actual == expected
+ end
+end
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2019 Louis-Vincent Boudreault <lv.boudreault95@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.
+
+# This module contains util classes and methods for `test_iter_extras`.
+import functional_types
+
+class SumFn
+ super Fun2[Int,Int,Int]
+
+ redef fun call(x, y)
+ do
+ return x + y
+ end
+end
+
+class MinFn[E: Comparable]
+ super Fun2[E,E,E]
+
+ redef fun call(x, y)
+ do
+ if x < y then
+ return x
+ end
+ return y
+ end
+end
+
+class InitArrayFn[E]
+ super Fun0[Array[E]]
+
+ var initial_val: nullable E
+
+ redef fun call
+ do
+ var xs = new Array[E]
+ if initial_val != null then
+ xs.push(initial_val)
+ end
+ return xs
+ end
+end
+
+class SnakeCaseFn
+ super Fun1[String,String]
+
+ redef fun call(x)
+ do
+ return x.to_snake_case
+ end
+end
+
+class UpperCaseFn
+ super Fun1[String, String]
+
+ redef fun call(x)
+ do
+ return x.to_upper
+ end
+end
+
+class IsLetterFn
+ super Fun1[Char, Bool]
+
+ redef fun call(c)
+ do
+ return c.is_letter
+ end
+end
+
+class AddOneFn
+ super Fun1[Int,Int]
+
+ redef fun call(x)
+ do
+ return x + 1
+ end
+end
+
+class CharsFn
+ super Fun1[String, Iterator[Char]]
+
+ redef fun call(str)
+ do
+ return str.chars.iterator
+ end
+end
+
+class LowerThanFn
+ super Fun1[Int, Bool]
+ var target: Int
+ redef fun call(x)
+ do
+ return x < target
+ end
+end
+
+class IdFn[E]
+ super Fun1[E,E]
+ redef fun call(x)
+ do
+ return x
+ end
+end
+
+class StrLenFn
+ super Fun1[String,Int]
+ redef fun call(x)
+ do
+ return x.length
+ end
+end
+
+class AddOneProc
+ super Proc1[Ref[Int]]
+ redef fun call(x)
+ do
+ x.item += 1
+ end
+end
+
+fun sum_fn: SumFn
+do
+ return new SumFn
+end
+
+fun min_int_fn: MinFn[Int]
+do
+ return new MinFn[Int]
+end
+
+fun new_int_arr(x: nullable Int): InitArrayFn[Int]
+do
+ return new InitArrayFn[Int](x)
+end
+
+fun snake_case_fn: SnakeCaseFn
+do
+ return new SnakeCaseFn
+end
+
+fun upper_fn: UpperCaseFn
+do
+ return new UpperCaseFn
+end
+
+fun is_letter_fn: IsLetterFn
+do
+ return new IsLetterFn
+end
+
+fun add_one: AddOneFn
+do
+ return new AddOneFn
+end
+
+fun add_one_proc: AddOneProc
+do
+ return new AddOneProc
+end
+
+fun chars_fn: CharsFn
+do
+ return new CharsFn
+end
+
+fun lower_than_fn(x: Int): LowerThanFn
+do
+ return new LowerThanFn(x)
+end
+
+fun id_int: IdFn[Int]
+do
+ return new IdFn[Int]
+end
+
+fun id_str: IdFn[String]
+do
+ return new IdFn[String]
+end
+
+fun str_len: StrLenFn
+do
+ return new StrLenFn
+end
end
return path
end
+
+ # Cache of all predecessors for each vertex.
+ # This attribute are lazy to compute the list use `get_all_predecessors` for each needed vertexe.
+ # Warning the cache must be invalidated after `add_arc`
+ private var cache_all_predecessors = new HashMap[V, Set[V]]
+
+ # Cache of all successors for each vertex.
+ # This attribute are lazy to compute the list use `get_all_successors` for each needed vertexe.
+ # Warning the cache must be invalidated after `add_arc`
+ private var cache_all_successors = new HashMap[V, Set[V]]
+
+ # Invalid all cache `cache_all_predecessors` and `cache_all_successors`
+ private fun invalidated_all_cache
+ do
+ if not cache_all_successors.is_empty then cache_all_successors = new HashMap[V, Set[V]]
+ if not cache_all_predecessors.is_empty then cache_all_predecessors = new HashMap[V, Set[V]]
+ end
+
+ # Returns the all predecessors of `u`.
+ #
+ # `u` is include in the returned collection
+ #
+ # Returns an empty Array is the `u` does not exist
+ # ~~~
+ # var g = new HashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 4)
+ # assert g.get_all_predecessors(4).has(4)
+ # assert g.get_all_predecessors(4).has(3)
+ # assert g.get_all_predecessors(4).has(2)
+ # assert g.get_all_predecessors(4).has(1)
+ # ~~~
+ fun get_all_predecessors(u: V): Array[V]
+ do
+ if not vertices.has(u) then return new Array[V]
+ if not cache_all_predecessors.has_key(u) then compute_all_link(u)
+ return cache_all_predecessors[u].clone.to_a
+ end
+
+ # Returns the all successors of `u`.
+ #
+ # `u` is include in the returned collection
+ #
+ # Returns an empty Array is the `u` does not exist
+ # ~~~
+ # var g = new HashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 4)
+ # assert g.get_all_successors(2).has(3)
+ # assert g.get_all_successors(2).has(4)
+ # assert g.get_all_successors(2).has(2)
+ # ~~~
+ fun get_all_successors(u: V): Array[V]
+ do
+ if not vertices.has(u) then return new Array[V]
+ if not cache_all_successors.has_key(u) then compute_all_link(u)
+ return cache_all_successors[u].clone.to_a
+ end
+
+ # Compute all succesors and all predecessors for the given `u`
+ # The result is stocked in `cache_all_predecessors` and `cache_all_predecessors`
+ private fun compute_all_link(u: V)
+ do
+ if not vertices.has(u) then return
+ if not cache_all_predecessors.has_key(u) then cache_all_predecessors[u] = new Set[V]
+ if not cache_all_successors.has_key(u) then cache_all_successors[u] = new Set[V]
+ for v in vertices do
+ if distance(v, u) != null then cache_all_predecessors[u].add(v)
+ if distance(u, v) != null then cache_all_successors[u].add(v)
+ end
+ end
end
# A directed graph represented by hash maps
class HashDigraph[V: Object]
if not has_arc(u, v) then
incoming_vertices_map[v].add(u)
outgoing_vertices_map[u].add(v)
+ invalidated_all_cache
number_of_arcs += 1
end
end
redef fun vertices_iterator: Iterator[V] do return outgoing_vertices_map.keys.iterator
end
+
+# A reflexive directed graph
+# i.e an element is in relation with itself (ie is implies `self.has_arc(u,u)`))
+# This class avoids manually adding the reflexive vertices and at the same time it's avoids adding useless data to the hashmap.
+class ReflexiveHashDigraph[V: Object]
+ super HashDigraph[V]
+
+ # Adds the arc (u,v) to this graph.
+ # if `u` is the same as `v` do nothing
+ #
+ # ~~~
+ # var g = new ReflexiveHashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(3, 1)
+ # assert g.has_arc(2,2)
+ # assert g.has_arc(1,2)
+ # assert g.has_arc(3,1)
+ # ~~~
+ redef fun add_arc(u, v)
+ do
+ # Check `u` is the same as `v`
+ if u != v then
+ super
+ end
+ end
+
+ # Is (u,v) an arc in this graph?
+ # If `u` is the same as `v` return true
+ #
+ # ~~~
+ # var g = new ReflexiveHashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(3, 1)
+ # g.add_vertex(4)
+ # assert g.has_arc(1,1)
+ # assert g.has_arc(2,2)
+ # assert g.has_arc(2,2)
+ # assert g.has_arc(3,2) == false
+ # assert g.has_arc(4,4)
+ # ~~~
+ redef fun has_arc(u, v)
+ do
+ return u == v or super
+ end
+
+ redef fun show_dot
+ do
+ var f = new ProcessWriter("dot", "-Txlib")
+ f.write to_dot
+ f.close
+ f.wait
+ end
+
+ # Returns a shortest path from vertex `u` to `v`.
+ #
+ # If `u` is the same as `v` return `[u]`
+ #
+ # ~~~
+ # var g = new ReflexiveHashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 4)
+ # assert g.a_shortest_path(1, 4).length == 4
+ # assert g.a_shortest_path(1, 1).length == 1
+ # ~~~
+ redef fun a_shortest_path(u, v)
+ do
+ if u == v then
+ var path = new List[V]
+ path.add(u)
+ return path
+ end
+ return super
+ end
+
+ # Returns the distance between `u` and `v`
+ #
+ # If `u` is the same as `v` return `1`
+ #
+ # ~~~
+ # var g = new ReflexiveHashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 4)
+ # assert g.distance(1, 1) == 1
+ # assert g.distance(2, 2) == 1
+ # ~~~
+ redef fun distance(u, v)
+ do
+ if has_arc(u, v) and u == v then return 1
+ return super
+ end
+
+ # Returns the predecessors of `u`.
+ #
+ # `u` is include in the returned collection
+ #
+ # ~~~
+ # var g = new ReflexiveHashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 1)
+ # assert g.predecessors(2).has(1)
+ # assert g.predecessors(2).has(2)
+ # ~~~
+ redef fun predecessors(u)
+ do
+ var super_predecessors = super
+ if incoming_vertices_map.has_key(u) then super_predecessors.add(u)
+ return super_predecessors
+ end
+
+ # Returns the successors of `u`.
+ #
+ # `u` is include in the returned collection
+ #
+ # ~~~
+ # var g = new ReflexiveHashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 1)
+ # assert g.successors(2).has(3)
+ # assert g.successors(2).has(2)
+ # ~~~
+ redef fun successors(u: V)
+ do
+ var super_successors = super
+ if outgoing_vertices_map.has_key(u) then super_successors.add(u)
+ return super_successors
+ end
+end
var contrib2proj = new MultiHashMap[Person, MPackage]
# Dependency between packages
- var deps = new POSet[MPackage]
+ fun deps: HashDigraph[MPackage] do return modelbuilder.model.mpackage_importation_graph
# Number of modules by package
var mmodules = new Counter[MPackage]
cat2proj[cat].add mpackage
score += tags.length.score
end
- if deps.has(mpackage) then
- score += deps[mpackage].greaters.length.score
- score += deps[mpackage].direct_greaters.length.score
- score += deps[mpackage].smallers.length.score
- score += deps[mpackage].direct_smallers.length.score
+ if deps.has_vertex(mpackage) then
+ score += deps.predecessors(mpackage).length.score
+ score += deps.get_all_predecessors(mpackage).length.score
+ score += deps.successors(mpackage).length.score
+ score += deps.get_all_successors(mpackage).length.score
end
var contributors = mpackage.metadata.contributors
var g = p.root
assert g != null
test_builder.scan_group(g)
-
- catalog.deps.add_node(p)
- for gg in p.mgroups do for m in gg.mmodules do
- for im in m.in_importation.direct_greaters do
- var ip = im.mpackage
- if ip == null or ip == p then continue
- test_catalog.deps.add_edge(p, ip)
- end
- end
end
# Build the catalog
for mpackage in test_model.mpackages do
super
main_tab.metadata.cards.add new CardMetadata(mentity, mentity.metadata,
doc.catalog.mpackages_stats[mentity],
- doc.catalog.deps[mentity].direct_greaters.to_a,
- doc.catalog.deps[mentity].direct_smallers.to_a)
+ doc.catalog.deps.successors(mentity).to_a,
+ doc.catalog.deps.predecessors(mentity).to_a)
end
end
self.in_importation = model.mmodule_importation_hierarchy.add_node(self)
end
- # Register the imported modules (ie "import some_module")
+ # Register the imported modules (ie "import some_module") and packages importation graph
+ # In the same time it register the imported package
# The visibility must be set with `set_visibility_for`.
fun set_imported_mmodules(imported_mmodules: Array[MModule])
do
for m in imported_mmodules do
self.model.mmodule_importation_hierarchy.add_edge(self, m)
+ var actual_mpackage = self.mpackage
+ var imported_mpackage = m.mpackage
+ if actual_mpackage != null and imported_mpackage != null then
+ # Register the imported package
+ self.model.mpackage_importation_graph.add_arc(actual_mpackage, imported_mpackage)
+ end
end
end
private import more_collections
import poset
import mdoc
+import graph::digraph
# A Nit package, that encompass a product
class MPackage
init
do
model.mpackages.add(self)
+ # Add `self` to the importation graph
+ model.mpackage_importation_graph.add_vertex(self)
model.mpackage_by_name.add_one(name, self)
end
end
redef class Model
+
+ # Full package importation graph
+ # Each package is in relation with itself
+ var mpackage_importation_graph = new HashDigraph[MPackage]
+
# packages of the model
var mpackages = new Array[MPackage]
end
res.add_list(ts2, ", ", ", ")
- if deps.has(mpackage) then
- var reqs = deps[mpackage].greaters.to_a
+ if deps.vertices.has(mpackage) then
+ var reqs = deps.get_all_successors(mpackage)
reqs.remove(mpackage)
alpha_comparator.sort(reqs)
res.add "<h3>Requirements</h3>\n"
else
var list = new Array[String]
for r in reqs do
- var direct = deps.has_direct_edge(mpackage, r)
+ var direct = deps.has_arc(mpackage, r)
var s = "<a href=\"{r}.html\">"
if direct then s += "<strong>"
s += r.to_s
res.add_list(list, ", ", " and ")
end
- reqs = deps[mpackage].smallers.to_a
+ reqs = deps.get_all_predecessors(mpackage)
reqs.remove(mpackage)
alpha_comparator.sort(reqs)
res.add "<h3>Clients</h3>\n"
else
var list = new Array[String]
for r in reqs do
- var direct = deps.has_direct_edge(r, mpackage)
+ var direct = deps.has_arc(r, mpackage)
var s = "<a href=\"{r}.html\">"
if direct then s += "<strong>"
s += r.to_s
res.add "<th data-field=\"name\" data-sortable=\"true\">name</th>\n"
res.add "<th data-field=\"maint\" data-sortable=\"true\">maint</th>\n"
res.add "<th data-field=\"contrib\" data-sortable=\"true\">contrib</th>\n"
- if deps.not_empty then
+ if deps.vertices.not_empty then
res.add "<th data-field=\"reqs\" data-sortable=\"true\">reqs</th>\n"
res.add "<th data-field=\"dreqs\" data-sortable=\"true\">direct<br>reqs</th>\n"
res.add "<th data-field=\"cli\" data-sortable=\"true\">clients</th>\n"
if p.metadata.maintainers.not_empty then maint = p.metadata.maintainers.first.name.html_escape
res.add "<td>{maint}</td>"
res.add "<td>{p.metadata.contributors.length}</td>"
- if deps.not_empty then
- res.add "<td>{deps[p].greaters.length-1}</td>"
- res.add "<td>{deps[p].direct_greaters.length}</td>"
- res.add "<td>{deps[p].smallers.length-1}</td>"
- res.add "<td>{deps[p].direct_smallers.length}</td>"
+ if deps.vertices.not_empty then
+ res.add "<td>{deps.get_all_successors(p).length-1}</td>"
+ res.add "<td>{deps.successors(p).length}</td>"
+ res.add "<td>{deps.get_all_predecessors(p).length-1}</td>"
+ res.add "<td>{deps.predecessors(p).length}</td>"
end
res.add "<td>{mmodules[p]}</td>"
res.add "<td>{mclasses[p]}</td>"
else
mmodules = modelbuilder.parse_full(args)
end
-var mpackages = new Set[MPackage]
-for m in mmodules do
- var p = m.mpackage
- if p != null then mpackages.add p
-end
+var mpackages = modelbuilder.model.mpackage_importation_graph.vertices
# Scan packages and compute information
-for p in model.mpackages do
+for p in mpackages do
var g = p.root
assert g != null
modelbuilder.scan_group(g)
-
- # Load the module to process importation information
- if opt_no_parse.value then continue
-
- catalog.deps.add_node(p)
- for gg in p.mgroups do for m in gg.mmodules do
- for im in m.in_importation.direct_greaters do
- var ip = im.mpackage
- if ip == null or ip == p then continue
- catalog.deps.add_edge(p, ip)
- end
- end
end
if not opt_no_git.value then for p in mpackages do
index.add "<h2>Highlighted Packages</h2>\n"
index.add catalog.list_best(catalog.score)
-if catalog.deps.not_empty then
+if catalog.deps.vertices.not_empty then
index.add "<h2>Most Required</h2>\n"
var reqs = new Counter[MPackage]
for p in mpackages do
- reqs[p] = catalog.deps[p].smallers.length - 1
+ reqs[p] = catalog.deps.get_all_successors(p).length - 1
end
index.add catalog.list_best(reqs)
end
var g = p.root
assert g != null
modelbuilder.scan_group(g)
-
- deps.add_node(p)
- for gg in p.mgroups do for m in gg.mmodules do
- for im in m.in_importation.direct_greaters do
- var ip = im.mpackage
- if ip == null or ip == p then continue
- deps.add_edge(p, ip)
- end
- end
end
# Build the catalog
for mpackage in mpackages do
var g = p.root
assert g != null
modelbuilder.scan_group(g)
-
- catalog.deps.add_node(p)
- for gg in p.mgroups do for m in gg.mmodules do
- for im in m.in_importation.direct_greaters do
- var ip = im.mpackage
- if ip == null or ip == p then continue
- catalog.deps.add_edge(p, ip)
- end
- end
end
# Build the catalog
for mpackage in mpackages do
redef class Catalog
# Build the catalog for Nitx
private fun build_catalog(model: Model, filter: nullable ModelFilter) do
- # Compute the poset
+ # Scan all modules of collected packages
for p in model.collect_mpackages(filter) do
var g = p.root
assert g != null
modelbuilder.scan_group(g)
-
- deps.add_node(p)
- for gg in p.mgroups do for m in gg.mmodules do
- for im in m.in_importation.direct_greaters do
- var ip = im.mpackage
- if ip == null or ip == p then continue
- deps.add_edge(p, ip)
- end
- end
end
# Build the catalog
for mpackage in model.collect_mpackages(filter) do
nitlanguage / nit.git / commitdiff