diff options
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc')
12 files changed, 1025 insertions, 139 deletions
diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java index 73ace88..88db172 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java @@ -13,16 +13,19 @@ import java.util.function.Function; import java.util.function.Predicate; import bjc.utils.data.GenHolder; +import bjc.utils.data.Pair; /** - * A wrapper over another list that provides eager functional operations over it. - * Differs from a stream in every way except for the fact that they both provide functional - * operations. + * A wrapper over another list that provides eager functional operations + * over it. Differs from a stream in every way except for the fact that + * they both provide functional operations. + * * @author ben * - * @param <E> The type in this list + * @param <E> + * The type in this list */ -public class FunctionalList<E> { +public class FunctionalList<E> implements Cloneable { private List<E> wrap; /** @@ -34,7 +37,9 @@ public class FunctionalList<E> { /** * Create a new functional list containing the specified items. - * @param items The items to put into this functional list. + * + * @param items + * The items to put into this functional list. */ @SafeVarargs public FunctionalList(E... items) { @@ -46,26 +51,32 @@ public class FunctionalList<E> { } /** - * Create a functional list using the same backing list as the provided list. + * Create a functional list using the same backing list as the provided + * list. * - * @param fl The source for a backing list + * @param fl + * The source for a backing list */ - public FunctionalList(FunctionalList<E> fl) { + public FunctionalList(FunctionalList<E> fl) { // TODO Find out if this should make a copy of fl.wrap instead. wrap = fl.wrap; } /** * Create a new functional list with the specified size. - * @param sz The size of the backing list . + * + * @param sz + * The size of the backing list . */ private FunctionalList(int sz) { wrap = new ArrayList<>(sz); } - + /** * Create a new functional list as a wrapper of a existing list. - * @param l The list to use as a backing list. + * + * @param l + * The list to use as a backing list. */ public FunctionalList(List<E> l) { wrap = l; @@ -73,17 +84,31 @@ public class FunctionalList<E> { /** * Add an item to this list - * @param item The item to add to this list. + * + * @param item + * The item to add to this list. * @return Whether the item was added to the list succesfully. */ public boolean add(E item) { return wrap.add(item); } + + /** + * Prepend an item to the list + * @param item The item to prepend to the list + */ + public void prepend(E item) { + wrap.add(0, item); + } /** - * Check if all of the elements of this list match the specified predicate. - * @param p The predicate to use for checking. - * @return Whether all of the elements of the list match the specified predicate. + * Check if all of the elements of this list match the specified + * predicate. + * + * @param p + * The predicate to use for checking. + * @return Whether all of the elements of the list match the specified + * predicate. */ public boolean allMatch(Predicate<E> p) { for (E item : wrap) { @@ -96,8 +121,11 @@ public class FunctionalList<E> { /** * Check if any of the elements in this list match the specified list. - * @param p The predicate to use for checking. - * @return Whether any element in the list matches the provided predicate. + * + * @param p + * The predicate to use for checking. + * @return Whether any element in the list matches the provided + * predicate. */ public boolean anyMatch(Predicate<E> p) { for (E item : wrap) { @@ -109,29 +137,36 @@ public class FunctionalList<E> { } /** - * Combine this list with another one into a new list and merge the results. - * Works sort of like a combined zip/map over resulting pairs. - * Does not change the underlying list. + * Combine this list with another one into a new list and merge the + * results. Works sort of like a combined zip/map over resulting pairs. + * Does not change the underlying list. + * + * NOTE: The returned list will have the length of the shorter of this + * list and the combined one. * - * NOTE: The returned list will have the length of the shorter of this list and the combined one. - * @param l The list to combine with - * @param bf The function to use for combining element pairs. + * @param l + * The list to combine with + * @param bf + * The function to use for combining element pairs. * @return A new list containing the merged pairs of lists. */ - public <T, F> FunctionalList<F> combineWith(FunctionalList<T> l, BiFunction<E, T, F> bf) { + public <T, F> FunctionalList<F> combineWith(FunctionalList<T> l, + BiFunction<E, T, F> bf) { FunctionalList<F> r = new FunctionalList<>(); - + Iterator<T> i2 = l.wrap.iterator(); - - for (Iterator<E> i1 = wrap.iterator(); i1.hasNext() && i2.hasNext();) { + + for (Iterator<E> i1 = wrap.iterator(); i1.hasNext() + && i2.hasNext();) { r.add(bf.apply(i1.next(), i2.next())); } - + return r; } /** * Get the first element in the list + * * @return The first element in this list. */ public E first() { @@ -139,10 +174,13 @@ public class FunctionalList<E> { } /** - * Apply a function to each member of the list, then flatten the results. - * Does not change the underlying list. - * @param f The function to apply to each member of the list. - * @return A new list containing the flattened results of applying the provided function. + * Apply a function to each member of the list, then flatten the + * results. Does not change the underlying list. + * + * @param f + * The function to apply to each member of the list. + * @return A new list containing the flattened results of applying the + * provided function. */ public <T> FunctionalList<T> flatMap(Function<E, List<T>> f) { FunctionalList<T> fl = new FunctionalList<>(this.wrap.size()); @@ -158,7 +196,9 @@ public class FunctionalList<E> { /** * Apply a given action for each member of the list - * @param c The action to apply to each member of the list. + * + * @param c + * The action to apply to each member of the list. */ public void forEach(Consumer<E> c) { wrap.forEach(c); @@ -166,7 +206,10 @@ public class FunctionalList<E> { /** * Apply a given function to each element in the list and its index. - * @param c The function to apply to each element in the list and its index. + * + * @param c + * The function to apply to each element in the list and its + * index. */ public void forEachIndexed(BiConsumer<Integer, E> c) { int i = 0; @@ -178,7 +221,9 @@ public class FunctionalList<E> { /** * Retrieve a value in the list by its index. - * @param i The index to retrieve a value from. + * + * @param i + * The index to retrieve a value from. * @return The value at the specified index in the list. */ public E getByIndex(int i) { @@ -187,6 +232,7 @@ public class FunctionalList<E> { /** * Get the internal backing list. + * * @return The backing list this list is based off of. */ public List<E> getInternal() { @@ -195,6 +241,7 @@ public class FunctionalList<E> { /** * Check if this list is empty. + * * @return Whether or not this list is empty. */ public boolean isEmpty() { @@ -202,9 +249,11 @@ public class FunctionalList<E> { } /** - * Create a new list by applying the given function to each element in the list. - * Does not change the underlying list. - * @param f The function to apply to each element in the list + * Create a new list by applying the given function to each element in + * the list. Does not change the underlying list. + * + * @param f + * The function to apply to each element in the list * @return A new list containing the mapped elements of this list. */ public <T> FunctionalList<T> map(Function<E, T> f) { @@ -216,8 +265,11 @@ public class FunctionalList<E> { } /** - * Select a random item from this list, using the provided random number generator. - * @param rnd The random number generator to use. + * Select a random item from this list, using the provided random + * number generator. + * + * @param rnd + * The random number generator to use. * @return A random element from this list. */ public E randItem(Random rnd) { @@ -226,27 +278,38 @@ public class FunctionalList<E> { /** * Reduce this list to a single value, using a accumulative approach. - * @param val The initial value of the accumulative state. - * @param bf The function to use to combine a list element with the accumulative state. - * @param finl The function to use to convert the accumulative state into a final result. - * @return A single value condensed from this list and transformed into its final state. + * + * @param val + * The initial value of the accumulative state. + * @param bf + * The function to use to combine a list element with the + * accumulative state. + * @param finl + * The function to use to convert the accumulative state + * into a final result. + * @return A single value condensed from this list and transformed into + * its final state. */ - public <T, F> F reduceAux(T val, BiFunction<E, T, T> bf, Function<T, F> finl) { + public <T, F> F reduceAux(T val, BiFunction<E, T, T> bf, + Function<T, F> finl) { GenHolder<T> acum = new GenHolder<>(val); - + wrap.forEach(e -> { acum.held = bf.apply(e, acum.held); }); - + return finl.apply(acum.held); } /** - * Perform a binary search for the specified key using the provided means of - * comparing elements. - * Since this IS a binary search, the list must have been sorted before hand. - * @param key The key to search for. - * @param cmp The way to compare elements for searching + * Perform a binary search for the specified key using the provided + * means of comparing elements. Since this IS a binary search, the list + * must have been sorted before hand. + * + * @param key + * The key to search for. + * @param cmp + * The way to compare elements for searching * @return The element if it is in this list, or null if it is not. */ public E search(E key, Comparator<E> cmp) { @@ -254,19 +317,22 @@ public class FunctionalList<E> { return (res >= 0) ? wrap.get(res) : null; } - + /** - * Sort the elements of this list using the provided way of comparing elements. - * Does change the underlying list. - * @param cmp The way to compare elements for sorting. + * Sort the elements of this list using the provided way of comparing + * elements. Does change the underlying list. + * + * @param cmp + * The way to compare elements for sorting. */ public void sort(Comparator<E> cmp) { Collections.sort(wrap, cmp); } - + /* * Reduce this item to a form useful for looking at in the debugger. * (non-Javadoc) + * * @see java.lang.Object#toString() */ public String toString() { @@ -274,9 +340,24 @@ public class FunctionalList<E> { forEach(s -> sb.append(s + ", ")); - sb.deleteCharAt(sb.length()); + sb.deleteCharAt(sb.length() - 1); sb.append(")"); return sb.toString(); } + + public <T> FunctionalList<Pair<E, T>> pairWith(FunctionalList<T> fl) { + return combineWith(fl, Pair<E, T>::new); + } + + @Override + public FunctionalList<E> clone() { + FunctionalList<E> fl = new FunctionalList<>(); + + for (E ele : wrap) { + fl.add(ele); + } + + return fl; + } } diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalStringTokenizer.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalStringTokenizer.java index 0fe8421..9ee6b60 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalStringTokenizer.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalStringTokenizer.java @@ -6,6 +6,7 @@ import java.util.function.Function; /** * A string tokenizer that exposes a functional interface + * * @author ben * */ @@ -14,35 +15,46 @@ public class FunctionalStringTokenizer { /** * Create a functional string tokenizer from a non-functional one - * @param inp The non-functional string tokenizer to wrap + * + * @param inp + * The non-functional string tokenizer to wrap */ public FunctionalStringTokenizer(StringTokenizer inp) { this.inp = inp; } - + + public FunctionalStringTokenizer(String inp) { + this.inp = new StringTokenizer(inp); + } + /** * Execute a provided action for each of the remaining tokens - * @param f The action to execute for each token + * + * @param f + * The action to execute for each token */ public void forEachToken(Consumer<String> f) { - while(inp.hasMoreTokens()) { + while (inp.hasMoreTokens()) { f.accept(inp.nextToken()); } } - + /** - * Return the next token from the tokenizer - * Returns null if no more tokens are available + * Return the next token from the tokenizer Returns null if no more + * tokens are available + * * @return The next token from the tokenizer */ public String nextToken() { return inp.hasMoreTokens() ? inp.nextToken() : null; } - + /** - * Convert the contents of this tokenizer into a list. - * Consumes all of the input from this tokenizer. - * @param f The function to use to convert tokens. + * Convert the contents of this tokenizer into a list. Consumes all of + * the input from this tokenizer. + * + * @param f + * The function to use to convert tokens. * @return A list containing all of the converted tokens. */ public <E> FunctionalList<E> toList(Function<String, E> f) { @@ -52,10 +64,12 @@ public class FunctionalStringTokenizer { return r; } - + /** * Create a new tokenizer from the specified string. - * @param s The string to create a tokenizer from. + * + * @param s + * The string to create a tokenizer from. * @return A new tokenizer that splits the provided string on spaces. */ public static FunctionalStringTokenizer fromString(String s) { diff --git a/BJC-Utils2/src/main/java/bjc/utils/gen/WeightedGrammar.java b/BJC-Utils2/src/main/java/bjc/utils/gen/WeightedGrammar.java index 8733723..228f14d 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/gen/WeightedGrammar.java +++ b/BJC-Utils2/src/main/java/bjc/utils/gen/WeightedGrammar.java @@ -1,46 +1,55 @@ package bjc.utils.gen; -import java.util.HashMap; +import java.util.Hashtable; import java.util.Map; import java.util.Random; +import java.util.Set; import java.util.function.Function; +import bjc.utils.data.Pair; import bjc.utils.funcdata.FunctionalList; /** - * A random grammar, where certain rules will come up morre often than + * A random grammar, where certain rules will come up more often than * others. * * @author ben * - * @param <E> The values that make up sentances of this grammar. + * @param <E> + * The values that make up sentances of this grammar. */ public class WeightedGrammar<E> { + protected String initRule; protected Map<E, WeightedRandom<FunctionalList<E>>> rules; + private Random sr; protected Map<E, WeightedGrammar<E>> subgrammars; - private Random sr; /** - * Create a new weighted grammar that uses the specified source of randomness. + * Create a new weighted grammar. */ - public WeightedGrammar(Random src) { - this(); - sr = src; + public WeightedGrammar() { + rules = new Hashtable<>(); + subgrammars = new Hashtable<>(); } - + /** - * Create a new weighted grammar. + * Create a new weighted grammar that uses the specified source of + * randomness. */ - public WeightedGrammar() { - rules = new HashMap<>(); + public WeightedGrammar(Random src) { + this(); + sr = src; } /** * Add a case to an already existing rule. * - * @param rule The rule to add a case to. - * @param prob The probability for this rule to be chosen. - * @param cse The case being added. + * @param rule + * The rule to add a case to. + * @param prob + * The probability for this rule to be chosen. + * @param cse + * The case being added. */ public void addCase(E rule, int prob, FunctionalList<E> cse) { WeightedRandom<FunctionalList<E>> rn = rules.get(rule); @@ -48,13 +57,28 @@ public class WeightedGrammar<E> { rn.addProb(prob, cse); } + public boolean addGrammarAlias(E name, E alias) { + if (subgrammars.containsKey(alias)) { + return false; + } else { + if (subgrammars.containsKey(name)) { + subgrammars.put(alias, subgrammars.get(name)); + return true; + } else { + return false; + } + } + } + /** * Add a new rule with no cases. - * @param name The name of the rule to add. + * + * @param name + * The name of the rule to add. * @return Whether or not the rule was succesfully added. */ public boolean addRule(E name) { - if(sr == null) { + if (sr == null) { sr = new Random(); } return addRule(name, new WeightedRandom<>(sr)); @@ -62,8 +86,11 @@ public class WeightedGrammar<E> { /** * Add a new rule with a set of cases. - * @param name The name of the rule to add. - * @param rnd The set of cases for the rule. + * + * @param name + * The name of the rule to add. + * @param rnd + * The set of cases for the rule. * @return Whether or not the rule was succesfully added. */ public boolean addRule(E name, WeightedRandom<FunctionalList<E>> rnd) { @@ -77,8 +104,11 @@ public class WeightedGrammar<E> { /** * Add a subgrammar. - * @param name The name of the subgrammar. - * @param subG The subgrammar to add. + * + * @param name + * The name of the subgrammar. + * @param subG + * The subgrammar to add. * @return Whether or not the subgrammar was succesfully added. */ public boolean addSubGrammar(E name, WeightedGrammar<E> subG) { @@ -91,9 +121,11 @@ public class WeightedGrammar<E> { } /** - * Generate a set of debug sentences for the specified rule. - * Only generates sentances one layer deep. - * @param rl The rule to test. + * Generate a set of debug sentences for the specified rule. Only + * generates sentances one layer deep. + * + * @param rl + * The rule to test. * @return A set of sentances generated by the specified rule. */ public FunctionalList<FunctionalList<E>> debugVals(E rl) { @@ -111,10 +143,14 @@ public class WeightedGrammar<E> { /** * Generate a generic sentance from a initial rule. * - * @param initRule The initial rule to start with. - * @param f The function to transform grammar output into something. - * @param spacer The spacer element to add in between output tokens. - * @return A randomly generated sentance from the specified initial rule. + * @param initRule + * The initial rule to start with. + * @param f + * The function to transform grammar output into something. + * @param spacer + * The spacer element to add in between output tokens. + * @return A randomly generated sentance from the specified initial + * rule. */ public <T> FunctionalList<T> genGeneric(E initRule, Function<E, T> f, T spacer) { @@ -141,18 +177,29 @@ public class WeightedGrammar<E> { } /** - * Generate a random list of grammar elements from a given initial rule. - * @param initRule The initial rule to start with. - * @param spacer The item to use to space the list. - * @return A list of random grammar elements generated by the specified rule. + * Generate a random list of grammar elements from a given initial + * rule. + * + * @param initRule + * The initial rule to start with. + * @param spacer + * The item to use to space the list. + * @return A list of random grammar elements generated by the specified + * rule. */ public FunctionalList<E> genList(E initRule, E spacer) { return genGeneric(initRule, s -> s, spacer); } + public String getInitRule() { + return initRule; + } + /** * Get the subgrammar with the specified name. - * @param name The name of the subgrammar to get. + * + * @param name + * The name of the subgrammar to get. * @return The subgrammar with the specified name. */ public WeightedGrammar<E> getSubGrammar(E name) { @@ -160,8 +207,68 @@ public class WeightedGrammar<E> { } /** + * Create a series of alternatives for a rule by prefixing them with a + * given token + * + * @param addProb + * The amount to adjust the probability by + * @param rName + * The name of the rule to prefix + * @param prefixToken + * The token to prefix to the rule + */ + public void prefixRule(E rName, E prefixToken, int addProb) { + WeightedRandom<FunctionalList<E>> rule = rules.get(rName); + + FunctionalList<Pair<Integer, FunctionalList<E>>> newResults = new FunctionalList<>(); + + rule.getValues().forEach((par) -> { + FunctionalList<E> nl = par.r.clone(); + nl.prepend(prefixToken); + + newResults.add(new Pair<>(par.l + addProb, nl)); + }); + + newResults.forEach((par) -> { + addCase(rName, par.l, par.r); + }); + } + + public void multiPrefixRule(E rName, E prefixToken, int addProb, + int nTimes) { + WeightedRandom<FunctionalList<E>> rule = rules.get(rName); + + FunctionalList<Pair<Integer, FunctionalList<E>>> newResults = new FunctionalList<>(); + + rule.getValues().forEach((par) -> { + FunctionalList<FunctionalList<E>> nls = new FunctionalList<>(); + + // TODO bugtest this. if it works, write multiSuffixWith + for (int i = 1; i <= nTimes; i++) { + FunctionalList<E> nl = par.r.clone(); + + for (int j = 1; j <= i; j++) { + nl.prepend(prefixToken); + } + + nls.add(nl); + } + + nls.forEach((ls) -> { + newResults.add(new Pair<>(par.l + addProb, ls)); + }); + }); + + newResults.forEach((par) -> { + addCase(rName, par.l, par.r); + }); + } + + /** * Remove a rule with the specified name. - * @param name The name of the rule to remove. + * + * @param name + * The name of the rule to remove. */ public void removeRule(E name) { rules.remove(name); @@ -169,9 +276,54 @@ public class WeightedGrammar<E> { /** * Remove a subgrammar with the specified name. - * @param name The name of the subgrammar to remove. + * + * @param name + * The name of the subgrammar to remove. */ public void removeSubgrammar(E name) { subgrammars.remove(name); } + + /** + * Returns the number of rules in this grammar + * + * @return The number of rules in this grammar + */ + public int ruleCount() { + return rules.size(); + } + + /** + * Returns a set containing all of the rules in this grammar + * + * @return The set of all rule names in this grammar + */ + public Set<E> ruleNames() { + return rules.keySet(); + } + + public void setInitRule(String initRule) { + this.initRule = initRule; + } + + public void suffixRule(E rName, E prefixToken, int addProb) { + WeightedRandom<FunctionalList<E>> rule = rules.get(rName); + + FunctionalList<Pair<Integer, FunctionalList<E>>> newResults = new FunctionalList<>(); + + rule.getValues().forEach((par) -> { + FunctionalList<E> nl = par.r.clone(); + nl.add(prefixToken); + + newResults.add(new Pair<>(par.l + addProb, nl)); + }); + + newResults.forEach((par) -> { + addCase(rName, par.l, par.r); + }); + } + + public boolean hasInitRule() { + return initRule != null && !initRule.equalsIgnoreCase(""); + } } diff --git a/BJC-Utils2/src/main/java/bjc/utils/gen/WeightedRandom.java b/BJC-Utils2/src/main/java/bjc/utils/gen/WeightedRandom.java index ecd4e36..4313360 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/gen/WeightedRandom.java +++ b/BJC-Utils2/src/main/java/bjc/utils/gen/WeightedRandom.java @@ -1,9 +1,9 @@ package bjc.utils.gen; import java.util.Random; - import bjc.utils.funcdata.FunctionalList; import bjc.utils.data.GenHolder; +import bjc.utils.data.Pair; /** * Represents a random number generator where certain results are weighted more heavily than @@ -65,4 +65,21 @@ public class WeightedRandom<E> { return res.held; } + + /** + * Return a list containing values that can be generated paired + * with the probability of those values being generated + * @return A list of pairs of values and value probabilities + */ + public FunctionalList<Pair<Integer, E>> getValues() { + return probs.pairWith(results); + } + + /** + * Return a list of values that can be generated by this generator + * @return A list of all the values that can be generated + */ + public FunctionalList<E> getResults() { + return results; + } } diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java b/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java new file mode 100644 index 0000000..7a79233 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java @@ -0,0 +1,100 @@ +package bjc.utils.graph; + +import java.io.InputStream; +import java.io.OutputStream; +import java.io.PrintStream; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Map; +import java.util.Scanner; +import java.util.Set; +import java.util.stream.IntStream; + +public class AdjacencyMap<T> { + private Map<T, Map<T, Integer>> adjMap; + + public AdjacencyMap(Set<T> vertices) { + vertices.forEach(src -> { + Map<T, Integer> srcRow = new HashMap<>(); + + vertices.forEach(tgt -> srcRow.put(tgt, 0)); + + adjMap.put(src, srcRow); + }); + } + + public boolean isDirected() { + GenHolder<Boolean> res = new GenHolder<>(true); + + adjMap.entrySet() + .forEach(src -> src.getValue().entrySet().forEach(tgt -> { + int lhs = tgt.getValue(); + int rhs = adjMap.get(tgt.getKey()).get(src.getKey()); + + if (lhs != rhs) { + res.held = false; + } + })); + + return res.held; + } + + public void setWeight(T src, T tgt, int weight) { + adjMap.get(src).put(tgt, weight); + } + + public Graph<T> toGraph() { + Graph<T> ret = new Graph<>(); + + adjMap.entrySet() + .forEach(src -> src.getValue().entrySet() + .forEach(tgt -> ret.addEdge(src.getKey(), + tgt.getKey(), tgt.getValue()))); + + return ret; + } + + public static AdjacencyMap<Integer> fromStream(InputStream stream) { + Scanner scn = new Scanner(stream); + scn.useDelimiter("\n"); + + // First, read in number of vertices + int numVertices = Integer.parseInt(scn.next()); + + Set<Integer> vertices = new HashSet<>(); + IntStream.range(0, numVertices).forEach(e -> vertices.add(e)); + + // Create the adjacency map + AdjacencyMap<Integer> aMap = new AdjacencyMap<>(vertices); + + GenHolder<Integer> row = new GenHolder<>(0); + + scn.forEachRemaining((strang) -> { + String[] parts = strang.split(" "); + int col = 0; + + for (String part : parts) { + aMap.setWeight(row.held, col, Integer.parseInt(part)); + + col++; + } + + row.held++; + }); + + scn.close(); + + return aMap; + } + + public void toStream(OutputStream os) { + PrintStream ps = new PrintStream(os); + + adjMap.entrySet().forEach(src -> { + src.getValue().entrySet() + .forEach(tgt -> ps.printf("%d ", tgt.getValue())); + ps.println(); + }); + ps.close(); + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java b/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java new file mode 100644 index 0000000..9fb20c0 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java @@ -0,0 +1,30 @@ +package bjc.utils.graph; + +public class Edge<T> { + private final T source, target; + private final int distance; + + public Edge(T node1, T node2, int distance) { + this.source = node1; + this.target = node2; + this.distance = distance; + } + + public T getSource() { + return source; + } + + public T getTarget() { + return target; + } + + public int getDistance() { + return distance; + } + + @Override + public String toString() { + return " first vertex " + source + " to vertex " + target + + " with distance: " + distance; + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/GenHolder.java b/BJC-Utils2/src/main/java/bjc/utils/graph/GenHolder.java new file mode 100644 index 0000000..df363fa --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/graph/GenHolder.java @@ -0,0 +1,75 @@ +package bjc.utils.graph; + +import java.util.function.Function; + +/** + * Holds a single value of a specific type. This is used for indirect + * references to data, and more specifically for accessing non-final + * variables from a lambda. AKA the identity monad + * + * @author ben + * + * @param <T> + * The type of the data being held + */ +public class GenHolder<T> { + /** + * The state this holder is responsible for. + */ + public T held; + + /** + * Creates a new empty holder, with its state set to null + */ + public GenHolder() { + held = null; + } + + /** + * Creates a new holder, with its state initialized to the provided + * value + * + * @param held + * The state to initialize this holder to. + */ + public GenHolder(T hld) { + held = hld; + } + + /** + * Apply the given transformation to the held value. Returns the holder + * for allowing chaining of transforms + * + * @param f + * The transform to apply to the value + * @return The holder + */ + public GenHolder<T> transform(Function<T, T> f) { + held = f.apply(held); + + return this; + } + + /** + * Return the result of applying the given transformation to the held + * value Doesn't change the held value + * + * @param f + * The transformation to apply + * @return A holder with the transformed value + */ + public <NewT> GenHolder<NewT> map(Function<T, NewT> f) { + return new GenHolder<NewT>(f.apply(held)); + } + + /** + * Returns a raw mapped value, not contained in a GenHolder + * + * @param f + * The function to use for mapping the value + * @return The mapped value outside of a GenHolder + */ + public <E> E unwrap(Function<T, E> f) { + return f.apply(held); + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java b/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java new file mode 100644 index 0000000..69e42e4 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java @@ -0,0 +1,236 @@ +package bjc.utils.graph; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.NoSuchElementException; +import java.util.PriorityQueue; +import java.util.Queue; +import java.util.Set; +import java.util.function.BiConsumer; +import java.util.function.BiPredicate; + +/** + * A directed weighted graph, where the vertices have some arbitrary label + * + * @author ben + * + * @param <T> + * The label for vertices + */ +public class Graph<T> { + + private final Map<T, Map<T, Integer>> graph; + + /** + * Create a new graph + */ + public Graph() { + graph = new HashMap<T, Map<T, Integer>>(); + } + + /** + * Add a edge to the graph + * + * @param source + * The source vertex for this edge + * @param target + * The target vertex for this edge + * @param distance + * The distance from the source vertex to the target vertex + */ + public void addEdge(T source, T target, int distance) { + // Can't add edges with a null source or target + if (source == null) { + throw new NullPointerException("The vertex 1 cannot be null"); + } + if (target == null) { + throw new NullPointerException("The vertex 2 cannot be null"); + } + + // Initialize adjacency list for vertices if necessary + if (!graph.containsKey(source)) { + graph.put(source, new HashMap<T, Integer>()); + } + if (!graph.containsKey(target)) { + graph.put(target, new HashMap<T, Integer>()); + } + + // Add the edge to the graph + graph.get(source).put(target, distance); + + // Uncomment this to make the graph undirected + // graph.get(target).put(source, distance); + } + + /** + * Execute an action for all edges of a specific vertex matching + * conditions + * + * @param source + * The vertex to test edges for + * @param bp + * The conditions an edge must match + * @param bc + * The action to execute for matching edges + */ + public void forAllEdgesMatchingAt(T source, BiPredicate<T, Integer> bp, + BiConsumer<T, Integer> bc) { + getEdges(source).forEach((tgt, weight) -> { + if (bp.test(tgt, weight)) { + bc.accept(tgt, weight); + } + }); + } + + /** + * Get all the edges that begin at a particular source vertex + * + * @param source + * The vertex to use as a source + * @return All of the edges with the specified vertex as a source + */ + public Map<T, Integer> getEdges(T source) { + // Can't find edges for a null source + if (source == null) { + throw new NullPointerException("The source cannot be null."); + } + + return Collections.unmodifiableMap(graph.get(source)); + } + + /** + * Get the initial vertex of the graph + * + * @return The initial vertex of the graph + */ + public T getInitial() { + return graph.keySet().iterator().next(); + } + + /** + * Uses Prim's algorothm to calculate a MST for the graph. If the graph + * is non-connected, this will lead to unpredictable results. + * + * @param graph + * a connected graph. + * @return a list of edges that constitute the MST + */ + public List<Edge<T>> getMinSpanTree() { + // Set of all of the currently available edges + Queue<Edge<T>> availEdges = new PriorityQueue<Edge<T>>(10, + (e1, e2) -> e1.getDistance() - e2.getDistance()); + + // The MST of the graph + List<Edge<T>> minEdges = new ArrayList<Edge<T>>(); + + // The set of all of the visited vertices. + Set<T> visited = new HashSet<T>(); + + // Start at the initial vertex and visit it + GenHolder<T> src = new GenHolder<>(getInitial()); + visited.add(src.held); + + // Make sure we visit all the nodes + while (visited.size() != getVertexCount()) { + // Grab all edges adjacent to the provided edge + + forAllEdgesMatchingAt(src.held, + (tgt, weight) -> !visited.contains(tgt), + (tgt, weight) -> availEdges + .add(new Edge<T>(src.held, tgt, weight))); + + // Get the edge with the minimum distance + Edge<T> minEdge = availEdges.poll(); + + // Only consider edges where we haven't visited the target of + // the edge + while (visited.contains(minEdge.getTarget())) { + minEdge = availEdges.poll(); + } + + // Add it to our MST + minEdges.add(minEdge); + + // Advance to the next node + src.held = minEdge.getTarget(); + + // Visit this node + visited.add(src.held); + } + + return minEdges; + } + + public int getVertexCount() { + return graph.size(); + } + + /** + * Get all of the vertices in this graph. + * + * @return A unmodifiable set of all the vertices in the graph. + */ + public Set<T> getVertices() { + return Collections.unmodifiableSet(graph.keySet()); + } + + /** + * Remove the edge starting at the source and ending at the target + * + * @param source + * The source vertex for the edge + * @param target + * The target vertex for the edge + */ + public void removeEdge(T source, T target) { + // Can't remove things w/ null vertices + if (source == null) { + throw new NullPointerException("The vertex 1 cannot be null"); + } + if (target == null) { + throw new NullPointerException("The vertex 2 cannot be null"); + } + + // Can't remove if one vertice doesn't exists + if (!graph.containsKey(source)) { + throw new NoSuchElementException( + "vertex " + source + " does not exist."); + } + if (!graph.containsKey(target)) { + throw new NoSuchElementException( + "vertex " + target + " does not exist."); + } + + graph.get(source).remove(target); + + // Uncomment this to turn the graph undirected + // graph.get(target).remove(source); + } + + /** + * Convert a graph into a adjacency map/matrix + * + * @return A adjacency map representing this graph + */ + public AdjacencyMap<T> toMap() { + AdjacencyMap<T> aMap = new AdjacencyMap<>(graph.keySet()); + + graph.entrySet().forEach(src -> src.getValue().forEach((tgt, + weight) -> aMap.setWeight(src.getKey(), tgt, weight))); + + return aMap; + } + + public static <E> Graph<E> fromEdgeList(List<Edge<E>> edges) { + Graph<E> g = new Graph<>(); + + edges.forEach(edge -> g.addEdge(edge.getSource(), edge.getTarget(), + edge.getDistance())); + + return g; + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/gui/SimpleDialogs.java b/BJC-Utils2/src/main/java/bjc/utils/gui/SimpleDialogs.java index 7731529..85b9fa9 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/gui/SimpleDialogs.java +++ b/BJC-Utils2/src/main/java/bjc/utils/gui/SimpleDialogs.java @@ -1,24 +1,39 @@ package bjc.utils.gui; import java.awt.Component; +import java.awt.Frame; import java.util.function.Function; import java.util.function.Predicate; +import javax.swing.JButton; +import javax.swing.JComboBox; +import javax.swing.JDialog; +import javax.swing.JLabel; import javax.swing.JOptionPane; +import javax.swing.JPanel; + +import bjc.utils.gui.layout.VLayout; /** * Utility class for getting simple input from the user. + * * @author ben * */ public class SimpleDialogs { /** * Get a bounded integer from the user. - * @param parent The parent component for the dialogs. - * @param title The title for the dialogs. - * @param prompt The prompt to tell the user what to enter. - * @param lower The lower integer bound to accept. - * @param upper The upper integer bound to accept. + * + * @param parent + * The parent component for the dialogs. + * @param title + * The title for the dialogs. + * @param prompt + * The prompt to tell the user what to enter. + * @param lower + * The lower integer bound to accept. + * @param upper + * The upper integer bound to accept. * @return A int within the specified bounds. */ public static int getBoundedInt(Component parent, String title, @@ -35,9 +50,13 @@ public class SimpleDialogs { /** * Get a integer from the user - * @param parent The parent component for dialogs. - * @param title The title for dialogs. - * @param prompt The prompt to tell the user what to enter. + * + * @param parent + * The parent component for dialogs. + * @param title + * The title for dialogs. + * @param prompt + * The prompt to tell the user what to enter. * @return A int. */ public static int getInt(Component parent, String title, @@ -54,23 +73,34 @@ public class SimpleDialogs { /** * Get a string from the user - * @param parent The parent component for dialogs. - * @param title The title for the dialogs. - * @param prompt The prompt to tell the user what to enter. + * + * @param parent + * The parent component for dialogs. + * @param title + * The title for the dialogs. + * @param prompt + * The prompt to tell the user what to enter. * @return A string. */ - public static String getString(Component parent, String title, String prompt) { + public static String getString(Component parent, String title, + String prompt) { return JOptionPane.showInputDialog(parent, prompt, title, JOptionPane.QUESTION_MESSAGE); } /** * Get a value parsable from a string from the user. - * @param parent The parent component for dialogs. - * @param title The title for dialogs. - * @param prompt The prompt to tell the user what to enter. - * @param p A predicate to determine if a input is valid. - * @param f The function to transform the string into a value. + * + * @param parent + * The parent component for dialogs. + * @param title + * The title for dialogs. + * @param prompt + * The prompt to tell the user what to enter. + * @param p + * A predicate to determine if a input is valid. + * @param f + * The function to transform the string into a value. * @return The value parsed from a string. */ public static <E> E getValue(Component parent, String title, @@ -88,9 +118,13 @@ public class SimpleDialogs { /** * Get a whole number from the user. - * @param parent The parent component for dialogs. - * @param title The title for dialogs. - * @param prompt The prompt to tell the user what to enter. + * + * @param parent + * The parent component for dialogs. + * @param title + * The title for dialogs. + * @param prompt + * The prompt to tell the user what to enter. * @return A whole number. */ public static int getWhole(Component parent, String title, @@ -100,9 +134,13 @@ public class SimpleDialogs { /** * Ask the user a Yes/No question. - * @param parent The parent component for dialogs. - * @param title The title for dialogs. - * @param question The question to ask the user. + * + * @param parent + * The parent component for dialogs. + * @param title + * The title for dialogs. + * @param question + * The question to ask the user. * @return True if the user said yes, false otherwise. */ public static boolean getYesNo(Component parent, String title, @@ -112,12 +150,62 @@ public class SimpleDialogs { return (res == JOptionPane.YES_OPTION ? true : false); } - + + /** + * Asks the user to pick an option from a series of choices. + * + * @param parent + * The parent frame for this dialog + * @param title + * The title of this dialog + * @param question + * The question being asked + * @param choices + * The availible choices for the question + * @return The choice the user picked, or null if they didn't pick one + */ + @SuppressWarnings("unchecked") + public static <E> E getChoice(Frame parent, String title, + String question, E... choices) { + JDialog jd = new JDialog(parent, title, true); + jd.setLayout(new VLayout(2)); + + JPanel questionPane = new JPanel(); + + JLabel questionText = new JLabel(question); + JComboBox<E> questionChoices = new JComboBox<>(choices); + + questionPane.add(questionText); + questionPane.add(questionChoices); + + JPanel buttonPane = new JPanel(); + + JButton okButton = new JButton("Ok"); + okButton.addActionListener(e -> jd.dispose()); + JButton cancelButton = new JButton("Cancel"); + cancelButton.addActionListener(e -> jd.dispose()); + + buttonPane.add(cancelButton); + buttonPane.add(okButton); + + jd.add(questionPane); + jd.add(buttonPane); + + jd.pack(); + jd.setVisible(true); + + return (E) questionChoices.getSelectedItem(); + } + /** * Show a error message to the user - * @param parent The parent component for dialogs. - * @param title The title for dialogs. - * @param err The error to show the user. + * + * @param parent + * The parent component for dialogs. + * @param title + * The title for dialogs. + * @param err + * The error to show the user. */ public static void showError(Component parent, String title, String err) { diff --git a/BJC-Utils2/src/main/java/bjc/utils/gui/SimpleJList.java b/BJC-Utils2/src/main/java/bjc/utils/gui/SimpleJList.java index 220ac7d..518805b 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/gui/SimpleJList.java +++ b/BJC-Utils2/src/main/java/bjc/utils/gui/SimpleJList.java @@ -1,7 +1,5 @@ package bjc.utils.gui; -import java.util.List; - import javax.swing.DefaultListModel; import javax.swing.JList; import javax.swing.ListModel; @@ -17,7 +15,7 @@ public class SimpleJList { * @param ls The list to populate the JList with. * @return A JList populated with the elements from ls. */ - public static <E> JList<E> buildFromList(List<E> ls) { + public static <E> JList<E> buildFromList(Iterable<E> ls) { return new JList<E>(buildModel(ls)); } @@ -26,7 +24,7 @@ public class SimpleJList { * @param ls The list to fill the list model from. * @return A list model populated with the elements from ls. */ - public static <E> ListModel<E> buildModel(List<E> ls) { + public static <E> ListModel<E> buildModel(Iterable<E> ls) { DefaultListModel<E> dlm = new DefaultListModel<>(); ls.forEach(dlm::addElement); diff --git a/BJC-Utils2/src/main/java/bjc/utils/gui/awt/ExtensionFileFilter.java b/BJC-Utils2/src/main/java/bjc/utils/gui/awt/ExtensionFileFilter.java new file mode 100644 index 0000000..fb857eb --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/gui/awt/ExtensionFileFilter.java @@ -0,0 +1,37 @@ +package bjc.utils.gui.awt; + +import java.io.File; +import java.io.FilenameFilter; +import java.util.ArrayList; +import java.util.List; + +import bjc.utils.funcdata.FunctionalList; + +public class ExtensionFileFilter implements FilenameFilter { + private FunctionalList<String> extensions; + + /** + * Create a new filter only showing files with the specified extensions. + * @param exts The extensions to show in this filter. + */ + public ExtensionFileFilter(String... exts) { + extensions = new FunctionalList<>(new ArrayList<>(exts.length)); + + for (String ext : exts) { + extensions.add(ext); + } + } + + /** + * Create a new filter only showing files with the specified extensions. + * @param exts The extensions to show in this filter. + */ + public ExtensionFileFilter(List<String> exts) { + extensions = new FunctionalList<>(exts); + } + + @Override + public boolean accept(File dir, String name) { + return extensions.anyMatch(name::endsWith); + } +}
\ No newline at end of file diff --git a/BJC-Utils2/src/main/java/bjc/utils/gui/awt/SimpleFileDialog.java b/BJC-Utils2/src/main/java/bjc/utils/gui/awt/SimpleFileDialog.java new file mode 100644 index 0000000..1d14903 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/gui/awt/SimpleFileDialog.java @@ -0,0 +1,58 @@ +package bjc.utils.gui.awt; + +import java.awt.FileDialog; +import java.awt.Frame; +import java.io.File; +import java.io.FilenameFilter; + +import bjc.utils.gui.SimpleDialogs; + +public class SimpleFileDialog { + public static File getOpenFile(Frame par, String title, + String... extensions) { + FileDialog fd = new FileDialog(par, title, FileDialog.LOAD); + + if (extensions != null) { + FilenameFilter filter = new ExtensionFileFilter(extensions); + fd.setFilenameFilter(filter); + } + + fd.setVisible(true); + + while (fd.getFile() == null) { + SimpleDialogs.showError(par, "File I/O Error", + "Please choose a file to open."); + fd.setVisible(true); + } + + return fd.getFiles()[0]; + } + + public static File getOpenFile(Frame par, String title) { + return getOpenFile(par, title, (String[]) null); + } + + public static File getSaveFile(Frame par, String title, + String... extensions) { + FileDialog fd = new FileDialog(par, title, FileDialog.SAVE); + + if (extensions != null) { + FilenameFilter filter = new ExtensionFileFilter(extensions); + fd.setFilenameFilter(filter); + } + + fd.setVisible(true); + + while (fd.getFile() == null) { + SimpleDialogs.showError(par, "File I/O Error", + "Please choose a file to save to."); + fd.setVisible(true); + } + + return fd.getFiles()[0]; + } + + public static File getSaveFile(Frame par, String title) { + return getSaveFile(par, title, (String[]) null); + } +} |