Trie Implementation in C++11 I implemented a Trie in C++11, but I am not sure if my usage of struct and std::unique_ptr, and std::unordered_map are correct and idiomatic. Therefore, I hope someone could provide constructive criticism on my code.

My Trie implementation has three simple methods:

void Trie::Insert(const std::string&  word);
bool Trie::StartsWithPrefix(const std::string& prefix);
bool Trie::IsACompleteWord(const std::string& word);

Code

// tries.h
#ifndef TRIE_H_
#define TRIE_H_

#include <vector>
#include <string>
#include <unordered_map>

class Trie {
 public:
  // Trie Constructor
  Trie();
  explicit Trie(std::vector<std::string>);

  // Trie Operations
  void Insert(const std::string&  word);
  bool StartsWithPrefix(const std::string& prefix);
  bool IsACompleteWord(const std::string& word);

 private:
  struct Node {
    bool end_of_word;
    std::unordered_map<char, std::unique_ptr<Node>> children;
    Node(): end_of_word(false) {}
  };
  std::unique_ptr<Node> root;
};

/// ===========================
/// Tries Implementation
/// ===========================

Trie::Trie() {
  root = std::unique_ptr<Node>(new Node());
}

Trie::Trie(std::vector<std::string> words) {
  root = std::unique_ptr<Node>(new Node());
  for (auto w : words)
    Insert(w);
}

void Trie::Insert(const std::string&  word) {
  if (word.empty()) return;
  auto it = root.get();
  for (const char & key : word) {
    int found = it->children.count(key);
    if (!found)
      it->children.emplace(key, std::unique_ptr<Node>(new Node()));
    it = it->children[key].get();
  }
  it->end_of_word = true;
}

bool Trie::StartsWithPrefix(const std::string& prefix) {
  auto it = root.get();
  for (const char & key : prefix) {
    auto found = it->children.count(key);
    if (!found)
      return false;
    it = it->children[key].get();
  }
  return true;
}

bool Trie::IsACompleteWord(const std::string& word) {
  auto it = root.get();
  for (const char & key : word) {
    auto found = it->children.count(key);
    if (!found)
      return false;
    it = it->children[key].get();
  }
  return (it->end_of_word) ? true : false;
}

#endif // TRIE_H_

Test

#define CATCH_CONFIG_MAIN
#include "catch2/catch.hpp"
#include "trie.h"

SCENARIO("Trie operations", "[trie]") {
  GIVEN("A Trie Data Structure") {

    Trie trie({"hello", "test"});

    REQUIRE(trie.StartsWithPrefix("hell") == true);
    REQUIRE(trie.StartsWithPrefix("helli") == false);
    REQUIRE(trie.StartsWithPrefix("test") == true);
    REQUIRE(trie.StartsWithPrefix("ab") == false);

    trie.Insert("ab");
    REQUIRE(trie.StartsWithPrefix("ab") == true);

    REQUIRE(trie.IsACompleteWord("ab") == true);
    REQUIRE(trie.IsACompleteWord("hell") == false);
  }
}

bool end_of_word;
    Node(): end_of_word(false) {}

This would be probably more idiomatic simply written as

    bool end_of_word = false;

Next,

    explicit Trie(std::vector<std::string>);

is probably more idiomatic written as

    template<typename Itr> Trie(Itr begin, Itr end);

Next,

    std::unique_ptr<Node> root;

Why is it allocated on heap? It's a private member owned by this object, by putting it on heap you simply get some (noticeable) dereference overhead, and that's all.

Same goes for branches: there's no point in keeping child Nodes on heap, std::unordered_map<char, Node> is quite sufficient for a tree, with no additional  overhead.

Trie::Trie() {
  root = std::unique_ptr<Node>(new Node());
}

Trie::Trie(std::vector<std::string> words) {
  root = std::unique_ptr<Node>(new Node());

Irrespective of what's said above about root's type, such initializations are better put in initialization lists:

Trie::Trie(): root(new Node) {}

And if you upgrade to C++14, recall that make_unique is the new new

Trie::Trie(std::vector<std::string> words)
  : root(std::make_unique<Node>())
{

Next,

  for (const char & key : word) {

char type is small enough to be bound by value. Scalar and small POD types, when passed by reference, can create unnecessary overhead so it is better written as

  for (char key : word) {

(or even

  for (auto key : word) {

which makes perfect sense if you ever decide to make character type a parameter to your Trie.)

    auto found = it->children.count(key);
    if (!found)
      return false;
    it = it->children[key].get();

In C++, even with unordered containers, it is better done as

    auto where = it->children.find(key);
    if (where == it->children.end()) return false;
    it = where->second.get();

And similarly for Insert().

Which, by the way, I would declare as

  Trie &Insert(const std::string &);

But that is more like a personal preference.

How about adding a method that searches for all the elements whose keys start with a given prefix, and returns them either as a subnode, or a fresh container, like list or vector?

And the final boss: define an iterator type for your trie.


Dynamically create array with nested objects/array I need help to dynamically create an array with nested objects holding again an array of objects each. The structure is as follows:

tiles=[
     { "row": [{isChecked: true, src: ''}, {isChecked: true, src: ''}, {isChecked: true, src: ''}] },
     { "row": [{isChecked: true, src: ''}, {isChecked: true, src: ''}, {isChecked: true, src: ''}] },
     { "row": [{isChecked: true, src: ''}, {isChecked: true, src: ''}, {isChecked: true, src: ''}] },
     { "row": [{isChecked: true, src: ''}, {isChecked: true, src: ''}, {isChecked: true, src: ''}] }
  ];

However, the amount of row objects and amount of rows is dynamic. In the example above, it's 3 x 4.

My current approach is a simple nested loop:

updateTileEditor(x: number, y: number) {
  this.tiles = [];
  for (var i = 0; i < y; i++) {
    let helperArray = [];
    for (var j = 0; j < x; j++) {
      helperArray.push({ isChecked: true, src: '' });
    }
    this.tiles.push({ "row": helperArray });
  }
}

Could you perhaps propose a more feasable approach to this?

Be aware that every nested object of the nested array must be a different object. In other words, the objects can not point to the same reference.

Thanks in advance!

I can propose more functional approach. I don't have arguments to say that it's better, it's just how I prefer to write code for generating two-dimensional arrays filled with some initial values.

function createRow(rowLength: number) {
    return Array(rowLength).fill(null).map(() => ({
        isChecked: true,
        src: ''
    }))
}

function updateTileEditor(length: number, height: number) {
    this.tiles = Array(height).fill(null).map(() => ({
        row: createRow(length)
    }));
}

Explanation:

Array(height) creates an empty array of fixed size height - we want to create height rows.
.fill(null) is used to fill the array with any values, so you can map these values to new ones. Any other value can be used instead of null. Mapping empty array would return us new empty array.
.map(() => createRow(rowLength)) creates new array in which each value is a new row. () => createRow(rowLength) gets called for each value in the array, so you can be sure that you will have new row for each value.

I also renamed x to length and y to height - these names are more descriptive, which I think can help new readers with figuring out the purpose of these variables.

I will write it here, because I don't have enough reputation to comment:
you could also use arrays for rows instead of objects that have one property called "row".
If you have only one value then maybe you don't need to wrap it in an object? - I guess I would need more details about the problem to say that.


A Start button handler I was told my code contains a lot of force unwrapping. I thought it's okay to do that if I am sure that the value operated won't be nil:
private var x: Int?
private var y: Int?

@IBAction func startButtonPressed(_ sender: UIButton) {

    guard let numberOfRooms = selectedRooms.text, !numberOfRooms.isEmpty else {
        return selectedRooms.placeholder = "type it, dude"
    } //if user typed something
    let rooms = Int(numberOfRooms)

    x = Int(ceil(sqrt(Double(rooms!))))
    y = x //grab some values from user input
    maze = MazeGenerator(x!, y!) //generate a maze
    hp = 2 * (x! * y!) //get hp value depending on user input
    hpLabel.text = "hp: \(hp)"

    currentX = getRandomX(x!) //get random value in 0...x
    currentY = getRandomY(y!)
    currentCell = maze?.maze[currentX!][currentY!] //game starts in a random part of the maze

    for item in items.indices { //create and show some imageViews
        items[item].location = (getRandomX(x!), getRandomX(y!))
        createItems(imageName: items[item].imageName)
        if items[item].location == (currentX!, currentY!) {
            reveal(index: item)
        } else {
            hide(index: item)
        }
    }
    refreshButtons() //refresh UI
    maze!.display() //print maze scheme in debug console
    }

Does it look fine? If not, what should be done?

Yes, force unwrapping is ok if you're 100% sure the value won't be nil, but this should only be used when, for code structure reasons, you can't do otherwise. The thing is, most of the times, you can do otherwise, so using force-unwrapping should rarely happen. In your case, I think most of it can be refactored.
For example: why are your variables x and y declared as Optionals in the first place? Do they have to be?
If they are only used in this method, they should not be declared as Optional, and they should be declared inside the method, not outside.
If they are used elsewhere, they should be declared as Optional only if you know they will be nil at some point (which means that they should not be force unwrapped when used, but instead properly validated with error handling).
If they are used elsewhere and won't be nil when used, but you declared them as Optional for structural reasons, then you could use an implicitly unwrapped Optional instead.
private var x: Int!
private var y: Int!

This way you won't have to force unwrap them each time you use them.
Also, if this is acceptable in your context, you could make them non-optional and have an initial value.
private var x: Int = 0
private var y: Int = 0

But let's say that you have a good reason to declare them as Optionals. In this case, you still can improve your code by safely unwrapping the variables before using them.
guard let x = Int(ceil(sqrt(Double(rooms!)))) else {
    // show some message
    return
}

That way, if the user types a letter, space or non-numeric character, instead of a number, the app won't crash.
Maybe you're making sure elsewhere that the user can only input a number? In this case, force unwrap x before using it:
x = Int(ceil(sqrt(Double(rooms!))))!

Now, actually, the issue might only happen if numberOfRooms is not a number, so this unwrapping should happen earlier.
guard let numberOfRooms = selectedRooms.text, !numberOfRooms.isEmpty, let rooms = Int(numberOfRooms) else {
    // error message 'please input a number'
    return
}

Same idea about currentX and currentY: why are these declared as Optionals? Can the getRandom method return nil? Maybe that can be changed?
Same for maze: if MazeGenerator can return nil, the shouldn't you handle possible errors instead of force unwrapping? And if it won't ever return nil, then why does it return an Optional instead of a normal value? (or maybe it doesn't return an Optional and the issue is that maze was declared as an Optional but shouldn't have been).

These are the issues you should address.
While force unwrapping is indeed not bad if you can guarantee the value won't be nil when you use it, most of the times it's better to make sure earlier in the code flow that the value won't be nil, which will allow you to not having to use Optionals.
In short: validate the values before use, abort and show an error message if the content is incorrect at the validation step, and then proceed to use the values without having to use Optionals and unwrapping.


Simulate the way that PHP receives the form Let's say I have this form:

<form action="/user/store" method="POST" enctype="multipart/form-data">
    Name: <input type="text" name="name">

    Male: <input type="radio" name="gender" value="male">

    Female: <input type="radio" name="gender" value="female">

    Photo: <input type="file" name="photo">

    Hobbies: <select name="hobbies[]" multiple>
        <option value="sport">Sport</option>
        <option value="movies">Movies</option>
        <option value="music">Music</option>
        <option value="games">Games</option>
    </select>

    Accept the terms?<input type="checkbox" name="terms">

    <input type="submit">
</form>

If I submit it to a PHP server with my data, this is the result:

array (size=5)
  'name' => string 'John' (length=4)
  'gender' => string 'male' (length=4)
  'hobbies' =>
    array (size=2)
      0 => string 'sport' (length=5)
      1 => string 'music' (length=5)
  'terms' => string 'on' (length=2)
  'photo' =>
    object(Symfony\Component\HttpFoundation\File\UploadedFile)[9]
      private 'test' => boolean false
      private 'originalName' => string 'test.jpg' (length=8)
      private 'mimeType' => string 'image/jpeg' (length=10)
      private 'size' => int 130677
      private 'error' => int 0

I want to have similar results with JavaScript, so I wrote this function:

//Add event listener for the form submit to the document
$(document).on('submit', 'form', function(e){
    //Prevent form submitting
    e.preventDefault();
    var form = $(':input').not(':submit,:button,:image,:radio,:checkbox');
    $.merge(form, $(':checked').not('option'));
    var data = [], input, name;

    form.each(function(i, obj){
        input = {};
        name = obj.name;
        if(name.indexOf('[]') < 0) {
            input['name'] = name;
            if(obj.type==='file'){
                var files = obj.files;
                input['value'] = files[files.length - 1];
            } else {
                input['value'] = obj.value;
            }
        } else {
            name = name.replace('[]', '');
            if(name in data){
                var tmp = input['value'];
                if(obj.type==='file'){
                    input['value'] = $.merge(tmp, obj.files);
                } else if(obj.type === 'select-multiple') {
                    input['value'] = $.merge(tmp, $.map(obj.selectedOptions, function(option, i){
                        return option.value;
                    }));
                } else {
                    input['value'] = $.merge(tmp, obj.value);
                }
            } else {
                data[name] = {};
                if(obj.type === 'file'){
                    input['value'] = obj.files;
                } else if(obj.type === 'select-multiple') {
                    input['value'] = $.map(obj.selectedOptions, function(option, i){
                        return option.value;
                    });
                } else {
                    input['value'] = [];
                    input['value'].push(obj.value);
                }
            }
        }
        data.push(input);
     });
});

And this return (JSON format):

[
    {"name":"firstname","value":"John"},
    {"name":"photo","value":
        {
            "webkitRelativePath":"",
            "lastModifiedDate":"2014-09-08T18:29:36.000Z",
            "name":"test.jpg",
            "type":"image/jpeg","size":130677
        }
    },
    {"name":"hobbies","value":["sport","music"]},
    {"name":"gender","value":"male"},
    {"name":"terms","value":"on"}
]

Is there any better way to do that? By better code, I mean less code. I don't mind if it will become slower.

I’m not sure if you still maintain this code but if so, you could consider using a FormData object. I see it has been documented on MDN since 2015 and the link to the specification points to whatwg.org, which has been archived since 2012. I found a post on SO from 2011 that uses it. That way you wouldn’t have to manually query the DOM for inputs (I.e. var form = $(':input').not(':submit,:button,:image,:radio,:checkbox'); $.merge(form, $(':checked').not('option'));)- you could just iterate over a newly created FormData object. You would still need to alter input names to remove the brackets when multiple values are allowed.

You might be able to remove jQuery as a dependency, unless there are specific plugins used on the page. For more information, check out youmightnotneedjquery.com/.

I see places where bracket notation is used to alter properties of objects, like below:

input['name'] = name;

and

input['value'] = files[files.length - 1];

However dot notation could be used instead, just as it is used to check the type of the object being iterated over (i.e. if(obj.type==='file'){). It is "faster to write and clearer to read"1

1https://stackoverflow.com/a/4968448/1575353


Search form sample pattern I've just started to practice coding in OOP and just wanted to ask if my code's pattern is correct.  I need your comments or suggestions so I can improve it.

sample_class.php:

<?php
$host = 'localhost';
$db = 'sample_db';
$user = 'sample_user';
$pass = 'sample_password';
$conn = new PDO("mysql:host=$host;dbname=$db", $user, $pass);
$conn->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
$conn->setAttribute(PDO::ATTR_EMULATE_PREPARES, false);

Class MySearchClass {

    public function __construct(PDO $conn) {
        $this->pdo=$conn;
    }

    public function search_name($keyword){

        $query = "SELECT * FROM table WHERE name = '$keyword'";
        $result = $this->pdo->prepare($query);
        $result ->execute();

        return $result;
    }

    public function view_all(){
        $query = "SELECT * FROM table";
        $result = $this->pdo->prepare($query);
        $result ->execute();

        return $result;
    }
}

search_form.php:

<?php
include('sample_class.php');
$search= new MySeachClass($database_connection);

if (isset($_POST['submit'])){
    $keyword = $_POST['keyword'];
    $go_search = $search->search_name($keyword);

    $data = $go_search->fetchAll(PDO::FETCH_ASSOC);

    foreach($data as $row){
        echo $row['name'];
        echo other rows....
    }

}else{
    $view = $search->view_all();
    $data = $view->fetchAll(PDO::FETCH_ASSOC);

    foreach($data as $row){
        echo $row['name'];
        echo other rows....
    }
}

<form action="" method="POST">
<input type="text" name="keyword">
<input type="submit" name="search">
</form>

Here's a recommendation to bind parameters correctly. This sort of thing is used to prevent against SQL injection attacks.

$query = "SELECT * FROM table WHERE name = :keyword";
$statement = $this->pdo->prepare($query);
$statement->bindParam(':keyword', $keyword, PDO::PARAM_STR);
$result $statement->execute();

Read more about PDOStatement#bindParam here


Parallel brute-force solution for Project Euler 4 (Largest palindrome product) The pe4Concurrent.go file given below is my first attempt at writing a concurrent programme, pe4.go is a non-concurrent implementation of the same algorithm for comparison purposes.

The algorithm itself is a simple, brute force solution to one of the Project Euler problems.

Basically, I'm very new to both Go and concurrency and would appreciated any suggestions as to how the efficiency or elegance of my use of channels and goroutines in pe4Concurrent.go might be improved.

Non-concurrent brute force solution (included for comparison purposes):

pe4.go

//Project Euler: Problem 4

//Largest palindrome product

//A palindromic number reads the same both ways. The largest
//palindrome made from the product of two 2-digit numbers is
//9009 = 91 × 99.

//Find the largest palindrome made from the product of two
//3-digit numbers.

package main

import "fmt"
import "time"

func isPalindrome(s string) bool {
    if len(s) <= 1 {
        return true
    }
    if s[0] != s[len(s)-1] {
        return false
    }
    s = s[:len(s)-1]
    s = s[1:]
    return isPalindrome(s)
}

func main() {

    start := time.Now()

    highestPal := 0

    lowerLimit := 100

    upperLimit := 1000

    for i := upperLimit - 1; i >= lowerLimit; i-- {

        for j := i - 1; j > 0; j-- {

            candidate := i * j

            s := fmt.Sprintf("%d", candidate)

            if isPalindrome(s) {

                if candidate > highestPal {

                    highestPal = candidate
                }
            }
        }
    }

    elapsed := time.Since(start)

    //num := 1000 * 999
    //s := fmt.Sprintf("%d", num)
    //output := isPalindrome(s)
    //fmt.Println(output)
    //output = isPalindrome("101")
    //fmt.Println(output)
    //output = isPalindrome("9")
    fmt.Println(highestPal)
    fmt.Println("Programme execution time %s", elapsed)
}

Concurrent brute force solution:

pe4Concurrent.go

//Project Euler: Problem 4

//Largest palindrome product

//A palindromic number reads the same both ways. The largest
//palindrome made from the product of two 2-digit numbers is
//9009 = 91 × 99.

//Find the largest palindrome made from the product of two
//3-digit numbers.

// Note:
// Brute force solution launching 900 goroutines outperforms
// the same algorithms without goroutines by a factor of
// five: 14 ms vs. 72 ms.

package main

import "fmt"
import "time"

func isPalindrome(s string) bool {
    if len(s) <= 1 {
        return true
    }
    if s[0] != s[len(s)-1] {
        return false
    }
    s = s[:len(s)-1]
    s = s[1:]
    return isPalindrome(s)
}

func getHighestPal(i int, c chan int) {

    for j := i - 1; j > 0; j-- {

        candidate := i * j

        s := fmt.Sprintf("%d", candidate)

        if isPalindrome(s) {

            c <- candidate
        }
    }
}

func main() {

    start := time.Now()

    highestPal := 0

    lowerLimit := 100

    upperLimit := 1000

    c := make(chan int)

    for i := upperLimit - 1; i >= lowerLimit; i-- {

        go getHighestPal(i, c)
    }

    for i := 0; i < upperLimit-lowerLimit; i++ {

        candidate := <-c

        if candidate > highestPal {

            highestPal = candidate
        }
    }

    elapsed := time.Since(start)
    fmt.Println(highestPal)
    fmt.Println("Programme execution time %s", elapsed)
}

Brute Force.
Your use of go-routines is pretty simple, but effective. The part I don't think is best, is the use of the channel. The channel itself is good, but the control structures you have to read content from the channel, could be better. In fact, you have a bug in them (although you are lucky that the data means you don't encounter the bug).
Let me describe the bug, first. You assume that every go-routine is going to add a value to the channel (there will be at least one palindrome). You also assume there is at most one palindrome. If there end up being fewer palindromes than routines, you may end up "hanging" on the channel when all routines are done, but no values are coming. If there are more palindromes than routines, you may have the "max" palindrome happen later in the channel than you read.
I would recommend using a wait-group for the go-routine, and then closing the channel in the completion. In essence, I would restructure the code:

lowerLimit := 100

upperLimit := 1000

c := make(chan int)

for i := upperLimit - 1; i >= lowerLimit; i-- {

    go getHighestPal(i, c)
}

for i := 0; i < upperLimit-lowerLimit; i++ {

    candidate := <-c

    if candidate > highestPal {

        highestPal = candidate
    }
}

to be:
lowerLimit := 100
upperLimit := 1000

count := upperLimit - 1 - lowerLimit

palindromes := make(chan int, 1024)

var wg sync.WaitGroup
wg.Add(count)
for i := 0; i < count; i++ {
    go func(val int) {
        getHighestPal(val, palindromes)
        wg.Done()
    }(i + lowerLimit)
}

go func() {
    // wait for all routines to complete
    wg.Wait()
    // close the channel to allow the terminal range
    close(palindromes)
}()

highestPal := 0
for candidate := range palindromes {
    if candidate > highestPal {
        highestPal = candidate
    }
}

Note how the internals of the getHighestPal no longer affect the reading of the channel? Also note how Ihave to create the closure parameter i + lowerLimit inside the go-routine call in order to have the right context for each routine.
A second bug you have is the elimination of square numbers. Again, it does not affect the results in this instance, but the code in getHighestPal should be for j := i and not j := i - 1. All squares of values containing only 1 digits are famously palindromes: 1111 * 1111 is 1234321 for example.
Finally, your method getHighestPal implies it gets the highest palindrome, but it gets all palindromes..... not just the highest.
Non-Brute-Force
So, a couple of other things to consider.
The fmt.Sprintf is slower than strconv.Itoa. Consider that change (it's 2 to 3 times slower in my tests).
Also, you can be creative about what you do in your algorithm to improve performance. I took your code and ran it my way.....
func isPalindrome(v int) bool {
    str := strconv.Itoa(v)
    right := len(str) - 1
    left := 0
    for left < right {
        if str[left] != str[right] {
            return false
        }
        left++
        right--
    }
    return true
}

func maxPalindrome(maxfact int) int {

    max := -1
    minlow := 0

    // establish a low and high value pair as the values that create the product.
    for low := maxfact; low >= minlow; low-- {
        for high := maxfact; high >= low; high-- {
            prod := low * high
            if prod <= max {
                // no need to keep looking for things that can't possibly be larger than previous max.
                break
            }
            if isPalindrome(prod) {
                max = prod
                // limit how far we search back to things that would exceed the smallest factor
                minlow = max / maxfact
            }
        }
    }

    return max
}

When run in the same way as your code:
func main() {
    start := time.Now()

    maxp := maxPalindrome(999)

    elapsed := time.Since(start)
    fmt.Println(maxp)
    fmt.Println("Programme execution time %s", elapsed)

}

I was substantially faster.
On my machine, your sequential code returned:

906609
Programme execution time %s 99.33103ms

your concurrent code returned:

906609
Programme execution time %s 26.010698ms

And the above code returned:

906609
Programme execution time %s 206.964µs

about 100 times faster than your concurrent code.


Big Sorting - Performant Sorting Consider an array of numeric strings where each string is a positive whole number. Sort the array's string elements in ascending order of their numeric values, and return the sorted array.
Return: string[n]: the array sorted in numeric order.
Constraints: Each string is guaranteed to represent a positive whole integer. There will be no leading zeros.
Sample Input:
6
31415926535897932384626433832795
1
3
10
3
5

Sample Output:
1
3
3
5
10
31415926535897932384626433832795

Code:
using System;
using System.IO;
using System.Linq;

namespace Big_Sorting
{
    class Solution
    {
        static string[] BigSorting(string[] unsorted) => unsorted.OrderBy(s => s.Length).ThenBy(s => s).ToArray();

        static void Main()
        {
            TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

            int n = Convert.ToInt32(Console.ReadLine());

            string[] unsorted = new string[n];

            for (int i = 0; i < n; i++)
            {
                unsorted[i] = Console.ReadLine();
            }

            textWriter.WriteLine(string.Join("\n", BigSorting(unsorted)));

            textWriter.Flush();
            textWriter.Close();
        }
    }
}

I need to improve upon this code.  Priority for me is performance here.  If the array is becomes long in length this begins to slow down. This is functional and working. I just want to get it as fast as possible.
The code works fine for test cases like this.
But has trouble with test case like this

You have been posting in CodeReview for about 1 year, so while you are still learning C# and a hobbyist, you are not a total newbie.  Therefore, you should expect the reviews to be a little more critical.  Do understand that "critical" does not mean "mean spirited" but rather more blunt while also being constructive.
What disappoints me most in your code is its structure.  You put almost everything in Main.  I would challenge you to step back and look at the big picture of what goes on:

UI Input - Ask for input values
Business Logic - manipulate or
process those input values
UI Output

So you could make your Main to look similar to those items.  This is a major principle to keep in mind: Separation of Concerns, namely your business logic and UI should be separate.  But Separation of Concerns also applies to breaking up a monster method that is doing too much into smaller methods where each call does a specific thing.
There is also the .NET guideline that you should limit the scope of a variable.  I am an old-timer who worked with VB and way back then it was common to define ALL the variables at the top of a method and then use them later.  With .NET, this is not needed.  In particular, I am referring to the variable textWriter.  You define at the very top but start to use it at the bottom.
I also do not like the name textWriter.  I personally would use a generic name of writer just in case you every change to a different implementation.  But that really doesn't matter because you don't need that variable at all.  You use 4 lines of code when only 1 is needed:
File.WriteAllLines(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"),
                   BigSorting(unsorted));

I have also observed in a history of your posts, and the same is true here, that you code to a specific implementation of array.  Your methods can have a broader reach and re-usability if you coded to a more basic implementation, such as IList or even IEnumerable.  Consider:
static IOrderedEnumerable<string> BigSorting(IEnumerable<string> items) => items.OrderBy(s => s.Length).ThenBy(s => s);

The input is no longer restricted to being an array, and I do not create an entirely new array for output.  I also changed the parameter name to items because I don't care if someone inputs a unsorted collection or one sorted in some other order.  Doesn't matter to the method.
What if you wanted to output to an array?  Then use .ToArray() when you make the call BigSorting rather than doing it inside BigSorting.
So that addresses quick and simple sorting use LINQ, which produces a 2nd array.  There is an alternative that doesn't require a 2nd array.  I haven't tested with huge number of elements or crazy long values.  I leave that to you and hopefully you will find it more performant.
I am referring to making a custom IComparer.  See this link.  Example:
public class NumericStringComparer : IComparer<string>
{
    // https://docs.microsoft.com/en-us/dotnet/api/system.array.sort?view=net-5.0#System_Array_Sort__1___0___System_Collections_Generic_IComparer___0__
    public int Compare(string x, string y)
    {
        // Compare x and y as numbers without leading zeroes.
        if (x == null)
        {
            return (y == null) ? 0 : -1;
        }
        if (y == null)
        {
            return 1;
        }
        if (x.Length < y.Length)
        {
            return -1;
        }
        if (y.Length < x.Length)
        {
            return 1;
        }
        return x.CompareTo(y);
    }
}

Now you would use it like:
Array.Sort(unsorted, new NumericStringComparer());
File.WriteAllLines(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"),
                       unsorted);

Except I now have a problem with the name "unsorted".  While the array containing inputs was initially unsorted, I later sorted in-place to that very same array, so in WriteAllLines the name choice of unsorted is misleading.  Thus, I would choose a generic name of items for the array.


Slow foreach loop to check for intersect I'm trying to make a loop where it returns whether or not a rectangle collides and then to which coords the rectangle should move to.

I'm calling my function like this:

rectangles2[i].rect = rectangleupdated(i, rectangles2);

And this is inside my function:

private Rectangle rectangleupdated(int i, List<rectList> rectangles2)
{
    //fills rectangles with rectangles to check intersect with
    BOTTOM = rectangles2[i].rect;
    BOTTOM_LEFT = rectangles2[i].rect;
    BOTTOM_RIGHT = rectangles2[i].rect;
    //bool to be set to false if intersects returns true
    bBOTTOM = true;
    bBOTTOM_LEFT = true;
    bBOTTOM_RIGHT = true;
    //move the intersect rectangles
    BOTTOM.Y++;
    BOTTOM_LEFT.Y++;
    BOTTOM_LEFT.X--;
    BOTTOM_RIGHT.Y++;
    BOTTOM_RIGHT.X++;

    foreach (rectList rects in rectangles2)
    {
        if (!rects.type.Contains("bg"))
        {
            if (rectangles2[i].rect.Y < 500)
            {
                if (BOTTOM.IntersectsWith(rects.rect))
                {
                    bBOTTOM = false;
                }
                else if (BOTTOM_LEFT.IntersectsWith(rects.rect))
                {
                    bBOTTOM_LEFT = false;
                }
                else if (BOTTOM_RIGHT.IntersectsWith(rects.rect))
                {
                    bBOTTOM_RIGHT = false;
                }
            }
            else
            {
                return rectangles2[i].rect;
            }
        }
    }
    if (bBOTTOM == true) return BOTTOM;
    else if (bBOTTOM_RIGHT == true) return BOTTOM_RIGHT;
    else if (bBOTTOM_LEFT == true) return BOTTOM_LEFT;
    return rectangles2[i].rect;
}

I think I know a little bit why it's lagging so hard but I don't know how to fix it / make this code more usable.

You're not using the C# naming convention:

class ClassNamesShouldBePascalCase
{
    const CONTANTS_ARE_IN_ALL_CAPS;
    private _membersShouldStartWithAUnderScoreAndBeCamelCase; //_camelCase
    public PropertiesShouldBePascalCase {get; set;} //PascalCase

    public void PublicMethodsShouldBePascalCase
    {
        object methodLevelVariablesShouldBeCamelCase; //camelCase
    }
}
//The underscore for private variables is optional, but good practice.

Is there a reason you are using a custom class called rectList instead of using a List<Rectangle>, besides the type ? If there are more reasons, I recommend calling the class Rectangles, otherwise, just manage the Type separately.

Don't call your parameter rectangles2 ... rectangles, or values is a good name.

if (rectangles2[i].rect.Y < 500)

500 is a magic number, and should be declared somewhere else as a constant with a useful name, so that those reading it know what it is for.

Give your booleans more descriptive names like:

bool bottomHasCollision

bool hasCollisionBottom

Use the ternary operator to clean up your final return statement:

return bBOTTOM       ? BOTTOM :
       bBOTTOM_RIGHT ? BOTTOM_RIGHT :
       bBOTTOM_LEFT  ? BOTTOM_LEFT :
       rectangles2[i].rect;

If you could fix these things, and upload another question I'd be more inclided to review the performance of the program, however I will need to know more about the program and see some of the other classes. You should try saving the DateTime.Now at the beginning and end of the method, and various other places inside to track the performance to pinpoint what is taking so long. There is also software out there that can help you do that.

Edit:

I've taken the liberty to implement the code changes I was talking about above. Plus some others to make the code more concise.

private Rectangle Rectangleupdated(List<Rectangles> rectangles, int i)
{
    Rectangle rect = rectangles[i].Rectangle;

    //fills rectangles with rectangles to check intersect with
    bottom = bottomLeft = bottomRight = rect;

    //bool to be set to false if intersects returns true
    bottomFlagged = bottomLeftFlagged = bottomRightFlagged = true;

    //move the intersect rectangles
    bottom.Y++;

    bottomLeft.Y++;
    bottomLeft.X--;

    bottomRight.Y++;
    bottomRight.X++;

    foreach (Rectangles rects in rectangles)
    {
        if (rects.Type.Contains("bg") || rect.Y >= 500) continue;

        bottomFlagged     = bottomFlagged && !bottom.IntersectsWith(rects.Rectangle);
        bottomLeftFlagged = bottomLeft    && !bottomLeft.IntersectsWith(rects.Rectangle);
        bottomRight       = bottomRight   && !bottomRight.IntersectsWith(rects.Rectangle);
    }
    return bottomFlagged      ? bottom :
           bottomRightFlagged ? bottomRight :
           bottomLeftFlagged  ? bottomLeft :
           rect;
}

I would however like to see your Rectangle and rectList classes, to understand where the pain points might be.


Retrieving input from either GET/POST Today, I created an input class with a method to check whether or not input via GET/POST exists, and another method to retrieve input from either GET/POST, without having to check both individually.

class input {
        public static function exists($type = 'post') {
            switch ($type) {
                case "post":
                    return (!empty($_POST)) ? true : false;
                break;
                case "get":
                    return (!empty($_GET)) ? true : false;
                break;
                default:
                    return false;
                break;
            }

        }

        public static function get($data) {
            if (isset($_GET[$data])){
                return $_GET[$data];
            } else if (isset($_POST[$data])){
                return $_POST[$data];
            } else {
                return '';
            }
        }
    }

Here is my form and example usage:

<?php
    require_once('core/init.php');

    if(input::exists()){
        echo input::get('username');
        echo input::get('password');
        echo input::get('confirm_password');
    }

?>

    <form method="POST" autocomplete="off">

                Username

            <input type="text" name="username" id="username" />

                Password

            <input type="password" name="password" id="password" />

                Confirm Password

            <input type="password" name="confirm_password" id="confirm_password" />

            <input type="submit" />

    </form>

First of all, is it okay for me to access the methods in the way that I have? Is using statics in this way bad practice?

Secondly, aside from what I asked above, are there any recommendations or improvements that you can suggest?

I see a few small issues with the code:

Method names: particularly get is quite ambiguous, I'd use something more descriptive like 'get_element_data($element_name)' or something like that. As it is now it is obvious when used but it's not clear when looking just at the class itself.
Instead of  return (!empty($_GET)) ? true : false; you can actually use just return (!empty($_GET))
You don't need to break after return. Some might, however, argue that using it anyway is a good practice that prevents errors. So choose for yourself.

Other than that, I don't see any big problems with it.


Bitwise Logic optimization I should be able to figure this out on my own, but I can't seem to wrap my head around how to optimize this set of logic for interpreting the existence of URL parameters.

<cfif ParameterExists(start) and not ParameterExists(end) and not ParameterExists(after)>
<cfquery name="STUDENT" datasource="#STUD_DB#">
    SELECT *
    FROM student_profile
    WHERE (Date_Modified BETWEEN '#token# #start#' AND '#token# 23:59:59')
</cfquery>
<cfelseif ParameterExists(end) and not ParameterExists(start) and not ParameterExists(after)>
<cfquery name="STUDENT" datasource="#STUD_DB#">
    SELECT *
    FROM student_profile
    WHERE (Date_Modified BETWEEN '#token# 00:00:00' AND '#token# #end#')
</cfquery>
<cfelseif ParameterExists(start) and ParameterExists(end) and not ParameterExists(after)>
<cfquery name="STUDENT" datasource="#STUD_DB#">
    SELECT *
    FROM student_profile
    WHERE (Date_Modified BETWEEN '#token# #start#' AND '#token# #end#')
</cfquery>
<cfelseif ParameterExists(after) and not ParameterExists(start) and not ParameterExists(end)>
<cfquery name="STUDENT" datasource="#STUD_DB#">
    SELECT *
    FROM student_profile
    WHERE (Date_Modified BETWEEN '#token# #after#' AND '#today# 23:59:59')
</cfquery>
<cfelse>
<cfquery name="STUDENT" datasource="#STUD_DB#">
    SELECT *
    FROM student_profile
    WHERE (Date_Modified BETWEEN '#token# 00:00:00' AND '#token# 23:59:59')
</cfquery>
</cfif>

It's a disgusting chunk of code, I know. Its operation is pretty simple, though: run a query with a set of parameters if they exist.

I would like to have some sort of short circuit logic so I can just say:

<cfif (logic to check parameters) >
    <cfquery name="STUDENT" datasource="#STUD_DB#">
        SELECT *
        FROM student_profile
        WHERE (Date_Modified BETWEEN '#startdate# #starttime#' AND '#enddate# #endtime#')
    </cfquery>

This would most likely require me to set default values as well, but I am okay with that.

Yeah, you're not doing yourself any favours by having the elements of the IF conditions in differing orders. It took a bit for me to re-sort everything so I could understand what the heck was going on. I think it distills down to this:

<cfscript>
    if (structKeyExists(URL, "after")){
        param name="URL.start" default=URL.after type="time";
        variables.endDate = today;  // I am not sure what scope TODAY is in, but SCOPE IT. TODAY *must* be a valid, unambiguous date string, EG YYYY-MM-DD
    }else{
        param name="URL.start" default="00:00:00" type="time";
        variables.endDate = token;  // same as with TODAY: scope it and make sure it's a valid date
    }
    param name="URL.end" default="23:59:59" type="time";

    variables.startDate = token;

    variables.start = parseDateTime("#startDate# #URL.start#"); // this could error if the contributing values don't comprise a date/time
    variables.end = parseDateTime("#endDate# #URL.end#");       // ditto
</cfscript>

<cfquery name="STUDENT" datasource="#STUD_DB#">
    SELECT *    <!--- [LIST YOUR COLUMNS HERE, DO NOT USE SELECT *] --->
    FROM student_profile
    WHERE Date_Modified BETWEEN <cfqueryparam value="#variables.start#" cfsqltype="CF_SQL_TIMESTAMP">
                        AND     <cfqueryparam value="#variables.end#"   cfsqltype="CF_SQL_TIMESTAMP">
</cfquery>

Some notes on this solution:

You probably want to do better validation than how I've just used a typed param, and parseDateTime() without first checking the thing actually parses as a date time!
You want to check and recheck the if statement logic I've used. I did not 100% compare it to your initial if logic

Some general notes:

always scope your variables.
parameterExists() has been deprecated for over ten years. Do not use it.
you seldom want to SELECT *. In general, specify the columns you want; do not return columns you don't actually need
NEVER hard-code values into the SQL string. ALWAYS pass them as parameters.
Don't use strings in place of date/times, when you are doing date operations.


Pagination algorithm in JS I needed a relatively simple pagination, as currently implemented on GoogleSearch (sans prev & next buttons). Most code I've seen was overly complicated so I came up with something that's simpler.

Any suggestions on how to further optimise this?

function doPaging(currentPageInput) {

    let currentPage = currentPageInput, // input
        range       = 5,  // amount of links displayed
        totalPages  = 20, // determined by amount of items, hardcoded for readability
        start       = 1;  // default

    let paging = [];      // output variable

    // Don't use negative values, force start at 1
    if (currentPage < (range / 2) + 1 ) {
        start = 1;

    // Don't go beyond the last page
    } else if (currentPage >= (totalPages - (range / 2) )) {
        start = Math.floor(totalPages - range + 1);

    } else {
        start = (currentPage - Math.floor(range / 2));
    }

    for (let i = start; i <= ((start + range) - 1); i++) {
        if (i === currentPage) {
            paging.push(`[${i}]`); // add brackets to indicate current page
        } else {
            paging.push(i.toString());
        }
    }
    return paging;
}

OUTPUT:

[ '[1]', '2', '3', '4', '5' ]
[ '1', '[2]', '3', '4', '5' ]
[ '1', '2', '[3]', '4', '5' ]
[ '2', '3', '[4]', '5', '6' ]
[ '3', '4', '[5]', '6', '7' ]
[ '4', '5', '[6]', '7', '8' ]
[ '5', '6', '[7]', '8', '9' ]
[ '6', '7', '[8]', '9', '10' ]
[ '7', '8', '[9]', '10', '11' ]
[ '8', '9', '[10]', '11', '12' ]
[ '9', '10', '[11]', '12', '13' ]
[ '10', '11', '[12]', '13', '14' ]
[ '11', '12', '[13]', '14', '15' ]
[ '12', '13', '[14]', '15', '16' ]
[ '13', '14', '[15]', '16', '17' ]
[ '14', '15', '[16]', '17', '18' ]
[ '15', '16', '[17]', '18', '19' ]
[ '16', '17', '[18]', '19', '20' ]
[ '16', '17', '18', '[19]', '20' ]
[ '16', '17', '18', '19', '[20]' ]

In addition to the remarks given by Blindman67, I'd like to suggest the following:

Passing options:

The first few lines of your function are some kind of configuration block:

let currentPage = currentPageInput, // input
    range       = 5,  // amount of links displayed
    totalPages  = 20, // determined by amount of items, hardcoded for readability
    start       = 1;  // default

Now, when the number of pages changes, you need to touch your code and modify the totalPages initialization.

So you will probably want to introduce function arguments with default values:

function doPaging(currentPageInput, start = 1, totalPages = 20, range = 5) {
  ...
}

// Example:
doPaging(3, 1, 4); // ["0", "1", "2", "[3]", "4"]

Unfortunately, if you e.g. desire to change just the number of total pages, this argument order still requires you to specify all arguments preceding the totalPages argument.

Therefore, you might want to consider using default parameters in combination with destructuring assignment:

function doPaging(currentPageInput, {start = 1, totalPages = 20, range = 5} = {}) {
  ...
}

// Example:
doPaging(3, {totalPages: 4}); // ["0", "1", "2", "[3]", "4"]

Separating logic and view:

Your current implementation returns an array of strings destined for immediate output. This comes with a few drawbacks:

If you want to change the markup of an active page index, you need to modify your code and replace the brackets [${i}] with something else.
If you want to output a usable pagination, e.g. a list of anchor tags, you need additional code to map each page index string to its URL. This would probably require you to map each index string back to a number first.

So how about just returning the paging range as an array of numbers? Later on, within your HTML template, you can then print page == currentPage ? `[${page}]` : `${page}` or - in case you print HTML - simply select a different CSS class for the current page.

Handling corner cases:

In case you choose a range of 5, but the total number of pages is set to just 4, a call to doPaging(4) will return ["0", "1", "2", "3", "[4]"] including an undesired "0" at the beginning. A robust implementation should probably reduce the range according to the available total number of pages.

Fixing issues:

Since we now allow user defined start values, we need to fix issues arising from start values that are not 1 caused by the hard coded "force start at 1" within your code.

Putting it all together:

Choosing simpler and more consistent variable names as well as renaming the nondescript doPaging to getPagingRange, we get an easier to read and understand implementation.

Replacing the loop with Array.from yields more descriptive code.

Adding a single comment describing the function's behavior instead of many individual inline comments helps the reader to better understand the purpose and usage of the function.

/**
 * Return an integer range within [min, min + total) of given length centered
 * around the current page number.
 */
function getPagingRange(current, {min = 1, total = 20, length = 5} = {}) {
  if (length > total) length = total;

  let start = current - Math.floor(length / 2);
  start = Math.max(start, min);
  start = Math.min(start, min + total - length);

  return Array.from({length: length}, (el, i) => start + i);
}

// Examples:
console.log(getPagingRange(20)); // [16, 17, 18, 19, 20]
console.log(getPagingRange(3, {total: 4, length: 3})); // [2, 3, 4]
console.log(getPagingRange(3, {min: 0, total: 4, length: 3})); // [1, 2, 3]


Build an Array of StringBuffer with x elements from a List of n elements I have an initial list that contains: 1,2,3,4,5,6,7 I want to create an array of StringBuffer that contains only 3 items per element as StringBuffer(String):

1,2,3
4,5,6
7

Initially I resolved this problem as in the following example, but I don't want to use another list to do that:

List accounts = new ArrayList();
List<Person> listOfObjects = results.getResults();
for(Person p: listOfObjects) {
   String persAccount = p.getAccount();
   accounts.add(persAccount);
}
String s = listToString(accounts);

public String listToString(List list) {
 StringBuffer b = new StringBuffer();
    for (int i = 0; i < list.size(); i++) {
        b.append(String.valueOf(list.get(i)));
        if (i < list.size()-1)
            b.append(',').toString();
    }
    return b.toString();
}

I think that an efficent way will be to create a StringBuffer and append all values in the for block.(3 by 3).

How can I do it in an efficient way?

StringBuffer

The first thing that comes to mind is the fact that you're using a StringBuffer instead of a StringBuilder. A StringBuffer is synchronized which means it has the additional overhead that comes with it. Unless you are doing this in a multithreaded environment that affects this piece of code, switching to a StringBuilder will be a good improvement.

ToString

Inside your loop you do b.append(',').toString(). Since you never do anything with the String that it returns, you are essentially needlessly creating a String each time it is hit.

Strongly typed collections

You have the collection accounts defined as List accounts = new ArrayList();: there is no type specified.

Proper handling would be List<Account> accounts = new ArrayList<>(); so you're working with Person objects instead of general Objects.

This is aside from any remarks on whether or not your code fits your problem description, as @rolfl states. I don't see where you split it in sublists of 3 elements.


Infinite and countdown counters I'm refactoring my scheduler and for one of its triggers I need an endless counter that would automatically restart. Since this is a simple and very common task I don't want to ever have to implement it again so I encapsulated it in such a way that it hopefully can be reused everywhere else.

The counter is represented by an enumerable interface with a couple or properties that provide information about the counter and methods allowing to interact with it.

public interface IInfiniteCounter : IEnumerable<(int Value, InfiniteCounterState State)>
{
    int Min { get; }

    int Max { get; }

    int Length { get; }

    int Current { get; }

    (int Value, InfiniteCounterState State) Next();

    void Reset();
}

It uses an enum to inform the caller about the type of the value. It returns First each time the counter restarted, Intermediate for values inbetween and Last for the last value.

public enum InfiniteCounterState
{
    First,
    Intermediate,
    Last,
}

I have one implementation of the interface. The InfiniteCounter that is a forward running counter:

public class InfiniteCounter : IInfiniteCounter
{
    private int _current;

    public InfiniteCounter(int min, int max)
    {
        Min = min;
        Max = max;
    }

    public InfiniteCounter(int max) : this(0, max) { }

    public int Min { get; }

    public int Max { get; }

    public int Length => Max - Min;

    public int Current => _current + Min;

    private bool IsLast => _current == Length;

    public (int Value, InfiniteCounterState State) Next()
    {
        if (IsLast)
        {
            Reset();
        }

        return
        (
            Current,
            _current++ == 0
                ? InfiniteCounterState.First
                : IsLast
                    ? InfiniteCounterState.Last
                    : InfiniteCounterState.Intermediate
        );
    }

    public void Reset()
    {
        _current = 0;
    }

    public IEnumerator<(int Value, InfiniteCounterState State)> GetEnumerator()
    {
        while (true)
        {
            yield return Next();
        }
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

In order to have it running backwards I created two extensions. One that is an extension for the IInfiniteCounter

public static class InfiniteCounterExtensions
{
    public static IEnumerable<(int Value, InfiniteCounterState State)> Countdown(this IInfiniteCounter counter)
    {
        return counter.Select(x => (x.Value.Flip(counter.Min, counter.Max), x.State));
    }
}

and one that is flipping the value:

public static class IndexMath
{
    public static int Flip(this int value, int min, int max)
    {
        return (-(value - max + 1) % (max - min)) + min;
    }
}

Examples:

void Main()
{
    var take = 4;
    new InfiniteCounter(3).Take(take).Dump("0-2");
    new InfiniteCounter(3).Countdown().Take(take).Dump("2-0");
    new InfiniteCounter(2, 5).Take(take).Dump("2-4");
    new InfiniteCounter(2, 5).Countdown().Take(take).Dump("4-2");

    0.Flip(0, 3).Dump();
    1.Flip(0, 3).Dump();
}

What do you think about it? It should be convenient to use and every piece of it should be testable. (Argument checking will be added later)

public interface IInfiniteCounter : IEnumerable<(int Value, InfiniteCounterState State)>

vs

    int Current { get; }

    (int Value, InfiniteCounterState State) Next();

    void Reset();

The interface itself looks a lot more like IEnumerator<> than IEnumerable<>, so IMO implementing IEnumerable<> is misleading and dangerous. The docs for IEnumerable<> don't say either way whether or not it's possible to have two active enumerators at the same time, but I can't think of any implementations in the standard library for which it isn't possible, and I've probably written a lot of code which assumes that it is possible.

    int Min { get; }

    int Max { get; }

    int Length { get; }

I can safely assume that Min is inclusive, but I absolutely need a comment to tell me whether Max is or not, and it would be helpful to have a comment indicating the standard implementation of Length. Also, should Length be uint both because it's guaranteed to be non-negative and to avoid overflow in edge cases?

public static class IndexMath
{
    public static int Flip(this int value, int min, int max)
    {
        return (-(value - max + 1) % (max - min)) + min;
    }
}

I don't understand why this method uses %. For me the obvious interpretation of the name (and the use case) is max - (value - min). If there's some trickery going on to avoid or handle overflow, it needs explanatory comments.


PyCrypto AES-CFB with SCrypt and HMAC I am brushing up on my Python, and since I would like to learn a bit about encryption, I figured I would give PyCrypto a try. I obviously wouldn't implement encryption in any production environment, but I am curious to see if I made any obvious mistakes from a security perspective, and also if my code could be optimized or made more pythonic.

PyCryptodome 3.4.6
quantumrandom 1.9.0
pyscrypt 1.6.2

from Crypto.Cipher import AES
import quantumrandom
import hmac
import hashlib
import pyscrypt

HMAC_KEY = "738525cf1f8acd06beb4cf6cd816d1dc"

class AuthenticationError(Exception):
    pass

def gen_key(password):
    """Derives a key from input string using SCrypt and returns it hex encoded."""
    hashed = pyscrypt.hash(
        password=password,
        salt="2df2e24c76d4d7b37e7ffcdf787e426b",
        N=16384,
        r=8,
        p=1,
        dkLen=16)

    return hashed.encode('hex')

def encrypt(plaintext, password):
    """Takes plaintext input and returns hex encoded ciphertext
    with hex encoded HMAC-SHA-512 hash appended."""

    key = gen_key(password)
    iv = quantumrandom.binary()[:16]
    cipher = AES.new(key, AES.MODE_CFB, iv)
    data = iv.encode("hex") + cipher.encrypt(plaintext).encode("hex")
    sig = hmac.new(HMAC_KEY, data, hashlib.sha512).digest().encode("hex")

    ciphertext = data + sig

    return ciphertext

def decrypt(ciphertext, password):
    """Takes ciphertext and password input, splits it into MAC hash and message
    data, verifies the hash and returns message plaintext if successful."""

    sig = ciphertext[-128:]
    data = ciphertext[:-128]

    if hmac.new(HMAC_KEY, data, hashlib.sha512).digest().encode("hex") != sig:
        raise AuthenticationError("Message Authentication failed!")

    iv = data[:32].decode("hex")
    message = data[32:].decode("hex")
    key = gen_key(password)
    cipher = AES.new(key, AES.MODE_CFB, iv)

    return cipher.decrypt(message)

SHARED_SECRET = "correct horse battery staple"
plaintext = "If You're Typing the Letters A-E-S Into Your Code You're Doing It Wrong"
ciphertext = encrypt(plaintext, SHARED_SECRET)

print "Ciphertext:", ciphertext

print "Decrypted:", decrypt(ciphertext, SHARED_SECRET)

import quantumrandom

The problem is that you should not trust third parties when importing random numbers. Furthermore, getting the randomness requires a secure connection in the first place. The secure connection relies on random numbers to remain secure. A secure random number generator that has been seeded by the OS is generally the best way to go.
HMAC_KEY = "738525cf1f8acd06beb4cf6cd816d1dc"

Generally keys should not be strings, not even hexadecimal strings. Strings are easy to find. I'd rather even use a Python \b string than hexadecimals, but preferably you'd use a keystore, or keys derived from a password supplied by the user. Which brings us to the next point:
hashed = pyscrypt.hash(
    password=password,
    salt="2df2e24c76d4d7b37e7ffcdf787e426b",
    N=16384,
    r=8,
    p=1,
    dkLen=16)

Don't use single-person unmaintained libraries. Never ever use a static salt. A salt, again, is a binary string, not a normal string. 16Ki iterations is on the short scale of things.
iv = quantumrandom.binary()[:16]

If you'd have used a random salt for each encryption then you can simply derive the keys (the encryption and MAC key) and IV from it. As the salt is unique, the key and IV combination will be unique as well.
data = iv.encode("hex") + cipher.encrypt(plaintext).encode("hex")
sig = hmac.new(HMAC_KEY, data, hashlib.sha512).digest().encode("hex")

I applaud you for having the IV authenticated as well. I also applaud you for using encrypt-then-MAC which is generally considered more secure than encrypt-and-MAC or MAC-then-encrypt.
I cannot applaud you to perform the HMAC over the hexadecimal representation of the bytes though; you've just doubled the required effort for calculating it. Never confuse binary with the representation of the binary in some textual format (hex, base64).
And while we're at it, hex requires an overhead of 100% when viewed as bytes (assuming an 8 bit encoding). Base 64 is a lot more efficient. Generally: first concatenate the binary, then encode; this will generate fewer characters as well. Or keep it as binary of course; a lot of ciphertext is encoded unnecessarily (leading to so called "stringified" code).

One improvement would be the use of an authenticated cipher such as AES-GCM instead of performing the encryption and HMAC separately.
For larger plaintext / ciphertext you could think about piecemeal updates / streaming so that the entire plaintext / ciphertext doesn't need to be in memory all at once.


Program to automate skipping users on a chat website until the username meets certain conditions (v.2.0) This is a python program that automates skipping through users on a chat website called talkwithstrangers using the Selenium Webdriver and BeautifulSoup modules of Python.

The first part uses Selenium to open the browser:

from selenium import webdriver
driver = webdriver.Chrome('C:\SeleniumDrivers\chromedriver.exe')
userName = 'null'
driver.get('https://talkwithstranger.com/talk-to-strangers')

The second part is a while loop that runs while the username has not met the required conditions:

while 'female' not in userName or 'Female' not in userName:
    driver.get('https://talkwithstranger.com/talk-to-strangers')
    html = driver.execute_script("return document.documentElement.innerHTML;")

    from bs4 import BeautifulSoup
    soup = BeautifulSoup(html, 'html5lib')
    userVal = soup.find(class_='alert text-center alert-success')
    userNames =  userVal.find_all('b')

    def getName(userNames):
        for name in userNames:
            return name.prettify()

    userName = getName(userNames)

The code is running fine but the problem is the efficiency and runtime.

There are instructions you should not repeat inside the loop, and they should be written before it:

from bs4 import BeautifulSoup should be written much above in your code, within the import section.
getName() should be defined outside the loop, and named get_names() according to the naming conventions (actually it should be named get_names() because you are dealing with more than one name)

You do not get all female users:

When you run userName = getName(userNames), you are getting the last female user whereas you are obviously looking for all of them. So you should create a list of usernames and append useName (should be written user_name) to it whenever found.

Main performance issue:

You quickly refresh the page using driver.get('https://talkwithstranger.com/talk-to-strangers') whereas when I visited the link, it does not refresh as frequently as you do it. In opposite, most often I am kicked out of the room and had to wait a dozen of seconds. I think it also depends on whether there are users or not. In all cases, you are refreshing the page too quickly and you have to study the behavior of the website to decide on the strategy and criteria upon which you can refresh the page


Thread safe Pooled Dictionary I have an object that is fairly expensive to create and has a tendency to get created multiple times because each distinct user may have one or many instances of this object. This object can expire as its internal authentication becomes stale and no longer valid.

Because of this, I want need to keep a dictionary so I can keep a list of objects for each user.... but....I need this dictionary to not retain objects indefinitely since they can expire. ( Managing the expiration is outside the scope of this )

I used this article as a starting point, but took the concept a little further to manage the number of objects stored internally to keep the pool from getting too large.

public sealed class PooledDictionary<TKey, TValue>
{
    private readonly byte m_poolSize;
    private readonly ConcurrentDictionary<TKey, ConcurrentQueue<TValue>> m_pool;
    private readonly ConcurrentQueue<TKey> m_keyQueue;
    public PooledDictionary(byte maxPoolSize)
    {
        if (maxPoolSize <= 0)
            maxPoolSize = (byte)Math.Min(Environment.ProcessorCount, byte.MaxValue);

        m_poolSize = maxPoolSize;
        m_keyQueue = new ConcurrentQueue<TKey>();
        m_pool = new ConcurrentDictionary<TKey, ConcurrentQueue<TValue>>(Environment.ProcessorCount * 2, m_poolSize);
    }

    public bool TryAdd(TKey key, TValue value)
    {
        if (key == null)
            return false;

        if (!m_pool.ContainsKey(key) && m_pool.TryAdd(key, new ConcurrentQueue<TValue>()))
        {
            m_keyQueue.Enqueue(key);

            while (m_pool.Count > m_poolSize)
            {
                TKey localKey;
                if (m_keyQueue.TryDequeue(out localKey))
                {
                    TryRemove(localKey);
                }
            }
        }

        ConcurrentQueue<TValue> q;
        if (m_pool.TryGetValue(key, out q))
        {
            q.Enqueue(value);
            while (q.Count > m_poolSize)
            {
                TValue localValue;
                q.TryDequeue(out localValue);
            }
        }
        else
        {
            return false;
        }
        return true;
    }

    public bool TryRemove(TKey key)
    {
        if (key == null)
            return false;

        ConcurrentQueue<TValue> value;
        return m_pool.TryRemove(key, out value);
    }

    public int Count(TKey key)
    {
        if (key == null)
            return 0;

        if (!m_pool.ContainsKey(key)) m_pool.TryAdd(key, new ConcurrentQueue<TValue>());
        ConcurrentQueue<TValue> q;
        if (m_pool.TryGetValue(key, out q))
        {
            return q.Count;
        }
        return 0;
    }

    public TValue Request(TKey key, Func<TValue> creator = null)
    {
        if (key == null)
            return default(TValue);

        if (!m_pool.ContainsKey(key)) m_pool.TryAdd(key, new ConcurrentQueue<TValue>());
        ConcurrentQueue<TValue> q;
        if (m_pool.TryGetValue(key, out q))
        {
            TValue v;
            if (q.TryDequeue(out v)) return v;
            if (null != creator) return creator();
        }
        return default(TValue);
    }

    public bool Release(TKey key, TValue value)
    {
        return TryAdd(key, value); //just adds it back to key's queue
    }
}

Anytime that you check a count then do something on that you have to assume another thread did something in between.

for example this code

while (q.Count > m_poolSize)
{
    TValue localValue;
    q.TryDequeue(out localValue);
}

Because no locking is happening two threads could read the count and see it's over and both could remove an item.  Since you are using ConcurrentQueue both will remove different items.  This would cause your pool to drop below max size.  Maybe that's ok in your situation.

Same issue is applied when having the Keys being a ConcurrentQueue.  In theory if you had your max pool size lower than the processor count times 2 and each thread hit that line at the same time you could get an exception, since you would try to dequeue when the queue has no items in it.  Granted this is an extreme example and one not likely to hit but at a min you would want to catch that exception.

If you want to have the max stored in the pool you will need to do locking on an object and if we are going to do then both the ConcurrentQueue can go away.  The Keys I would replace as a list since that will do the array manipulation for us and change the ConcurrentDictionary values to just be a normal Queue.

private readonly ConcurrentDictionary<TKey, Queue<TValue>> m_pool;
private IList<TKey> m_keys;
private readonly object m_lock = new object();

We can simplify the Count method to use the concurrentDictionary GetOrAdd method

public int Count(TKey key)
{
    if (key == null)
        return 0;

    var q = m_pool.GetOrAdd(key, _ => new Queue<TValue>());
    return q.Count;
}

The Queue class implements ICollection and ICollection has a SyncRoot object.  To make it easy I would create a helper method so I don't have to cast to the Icollection each time I wanted the SyncRoot

private object SyncLock(ICollection collection)
{
    return collection.SyncRoot;
}

For the Request Method I would use the GetOrAdd again and lock on the return queue to know the count hasn't changed when Dequeued

public TValue Request(TKey key, Func<TValue> creator = null)
{
    if (key == null)
       return default(TValue);

    var q = m_pool.GetOrAdd(key, _ => new Queue<TValue>());
    lock (SyncLock(q))
    {
        if (q.Count > 0)
        {
            return q.Dequeue();
        }
    }
    if (creator != null)
    {
        return creator();
    }
    return default(TValue);

}

TryAdd method now needs locking as well.  Plus we will use the ConcurrentDictionary GetOrAdd method and pass in the value to add so we can tell if it added to the dictionary or if it returned back an existing value.

public bool TryAdd(TKey key, TValue value)
{
    if (key == null)
       return false;

    var addedQueue = new Queue<TValue>();
    var q = m_pool.GetOrAdd(key, addedQueue);

    lock (SyncLock(q))
    {
        q.Enqueue(value);
        if (q.Count > m_poolSize)
        {
            q.Dequeue();
        }
    }

    // If these are the same then we added to the concurrent dictionary
    if (q == addedQueue)
    {
        lock (m_lock)
        {
            m_keys.Add(key);
            if (m_keys.Count > m_poolSize)
            {
                var ejected = m_keys[0];
                m_keys.RemoveAt(0);
                TryRemove(ejected);
            }
        }
    }

    return true;
}

Since we add to both the keys and concurrentdictionary then check to see if over we should init them with plus one of the max count

public PooledDictionary(byte maxPoolSize)
{
    if (maxPoolSize <= 0)
        maxPoolSize = (byte)Math.Min(Environment.ProcessorCount, byte.MaxValue);

    m_poolSize = maxPoolSize;
    m_keys = new List<TKey>(maxPoolSize + 1);

    m_pool = new ConcurrentDictionary<TKey, Queue<TValue>>(Environment.ProcessorCount * 2, m_poolSize + 1);
}

In this implementation there is no need for while(q.Count > m_poolsize) as we controlling the adding an could only ever be one over the size.  Which is our trigger to remove one.


Printing Pascal’s triangle for n number of rows in Python I have written a program that takes a number n and prints Pascal's triangle having n number of rows.

Here is my code -

n = int(input("Enter number of rows: "))
a = []

for i in range(n):
    a.append([])
    a[i].append(1)

    for j in range(1, i):
        a[i].append(a[i - 1][j - 1] + a[i - 1][j])
    if (n != 0):
        a[i].append(1)

for i in range(n):
    print("   " * (n - i), end = " ", sep = " ")

    for j in range(0, i + 1):
        print('{0:5}'.format(a[i][j]), end = " ", sep = " ")
    print()

Here are some example outputs -

Enter number of rows: 3
              1
           1     1
        1     2     1

Enter number of rows: 6
                       1
                    1     1
                 1     2     1
              1     3     3     1
           1     4     6     4     1
        1     5    10    10     5     1

Enter number of rows: 10
                                   1
                                1     1
                             1     2     1
                          1     3     3     1
                       1     4     6     4     1
                    1     5    10    10     5     1
                 1     6    15    20    15     6     1
              1     7    21    35    35    21     7     1
           1     8    28    56    70    56    28     8     1
        1     9    36    84   126   126    84    36     9     1

Therefore, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

One issue with your approach is your memory usage is \$O(n^2)\$.  You are building up the entire Pascal's Triangle, and subsequently printing it.  If you simply want to print Pascal's Triangle, you don't need to keep the entire triangle in memory.  You can simply generate and print it row by row.  Since you generate the next row from only the previous row, the memory requirement is simply two rows, which is \$O(n)\$.

>>> row = [1]
>>> for _ in range(5):
...    row = [1] + [x + y for x, y in zip(row[:-1], row[1:])] + [1]
...    print(row)
...
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
>>>

Demystifying [1] + [x + y for x, y in zip(row[:-1], row[1:])] + [1]:

row[:-1] is all the values in row, except the last one.  For example, if row is [1, 3, 3, 1], then row[:-1] is [1, 3, 3].  Similarly, row[1:] is all the values of row except the first, so [3, 3, 1].  zip() takes the first value of each of the lists, and returns those as the tuple (1, 3), which get assigned to x and y respectively, which get added together to get 4.  Then, zip() emits the next pair of values, (3, 3) which results in 6, and then the final pair (3, 1) results in 4, producing the list [4, 6, 4].  The [1] + ... + [1] adds the bookends, which results in the next row of the triangle: [1, 4, 6, 4, 1].

Instead of needing to keep track of the last row, and feed that back to generate the next row, we can package that up into a generator function, which can prime the loop and do the feedback itself:

>>> def pascals_triangle(n):
...     row = [1]
...     yield row
...     for _ in range(n):
...         row = [1] + [x + y for x, y in zip(row[:-1], row[1:])] + [1]
...         yield row
...
>>> for row in pascals_triangle(5):
...     print(row)
...
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
>>>

Format the resulting rows as desired.

>>> for i, row in enumerate(pascals_triangle(5)):
...     print(("   "*(5-i) + "{:6}"*(i+1)).format(*row))
...
                    1
                 1     1
              1     2     1
           1     3     3     1
        1     4     6     4     1
     1     5    10    10     5     1
>>>


Classes for background layer and parallax effect I have two classes DigBackground and DigParallaxBackgroundLayer (a parallax background is a image consisting of several images that move at different scroll speeds, for games etc.).  My idea was to have the DigBackground class which is basically just a image with some added properties that can be set were it will draw itself on the screen. It just has one method currently and that is the initWithImageNamed that sets all of it properties.  Some of its properties are public, but read-only. So they can be accessed by the DigParallaxBackground class.

The DigParallaxBackground class currently also have one method at present - the initializer which takes an array of DigBackground´s as argument. And will display them on screen.

I want to know if this is decent design and how I can improve it if need be.

This is how it's used:

    DigBackground *bg1 = [[DigBackground alloc]initWithImageNamed:@"Default.png"
                                                  withScrollSpeed:1.0f
                                                  InitialOffsetOf:ccp(0, 0)
                                                         position:ccp(100, 100)
                                                         setFlipX:NO];

    DigParallaxBackgroundLayer *parallaxBg = [[DigParallaxBackgroundLayer alloc]
                                              initParallaxBackgroundWithImages:@[bg1] inOrder:kAscending];

    [self addChild: parallaxBg];

Header for DigBackground:

@property (nonatomic, readonly) float bgScrollSpeed;
@property (nonatomic, readonly) CGPoint initialOffset;

// Designated initializer
- (id) initWithImageNamed: (NSString *)image
          withScrollSpeed: (float)scrollspeed
          InitialOffsetOf: (CGPoint)offset
                 position: (CGPoint)position
                 setFlipX: (BOOL)flipX;

Header for DigParallaxBackground:

typedef enum {
    kAscending,
    kDescending
} ImagesOrder;

@interface DigParallaxBackgroundLayer : CCLayer
{
    NSArray *backgrounds;
}

// Designated initializer
- (id) initParallaxBackgroundWithImages: (NSArray *) images inOrder: (ImagesOrder) order;

Just a couple nit-picky things...

InitialOffsetOf: should instead be initialOffset:

withScrollSpeed: should just be scrollSpeed:

I'd probably also add factory methods.  When I'm writing code, no class is complete until it has its factory methods.


Wavelet decomposition of images I am working on wavelet decomposition and found a formula for it and wrote it by myself for computation.

The formula is:

$$I_{LH}(i,j) = \sum_{p=1}^{N_L} \sum_{q=1}^{N_H}\ L(p)\ H(q)\ I(i+p, j+q)$$

This is LH filtered and I do it for LL, LH, HL and HH so i get 4 images.

Can someone check the for loop in it and help me improve the computation time of it?

Elapsed time is 10.040462 seconds. I want to reduce time as much as possible as I need to work on hundreds of images.

%   Wavelet Decomposition
%Decomposition wavelet 'coif1' filters
[Lo_D,Hi_D] = wfilters('coif1','d');
img = imread('tumor-1.jpg');
img=  im2double(img);
figure, imshow(img), title('original image');
[nrows ncols] = size(img);
imgg = zeros(nrows+6,ncols+6);
imgg(1:nrows,1:ncols) = img(:,:);
figure, imshow(imgg);

% wavelet decomposition.
imgD_LL = zeros(size(img));
imgD_LH = zeros(size(img));
imgD_HL = zeros(size(img));
imgD_HH = zeros(size(img));

% Deconstruction
tic
for i = 1: nrows
    for j = 1:ncols
        for p = 1:numel(Lo_D)
            for q = 1:numel(Hi_D)
                tempqD_LL(q) = Lo_D(p)*Lo_D(q)*imgg(i+p,j+q);
                tempqD_LH(q) = Lo_D(p)*Hi_D(q)*imgg(i+p,j+q);
                tempqD_HL(q) = Hi_D(p)*Lo_D(q)*imgg(i+p,j+q);
                tempqD_HH(q) = Hi_D(p)*Hi_D(q)*imgg(i+p,j+q);
            end
            if (length(tempqD_LL) == q)
                tempQD_LL(p) = sum(tempqD_LL);
                tempQD_LH(p) = sum(tempqD_LH);
                tempQD_HL(p) = sum(tempqD_HL);
                tempQD_HH(p) = sum(tempqD_HH);
            end

        end
        if (length(tempQD_LL) == p )
            imgD_LL(i,j) = sum(tempQD_LL);
            imgD_LH(i,j) = sum(tempQD_LH);
            imgD_HL(i,j) = sum(tempQD_HL);
            imgD_HH(i,j) = sum(tempQD_HH);
        end
    end
end
toc
% Plots Deconstruction..
figure,
subplot(2,2,1), imshow(imgD_LL, [min(min(imgD_LL)) max(max(imgD_LL))]), title('Img Deconstruction - LL filter');
subplot(2,2,2), imshow(imgD_LH, [min(min(imgD_LH)) max(max(imgD_LH))]); title('Img Deconstruction - LH filter');
subplot(2,2,3), imshow(imgD_HL, [min(min(imgD_HL)) max(max(imgD_HL))]); title('Img Deconstruction - HL filter');
subplot(2,2,4), imshow(imgD_HH, [min(min(imgD_HH)) max(max(imgD_HH))]); title('Img Deconstruction - HH filter');

The image i used for above is :

Okay, I looked into the problem a bit deeper.

Currently, with your use case, you are doing a lot of multiplications which end up in zero anyway. Most of the image is namely black. You can easily skip all these multiplications by checking if the image block you are looping over is bigger than zero.
The two loops basically do a matrix multiplication. You are multiplying an image block with two vector values over which you loop. You can create a matrix which has all the possible combinations of Lo_D(p)*Lo_D(q) by taking the Kronecker product of Lo_D. Then you can simply do a matrix multiplication. and sum all elements over the matrix. However, it seems that this optimization is actually slower then the first one in this case. It might be the case that it is faster in other cases.
You are calculating each index of an array each time and afterwards you are summing it, this can be done in one line as well. The performance is however does not seem to increase or decrease.
Finally, you can do one minor optimization the for loop where you loop over Lo_D, you can also there check if an entire row is equal to zero. This is a small optimization but might give you something. Doing this another time in the next loop is useless.

Full code:

clear all;
close all;
clc

[Lo_D,Hi_D] = wfilters('coif1','d');

img = imread('tumor-1.jpg');
img = im2double(img);
figure;
imshow(img);
title('original image');

[nrows ncols] = size(img);
imgg = zeros(nrows+6,ncols+6);
imgg(1:nrows,1:ncols) = img(:,:);
figure;
imshow(imgg);

% Wavelet decomposition.
imgD_LL = zeros(size(img));
imgD_LH = zeros(size(img));
imgD_HL = zeros(size(img));
imgD_HH = zeros(size(img));

timgD_LL = zeros(size(img));
timgD_LH = zeros(size(img));
timgD_HL = zeros(size(img));
timgD_HH = zeros(size(img));

%% Optimization #1
tic
for i = 1:nrows
    for j = 1:ncols

        imgBlock = imgg((i+1):(i+numel(Lo_D)),(j+1):(j+numel(Hi_D)));

        if any(imgBlock(:) > 0)

            for p = 1:numel(Lo_D)
                for q = 1:numel(Hi_D)
                    tempqD_LL(q) = Lo_D(p)*Lo_D(q)*imgg(i+p,j+q);
                    tempqD_LH(q) = Lo_D(p)*Hi_D(q)*imgg(i+p,j+q);
                    tempqD_HL(q) = Hi_D(p)*Lo_D(q)*imgg(i+p,j+q);
                    tempqD_HH(q) = Hi_D(p)*Hi_D(q)*imgg(i+p,j+q);
                end
                if (length(tempqD_LL) == q)
                    tempQD_LL(p) = sum(tempqD_LL);
                    tempQD_LH(p) = sum(tempqD_LH);
                    tempQD_HL(p) = sum(tempqD_HL);
                    tempQD_HH(p) = sum(tempqD_HH);
                end

            end
            if (length(tempQD_LL) == p)
                timgD_LL(i,j) = sum(tempQD_LL);
                timgD_LH(i,j) = sum(tempQD_LH);
                timgD_HL(i,j) = sum(tempQD_HL);
                timgD_HH(i,j) = sum(tempQD_HH);
            end
        end
    end
end
toc

%% Optimization #2
% % Kronecker product
% LL = kron(Lo_D,Lo_D);
% LH = kron(Hi_D,Lo_D);
% HL = kron(Lo_D,Hi_D);
% HH = kron(Hi_D,Hi_D);
%
% % Reshape to matrix
% LL = reshape(LL,numel(Lo_D)*[1 1]);
% LH = reshape(LH,numel(Lo_D)*[1 1]);
% HL = reshape(HL,numel(Lo_D)*[1 1]);
% HH = reshape(HH,numel(Lo_D)*[1 1]);
%
% tic
% for i = 1:nrows
%     for j = 1:ncols
%
%         imgBlock = imgg((i+1):(i+numel(Lo_D)),(j+1):(j+numel(Hi_D)));
%
%         if any(imgBlock(:) > 0)
%             timgD_LL(i,j) = sum(sum(LL.*imgBlock));
%             timgD_LH(i,j) = sum(sum(LH.*imgBlock));
%             timgD_HL(i,j) = sum(sum(HL.*imgBlock));
%             timgD_HH(i,j) = sum(sum(HH.*imgBlock));
%         else
%             timgD_LL(i,j) = 0;
%             timgD_LH(i,j) = 0;
%             timgD_HL(i,j) = 0;
%             timgD_HH(i,j) = 0;
%         end
%     end
% end
% toc
%
%% Optimization #3
% tic
% for i = 1:nrows
%     for j = 1:ncols
%         tLL = 0;
%         tLH = 0;
%         tHL = 0;
%         tHH = 0;
%
%         imgBlock = imgg((i+1):(i+numel(Lo_D)),(j+1):(j+numel(Hi_D)));
%
%         if any(imgBlock(:) > 0)
%             for p = 1:numel(Lo_D)
%                 for q = 1:numel(Hi_D)
%                     tLL = Lo_D(p)*Lo_D(q)*imgg(i+p,j+q) + tLL;
%                     tLH = Lo_D(p)*Hi_D(q)*imgg(i+p,j+q) + tLH;
%                     tHL = Hi_D(p)*Lo_D(q)*imgg(i+p,j+q) + tHL;
%                     tHH = Hi_D(p)*Hi_D(q)*imgg(i+p,j+q) + tHH;
%                 end
%             end
%         end
%
%         timgD_LL(i,j) = tLL;
%         timgD_LH(i,j) = tLH;
%         timgD_HL(i,j) = tHL;
%         timgD_HH(i,j) = tHH;
%     end
% end
% toc
%
%% Original implementation
tic
for i = 1:nrows
    for j = 1:ncols
        for p = 1:numel(Lo_D)
            for q = 1:numel(Hi_D)
                tempqD_LL(q) = Lo_D(p)*Lo_D(q)*imgg(i+p,j+q);
                tempqD_LH(q) = Lo_D(p)*Hi_D(q)*imgg(i+p,j+q);
                tempqD_HL(q) = Hi_D(p)*Lo_D(q)*imgg(i+p,j+q);
                tempqD_HH(q) = Hi_D(p)*Hi_D(q)*imgg(i+p,j+q);
            end
            if (length(tempqD_LL) == q)
                tempQD_LL(p) = sum(tempqD_LL);
                tempQD_LH(p) = sum(tempqD_LH);
                tempQD_HL(p) = sum(tempqD_HL);
                tempQD_HH(p) = sum(tempqD_HH);
            end

        end
        if (length(tempQD_LL) == p)
            imgD_LL(i,j) = sum(tempQD_LL);
            imgD_LH(i,j) = sum(tempQD_LH);
            imgD_HL(i,j) = sum(tempQD_HL);
            imgD_HH(i,j) = sum(tempQD_HH);
        end
    end
end
toc

%%
% Check if they are the same, calculate difference and check if it is
% smaller then 5 machine epsilon because of numerical differences
all(all(timgD_LL - imgD_LL < 5*eps))
all(all(timgD_LH - imgD_LH < 5*eps))
all(all(timgD_HL - imgD_HL < 5*eps))
all(all(timgD_HH - imgD_HH < 5*eps))

% Plots Deconstruction..
figure;
subplot(2,2,1), imshow(timgD_LL, [min(min(timgD_LL)) max(max(timgD_LL))]), title('Img Deconstruction - LL filter');
subplot(2,2,2), imshow(timgD_LH, [min(min(timgD_LH)) max(max(timgD_LH))]); title('Img Deconstruction - LH filter');
subplot(2,2,3), imshow(timgD_HL, [min(min(timgD_HL)) max(max(timgD_HL))]); title('Img Deconstruction - HL filter');
subplot(2,2,4), imshow(timgD_HH, [min(min(timgD_HH)) max(max(timgD_HH))]); title('Img Deconstruction - HH filter');
figure;
subplot(2,2,1), imshow(imgD_LL, [min(min(imgD_LL)) max(max(imgD_LL))]), title('Img Deconstruction - LL filter');
subplot(2,2,2), imshow(imgD_LH, [min(min(imgD_LH)) max(max(imgD_LH))]); title('Img Deconstruction - LH filter');
subplot(2,2,3), imshow(imgD_HL, [min(min(imgD_HL)) max(max(imgD_HL))]); title('Img Deconstruction - HL filter');
subplot(2,2,4), imshow(imgD_HH, [min(min(imgD_HH)) max(max(imgD_HH))]); title('Img Deconstruction - HH filter');


Mapping from multiple sources to destination using JMapper I am using JMapper to map from multiple sources to a destination class. Could you review it and let me know if the code looks OK to you? Please suggest any changes that I can make to improve it.

Interface to Map sources to destination object:

public interface ObjectMapper<D> {

    public D getDestination(Object... sources);

}

Class that implements this interface to perform the desired mapping using JMapper:

import org.apache.commons.lang.WordUtils;
import com.googlecode.jmapper.JMapper;

public class JMapperImpl<S1, S2> implements ObjectMapper<DestinationClazz> {

    private static ObjectMapper<DestinationClazz> INSTANCE;
    private static final String CONVERSION_END = "Conversion.xml";

    private Class<S1> source1;
    private Class<S2> source2;

    private final JMapper<DestinationClazz, S1> mapper1;
    private final JMapper<DestinationClazz, S2> mapper2;

    private JMapperImpl(Class<DestinationClazz> destination, Class<S1> source1, Class<S2> source2) {
        final String mappingFile = getMappingFile(destination);
        mapper1 = new JMapper<DestinationClazz, S1>(destination, source1, mappingFile);
        mapper2 = new JMapper<DestinationClazz, S2>(destination, source2, mappingFile);

        this.source1 = source1;
        this.source2 = source2;
    }

    /**
     * @param destination
     * @return uncapitalizes the first letter of destination class name.
     */
    private String getMappingFile(Class<DestinationClazz> destination) {
        return WordUtils.uncapitalize(destination.getSimpleName())+CONVERSION_END;
    }

    public static <S1, S2> ObjectMapper<DestinationClazz> getJMapperInstance(Class<DestinationClazz> destination, Class<S1> source1, Class<S2> source2) {
        if(INSTANCE == null) {
            INSTANCE = new JMapperImpl<S1, S2>(destination, source1, source2);
        }
        return INSTANCE;
    }

    /**
     * Returns new instance of destination object with its properties mapped from source objects
     */
    @Override
    public DestinationClazz getDestination(Object... sources) {
        DestinationClazz destination;
        try {
            destination = DestinationClazz.class.newInstance();
            for(Object source : sources) {
                Class<? extends Object> sourceClass = source.getClass();
                if(sourceClass == source1) {
                    destination = mapper1.getDestination(destination, (S1)source);
                }
                else if(sourceClass == source2) {
                    destination = mapper2.getDestination(destination, (S2)source);
                }
            }
        } catch (InstantiationException e) {
            throw new CustomException("Couldn't instantiate DestinationClazz class:"+e.getMessage());
        } catch (IllegalAccessException e) {
            throw new CustomException("Couldn't access DestinationClazz class:"+e.getMessage());
        } catch (Exception e) {
            throw new CustomException("Exception while mapping source objects to DestinationClazz object:"+e.getMessage());
        }
        return destination;
    }
}

I can understand the usefulness of a class/tool like this. The basic thinking is:

need to transform class A to class B.
also need to transform class C to class B.
JMapper can help.
there are other classes that need transformations as well
we should make a generic factory for it.
we can also make the concept referencable as an interface, so things other than JMapper can do the mapping if necessary.

This is what I assume your thought process was, so I will review based on that assumption...

Interface

First up, the interface idea is a good one.... but the varargs Object parameter is a problem. You should only have a single argument. Also, since you want to keep the input argument anonymous (Object instead of <T>), you should have some exception handling for those times when invalid data is supplied....

The reason for suggesting you have only a single input parameter is because the logic for choosing which instance is used for the transform is not easy to specify when there's multiple candidate input values. You should let the calling code make the decision as to which instance to convert from (note, this is related to a second problem I will address again in a moment)

I would also recommend renaming the interface method to something more verb-like, such as mapToDestination(...) instead of getDestination(...)

Bottom line, I would recommend an interface like:

public interface ObjectMapper<D> {

    public D mapToDestination(Object source) throws IllegalArgumentException;

}

Right, now for the actual implementation.... using JMapper. Unfortunately there are some real concerns I have in here.

DestinationClazz

Do you have an actual class called DestinationClazz? I imagine not. I think this is supposed to be a generic type, but then you are not treating it like a normal type. For example, your class definition is:

public class JMapperImpl<S1, S2> implements ObjectMapper<DestinationClazz> {

but then your constructor is:

private JMapperImpl(Class<DestinationClazz> destination, Class<S1> source1, Class<S2> source2) {
    final String mappingFile = getMappingFile(destination);

This makes no sense because since you have declared the ObjectMapper as an exactly typed value, you may as well have a constructor that knows it is production DestinationClazz instances... no need to pass in the class:

private JMapperImpl(Class<S1> source1, Class<S2> source2) {
    final String mappingFile = getMappingFile(DestinationClazz.class);

So, because of this inconsistency, I imagine that you really want the DestinationClazz to be a generic type.... and you should specify it as part of the class signature:

public class JMapperImpl<S1, S2, D> implements ObjectMapper<D> {
    private JMapperImpl(Class<D> destination, Class<S1> source1, Class<S2> source2) {
        final String mappingFile = getMappingFile(destination);
        ....

    @Override
    public D getDestination(Object source) {
        ....

Static Singleton

This code is broken for a number of reasons:

public static <S1, S2> ObjectMapper<DestinationClazz> getJMapperInstance(Class<DestinationClazz> destination, Class<S1> source1, Class<S2> source2) {
    if(INSTANCE == null) {
        INSTANCE = new JMapperImpl<S1, S2>(destination, source1, source2);
    }
    return INSTANCE;
}

Here you have a lot of pretty complicated problems going on. I will try to address them in a sensible way....

synchronization - you are vulnerable to having multiple instances of the same JMapper since multiple threads could be calling this at any one time, and ending up with different instances.
misleading generics - This is a generic method and not a method with generic arguments. What I am saying is that the <S1, S2> here are not the same ones as those on the class (public class JMapperImpl<S1, S2> implements ....). Your code implies that this static method takes the same generic arguments as the INSTANCE instance, but this static method is not related to any particular class instance anywhere.
Generic Erasure - when a class with Generics is compiled, the compiler uses the generics to do compile-time validation of the code. Once the compile is validated though, the generic information is completely erased. The effect of this is that there is actually only one class called JMapperImpl. You can create many instances of this class each with different generic types: new JMapperImpl<Double, Long>(Double.class, Long.class), or new JMapperImpl<String, StringBuilder>(String.class, StringBuilder.class), etc.... but only the first one you create using the static method will be the INSTANCE, and the others will never exist.... ;-)

Where to, Sir?

In your actual mapping method you loop through the input source variables, and, if they match one of your defined source classes, you create a destination instance using the JMapper.

Unfortunately, you keep going until you run out of input source values.... If the user supplies 100 source values, you map them all! and only return the last one....

Which one is the right destination (what's the destination? ... where to, Sir)?

Conclusion....

You should:

add the D Destination generic type to your class definition
completely remove the static INSTANCE and factory method
make the constructor public.... these are light-weight classes, and you can easily have multiple instances.
change the mapping method name to something more meaningful.
change the mapping argument to a single source parameter which is the only thing to map.
throw an exception if the source does not match one of the anticipated sources.


Linked lists of templated classes vs function ptr I am designing a library for a hierarchical problem. At each stage of the hierarchy there are several "tools" at hand. If at a state N one tool succeeds, the solution is passed to the next (N+1) state. If all tools of stage N fail, we return to the state N-1 (previous) and let the previous stage handle the problem.

I have two possible ideas how to structure this problem. One uses a linked list of templated classes, the other binds directly to the next stage's run function.
My question is, is any of these superior to the other (or are both flawed) and why?

The first solution uses templates to create a linked list of templated classes.

template <typename Input, typename Output>
struct BaseSolver
{
    virtual boost::optional<Output> run(const Input& _input) = 0;
};

template<typename Input>
struct BaseStage
{
    virtual bool runAndRecover(const Input &_input)
    {
        return true;
    }
};

template<typename Input, typename Output>
struct Stage1 : BaseStage<Input>
{
    bool run(const Input& _input)
    {
        for(const auto& solver : solvers_)
        {
            const auto currentResult = solver->run(_input);
            if(currentResult && nextStage->runAndRecover(currentResult.get()))
            {
                return true;
            }
        }
        return false;
    }

    std::vector<boost::shared_ptr<BaseSolver<Input, Output>>> solvers_;

    BaseStage<Output>* nextStage;
};

This is the other solution. It binds only to the run() function of the next stage

template<typename Input, typename Output>
struct Stage2
{
    typedef boost::function<boost::optional<Output> (Input)> SolverFunction;
    typedef boost::function<bool(Output)> NextStage;

    bool run(const Input& _input)
    {
        for(const auto& solver : solverFunctions_)
        {
            const auto solverResult = solver(_input);
            if(solverResult && nextStage_(solverResult.get()))
            {
                return true;
            }
        }
        return false;
    }

    std::vector<SolverFunction> solverFunctions_;
    // will be bind to the next stage::run
    NextStage nextStage_;
};

PS: Both versions compile and run as a prototype.

The second is simpler, neater and avoids virtual functions. Prefer std::function over boost::function unless the latter gives you something extra, which it doesn't here