Fetch entire table from database after validating the table name I'm creating a database class. It's part academic and part something I may show in an interview.

The purpose of this method is to accept a table name as a parameter, check if the PDO Object has been created (this is in an earlier method), check if the table is in the database as to white list the table for going further in the script, and also to check if the parameter contains any characters that MySQL does not support for unquoted identifiers. If it passes then the table is returned.

<?php
class DatabaseClass{
...
public static function getTable($tablename = ''){
    if(!isset(self::$pdo)){
        trigger_error('Error: '.__CLASS__.'::'.__METHOD__.'() requires a database connection.',E_USER_ERROR);
        return false;
    }
    $whitelist = self::$pdo->query('SHOW TABLES');
    if(!in_array($tablename, $whitelist->fetchAll(PDO::FETCH_ASSOC)) || preg_match('[^0-9,a-z,A-Z$_]',$tablename)){
        /*If tablename is not in the database or if it contains illegal characters*/
        return false;
    }else{
        $tbl = self::$pdo->query('SELECT * FROM `'.$tablename.'`');
        return $tbl->fetchAll(PDO::FETCH_ASSOC);
    }
}
...

When looking over your code I find several things I would do differently. I may seem harsh in my review, but I have no intention of making this a painful experience. If you have any questions feel free to ask. Without further ado, let's go!

The first thing which comes to my mind is the use of static methods. When working in an object oriented manner I rarely use static methods. When I use them though I ensure they follow this simple rule:

  Static methods should be entirely self contained. If a static methods depends on an instance, it has potential side-effects.

This is a personal rule :)

To me this means that static methods should be purely input -> process -> output methods. This also implies that no kind of persistence can be done as it would not be associated with the specific instance the static method is declared in. Even if an instance is provided through its argument list you cannot be sure any persistence wasn't done inside the instance. If you use an object inside the static method it should only exists within the method's scope.

A good example for a static method is when the logic is related. Consider normalization of class names before it's instantiated.

/*
 * An entirely self contained static method. The reason it is
 * declared inside the class is, because the functionality is
 * related to the class.
 */
public function normalizeClassname($classname)
{
    $basename  = ucfirst(basename($classname));
    $namespace = substr($classname, 0, -strlen($basename));

    return str_replace('/', '\\', $namespace) . $basename;
}

Preventing side-effects helps you avoid those moments when a bug has you wondering what the !@*? is going on? (More on this in the linked resource in the link "Global State and Singletons").

Your method depends on an instance of PDO. If you adhere to the rule above this cannot happen inside a static method and it should therefore be changed.

/*
 * The 'static' keyword has been removed.
 */
public function getTable($tablename = '') {...

Then looking over the argument list of the method I find it hard to understand why the table name can be omitted (has a default value)? If you don't provide a table name what is there to search for inside the database? I would change this into a required argument.

/*
 * The default argument value has been removed.
 */
public function getTable($tablename) {...

The next may be a little weird, but try to follow me. But first we need quote, everyone loves quotes!

  A method/function should do one thing and do it good.

  - Robert C. Martin

Both checking for a valid PDO instance and checking if provided table name exists violates this rule. Your method have 2 concerns as of now (there is actually one more, but more on that later). The issue can easily be solved with 2 possible solutions. Since a PDO instance cannot be created if invalid parameters are provided you can always assume any given PDO instance is valid.

The first solution: I assume an instance of PDO is required by your database class. This would be a perfect opportunity to use dependency injection inside a __construct() method. This removes the requirement of checking if a valid PDO instance was provided to your getTable() method as you can fetch the instance from a class property.

/*
 * Example of constructor injection.
 */
public function __construct(PDO $pdo)
{
    $this->pdo = $pdo;
}

The second solution: If you do want a __constructor() method or this is the only method to use a PDO instance, you could require the PDO instance in the argument list.

/*
 * Alternative to constructor injection. Argument injection!
 */
public function getTable(PDO $pdo, $tablename) {...

If you decide to follow one of the above solutions you have removed the unrelated concern of checking the validity of the PDO instance from your method.

You then make a white-list by fetching an array of tables inside the selected database and check if your provided table name exists in the array. After this you check if the table name is valid. Checking if the table name is valid should be done before the database query is issued (saving server resources). After all there's no use checking if a table exists when the provided table name is invalid.
I would also throw exceptions instead of emitting fatal errors. The end result would be the same, but you would have a nice backtrace with the exception.

Your method should now look like the following:

public function getTable($tablename)
{
    /*
     * I have fixed your regular expression since a delimiter was missing. I
     * have also simplified the expression to be case-insensitive (using the 'i' modifier) and
     * removed the comma since (as far as I know) isn't a valid table name character.
     */
    if(!preg_match('~[^a-z0-9$_]~i',$tablename)) {
        throw new UnexpectedValueException('The provided table name contains invalid characters.');
    }

    /*
     * Notice PDO is now fetched through an instance property and
     * is not static anymore.
     */
    $whitelist = $this->pdo->query('SHOW TABLES')->fetchAll(\PDO::Fetch_ASSOC);

    if(!in_array($tablename, $whitelist)){
        return false;
    }

    // Removed the ´else´ block as it was unnecessary.

    $tbl = self::$pdo->query('SELECT * FROM `'.$tablename.'`');
    return $tbl->fetchAll(PDO::FETCH_ASSOC);

}

I would then argue that fetching everything inside the table creates 2 new (major) issues. The first is that it's another concern. As I have understood the method validates that a table exists inside the database. Therefore it should't be concerned with fetching data from it. This could also imply renaming the method to validateTableName() or something like it.

The second being a performance risk. Imagine the provided table stores 1 million rows. Are you sure the database connection allows that long a connection? Does PHP have enough memory dedicated? Is the execution time increased for this (potentially) long running task? Are you aware this halts script execution as long as the query is being processed?

There are properly more concerns when fetching entire tables. I would urge you to consider simply returning TRUE and let other methods deal with fetching data.

If you still want to fetch data you should use a prepared statement instead of interpolating the table name directly into the query string. You may reason that it's always you who decides the table name, but using defense in depth is always better. Malicious users can unfortunately do some scary things.

If you agree with me this far your method should look like this:

/*
 * Changed method name to reflect is new intent.
 */
public function tableExists($tablename)
{
    if(!preg_match('~[^a-z0-9$_]~i',$tablename)) {
        throw new UnexpectedValueException('The provided table name contains invalid characters.');
    }

    $whitelist = $this->pdo->query('SHOW TABLES')->fetchAll(\PDO::Fetch_ASSOC);

    /*
     * Added strict comparison.
     */
    return in_array($tablename, $whitelist, true));
}

The method is now more concise and shows a clear purpose. The readability has also improved by giving more space between the lines. Remember that your code shouldn't be hard to read.

Bonus

Your original method emitted an error using the native trigger_error() function with the E_USER_ERROR flag. This is the same as an exception regarding functionality. But with exceptions you give your program a chance to recover. The calling code or a generic exception handler (set using set_exception_handler()) can then decide if anything can be done before the script fails with a fatal error.

Regarding concerns: I have mentioned this several times and I think this is one of the best things you can make a habit. I have several times when I found a bug  praised myself for separating logic into small pieces from the start. This makes correcting the bug easier as you know exactly where the logic in question is defined. This also helps readability when your functions/methods are concise.

The resources linked in this awesome answer on StackOverflow has helped me along the way. Especially the second link about Clean Code III: Functions about function/method concerns is relevant to this question.

Hope this helps, happy coding!


Check if a string contains a set of characters I have written this piece of code to check if a string contains a set of characters, regardless of the order.

Eg: 'ruby is best' / 'bysbe' => true

Code:

def find_chars(s1,s2)
s1.chars.sort.join =~ Regexp.new(s2.chars.sort.join(".*")) ? true : false
end

I need to optimize it to reduce executing time. How? What is slowing the performance, the regex, the methods, the ternary, or all together?

EDIT:

The last one provided by @Flambino performs significantly better, and this one performs best

def find_chars(subject, characters)
  characters.chars.uniq.all?{|i| characters.count(i) <= subject.count(i)}
end

Now I only need to investigate why :)

Using regex for this is overkill, but so is sorting both strings. I'd just do:

def find_chars(subject, characters)
  characters.chars.all? { |char| subject.include?(char) }
end

Just doing a very cursory benchmarking, but it's an order of magnitude faster, at least for small strings like your example.

Edit: I should point out that this implementation is different from the original in that it doesn't care about multiples of the same character.

The original code will return false if given, say, ruby and rr, since there's only one "r" in the string. The implementation above, however, just matches the first letter twice - or N times, if need be.

Whether this is correct for your use-case, I don't know.

Incidentally, you could consider uniqing the character set to avoid redundant matching, but it'll probably be much slower for all but the most extreme input.

Edit 2: Responding to comments. This isn't very pretty, but should get the job done:

def find_chars(subject, characters)
  letters = characters.chars
  subject.chars.each do |letter|
    i = letters.index(letter)
    next if i.nil?
    letters.delete_at(i)
    return true if letters.empty?
  end
  false
end

Unfortunately, something simple like (characters.chars - subject.chars).empty? won't work as it too deletes duplicates.

In the above, it doesn't actually matter if you loop through the subject and search the characters, or vice-versa. However, it might matter performance-wise. I'd suggest looping over the longer string, and searching the shorter one (which'll get shorter the more stuff gets matched and deleted):

def find_chars(subject, characters)
  letters, repertoire = [subject, characters].sort_by(&:length)
  repertoire.each do |letter|
    i = letters.index(letter)
    next if i.nil?
    letters.delete_at(i)
    return true if letters.empty?
  end
  false
end

Now, I don't know how this fares in terms of performance. You'll have to test it out.

You could also return to sorting the characters string, and do binary search; maybe quicker than index.

By the way, I'd consider monkey-patching this method into String. It'd be nicer to write "hello".covers?("lelo") or something. But whether stand-alone or monkey-patched, find_chars isn't a great name.

Edit 3: The above can also be written as so, though performance is likely similar:

def find_chars(subject, characters)
  letters, repertoire = [subject, characters].sort_by(&:length)
  repertoire.each_char do |letter|
    letters.sub!(letter, '')
    return true if letters.empty?
  end
  false
end

Just for the heck of it, here's another approach. But I doubt it'll be fast:

def find_chars(subject, characters)
  repertoire = subject.chars.group_by { |char| char } # use &:itself for Ruby 2.2+
  letters = characters.chars.group_by { |char| char }

  letters.all? do |char, list|
    repertoire[char] && repertoire[char].count >= list.count
  end
end

It's basically frequency analysis and comparison. Again, it might be worth to pick the shortest of the two strings as the one to loop.


Adding Combinations of Numbers in an Array Could someone help me optimize this code for time complexity? What is the best way to do this that doesn't include nested for loops?

  Take an array of integers and return a list of sums of every combination
  of 2 numbers. So, for this array [1,2,3], spit out "3,4,5 (1+2, 1+3, 2+3)."

Here is a possible solution using \$O(n^2)\$ time complexity:

static List<int> returnSums(int[] integers)
{
    List<int> sums = new List<int>();
    for (int x = 0; x < integers.Length; x++)
    {
        for (int y = x + 1; y < integers.Length; y++)
        {
            sums.Add(integers[x] + integers[y]);
        }
    }
    return sums;
}

Is there a way to write this with \$O(n)\$?

The code is fine, and asymptotically optimal. There is a potential speedup by preallocating the output list to the correct size, but it's at best a factor of 2. VisualMelon's comment is unnecessarily pessimistic: List<T>.Add has an amortised cost of \$O(1)\$, although to show that it's necessary to rely on implementation details which are not in the API documentation.

There are some small improvements which could be made. The spec asks for "a list" rather than "a List", so I see no reason not to follow the principle of coding to the interface. I would prefer to return IList<int> or IReadOnlyList<int>.

The other thing is names. The return in returnSums doesn't tell me anything useful. How about pairwiseSums? And instead of x and y I would use i and j, which are de facto standard variable names for array indices for reasons going back to FORTRAN's type system.


Forming a dynamic dictionary based on searched key and values pair using RAW logic and not modules of python I am trying to create a dictionary with a file containing text based on a matched pattern. Lines containing key_str should become keys and subsequent lines not matching key_str should become values and get associated with keys in the dictionary. so i have below code working: But I need help and getting the

best practices and design pattern in my case
Performance in case my file is in GB
Alternate/different approaches without using any modules but just raw logic. don't want to use collections for example. for using python module I can ask a different question but here I just want to get to raw logic approaches.

File: file2dict.result-soa1
ml1
/var
/home

cpuml2
/var
/home

Output
my_dict: {ml1: ['/var','/home'], cpuml2: ['/var','/home']}

Code:
import os
homedir = os.environ.get('HOME')

key_str = "ml"
my_dict = {}
val_list = []
key = ''
with open(homedir + '/backup/file2dict.result-soa1') as file2dict:
    for line in file2dict:
        words = line.split()
        for aWord in words:
            if key_str in aWord:
                if key:
                    my_dict[key] = val_list
                    val_list = []
                    key = aWord
                else:
                    key = aWord
            else:
                val_list.append(aWord)
    my_dict[key] = val_list
print(my_dict)

Your code is off to a good start, but here are some suggestions either
for modest improvements or ways to simplify and clarify things.
The built-in pathlib library
is often the easiest and most robust way to work with file paths.
Scripts with hard-coded file paths tend to be inflexible. For example,
to review your code I had to edit it right out of the gate, because
my computer lacks your directory structure. During your own development and
debugging of a script, you might not want to operate on the real
file every time (using a tiny replica is often easier). All of
which is to say that you are better off using default paths with
the option of command-line overrides. This adjustment also positions
you well for the future: if the needs of a script increase, you
can easily add support for more command-line arguments or options.
I would encourage you to embrace the time-tested best-practice of putting
nearly all substantive code inside of function or class definitions. It's an
easy change to make and the greater isolation tends to increase flexibility.
For example, in the suggested edits below, which still stick pretty closely to
your original code, the algorithmic complexity of parsing has been extracted
into a narrowly tailored function that knows nothing about the program's larger
concerns. It doesn't have to know about paths, file reading, etc. Instead, it
takes any iterable containing lines of relevant data. That makes it easier to debug
and test, because you can call it separately with just a list of strings.
The edits below also provide a short illustration of how even fairly brief
comments can add context and help the reader understand both purpose and the
general logic. Some of the comments are like organizational sign posts: for
example, "Setup" or "Parse". They make it easier to scan code visually to get
your bearings. Other comments can help a reader by explain the gist of the
algorithm intuitively (for example, the two comments in the inner loop). Notice
that the comments do not mimic the code; rather, they help to organize it and
throw additional light on it.
At a minimum, I would encourage you to adopt consistent variable naming
conventions. Sometimes you follow the practice of appending data-type suffixes
to names; other times not. That's not a practice I've ever found valuable, but
opinions differ. Naming variables, functions, and classes is difficult because
there are often competing priorities: clarity, brevity, ease of typing, ease of
reading, need to compare/contrast similar things, and so forth. In the edits
below, some of the names below are conventional. For example, unless I need to
have multiple files open at once, I always use fh for "file handle". Same
thing for args in a main() function. Other names are fairly explicit and
human-readable: default, file_name, file_path, line, and word are
examples in this bucket. And other names are less strong: for example, data
and vals. In some contexts, a generic name is appropriate (for example, a
general-purpose function that performs a general operation on some input). In
your case, I suspect that more substantive names exist, but only you know them.
from sys import argv
from pathlib import Path

def main(args):
    # Get file path to the input data file.
    default = 'backup/file2dict.result-soa1'
    file_name = args[0] if args else default
    file_path = Path.home() / file_name

    # Parse.
    with open(file_path) as fh:
        data = parse_data(fh)

    # Report.
    print(data)

def parse_data(lines):
    # Setup.
    data = {}
    vals = []
    key = None
    marker = 'ml'

    # Parse.
    for line in lines:
        for word in line.split():
            if marker in word:
                # Store current VALS; and setup new KEY and VALS.
                if key:
                    data[key] = vals
                    vals = []
                key = word
            else:
                # Or just store with current VALS.
                vals.append(word)

    # Wrap-up and return.
    data[key] = vals
    return data

if __name__ == '__main__':
    main(argv[1:])


Very simplistic style add or update In my library for styling the Console I need to be able to add or update two styles: color and background-color.

The use case is very simple. There is a string with styles that I'm building and that I update to change the color if necessary.

I divided this task into three steps:

explode the string into declarations
manipulate the style
reconstruct the style

Example Each of these steps has its own extension:

void Main()
{
    var style = "color: red;";

    style
        .ToDeclarations()
        .AddOrUpdate(
            ("color", "black"),
            ("background-color", "blue")
        )
        .ToStyle()
        .Dump();
}

These extensions are used by higher-level extensions that call them with const string for property names. I just used simple strings in LINQPad.

Code Their implementation is very straightforward. They use only LINQ and tuples.

public static class CssExtensions
{
    public static IEnumerable<(string property, string value)> ToDeclarations(
        this string style)
    {
        const string declarationPattern = @"(?<property>[a-z-]+):\s*(?<value>.+?)(;|$)";

        return
            Regex
                .Matches(style, declarationPattern, RegexOptions.IgnoreCase)
                .Cast<Match>()
                .Select(m => (
                    property: m.Value("property").Trim(),
                    value: m.Value("value").Trim())
                );
    }

    public static IEnumerable<(string property, string value)> AddOrUpdate(
        this IEnumerable<(string property, string value)> declarations,
        params (string property, string value)[] updates)
    {
        return
            declarations
                .Concat(updates)
                .GroupBy(t => t.property)
                .Select(t => t.Last())
                .Skip(t => string.IsNullOrEmpty(t.value));
    }

    public static string ToStyle(
        this IEnumerable<(string property, string value)> declarations)
    {
        return
            declarations
                .Select(t => $"{t.property}: {t.value};")
                .Join(" ");
    }
}

As the use case is very simple and I also don't need to parse any complex styles so are the extensions, just a simple regex with some string manipulation.

I update the style by grouping by the property and pick the last one if there are mutliple ones, if there is none yet, then a new style is added. If the value happens to be null or Empty then it's removed.

There are three more extensions: one that I use to Join declarations, one Value shortcut for regex and a Skip that I use as an inverse of Where to use positive conditions if I want to exclude some cases.

public static class EnumerableExtensions
{
    public static string Join<T>(this IEnumerable<T> values, string separator)
    {
        return string.Join(separator, values);
    }

    public static IEnumerable<T> Skip<T>(this IEnumerable<T> source, Func<T, bool> predicate)
    {
        return source.Where(x => !predicate(x));
    }
}

public static class MatchExtensions
{
    public static string Value(this Match match, string groupName)
    {
        return match.Groups[groupName].Value;
    }
}

Should I still improve it in any way?

The only thing that pops out to me (though admittedly, it is very minor) is that you're recompiling the regex every time you call ToDeclarations.

You could use a static Regex instance which compiles the expression only once. Regex instances are also threadsafe - so no worries there.

Thus, your code could look like:

private static Regex _cssRegex = new Regex("(?<property>[a-z-]+):\s*(?<value>.+?)(;|$)", RegexOptions.IgnoreCase);
public static IEnumerable<(string property, string value)> ToDeclarations(this string style)
{
    return
        _cssRegex
            .Matches(style)
            .Cast<Match>()
            .Select(m => (
                property: m.Value("property").Trim(),
                value: m.Value("value").Trim())
            );
}


MIT Puzzle: The Best Time to Party This problem is from MIT Course and I have implemented it in C++. Please review and suggest improvements.

  There is a party to celebrate celebrities that you get to attend
  because you won a ticket at your office lottery. Because of the high
  demand for tickets you only get to stay for one hour but you get to
  pick which one since you received a special ticket. You have access to
  a schedule that lists when exactly each celebrity is going to attend
  the party. You want to get as many pictures with celebrities as
  possible to improve your social standing. This means you wish to go
  for the hour when you get to hob-nob with the maximum number of
  celebrities and get selfies with each of them.

  We are given a list of intervals that correspond to when each celebrity
  comes and goes. Assume that these intervals are [i, j), where i and j
  correspond to hours. That is, the interval is closed on the left hand
  side and open on the right hand side. This just means that the
  celebrity will be partying on and through the ith hour, but will have
  left when the jth hour begins. So even if you arrive on dot on the th
  hour, you will miss this particular celebrity.

  Here’s an example:

  When is the best time to attend the party? That is, which hour should
  you go to?

#include <iostream>
#include <vector>
#include <algorithm>

struct range
{
    int start = 0;
    int end = 0;

    range() = default;
    range(int start_time, int end_time):
        start(std::move(start_time)),
        end(std::move(end_time))
        {}
};

int celeb_density(std::vector<range>& schedule)
{
    //sort according to start_time
    auto by_start_time = [](const range &a, const range &b)
    {
        return a.start < b.start;
    };
    std::sort(schedule.begin(), schedule.end(), by_start_time);

    int party_start = schedule[0].start;   //Party start time
    int party_end = schedule[schedule.size()-1].end;  //Party end time
    int max_count = 0, curr_max = 0, best_time, curr_best_time;

    int i = party_start;
    while (i < party_end)
    {
        for (int j = 0; j < schedule.size(); ++j)
        {
            if (i == schedule[j].start)
            {
                curr_max++;
                curr_best_time = i;
            }
            else if (i < schedule[j].start)
            {
                break;
            }

            if (i == schedule[j].end)
            {
                curr_max--;
            }
        }
        if (curr_max > max_count)
        {
            max_count = curr_max;
            best_time = curr_best_time;
        }
        i++;
    }
    return best_time;
}

int main()
{
    std::vector<range> schedule;

    int number_of_celebs;
    std::cout << "Enter number of celebrities attending party: ";
    std::cin >> number_of_celebs;

    std::cout << "Enter entry time and exit time for a celebrity\n";
    for (int i = 0; i < number_of_celebs; ++i)
    {
        int s, e;
        std::cin >> s >> e;
        schedule.push_back(range(s, e));
    }

    int best_time = celeb_density(schedule);
    std::cout << "Best time to attend party is from " << best_time << " to " << best_time + 1 << "\n";
}

Good to see you're not doing a using namespace std ;).
Of course it doesn't really hurt in a source file (.cpp) (it does in a header file!),
but even then that is still considered bad practice. My personal reason to just always type the namespace is because it makes code easier to read (you know what is part of a namespace and which and don't have to guess that) and it is easier to search with regular expressions and the like.

While the standard does not use class names that begin with an upper case letter, many good coders do. It allows you - in fact - to have your own classes to stand out better, and using both upper case and lower case adds more state to your namespace (aka, less collisions). For example, you can call your class Range and a Range variable range.

Also for both, readability and regular expression searches, I strongly recommend only to use complete English words for any class, variable or function name and never resort to abbreviations. The only exceptions to this rule are local variables that are so local (used in a scope of only a few lines) that you can easily see their declaration and use on one screen and where their meaning is mostly irrelevant(!). For example a counter of a for loop can be called i if you must.

Also for ease of regular expression search and understandability (maintenance) of code it is a good idea to use the same name for variables that contain the same object (you copied a value from one to the other). Ok, that is normally not possible unless you pass them as function argument (you can't write range = range) but you'll surprised how often it is; for example use range_end for every variable that means "the end of a range". Why am I mentioning this? Well, this is the reason that class member variables often have a prefix (either M_ or m_ or something. I use m_. That way you avoid collisions with local variables with the same name, and member functions with the same name.

C++ provides classes with a reason: to write Object Oriented code. Encapsulation is part of that. In almost all cases your class member variables should be private!

For (ostream based) debugging output, it is a good idea to make every class
writable to an ostream.

std::move is just a cast, from an lvalue reference to an rvalue reference, and only useful when you pass the result to a function that takes an rvalue reference (aka, you pick the right overloaded function with it). Where you used std::move the argument isn't an lvalue reference, nor do you pass the result of the std::move to a function that accepts an rvalue reference, so using std::move there is nonsense. PS By convention a moved object (whose rvalue reference was passed to a function) should only be destructed afterwards (in all but exceptional cases). So if you cast an lvalue reference to an rvalue reference then that variable had better be passed in as an rvalue reference in the first place. The typical use case therefore looks as follows:

void bar(Bar&& bar);

void foo(Bar&& bar)
{
  // Here bar is an lvalue reference!
  bar(std::move(bar));
  // Now 'bar' may no longer used, only destructed (by convention:
  // it is like that because one would expect that bar() makes it so.
}

This would work fine when foo() took an lvalue reference (foo(Bar& bar)) but
then the caller of foo wouldn't be aware of the fact that bar was moved and could "accidently" use bar still after returning from foo(bar).

Combining what we learned so far, I arrive at the follow code for Range:

class Range
{
  private:
    int m_start_time = 0;
    int m_end_time = 0;

  public:
    Range() = default;
    Range(int start_time, int end_time) :
        m_start_time(start_time),
        m_end_time(end_time)
        { }

    int start_time() const { return m_start_time; }
    int end_time() const { return m_end_time; }

    friend std::ostream& operator<<(std::ostream& os, Range const& range);
};

Well, that's enough for today.
I'll finish with my own stab at celeb_density:

int celeb_density(std::vector<Range> const& schedule)
{
    // Do not pass an empty schedule.
    assert(!schedule.empty());          // #include <cassert>

    std::array<unsigned int, 24> hours; // #include <array>
    hours.fill(0);

    int best_time = schedule[0].start_time();
    int max_celebs = 1;
    for (auto range : schedule)
      for (int hour = range.start_time(); hour < range.end_time(); ++hour)
        if (++hours[hour] > max_celebs)
        {
          ++max_celebs;
          best_time = hour;
        }

    return best_time;
}


Get certification rules from collection How could the following function (the for loop) be transformed to a lambda expression or refactored to be cleaner:

public static Collection<AccessRuleTemplate> getCaRules(String roleName, Collection<Integer> currentcas) {
    Collection<AccessRuleTemplate> result = new ArrayList<AccessRuleTemplate>();
    boolean allcafound = false;
    List<AccessRuleTemplate> carules = new ArrayList<AccessRuleTemplate>();
    for (Integer caId : currentcas) {
        if (caId.equals(Integer.valueOf(BasicAccessRuleSet.CA_ALL))) {
            allcafound = true;
            break;
        }
        carules.add(new AccessRuleTemplate(StandardRules.CAACCESS.resource() + caId.toString(), AccessRuleState.RULE_ACCEPT, false));
    }
    if (allcafound) {
        carules.clear();
        carules.add(new AccessRuleTemplate(StandardRules.CAACCESSBASE.resource(), AccessRuleState.RULE_ACCEPT, true));
    }
    result.addAll(carules);
    return result;

}

In particular i don't like the use of boolean flag and would like to avoid it. The idea with the function is to traverse list of ids and if a particular id found it breaks the loop and sets a flag to true and then checks the flag later and clears idlist and only adds something to list. Otherwise all other ids are added to list.

There's a lot of waste in this method.  You're copying things to idList, only to clear them.  You're creating idList, only to copy it to result.

Try this:

public static Collection<AccessRuleTemplate> getCaRules(String roleName, Collection<Integer> currentcas) {
    List<AccessRuleTemplate> carules = new ArrayList<>();
    if (currentcas.contains(Integer.valueOf(BasicAccessRuleSet.CA_ALL))) {
        carules.add(new AccessRuleTemplate(StandardRules.CAACCESSBASE.resource(), AccessRuleState.RULE_ACCEPT, true));
    } else {
        for (Integer caId : currentcas) {
            carules.add(new AccessRuleTemplate(StandardRules.CAACCESS.resource() + caId.toString(), AccessRuleState.RULE_ACCEPT, false));
        }
    }
    return carules;
}

So, in the case where the item is found, there's a big savings - you don't create a bunch of objects and discard them.
In the case where the item is not found, there's a very slight increase in time to traverse the list twice.
In both cases, the copying between lists is eliminated, making this much more efficient (and readable).

I'd also recommend that for the "found" case, you pre-create a static, immutable, singleton list which you can directly return each time.

private static final Collection<AccessRuleTemplate> BASE_ACCESS_TEMPLATE
        = Collections.singletonList(new AccessRuleTemplate(StandardRules.CAACCESSBASE.resource(), AccessRuleState.RULE_ACCEPT, true));

Also "roleName" is unused.  I'm guessing it was only used in logging which was stripped out.

Finally, though you could use a lambda function for the conversion loop, I think the code above is simpler.  If you really want to, it would look something like:

return currentcas.stream()
        .map(caId -> {new AccessRuleTemplate(StandardRules.CAACCESS.resource() + caId.toString(), AccessRuleState.RULE_ACCEPT, false)})
        .collect(Collectors.toList());


Simple Java ArrayList stores and shows not repeated elements entered by user Is this good code? I do believe I improved quite a lot since last year, still I would really appriciate some feedback :)

import javax.swing.JOptionPane;
import java.util.ArrayList ;

public class IfNotRepeated {

    /*
     *  7.12 (Duplicate Elimination) Use a one-dimensional array to solve the following problem:
        Write an application that inputs five numbers, each between 10 and 100, inclusive. As each number
        is read, display it only if it’s not a duplicate of a number already read. Provide for the “worst case,”
        in which all five numbers are different. Use the smallest possible array to solve this problem. Display
        the complete set of unique values input after the user enters each new value.
     */

    final static int ELEMENTS = 5 ;
    final static int UPPER_BOUND = 100 ;
    final static int LOWER_BOUND= 10 ;

    public static void main(String[] args) {

        int number = 0; //user's input

        while ( true ) //allows the input of numbers which are bounded between 10 and 100 encompass,
            //whenever this boundary is violated, the program ends, without showing any information.
        {

            ArrayList <Integer> vector = new ArrayList <Integer> (5) ; //Array of not repeated user inputs', I need to get a new one
            //every time the user had the chance to input ELEMENTS numbers

            for ( int i = 0 ;
                    i < ELEMENTS
                    && ( number = gimmeValue() ) >= LOWER_BOUND
                    && number <= UPPER_BOUND
                            ; i++ ) // iterates as long as there are less than ELEMENTS numbers per array, and the boundary is respected
            {

                if ( !vector.contains(number) )
                    vector.add(number) ; //adds a number if the legit value entered hasn't been previously entered (in this serie).

                String elements = "" ;

                for ( int notRepeatedElement : vector )
                    elements += String.valueOf(notRepeatedElement) + '\n' ; //concatenates not repeated elements leaving a new line at the end

                JOptionPane.showMessageDialog(null, elements); //show every non-repeated element

            }
            if ( number < LOWER_BOUND || number > UPPER_BOUND )
                break ; // if out bounds, exit program
        }
    }

    public static int gimmeValue () //shows an input dialog for the user to enter a number and returns that value as an Int
    {

        String number = JOptionPane.showInputDialog("Enter a number between 10 and 100 encompass:") ;
        return Integer.valueOf(number) ;

    }
}

Personally, I'd refrain from putting the bulk of your logic into the main method. I'd refactor the code out into other methods and just call them from the main method.

Also, I wouldn't consider 'while(true)' to be good programming practise with some exceptions. If I were you I'd get the ArrayList size and use a loop that runs up to that. This also removes the need for that if-break statement you have at the bottom of the while loop.

I would also note that the question outlined in the comments says to use an array, not an ArrayList which may or may not be important but given the student/interview style of the question it may need to be a normal array as specified...strictly speaking an ArrayList is an object that behaves 'like' and array.

In regards to comments although they are thorough I'd advise against writing comments on the same line as statements (unless they are very short) as it is inconvenient for anyone reviewing your code to have to scroll left and right just to read the comments.

Variable names could be a touch better too but this only really applies in a professional context where other people are going to be looking at your work (same as comments I suppose). Rather that use 'number' as variable name use something a bit more descriptive like 'usersNumber' or something like that...all goes towards easier understanding and readability. I should also note that this applies to method names too (eg. gimmeValue doesn't really make much sense).

However with all that being said, keep it up! Programming is all about refinement and practise and no doubt you'll be an excellent, clean coder in no time!


Am I writing good Go here? Python functions converted to Go I originally asked this question on StackOverflow. Reproduced here by recommendation.

I've got a number of Python scripts that I'm considering converting to Go. I'm seeking confirmation that I'm using Go in essentially the way it was meant to be used. Full code is available here: https://gist.github.com/anonymous/7521526

So the primary question is: Am I writing what is considered "good Go" ?

Python function #1: Look at the files in a folder and extract the latest encoded date in the filenames.

def retrieveLatestDateSuffix(target):
    return max(map("".join, filter(lambda x: x,
        map(lambda x: re.findall(r"_([0-9]{8})\.txt$", x),
            os.listdir(target)))))

My translation for #1:

var rldsPat = regexp.MustCompile(`_([0-9]{8})\.txt$`)
func retrieveLatestDateSuffix(target string) (string, error) {
    if fis, e := ioutil.ReadDir(target); e == nil {
        t := ""
        for _, fi := range fis {
            if m := rldsPat.FindStringSubmatch(fi.Name()); m != nil {
                if m[1] > t { t = m[1] }
            }
        }
        return t, nil
    } else {
        return "", e
    }
}

Python function #2: Add a date suffix to each filename inside a folder that doesn't already have a suffix added. Printing the from/to for now instead of doing the rename.

def addDateSuffix(target, suffix):
    for fn in filter(lambda x: re.search(r"(?<!_[0-9]{8})\.txt$", x), os.listdir(target)):
        pref, ext = os.path.splitext(fn)
        gn = "{0}_{1}{2}".format(pref, suffix, ext)
        print(fn, " -> ", gn)

My translation for #2:

var adsPat1 = regexp.MustCompile(`\.txt$`)
var adsPat2 = regexp.MustCompile(`_[0-9]{8}\.txt$`)
func addDateSuffix(target string, suffix string) error {
    if fis, e := ioutil.ReadDir(target); e == nil {
        for _, fi := range fis {
            if m1 := adsPat1.FindStringSubmatch(fi.Name()); m1 != nil {
                if m2 := adsPat2.FindStringSubmatch(fi.Name()); m2 == nil {
                    ext := filepath.Ext(fi.Name())
                    gn := fmt.Sprintf("%s_%s%s", strings.TrimSuffix(fi.Name(), ext), suffix, ext)
                    fmt.Println(fi.Name(), "->", gn)
                }
            }
        }
        return nil
    } else {
        return e
    }
}

Early return is better than nesting. For example:

var adsPat1 = regexp.MustCompile(`\.txt$`)
var adsPat2 = regexp.MustCompile(`_[0-9]{8}\.txt$`)
func addDateSuffix(target string, suffix string) error {
    fis, e := ioutil.ReadDir(target)
    if e != nil {
        return e
    }
    for _, fi := range fis {
        if m1 := adsPat1.FindStringSubmatch(fi.Name()); m1 == nil {
            continue
        }
        if m2 := adsPat2.FindStringSubmatch(fi.Name()); m2 != nil {
            continue
        }
        ext := filepath.Ext(fi.Name())
        gn := fmt.Sprintf("%s_%s%s", strings.TrimSuffix(fi.Name(), ext), suffix, ext)
        fmt.Println(fi.Name(), "->", gn)
    }
    return nil
}

Also see this post for more idiomatic go discussion: https://stackoverflow.com/questions/20028579/what-is-the-idiomatic-version-of-this-function


Checking for automating water topoff The purpose of this code to is check the 3 float switches in the laminator chamber for water. The float switches vote with the majority winning. A momentary switch must be pressed for the section of code (//// START FILL LAMINATOR FROM 70GALLON RES ///) to be active.

We can also take water from the reservoir using a different button (latching):

///// START Fill Water Bucket

///START set pins  ///
const int startBucket =5;
const int pumpBucketValve =6;
const int startButton = 7;
const int floatSwitch1 = 8;
const int floatSwitch2 = 9;
const int floatSwitch3 = 10;
const int pumpPower = 11;
const int pumpBallValve = 12;
///END set pins  ///

///START set pins values  ///
int floatSwitchState1 = 0;
int floatSwitchState2 = 0;
int floatSwitchState3 = 0;
int summedValue = 0;
int pumpPowerState = 0; //turns pump on and opens the ball valve to the laminator
int startButtonState = 0;
int startBucketState = 0;
int pumpBucketValveState = 0;

///END set pins values  ///

///START set pins mode  ///
void setup() {

pinMode(floatSwitch1, INPUT);
pinMode(floatSwitch2, INPUT);
pinMode(floatSwitch3, INPUT);
pinMode(pumpPower, OUTPUT);
pinMode(pumpBucketValve, OUTPUT);
pinMode(startButton, INPUT);
pinMode(startBucket, INPUT);
}

///END set pins modes  ///

void loop() {
//// START FILL LAMINATOR FROM 70GALLON RES ///
startButtonState = digitalRead(startButton);
if (startButtonState == HIGH) {
    while (checkFloat >= 2) {
      digitalWrite(pumpPower, HIGH);
    }
      digitalWrite(pumpPower, LOW);
}
//// END FILL LAMINATOR FROM 70GALLON RES ///

///// START Fill Water Bucket
startBucketState = digitalRead(startBucket);
while (startButtonState == HIGH) {
      digitalWrite(pumpBucketValve, HIGH); //turn ball valve to on
    }

digitalWrite(pumpBucketValve, LOW); //turn ball valve to off

///// END FILL Water Bucket
}

int checkFloat() {
    summedValue = 0;
    floatSwitchState1 = digitalRead(floatSwitch1);
    if (floatSwitchState1 == HIGH) {
      summedValue = summedValue + 1;
    }
    floatSwitchState2 = digitalRead(floatSwitch2);
    if (floatSwitchState2 == HIGH) {
      summedValue = summedValue + 1;
    }
    floatSwitchState3 = digitalRead(floatSwitch2);
    if (floatSwitchState3 == HIGH) {
      summedValue = summedValue + 1;
    }
    return summedValue;
}

You have a lot of comments that are completely unnecessary, they are not needed.

int pumpPowerState = 0; //turns pump on and opens the ball valve to the laminator

The name of the variable tells me what this is and what it needs to do.  pumpPowerState that tells me the pump is either off or on and the assignment tells me we are using a 0 or a 1 to determine the on/off state of the device being controlled.

also the comments before and after the blocks are rather redundant as well, most of your blocks of code that you comment before and after are obvious what they are

///START set pins mode  ///

then there is your comment before the code inside the loop.

//// START FILL LAMINATOR FROM 70GALLON RES ///

This tells me that you should have a function that you call inside the loop, something like this

void FillLaminator() {
    startButtonState = digitalRead(startButton);
    if (startButtonState == HIGH) {
        while (checkFloat() >= 2) {
            digitalWrite(pumpPower, HIGH);
        }
    }
    digitalWrite(pumpPower, LOW);
}

And while we are at it:

void FillWaterBucket() {
    startBucketState = digitalRead(startBucket);
    while (startButtonState == HIGH) {
        digitalWrite(pumpBucketValve, HIGH); //turn ball valve to on
    }
    digitalWrite(pumpBucketValve, LOW); //turn ball valve to off
}

Then you call it like this inside of the loop

void loop() {
    FillLaminator();
    FillWaterBucket();
}

Please indent the code inside of brackets so that you can tell the scope more easily.

Do this:

void setup() {

    pinMode(floatSwitch1, INPUT);
    pinMode(floatSwitch2, INPUT);
    pinMode(floatSwitch3, INPUT);
    pinMode(pumpPower, OUTPUT);
    pinMode(pumpBucketValve, OUTPUT);
    pinMode(startButton, INPUT);
    pinMode(startBucket, INPUT);
}

instead of this:

void setup() {

pinMode(floatSwitch1, INPUT);
pinMode(floatSwitch2, INPUT);
pinMode(floatSwitch3, INPUT);
pinMode(pumpPower, OUTPUT);
pinMode(pumpBucketValve, OUTPUT);
pinMode(startButton, INPUT);
pinMode(startBucket, INPUT);
}

that should be a good start to writing cleaner Arduino code.


Preventing numbers from showing up in scientific notation We have a StreamBuffer class which is not inherited from std::ios_base (or some of it's derivatives such as std::ostream) so that I can use std::fixed operations and I am trying to prevent number showing up in scientific notations. With my below code some numbers are getting shown in scientific notations. We want to avoid doing any allocations so that's why we implemented StreamBuffer class because of performance reason.

T value = 0;

template<typename U> void process(U& buf, DataOption holder) const {
    if (holder == DataOption::TYPES) {
        switch (type_) {
        case teck::PROC_FLOAT:
            buf << "{\"float\":" << value << "}";
            break;
        case teck::PROC_DOUBLE:
            buf << "{\"double\":" << value << "}";
            break;
        default:
            buf << "{\"" << type_ << "\":" << value << "}";
        }
    }
}

This is the way it is being called:

void HolderProcess::dump(std::ostream& os, DataOption holder) const
{
    process<std::ostream>(os, holder);
}

void HolderProcess::dump(StreamBuffer& buffer, DataOption holder) const
{
    process<StreamBuffer>(buffer, holder);
}

I came up with this solution to avoid number (here value is coming in exponent form and I want to have a fixed number for that value) getting converted to scientific notation, but it uses string and it will do some allocations, which is not performance-efficient.

template <typename T> string str(T number)
{
   std::ostringstream ss;
   ss << std::fixed << number;
   return ss.str();
}

And then I can call above template method from my above each case block. This, however, will most certainly allocate more memory. Is there any better way to solve this problem which is optimized, efficient and doesn't do any allocations?

You could use vsnprintf if it's available on your system.  It might seem like a step backwards to use a C-style printf derivative in C++ code, but that's what's used in gcc on my Linux machine.  You can use alloca which allocates space on the stack, or a fixed size (but guaranteed sufficient) local array.

Because your StreamBuffer is not derived from std::ios_base and you haven't provided details of its implementation, I can't really show a code example but I presume that the StreamBuffer& operator<<() either is already or can be adapted to use vsnprintf.


Overriding equals and hashCode vs providing only Single Instance on immutable Objects Let's say we have a class SomeInt which holds just one single final int value:

public class SomeInt
{
    private final int value;

    public SomeInt(int value)
    {
        this.value = value;
    }

    public int getValue()
    {
        return this.value;
    }
}

Option A - Overring equals and hashCode:

public class SomeInt
{
    private final int value;

    public SomeInt(int value)
    {
        this.value = value;
    }

    public int getValue()
    {
        return this.value;
    }

    @Override
    public boolean equals(Object other)
    {
        if (!(other instanceof SomeInt))
        {
            return false;
        }

        return ((SomeInt) other).hashCode() == hashCode();
    }

    @Override
    public int hashCode()
    {
        return this.value;
    }
}

Option B - Providing only one Instance per Value:

import java.util.Map;
import java.util.HashMap;
import java.lang.ref.WeakReference;

public class SomeInt
{
    private static final Map<Integer, WeakReference<SomeInt>> INSTANCES = new HashMap<>();
    private final int value;

    private SomeInt(int value)
    {
        this.value = value;
    }

    public synchronized static SomeInt of(int value)
    {
        WeakReference<SomeInt> weakRef = INSTANCES.get(value);
        SomeInt instance = null;

        if (weakRef != null)
        {
            // keep reference before asking isEnqueued to ensure
            // it's not getting garbage collectedbetween the calls
            instance = weakRef.get();
        }

        if (weakRef == null || instance == null || weakRef.isEnqueued())
        {
            instance = new SomeInt(value);
            INSTANCES.put(value, new WeakReference<>(instance));
        }

        return instance;
    }

    public int getValue()
    {
        return this.value;
    }
}

Pros of A:

If the Object holds references to other Complex-Types the implementation is much easier and will be easy to customize when something changes
Can also be used with mutable Objects

Cons of A:

There may be many Objects with the same information

Pros of B:

There will always be only one Object holding this information
== comparison possible since equality is guaranteed by the generating method

Cons of B:

Can only be used with immutable Objects

Question:
What is the better approach to ensure comparisons and occurences in Maps and Collections don't fail?

Your approach is flawed in both ways. I see some fundamental misunderstanding of equals, hashcode and == operator.

To Option A

  Pros of A ... Can also be used with mutable Objects

Overriding hashcode and equals on mutable objects will lead to unaccessable elements within hash-based datastructures like HashMap or HashSet. Always make sure your objects are immutable when overriding these methods.

Furthermore your implementation of equals is semantically wrong. This is because you make "equals" dependent on hashcode only.

Maybe you can precheck the hashcode to avoid a complex equals-evaluation if the hashcodes aren't equal.

hashcode has a totally other purpose. It provides a value that is used in hash-based datastructures to balance lookup tables to increase lookup performance and minimze the binary search path.

You may say that Integer.hashcode(int i) always returns i. Yes, but you depend on implementation details for a totally different semantic.

A correct implementation for your SomeInt:

public class SomeInt {

    private final int value;

    public SomeInt(int value) {
        this.value = value;
    }

    public int getValue() {
        return this.value;
    }

    @Override
    public boolean equals(Object object) {

        boolean equals = false;

        if (object instanceof SomeInt) {

            SomeInt that = (SomeInt) object;

            equals = this.value == that.value;

        }

        return equals;
    }

    @Override
    public int hashCode() {
        return this.value;
    }

}

To Option B

Yes you can do so. But the achieve the same with the correct hashcode equals implementation on immutable datastructures with less overhead.

Logical path

If you override equals you have to override hashcode
hashcode is used within hash-based datastructures to put objects into  buckets
If you change the value hashcode depends on AND you have put the object into a hash-based datastructure before, it is very probable that you never find this object again.
Therefore values that are used to generate the hashcode must not change if you want to use the objects within hash-based datastructures.


improvements to this php function to calculate monthly returns from a set of price data I have made this function that should take a set of price data and calculate a set of monthly returns. The idea is that is should be able to cope with irregular time intervals.
For example I have daily data for the S&P 500 but many hedge funds only release price data monthly.

Here is what I have come up with:

//Turns a price series into an array of monthly returns.
function monthlyReturns($dates, $prices, $startDate = "", $endDate = ""){
if ($endDate == "") $endDate = time();

if (count($dates) != count($prices)){
die("The dates array must be the same length as the prices array");
}
$i = 0; $firstPass = false;
foreach ($dates as $date){
  $d = strtotime($date);
  if ($startDate == "" || ($d >= $startDate && $d <= $endDate )) :
    $p = $prices[$i];
    $month = date('M',$d);
    $year = date('Y',$d);

    if ($i == 0 || $firstPass == false){
      $startPrice = $p;
      $lastMonth = $month;
    }

    if ($month != $lastMonth && $i != 0){
      $returnTable['date'][] = $dates[$i-1];
      $returnTable['return'][] = $p / $startPrice - 1;
      $startPrice = $p;
    }
    $lastMonth = $month;
    $firstPass = true;
  endif;
  $i++;
  }
  return $returnTable;
}

I noticed that for a fund with only monthly data the returns are off by a month. Can anyone see any major flaws with this function that could explain this or a solution to solve it.

For info, the monthly returns for hedge funds often come near the end of the month. E.g.

date       | Price
-----------------
2013-01-29 | 25.69
2013-02-28 | 27.62
2013-03-30 | 26.53
2013-04-29 | 28.45

If there are now performance constraint I always prefere a readable solution over a compact one. So I would go with the following: (assuming $prices is sorted and there are no gaps in the months)

<?
date_default_timezone_set('Europe/Berlin');

//Put the data into a assoc array. If necessary I would maybe create a separate
//method to create this input or put it also to extractMonthlyFinalPrice()
$prices=array();
$prices['2013-01-29']='25.69';
$prices['2013-02-28']='27.62';
$prices['2013-03-02']='13.53';
$prices['2013-03-07']='16.53';
$prices['2013-03-30']='26.53';
$prices['2013-03-30']='26.53';
$prices['2013-04-29']='28.45';

$monthlyFinalPrice=extractMonthlyFinalPrice($prices);
/*
array(4) {
  ["2013-01"]=> string(5) "25.69"
  ["2013-02"]=> string(5) "27.62"
  ["2013-03"]=> string(5) "26.53"
  ["2013-04"]=> string(5) "28.45"
}
*/

$monthlyReturns=calculateMonthlyReturn($monthlyFinalPrice,new DateTime("2013-02"));
/*
array(3) {
  ["2013-02"]=>  float(1.93)  //with '2013-01' as start
  ["2013-03"]=>  float(-1.09)
  ["2013-04"]=>  float(1.92)
*/

function extractMonthlyFinalPrice($prices)
{
    $monthlyPrice=array();
    foreach ($prices as $date=>$price)
    {
        $month=substr($date,0,7);
        $monthlyPrice[$month]=$price; // just overwrite existing value and use the last
    }
    return $monthlyPrice;
}

//Be careful with timestamps. Think about using DateTime.
function calculateMonthlyReturn($monthlyFinalPrice, DateTime $startDate=null, DateTime $endDate=null)
{
    if ($endDate==null) $endDate=new DateTime();
    $monthlyReturns=array();
    $lastMonthPrice=null;
    foreach ($monthlyFinalPrice as $month=>$price)
    {
        $date=new DateTime($month);
        $inRange = $date>=$startDate && $date <=$endDate;
        if ($lastMonthPrice!=null && $inRange)
        {
            $monthlyReturns[$month]=$price-$lastMonthPrice;
        }
            //assuming that there are no gaps in the list.
            //Otherwise some date magic is required.
        $lastMonthPrice=$price;
    }
    return $monthlyReturns;
}

As you see, there is no much "logic" left. I get rid of a bunch of ifs and could split the bigger problem in two smaller own. Now you could write tests independently.


SQL Insert Performance I am using a DataTable and the MySqlAdapater to insert around 100 000 rows with around 40 columns to a MySQL database.

I chose this way, because my program needs run on mono (unix / mac) where I could not establish a connection to my database via the System.Data.Sql package, but only via the .NET connector Mysql.Data.MySqlClient which has no SqlBulkCopy-method.

Additionally the amount of columns in my table is flexible, so I was looking for an easy way to iterate the columns. Thats why I used the way:

Parsing my data
Loading it into a DataTable Object
Create a MySQL table dynamically based on my DataTable Object
Use a MySqlDataAdapter to bulk insert the DataTable to the Database via its .Update()-method

Right now, it takes around 3-4 minutes to insert 100 000 rows this way - which is subjectively slow (mac mini 2012, i7, 512 GB SSD, 16 GB ram)

Is there any way to speed this up with the Mysql.Data.MySqlClient ?

public static void Import(DataTable dt, string tableName, string conString)
        {
            using (MySqlConnection con = new MySqlConnection(conString))
            {
                con.Open();

                string createTableString = GetCreateTableSql(dt, tableName);
                MySqlCommand cmd = new MySqlCommand(createTableString, con);
                cmd.ExecuteNonQuery();

                using (MySqlCommand selectcmd = new MySqlCommand("SELECT * FROM " + dt.TableName, con))
                {
                    using (MySqlDataAdapter sda = new MySqlDataAdapter())
                    {
                        MySqlCommandBuilder builder = new MySqlCommandBuilder(sda);
                        sda.SelectCommand = selectcmd;

                        builder.GetUpdateCommand();

                        using (DataTable dttemp = new DataTable())
                        {
                            sda.Fill(dttemp);
                            // prevent duplicating data
                            if (dttemp.Rows.Count == 0)
                            {
                                dttemp.Merge(dt);
                                sda.Update(dttemp);
                            }
                            else
                            {
                                Console.WriteLine("Data already present. Delete manually");
                            }

                        }
                    }
                }
            }
        }

Some quick remarks:

Naming is important. I don't consider dt, conString, con, etc. proper names since they don't tell me enough. There's no need to abbreviate. selectcmd doesn't follow Microsoft's rules about compound words, and dttemp even contains the dreaded "temp".
You haven't encapsulated the MySqlCommand which creates the table in a using.
MySqlCommandBuilder inherits from a class that implements IDisposable, so perhaps that too should be used in a using statement?


Merging two square matrices I would like to optimize a snippet of code, which uses a multiple nested if statements. I am looking for a formula to make it as a combination of multiple arrays logical operations. Please, I need just a hint to start. Can you please help me review the loop and vectorize it?

The I is an input image (any):

I = 5*rand(4,4);
A = rand(4,4);
B = [ 1 0 1 0; 0 0 1 1 ; 0 1 1 0; 0 0 1 1];

result = zeros(4,4);
 for i = 1:4
     for j = 1:4
         if A(i,j) > 0.75
             result(i,j) = 1;
         elseif A(i,j) < 0.25
             result(i,j) = 0;
         else
             if B(i,j) == 1
                 result(i,j) = 1;
             elseif B(i,j) == 0
                 result(i,j) = 0;
             end
         end
     end
 end

 figure,
 subplot(2,1,1), imagesc(A),title('I');
 subplot(2,1,2), imagesc(result),title('result');

You shouldn't use i and j as variables in MATLAB, as they are used to denote the imaginary unit (sqrt(-1)).
In fact, the official MATLAB documentation warns you about it. It's better to use 1i or 1j for the imaginary unit.
The documentation says the performance is better, but that's not really true. The main problem however is that using those variable names
can result in some stange behavior. As i is not undefined, you don't get the usual Undefined function or variable 'x'.

For instance, assume you intended to write i = true, but forgot it. Now, try out:

if i == true
   disp('What happens here?')
end

This should normally result in "What happens here?" being displayed on the screen, but since i = sqrt(-1), which is neither true nor false, you get nothing. You won't get anything for this either:

if i == false
   disp('What happens here?')
end

Similarly, this will result in an infinite loop:

while i < 10
    i = i * 2;
end

So, change i and j to ii and jj (this is common for users on SO at least), or some other variable names.

Now, what about the loops and ifs?

You are right, this should definitely be vectorized. Althoug the performance of loops have been drastically improved after the new exectuion engine
was included, vectorization is still fastest in most cases.

First off, you should know that boolean values can be treated as numeric values. They can be subtracted, added, etc. Furthermore, any non-zero real number is considered to be true, while a zero is considered to be false. Also, if a == true is the same as just if a, and if a == false is the same as just if ~a (~ means not in this case), or if a ~= 0.

If you had only the first part about where result is defined only be the values of A, then this could be done quite simply:

results = (A > 0.75)  % or `results = (A > 0.75)

The part with A < 0.25 is irrelevant there, since those elements are already zero.

x | y means x == true and/or y == true. So, it's enough that one of the conditions are true. If you do x & y, then both x and y must be true.

Since you include the part with B, you must add a term, the above line is not enough. First note that the part with B is only relevant if the two conditions

A < 0.75

and

A > 0.25

are both false. We can disregard the A < 0.75 part, since those elements are already set to 1.

In plain text: The elements in result shall be 1 if either A > 0.75 or A > 0.25 and B == 1. Since the last part has an and in there, we must use &.

So, the loops and ifs can simply be rewritten as:

result = ((A > 0.75) | (A > 0.25 & B))

It's a matter of preference, but you might want to do ... & B == true alternatively ... & B == 1 for clarity. It's common to ignore the true part, but it is a bit clearer to include it.

Example:

A =

   0.568800   0.162200   0.165600   0.689200
   0.469400   0.794300   0.602000   0.748200
   0.011900   0.311200   0.263000   0.450500
   0.337100   0.528500   0.654100   0.083800

B =
   1   0   1   0
   0   0   1   1
   0   1   1   0
   0   0   1   1

res =
   1   0   0   0
   0   1   1   1
   0   1   1   0
   0   0   1   0


Handling access to database connection both inside and outside of classes Is this an OK way to handle access to database connection both inside and outside of classes?

I used to include a PHP file -- database.detl.php -- at the very top of my index.php file containing the following code:

try{
    $dbh_options = array(/*...*/);
    $dbh = new PDO('mysql:host=localhost;dbname='.db_name.';charset=utf8',db_user,db_user_pw,$dbh_options);
} catch(PDOException $e) {
    /*...*/
}

Now every document that got included by index.php could use $dbh to access my database. This made it quite easy to work with.

But despite including that file before any classes got loaded, this $dbh-variable was not available from inside the classes. This was not possible to do:

class KD_sql {
    public static function get_recipes(){
        $qry = $dbh->query('SELECT * FROM recipes');
        $get = $qry->fetchAll();
        return $get;
    }
}

new KD_sql();

$recipes = sql_query::get_recipes();

This resulted in a fatal error: Call to a member function query() on a non-object....

So I guess no variables outside of a class is ever available inside unless you somehow send it there as an additional parameter to the method.

Anyway:

This is how I rewrote the code in order to still be able to have the $dbh-variable available throughout the entire site - just like before, and also have the connection available inside my KD_sql-class - without creating the connection in multiple locations:

First I changed database.detl.php into this:

try{
    $_SITE_DATABASE_details = function(){  //  <  added a function that holds the connection details
        $dbh_options = array(/*...*/);
        $dbh = new PDO('mysql:host=localhost;dbname='.db_name.';charset=utf8',db_user,db_user_pw,$dbh_options);
        return $dbh;  //  <  return connection details
    };
    new KD_db($_SITE_DATABASE_details);  //  the details is sent to a new class
    $dbh = KD_db::con();  //  <  a method, in this new class, returns the connection in order to still have $dbh available
} catch(PDOException $e) {
    /*...*/
}

This might seem a bit wierd, but let me finish.
Here's the new KD_db-class:

class KD_db {
    protected static $con = null;
#   initiate and stores the connection to the $con-variable
    public function __construct(callable $db_details){
        if (self::$con===null){
            self::$con = call_user_func($db_details);
        }
    }
//
#   the method that returns the database connection.
    public static function con(){
        return self::$con;
    }
//
}

This class is basically just a parent class that other classes can extend to in order to have the database connection available as well.

Here is the rewritten KD_sql-class:

class KD_sql extends KD_db {
    public static function get_recipes(){
        $qry = self::$con->query('SELECT * FROM recipes');  //  uses the $con -variable from parent class
        $get = $qry->fetchAll();
        return $get;
    }
}

I can now easily create quick-queries inside my KD_sql-class and just do this:

$recipes = KD_sql::get_recipes();

which quickly returns an array of all the recipes. Or, if that doesn't cut it, I can write a more complex SQL query like this:

$recipes = $dbh->prepare('
    SELECT r.columns,
        ot.columns
    FROM recipes r
        JOIN other_table ot ON r.fk_other_table_pk = ot.id
    WHERE r.some_column = :value
');

But I do have some "bugs" with the returned resultset from the class. If I only use fetch(), instead of fetchAll(), I can't do a while()-loop like this:

$recipes = KD_sql::get_recipes();
while($recipes){
    echo $recipes['id'].' '.$recipes['name'].'<br>';
}

Nothing happens, beside it looks like the loop is never ending or something. That's why I'm using fetchAll() for now. Then uses foreach() because that works.

But besides that. I would really appreciate som feedback on my way of doing this. I'm not that good with classes, oop and such. So if I'm breaking any golden rules or something - please let me know.

Use the global keyword to make globals accessible from inside of methods and functions:

class KD_sql
{
    public static function get_recipes()
    {
        global $dbh; // *** ADD THIS ***

        $qry = $dbh->query('SELECT * FROM recipes');
        $get = $qry->fetchAll();
        return $get;
    }
}

http://www.php.net/manual/en/language.variables.scope.php

Should you use globals for this?  That is another topic completely.


View Model Constructor Arguments I have created a ViewModel for a Product Edit page because it has specific related entities I need to load - the class currently looks like this:

public class ProductEditView
{
    public ProductEditView(Product product)
    {
        this.ID = product.ID;
        this.Code = product.Code;
        this.ProductLanguage = product.ProductLanguages.Where(x => x.LanguageID == Global.Language).FirstOrDefault();
        this.PrimaProduct = product.PrimaProduct;
        this.Multimedias = product.Multimedias;
    }

    public int ID { get; set; }
    public string Code { get; set; }
    public ProductLanguage ProductLanguage { get; set; }
    public PrimaProduct PrimaProduct { get; set; }
    public IEnumerable<Multimedia> Multimedias { get; set; }

}

So then in my controller I can go:

public ActionResult Edit(int? id)
{
    if (id == null) return new HttpStatusCodeResult(HttpStatusCode.BadRequest);

    Product product = db.Products.Find(id);
    if (product == null) return HttpNotFound();

    ProductEditView productEditView = new ProductEditView(product);
    return View(productEditView);
}

I've not really seen anybody do it like this though, is it bad practice - and for what reason? What are the better alternatives to accomplish this if this is wrong?

Its a very tight coupling between HTTP and your domain.
However I do not like classic layered architecture. I often utilizes CQS for my service API's

Your example would look like

public class GetProductQueryHandler: IQueryHandler<GetProductQuery, Product>
{
   private readonly DbContext db;

   public GetProductQueryHandler(DbContext db) {
      this.db = db;
   }
   public async Task<Product> Handle(GetProductQuerycommand query) {
      if (!query.Id.HasValue) throw new ArgumentExpection("Id is required"); //Not accepting null for a Nullable is a bit strange

      var product = await db.Products.FindAsync(id);
      if (product == null) throw new NotFoundExcpetion("Product");

      return product;
   }
}

You can then translate the errors into HTTP codes using a Exception filter, here is an example from my current project

    public class ExceptionFilter : ExceptionFilterAttribute
    {
        public override void OnException(HttpActionExecutedContext actionExecutedContext)
        {
            base.OnException(actionExecutedContext);

            var message = "Server error";
            var details = "Please contact support if the problem persists";

            var code = HttpStatusCode.InternalServerError;

            if(actionExecutedContext.Exception is ArgumentException)
            {
                code = HttpStatusCode.BadRequest;
                message = "Bad Arguments";
                details = actionExecutedContext.Exception.Message;
            }

#if DEBUG
    details =   string.Format("{0}: {1}", actionExecutedContext.Exception.Message, actionExecutedContext.Exception.StackTrace);
#endif

            var response = new
            {
                Message = message,
                Details = details
            };

            actionExecutedContext.Response = actionExecutedContext.Request.CreateResponse(code, response);
        }
    }


Filtering a long list of files through a set of ignore patterns using iterators I have a backup job that walks across a huge directory with potentially millions of files. Python's os.walk() works just fine.

Now, I have implemented a feature to ignore files based in a black list of patterns. I just want it to behave like a .gitignore file.

Currently I do this:

import os
from fnmatch import fnmatch

some_dir = '/'
ignore_list = ['*.tmp', 'tmp/', '*.py']
for dirname, _, filenames in os.walk(some_dir):
    for filename in filenames:
        should_ignore = False
        for pattern in ignore_list:
            if fnmatch(filename, pattern):
                should_ignore = True
        if should_ignore:
            print 'Ignore', filename
            continue

It works, but I failed to write it in terms of iterators.

Can this routine be written in terms of python iterators? Can it be improved in terms of iterators or generators?

You can simplify the loop by using a generator expression like this:

for filename in filenames:
    if any(fnmatch(filename, pattern) for pattern in ignore_list):
        print 'Ignore', filename
        continue


Promise-based fixed delay poller with timeout I have the following functions for polling some function periodically with a timeout

export function promiseTimeout(ms: number): Promise<NodeJS.Timer> {
  return new Promise<NodeJS.Timer>((resolve) => {
    return setTimeout(resolve, ms);
  });
}

export function poll(predicate: () => boolean, delayMS: number, timeoutMS: number): Promise<void | NodeJS.Timer> {
  const fixedDelayPoller: Promise<void> = new Promise<void>(async (): Promise<void> => {
    while (!predicate()) {
      await promiseTimeout(delayMS);
    }
  });
  return Promise.race([promiseTimeout(timeoutMS), fixedDelayPoller]);
}

I'm new to Typescript and Promises so I'm curious if there is a more idiomatic or flexible way for this to be written.  For example, should there be parameters for a callback to be called after the timeout?  Or would that be handled by the caller calling poll(x, y, z).then(onFulfilled)?  Further, should this function return a boolean rather than a possible void, false in the case of timeout and true otherwise?

Polling is not good.

I'm curious if there is a more idiomatic or flexible way for this to be written.

Generally polling for a state change is not considered best practice so there is no idiomatic approch.
The code

async functions are a promise you don't need to put them inside a promise, you are just doubling up.

 const fixedDelayPoller = new Promise(async () => {
     while (!predicate()) {
         await promiseTimeout(delayMS);
     }
 });

Then the same as with one less promise to negotiate.
 const fixedDelayPoller = (async () => {
     while (!predicate()) {
         await promiseTimeout(delayMS);
      }
 })(); // invoke async function

It seams that JS coders are still getting used to promises as they never name the callbacks. You name the callback resolve but that is inferred and does not describe what the function does

  return new Promise((resolve) => {
    return setTimeout(resolve, ms);
  });

would be better as
  return new Promise(timeup => setTimeout(timeup, ms))

You are creating way too many promises. When you look at the problem you only need one promise that resolves on timeout or predicate() is true. As your code stands you create 5 promises (Promise.race counts as a promise) minimum and then an extra one for each delay timeout.
A better approch is to have the poll function return only one promise. You can then resolve it without the need to create a string of promises one after another.

function poll(predicate, delayMS, timeoutMS){
    var intervalHandle;
    return new Promise(pollingOver => {
        const complete = () => {
            clearInterval(intervalHandle);
            pollingOver();
        }
        intervalHandle = setInterval(() => predicate() && complete(), delayMS);
        setTimeout(complete, timeoutMS);
    });
}

function poll(predicate, delayMS, timeoutMS){
    var intervalHandle;
    return new Promise(pollingOver => {
        const complete = (ready = false) => {
            clearInterval(intervalHandle);
            pollingOver(ready);
        }
        intervalHandle = setInterval(() => predicate() && complete(true), delayMS);
        setTimeout(complete, timeoutMS);
    });
}

// Poll waits fot state to === true or two seconds
test();
var state;
function test() {
    state = false;
    var timer = setTimeout(()=>state = true, Math.random() * 4000)
    poll(() => state, 200, 2000).then(inTime => {
        console.log(inTime ? "State in time" : "State change timed out");
        clearTimeout(timer);
        test();
    });
}

Back to your questions

I'm curious if there is a more idiomatic or flexible way for this to be written. For example, should there be parameters for a callback to be called after the timeout? Or would that be handled by the caller calling poll(x, y, z).then(onFulfilled)? Further, should this function return a boolean rather than a possible void, false in the case of timeout and true otherwise?

If you did need some event to happen on resolution then using poll(...).then( is the better approch.
Should your function return a bool? that is up to you. The predicate has access to the state so it can be used to workout the current state. However it is better to return a result via the promise callback (see snippet above, returns false on timeout)
Why are you polling?
I am having trouble understanding why you need to poll some state. There are many other ways to communicate state changes in JavaScript (TypeScript) without the need for code to run at regular intervals. But without some context it is hard to say which approch would be best.


ASP.NET MVC using an N-Tier Model and DDD Any comments are welcome. However I'd like to call specific attention to my... interpretation of the N-Tier application architecture and how I'm consuming data. Note that the namespacing and inline comments have been factored out for brevity.

The Data Tier (DataModel.csproj)

// Base class for EF4 Entities
public abstract class EntityBase {
    public int Id { get; set; }
}

// Entities
public class Account : EntityBase {
    public string UserName { get; set; }
    public string Password { get; set; }
    public byte[] Salt { get; set; }
    public string EmailAddress { get; set; }
}

public class Entry : EntityBase {
    public string Title { get; set; }
    public DateTime Created { get; set; }
    public Account Owner { get; set; }
}

// EF4 Code-First Data Context
public class DataContext : DbContext {
    public DbSet<Account> Accounts { get; set; }
    public DbSet<Entry> Entries { get; set; }
}

// Repository Pattern
public interface IRepository<TEntity>
    where TEntity : EntityBase {
    TEntity Create();
    void Delete(TEntity entity);
    TEntity Get(int id);
    TEntity Get(Expression<TEntity,bool>> where);
    void Insert(TEntity entity);
    void Save();
    IQueryable<TEntity> Where(Expression<TEntity,bool>> where);
}

public class Repository<T> : IRepository<T>
    where T : EntityBase, new() {
    private readonly DataContext context;
    private readonly DbSet<T> set;

    public Repostory(DataContext context) {
        // context injected via ioc.
        this.context = context;
        this.set = this.context.Set<T>();
    }

    // Implementation of IRepository<T>
}

Business Logic Tier (Runtime.csproj)

// IOC Container
public static class IOC {
    public static readonly IWindsorContainer Container = new WindsorContainer();

    static IOC() {
        InstallAssembly("Presentation");
        InstallAssembly("Runtime");
        InstallAssembly("DataModel");
    }

    public static void InstallAssembly(string name) {
        Container.Install(FromAssembly.Named(name));
    }
}

// Also includes System.Configuration ConfigSections, HttpModules and Provider classes
// which are strongly tied to IRepository<>.

Presentation Layer (Mvc App) (Presentation.csproj)

protected void Application_Start() {
    AreaRegistration.RegisterAllAreas();
    FilterConfig.RegisterGlobalFilters(GlobalFilters.Filters);
    RouteConfig.RegisterRoutes(RouteTable.Routes);
    // Controller Factory instance makes initial reference to IOC class, causing
    // the installers to run.
    ControllerBuilder.Current.SetControllerFactory(new Runtime.Mvc.WindsorControllerFactory());
}

// Data-Driven Controller
public class DashboardController : SecureController {
    private readonly IRepository<Entry> entries;

    public DashboardController(IRepository<Entry> entries) {
        // entries injected via ioc.
        this.entries = entries;
    }

    [ChildActionOnly, HttpGet]
    public ActionResult RecentEntries() {
        var viewModel = new RecentEntriesViewModel( entries.Where( stuffHappens ) );
        return PartialView(viewModel);
    }
}

I feel like letting IRepository<> reach the presentation layer may be a violation of the pattern. Exposition of an IQueryable<> through IRepository<>.Where seems like a bad idea at the Presentation level. There's no way to moderate the use of IQueryable and could lead to brittle code. Inputs?

I agree that exposing IRepository<> to the presentation layer is bad.

The reason it's bad is that your Business Logic Tier (BLT) might want to enforce business-y rules on the access of data. That's what the business layer is for, after all.

Your heart is in the right place when you restrict use of the repository to .Where in the presentation layer. However, you still have that entries field exposed for another programmer to come along and abuse later. To prevent this from happening, you could expose only an Expression in the presentation layer. Pass that Expression to the BLT, which would then instantiate the IRepository<> and use the Expression. That would also provide a hook for the BLT to add additional conditions to the Expression for access control, etc.


Hashing 2 strings to an int and adding to HashMap I am trying to use an algorithm similar to the Apriori algorithm for discovering frequent itemsets. This program hashes 2 strings to an int and maps them in the HashMap. I'm not concerned with how good the hashing algorithm is but whether or not it is a good attempt at my own implementation of counting frequent item sets using the Triples counting method.

package hashTest;
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map;
public class TriplesCount {
public static void main(String[] args)
{
    String testSentence = "Facebook is looking good. Facebook is looking horrible.";

    Map<Integer, Integer> triplesCount = new HashMap<Integer, Integer>();

      String stripPunctuation = testSentence.replaceAll("\\.", "");
      //out.println(stripPunctuation);

      String[] wordArray = stripPunctuation.split(" ");
    List<String> wordList = new ArrayList<String>();
      for(int a=0; a<wordArray.length; a++)
          wordList.add(wordArray[a]);

      //Lists of "good" and "bad" words. If a word in testSentence matches one of these, it will be added to the
      List<String> goodWords = new ArrayList<String>();
      List<String> badWords = new ArrayList<String>();

      goodWords.add("good");goodWords.add("increase");goodWords.add("excellent");goodWords.add("partnering");goodWords.add("bullish");goodWords.add("better");
      badWords.add("bad");badWords.add("problem");badWords.add("drop");badWords.add("bearish");badWords.add("worse");badWords.add("horrible");

      for(int i=0; i<wordList.size(); i++)
      {
          System.out.println("Checking: " + wordList.get(i));

          for(int i2=0; i2< goodWords.size(); i2++)
          {
              if(goodWords.get(i2).equals(wordList.get(i)))
                  triplesCount = addToMap("facebook", goodWords.get(i2), triplesCount);

              if(badWords.get(i2).equals(wordList.get(i)))
                  triplesCount = addToMap("facebook", badWords.get(i2), triplesCount);

              System.out.println(triplesCount);
          }

      }

}

  public static Map<Integer,Integer> addToMap(String stock, String adjective, Map<Integer,Integer> triplesCount)
  {
      int hash=11;
      String key = (stock+":"+adjective).toLowerCase();
      char[] charsArray = key.toCharArray();
      for(int a=0; a<charsArray.length; a++)
          hash = hash*31 + a-charsArray[a]; //multiplies 2 prime #s and adds an int value for the character

      //now have to set the stock + adjective string to the index of hash, and set the value to the count of how many times that combo has occurred
      if(triplesCount.get(hash) == null)
          triplesCount.put(hash, 1);
      else
          triplesCount.put(hash, triplesCount.get(hash)+1);
      return triplesCount;
  }
}

The indentation looks a little a bit off, but it might be the case that the code did not paste from your editor properly, so I will omit this topic.
There are two methods in your code, and each of them does a lot of different things. It's not a good practice. One method should do one thing.
Let's take a look at the addToMap method. It computes the hash and then puts it's to the map. I would recommend to factor out a separate method for hash computation. You can also make the code more concise by using the getOrDefault method (to avoid the if statement at the end of the method. It applies only if you're using Java 8).
The main method is even bigger. Firstly, it does some input preprocessing (removing punctuation marks, splitting and so on). This part is definitely a candidate for its own method. Iterating over a list with an index-based loop is less readable (and, for some types of lists (not the case for ArrayList), is much slower than a Collection-based for): you could just write something like: for (String currentWord : wordList) ....
You may also consider making logging more flexible and separating it from the code that performs computations (print statements in the main method look quite arbitrary).
It is conventional to surround all binary operators with whitespaces.
It's not common to have more than one statement per line as it makes the code less readable: goodWords.add("good");goodWords.add("increase");goodWords.add("excellent");... doesn't look good, does it?
It's better to store "magic" constants (like 11 and 31 in your code) in final variables with meaningful names to minimize confusion(int hash=11; looks sort of arbitrary to me. What does 11 mean? int hash = INITIAL_HASH_VALUE or something like this is easier to understand).


Storing hierarchical data into a data structure With the following data in a table,

+----+-----------+-----------+---------+
| id | name      | parent_id | prev_id |
+----+-----------+-----------+---------+
| 1  | Section 1 | NULL      | NULL    |
| 2  | Item 1.1  | 1         | NULL    |
| 3  | Item 1.2  | 1         | 2       |
| 4  | Item 1.3  | 1         | 3       |
| 5  | Section 2 | NULL      | 1       |
| 6  | Item 2.1  | 5         | NULL    |
| 7  | Item 2.2  | 5         | 6       |
| 8  | Item 2.3  | 5         | 7       |
| 9  | Item 1.4  | 1         | 4       |
+----+-----------+-----------+---------+

I have created this data structure:

[
    1: stdClass Object (
        [id] => 1
        [name] => Section 1
        [parent_id] => NULL
        [prev_id] => NULL
        [children] => [
            2: stdClass Object ([id] => 2, [name] => Item 1.1, [parent_id] => 1, [prev_id] => NULL)
            3: stdClass Object ([id] => 3, [name] => Item 1.2, [parent_id] => 1, [prev_id] => 2)
            4: stdClass Object (...)
            9: stdClass Object (...)
        ]
    ),
    5: stdClass Object (
        [id] => 5
        [name] => Section 2
        [parent_id] => NULL
        [prev_id] => 1
        [children] => [
            6: stdClass Object (...)
            7: stdClass Object (...)
            8: stdClass Object (...)
        ]
    )
]

Here is the working code that I wrote:

function build_tree(array $rows)
{
    $accum = array();

    $rec = function ($parentId = null, $prevId = null) use (&$rec, &$accum, $rows) {
        foreach ($rows as $row) {
            if ($row->parent_id == $parentId && $row->prev_id == $prevId) {
                // add child
                if ($row->parent_id) {
                    if (!isset($accum[$row->parent_id]->children)) {
                        $accum[$row->parent_id]->children = array();
                    }
                    $accum[$row->parent_id]->children[$row->id] = $row;
                // add root
                } else {
                    $accum[$row->id] = $row;
                }
                // find children
                $rec($row->id);
                // find next root
                $rec($row->parent_id, $row->id);
            }
        }
    };
    $rec();

    return $accum;
}

// SELECT * FROM table ORDER BY parent_id, prev_id
$rows = $itemDAO->getItems();
$items = build_tree($rows);

I am terrible at recursion, so any suggestions on how to improve the code would be helpful.

There are actually a couple of issues with that approach, so we will step through them one by one.

Let's start with with revising what a tree is. A tree is coherent, undirected graph with a single root node and no loops.

Let's compare that with your sample data (and the implementation based on it):

There are no loops - Check
There is exactly one root node - No, there are two. And the graph isn't coherent either.

So what you have in your database isn't a tree to start with.

Add a new node which is the only root to your graph, and attach all of the previously created root nodes to this new node. This makes it much easier to work with the data.

Now let's have a look at your code. There are a couple of oddities which strike immediately:

Using == for comparisons

You got to be careful with with == in PHP, it's not typesafe. What this specifically means for you, in your case, it that 0 == NULL is actually true, while the typesafe === operator correctly yields false.

This is an important difference for you, since you are using NULL as a special value, but there might also exist an entry with the perfectly valid numerical ID 0.

Having an $accum variable

This is a direct consequence of not having a single root node. Half of your code revolves around deciding whether a node you visited is a root node or not. Specify a root node explicitly prior to entering the recursion, and this problem is void.

Scanning the result set multiple times instead of indexing it

You don't actually need to iterate over the result set over and over again to find the rows you want. Index it once, and you are good to go:

index = []
foreach(rows as row) {
    index[row->id] = row
}

That's one of the benefits of PHP, you have always a hashmap at hand when you need one ;)

Supporting only a single level of nesting

Let's see what happens if we add another generation of children. $items suddenly lists the child with grandchildren as another regular root.

Ups, that did not go as expected, did it?

Not using the return statement in a recursion

This points out that you have a rather weird understanding of recursion. When you do a recursion, your goal is always to to break the problem down into smaller problems, and to return a partial solution.

In this case, respectively for a tree in general, your goal is always to completely construct a single sub-tree, starting at the current node, prior to passing the current tree back to the parent context.

So in short, for traversing a tree, the recursion function looks something like (pseudo code):

TreeObject build_tree(id, index) {
    tree = new TreeObject(index[id]);
    foreach(index as node) {
        if(node->parent == id) {
            tree->children[] = build_tree(node->id, rows);
        }
    }
    return tree;
}

Notice a difference? There is nothing modified by reference. In a recursion, there is no global state, each single recursion step only reads the data.

A strange way to sort children

There is nothing wrong with wanting to define an order on children of a node, but make sure you are aware what it actually means. It's still a tree, so the same construction applies. But in addition, you want to be able to sort the children of a node. Or even better, already have them sorted, e.g. in a linked list.

A linked list just what you constructed with prev_id, except that you got it linked backwards, not forwards. If you really want to use this structure (I will cover alternatives later), do yourself a favor and use next_id instead. This at allows to traverse the list of children in a more natural way.

Furthermore, if you want to be able to use the linked list half way efficient, make sure that you always store an entry point to the linked list. This means in addition to next_id, also store a first_child on the parent node.

Let's just extend the code sample for better comprehension:

TreeObject build_tree(id, index) {
    tree = new TreeObject(index[id]);

    next_child = tree->first_child;
    while(next_child_id != NULL) {
        tree->children[] = build_tree(next_child, index);
        next_child = index[next_child]->next;
    }
    return tree;
}

Still rather comprehensible, isn't it? Unfortunately, the drawback of using next and first_child references is that updating the database just got slightly more complicated.

It's generally better to just use a index which can be sorted by. So best drop next_id and first_child again, and instead just add an sort_index field which contains a unique number for each entry. You can then just fetch the rows in the correct order from the database, and the previous algorithm already yields the children in the correct order.

(Bonus round: Ensure that sort_index is not only ascending for all children of a single node, but also when traversing the tree in pre-order. Now the previous algorithm can be modified to traverse the result set from the database only a single time, treating it as a queue which only supports the pop and peek functions. If you got that working, congratulations. Your algorithm has just reached O(n) runtime.)

Reinventing the wheel. While it is possible to fix the flaws in the design to get the recursion working properly, storing a tree with a fixed order in a database is actually a standard problem. A problem to which much better solutions than explicitly storing parent-child relations are known.

Before we go ahead, ask yourself a question: Given that the database actually contains a much larger tree, and you only want to fetch a sub-tree starting at a given node, how would you do that?

Right, you couldn't, at least not without modifying the algorithm slightly. You would always have to fetch the whole table content.

There is actually a model which provides that, and also gives the sort order of children for free: Nested set model

Have a read for yourself, knowing how these structures work can never hurt.


Bank account balance data structure design and code I'm working on designing a bank account data structure and related operations (1. debit, 2. credit and 3. get balance difference).

Debit means withdraw some money from an account, at a certain timestamp
Credit means deposit some money to an account, at a certain timestamp
Get balance means getting the account balance difference between time A and time B (balance of time B - balance of time A).

Suppose the start balance of the account is zero. Assume transactions happen in a timely order.

My major ideas are:

Use a hash table to maintain account ID - list of balance. List of balance is represented by a list of tuple, and each tuple has two elements (time_stamp and balance)
With debit and credit, create a new balance item in a balance list data structure mentioned above
When calculating the balance difference, try to use binary search to find lower bound of time stamp, then get the balance at that timestamp

Example:

Suppose for a specific account, at time 10, credit 10 USD, at time 20, credit 100 USD, and at time 30 withdraw 20 USD, and at time 40, withdraw 50 USD, and at time 50, credit 20 USD. Then at time 25, balance is 10+100=110, at time 45, balance is 10+100-20-50 = 40, so balance diff between 25 to 45 is 40-110=-70.

Any advice on using the right data structure/algorithm for better performance in terms of algorithm time complexity perspective, any code bugs or code style advice is highly appreciated.

from collections import defaultdict
def debit(account, time_stamp, amount, balance_map):
    if len(balance_map[account]) > 0:
        balance_map[account].append((time_stamp, balance_map[account][-1][1]-amount))
    else:
        balance_map[account].append((time_stamp, -amount))
def credit(account, time_stamp, amount, balance_map):
    if len(balance_map[account]) > 0:
        balance_map[account].append((time_stamp, balance_map[account][-1][1]+amount))
    else:
        balance_map[account].append((time_stamp, amount))
def get_balance_diff(account, exclusive_start_timestamp, inclusive_end_timestamp, balance_map):
    start_balance = (0,0)
    end_balance = (0,0)
    matched = False
    if len(balance_map[account]) != 0:
        i = find_lower_bound(balance_map[account], exclusive_start_timestamp)
        if i != -1:
            start_balance = balance_map[account][i]
    if len(balance_map[account]) != 0:
        j = find_lower_bound(balance_map[account], inclusive_end_timestamp)
        if j != -1:
            end_balance = balance_map[account][j]

    return end_balance[1] - start_balance[1]

def find_lower_bound(nums, target):
    i = 0
    j = len(nums) - 1
    while i <= j:
        mid = i + (j-i)/2
        if nums[mid][0] == target:
            return mid
        elif nums[mid][0] > target:
            j = mid - 1
        else:
            i = mid + 1
    return i-1

if __name__ == "__main__":
    balance_map = defaultdict(list)
    account_id = 1
    credit(account_id, 10, 10, balance_map)
    credit(account_id, 20, 100, balance_map)
    debit(account_id, 30, 20, balance_map)
    debit(account_id, 40, 50, balance_map)
    credit(account_id, 50, 20, balance_map)
    print get_balance_diff(account_id, 25, 45, balance_map)
    print get_balance_diff(account_id, 30, 50, balance_map)
    print get_balance_diff(account_id, 0, 5, balance_map)
    print get_balance_diff(account_id, 0, 60, balance_map)

I think using dictionaries is about right for this small project.

However, the code will not scale well in terms of readability with lists of tuples. You should consider using object oriented approach, and implement some serialization, deserialization methods (for storing the data onto the disk and reading it back). That way you can add more functionalities in a more manageable way.

I don't understand why you allow negative balance!