Packet process time simulation using queue Here is my code for the below packet time simulation problem using queue. My code works correctly but it's slow, please help with suggestions to improve run time and other suggestions for performance improvement.

Problem: You are given a series of incoming packets in an array of [t_a, t_d] pairs (one pair for each packet) where t_a is arrival time of the packet and t_d is the processing time required for that packet. The processor has a buffer with a fixed size and when full, packets are dropped. For each packet, output either the start of process time or -1 if the packet is dropped. Processor only processes one packet at the time and packet arrival times are non-decreasing.

eg. input of [ [0, 2], [1, 4], [5, 3] ] with buffer size of 2 gives output equal to [0, 2, 6].

def process_packets(packets, buffSize):
    # base case for packet size or buffSize == 0
    if packets == [] or buffSize == 0:
        return []
    # initializing parameters:
    # ts_te is array of [ts,te] pairs where ts = start of packet process time
    # and te = end of packet process time
    # length of ts_te array is treated as buffer size
    ts_te = [  [ packets[0][0], packets[0][0] + packets[0][1] ]  ]
    # results is either start of packet process time (if packet makes it to buffer)
    # or -1 for packets when buffer is full at their arrival time
    results = [ ts_te[0][0] ]

    # since first packet is processed in initialization, I remove it
    packets = packets[1:]

    for packet in packets:
        packetArr = packet[0]
        packetDur = packet[1]
        # processor's start time is either end of last packet in buffer or
        # new packet's arrival time, whichever is bigger
        startTime = max ( ts_te[-1][1], packetArr )

        # removing all packets that have been processed from buffer when new
        # packet arrives
        for elem in ts_te:
            if packetArr >= elem[1]:
                ts_te.pop(0)

        # if there is room in the buffer, add new packets [ts,te] information
        # and append process time start to result
        if len(ts_te) < buffSize:
            ts_te.append( [startTime , startTime+packetDur] )
            results.append(startTime)
        else:
            results.append(-1)

    return results

Efficiency

Your algorithm is actually quite simple and efficient.  Keeping track of the scheduled finish times for each packet in the buffer (using ts_te) is a great idea.  The main problem is your poor choice of data structure for ts_te.

Actually, even though ts_te stores the scheduled start and end times for each buffered packet, you never care about the start times.  So, you can just store the end times.  (Incidentally, if you had to store a pair of immutable elements, you should use a tuple rather than a list.  A list implies that the length may vary or that the contents may change.)

You have a performance problem in ts_te.pop(0).  Removing the first item in a list requires all the subsequent elements to be copied over to fill in the hole.  What you want is a data structure that lets you efficiently remove items from the head and append items at the tail.  Such a structure is called a deque (a double-ended queue), and it's in Python's standard library:

  Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

  Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

Futhermore, if you specify a maxlen when creating the collections.deque, then it acts as a ring buffer, which is often how fixed-size buffers are implemented in real-life systems.

On a related note, I recommend creating results to be the same size as packets, since you know exactly how long it is supposed to be.  That would be more efficient than repeatedly calling .append() and letting Python resize the list as necessary.  (Each resizing operation can be expensive, possibly involving the copying of the entire existing contents.)  Alternatively, if you don't need the results to be a list, simply yield the results instead of building a list.

Style

Follow PEP 8 naming conventions.  buffSize and startTime don't comply.

Avoid introducing special cases.  I don't think that buffSize == 0 should result in an empty list; rather, the results should all be -1, since every packet would have to be dropped.  Furthermore, your algorithm should be designed so that it does not rely on the buffer always being non-empty.

To avoid writing this:

for packet in packets:
    packetArr = packet[0]
    packetDur = packet[1]

… use destructuring assignments:

for packetArr, packetDur in packets:

As a rule, it's more elegant to write if failure_condition: (e.g detecting a dropped packet) rather than if success_condition:.  Usually, failure cases have short code to handle them, and there may be multiple failure cases to handle.

Suggested solution

from collections import deque

def process_packets(packets, bufsize):
    # Stores the scheduled finish times for packets
    buffer = deque(maxlen=bufsize)

    start_times = [None] * len(packets)
    for i, (arrival, duration) in enumerate(packets):
        # Remove packets from the buffer that have been processed by the
        # arrival time.
        while buffer and buffer[0] <= arrival:
            buffer.popleft()

        if len(buffer) >= bufsize:
            # Buffer overrun
            start_times[i] = -1
        else:
            # This packet will start being processed after the finish time of
            # the last buffered packet (if there is anything in the buffer).
            start_times[i] = max(arrival, buffer[-1] if buffer else 0)

            # Store the scheduled finish time for this packet.
            buffer.append(start_times[i] + duration)
    return start_times


Looping through an Array of objects to find an ID in a sub array I have an Array of objects, each which contain their own sub Tags Array, and I need to loop through and find a matching id.

Array: [
    Object {
        tags: [
            { tag_id: 1 },
            { tag_id: 2 }
        ]
        name: name_1
    },
    Object {
        tags: [
            { tag_id: 3 },
            { tag_id: 4 },
            { tag_id: 5 }
        ]
        name: name_2
    }
]

I have a click action when sends in 1 tag from the page to compare and I need to check it's ID to the id of all tags in the larger array.

This is what I have so far which works, but is there a cleaner, simpler more efficient way to do this? With a hashtable perhaps? If so, how?

// I get the large stored Array to compare too:
var tagObjects = TagFactory.retrieveTags();
var index = -1;
var temp_tags = [];

// tagObj is the single tag that is sent from the markup to check:
// Below is what I'm trying to find in the larger array:
console.log(tagObj.tag_id);

// Checking if the large Array has anything
if (tagObjects.length > 0) {

    // I go through and separate the smaller tag Arrays out:
    for (var i = 0; i < tagObjects.length; i++) {
        temp_tags.push(tagObjects[i].tags);
    }

    // Finally I try to find the ID inside of the temp_tags Array:
    for (var i = 0; i < temp_tags[0].length; i++) {
        if (tagObj.tag_id === temp_tags[0][i].tag_id) {
            console.log('found id YEAH!');
            index = 1;
        }
    }
}

// If I found the ID, it means I can remove the tag
if (index !== -1) {
    tagObj.selected = false;
    TagFactory.removeTags(tagObj);
}

// If I did not find the ID, it means I can add it
// Add tag:
else {

I cannot say about AngularJS, but in normal JavaScript I would do something like this:

var tagObjects = TagFactory.retrieveTags();

if (findTag(tagObjects, tagObj.tag_id)) {
    // remove tag
}
else {
    // add tag
}

function findTag(tagObjects, tag_id) {
    return tagObjects
        .reduce(function (total, obj) { return total.concat(obj.tags); }, [])
        .find(function (tag) { return tag.tag_id === tag_id; })
    ;
}

Note that find is a part of upcoming es6 standard. So you might need to use es6-shims (like I do) or write your own version. It's very easy.

Or, if TagFactory.retrieveTags() returns some special structure — shouldn't it also provide findTag method?


Yet another FizzBuzz in Haskell Time for the most original question of the year: writing a FizzBuzz in Haskell!

So here is what I came up with:

fizzBuzz :: [Int] -> [String]
fizzBuzz xs =
    [fizz x | x <- xs]

fizz :: Int -> String
fizz x
    | mod x 15 == 0  = "FizzBuzz"
    | mod x 3 == 0   = "Fizz"
    | mod x 5 == 0   = "Buzz"
    | otherwise      = show x

Then I can call

> mapM_ print $ fizzBuzz [1..15]
"1"
"2"
"Fizz"
"4"
"Buzz"
etc

My questions are:

What are obvious awkwardnesses in this code?
How could I mix fizzBuzz and fizz so that there's only one function?
In fizz, is it possible to use a string buffer so that I get rid of the mod x 15 == 0 guard, taking advantage of its redundancy with mod 3 x == 0 and mod 5 x == 0?

[fizz x | x <- xs] is the same as map fizz xs, so fizzBuzz = map fizz.

You can use putStrLn instead of print to print strings without quotes.

Using the fact that map (g . f) = map g . map f,  you can merge mapM_ putStrLn and map fizz into:

mapM_ (putStrLn . fizz) [1..15]

Another solution with everything in single function and without mod x 15:

import Control.Monad (forM_, when)

fizzBuzz :: IO ()
fizzBuzz = forM_ [1..15] $ \x -> do
  let [m3, m5] = map ((==0) . mod x) [3,5]
  when m3 $ putStr "Fizz"
  when m5 $ putStr "Buzz"
  when (not m3 && not m5) $ putStr $ show x
  putStrLn ""


Restrictive stupid shell I'm attempting to create a replacement shell for /bin/bash, that only permits commands defined by a read only config file. These commands will be run by absolute paths, and take no arguments. I'm not an experienced C programmer, so I kindly ask for your comments and feedback. I'm especially concerned with buffer overflows etc. Please note that the "re read" config file is by design, if the rules change I would like the sessions already running to adhere to these changes.

#include <stdio.h> /* fopen et al */
#include <string.h> /* strcmp, strlen */
#include <unistd.h> /* access */
#include <stdlib.h> /* system */
#define RULEFILE "/home/ole/wannabeshell/rules.conf"
#define PROMPT "$ "
#define BUFFER 512

// not really a shell - just executes commands
// thats given in the config file by absolute
// paths..

int main (int argc, char **argv) {
    // buffer size + 1 for \0 ending
    char sbuffer[BUFFER + 1], fbuffer[BUFFER + 1];

    // open the rulefile
    FILE *fh = fopen(RULEFILE, "r");

    // give up if unable to open it
    if (fh == NULL) {
        perror("unable to open rulefile");
        return(EXIT_FAILURE);
    }

    while (1) {
        // print prompt character
        printf(PROMPT);

        // force flush
        fflush(NULL);

        // make sure buffers does not contain data
        // from previous runs of the loop
        memset(sbuffer, 0, sizeof(sbuffer));
        memset(fbuffer, 0, sizeof(fbuffer));

        // read up to sizeof buffer, or \n
        if (fgets(sbuffer, sizeof(sbuffer), stdin) == NULL) {
            break;
        }

        // check for data up to NULL, must be atleast one !NULL
        // char for this test to be successful
        if (strlen(sbuffer) < 1) {
            break;
        }

        // find and replace \r and \n if exists
        sbuffer[strcspn(sbuffer, "\r\n")] = 0;

        // time to exit?
        if (strcmp(sbuffer, "exit") == 0 || strcmp(sbuffer, "quit") == 0) {
            break;
        }

        // seek to start of rulefile
        fseek(fh, 0, SEEK_SET);

        // read one line from rule file
        while (fgets(fbuffer, sizeof(fbuffer), fh) != NULL) {
            // strip \n and \r from line
            fbuffer[strcspn(fbuffer, "\r\n")] = 0;

            // if requested command equals rulefile line
            if (strlen(fbuffer) == strlen(sbuffer) && strcmp(fbuffer, sbuffer) == 0) {

                // make sure the command e.g. file exists
                // and is actually executable
                if (access(fbuffer, X_OK) == 0) {
                    // fork and execute fbuffer with /bin/sh -c
                    // system blocks till finished
                    system(fbuffer);
                    break;
                } else {
                    // not executable or does not exist
                    break;
                }
            }
        }
    }

    // close the rulefile
    fclose(fh);

    // indicate success
    return(0);
}

An initial attempt to overflow by perl -e 'print "\0"x50000;' did not reveal anything apparent. I've also tested that it runs as it should.

Example run

[ole@playground ~]$ ./strictshell
$ foo
$ \0
$ bar
$ /usr/bin/uptime
 15:14:44 up 157 days,  1:04, 23 users,  load average: 0.13, 0.15, 0.10
$ exit

Security

It's not safe to execute commands using system.
Try to use one of the execv functions instead (see man execv for the flavors that exist in your system).

Although you wrote that only absolute paths can be executed,
there's nothing in this code to ensure that.
If a malicious user gains access to the rule file,
they can enter a relative path,
and your program will be happy to execute that.
To make this safer using system,
the program should ensure that the paths are absolute paths.

The bottom line is, don't use system, use execv.
The big difference is that the execv commands don't use the shell,
but invoke the specified executables directly,
which frees you from potential vulnerabilities of shells,
such as environment variable command injection, and who knows what else.

Efficiency

After every validated user input,
the program re-reads the rules file.
It would be better to read and parse the rules file once at the start into an array,
and reuse it in the infinite loop of handling user input.

Simplify

This can be written simpler:

if (access(fbuffer, X_OK) == 0) {
    // ...
    // system blocks till finished
    system(fbuffer);
    break;
} else {
    // not executable or does not exist
    break;
}

Since both branches of the if-else will break,
you can move the break outside,
and simply drop the else:

if (access(fbuffer, X_OK) == 0) {
    // ...
    // system blocks till finished
    system(fbuffer);
}
// not executable or does not exist
break;


Sum of multiples of 3 or 5 below 1000 in Scala I'm in the process of learning Scala, and started working through a series of coding puzzles that I've done previously in other languages.

For example, this solution, coded in Erlang:

sum_multiples(Max, Max, Acc) -> io:format("The sum of all the multiples of 3 or 5 below ~p: ~p~n", [Max, Acc]);
sum_multiples(Current, Max, Acc) when (Current rem 3 == 0) or (Current rem 5 == 0) -> sum_multiples(Current + 1, Max, Current + Acc);
sum_multiples(Current, Max, Acc) -> sum_multiples(Current + 1, Max, Acc).

Now, doing this same problem in Scala, I wrote this:

val max = 1000
println(s"The sum of all the multiples of 3 or 5 below ${max}: " + sum_multiples_recursive(1, max, 0))
def sum_multiples_recursive(current: Int, max: Int, acc: Int): Int = {
  if(current < max){
    if(current % 3 == 0 || current % 5 == 0){
      sum_multiples_recursive(current + 1, max, current + acc)
    } else {
      sum_multiples_recursive(current + 1, max, acc)
    }
  } else {
    acc
  }
}

I'd like to see what an experienced Scala coder might write, what Scala idioms might come into play.

In the Scala solution as in the Erlang solution, the accumulator is pointless.  For max = 1000, you don't necessarily have to be concerned about tail recursion, and you could just write it without an accumulator:

def sumMultiplesRecursive(from: Int, to: Int): Int = {
    if (from >= to) {
        0
    } else if (from % 3 == 0 || from % 5 == 0) {
        from + sumMultiplesRecursive(from + 1, to)
    } else {
        sumMultiplesRecursive(from + 1, to)
    }
}

Note that the sum_multiple_recursive name, with underscores, does not follow the Scala naming convention.  It is not so helpful to mention that it works recursively, but it would also be useful to describe what you mean by "multiples".

The from and to parameters, together, could constitute a Range.  If you are going to use a Range, then you might as well take advantage of its capabilities:

def sumMultiplesOf3Or5(range: Range): Int = {
    range.filter(n => n % 3 == 0 || n % 5 == 0).sum
}

val max = 1000;
println(s"The sum of all the multiples of 3 or 5 below ${max}: " + sumMultiplesOf3Or5(1 until max));


Batch renames file's extension in a given directory with Python Arguments:

The directory in which you would like to change file extensions
Old file extension
And what the new extension should be

Example:
$ touch /tmp/spam.eggs
$ python change-ext.py /tmp .eggs .spam
$ ls /tmp
$ spam.spam

My Concerns.

Is the code easy to read and comprehend?
Is the code Pythonic?
Does the code have any BUGS?
Should i have used argparse instead of sys.argv

'''
Batch renames file's extension in a given directory
'''

import os
import sys
from os.path import join
from os.path import splitext

def main():
    try:
        work_dir, old_ext, new_ext = sys.argv[1:]
    except ValueError:
        sys.exit("Usage: {} directory old-ext new-ext".format(__file__))

    for filename in os.listdir(work_dir):
        if old_ext == splitext(filename)[1]:
            newfile = filename.replace(old_ext, new_ext)
            os.rename(join(work_dir, filename), join(work_dir, newfile))

if __name__ == '__main__':
    main()

Questions

  Is the code easy to read and comprehend?

Import both join and splitext on the same line, and it'll be perfect.

  Is the code Pythonic?

Yes... But is it good?

It's doesn't follow *nix too much. And sys.exit is just wrong.
When using sys.exit you pass an error status, not a message.
The status should be a number from 0-127, where 0 is successful.
And all the other numbers are an error of sorts.

Also you can set up your terminal to change colour or add words if you get an error response. So when sys.exit(1) is called my prompt goes from green to red.

  Does the code have any BUGS?

Yes:

>>> '.txt_file.txt'.replace('.txt', '.spam')
'.spam_file.spam'

  Should i have used argparse instead of sys.argv

I'd say no, as this is a very small script.
Otherwise, I'd say yes.
If you need flags and such you should use argparse, even if the program is very small. So if you think about adding a --verbose flag, you should.

Code review

As noted above, your usage for sys.exit is wrong.

To amend this, I would change your sys.exit to a standard raise.
And then catch it, print the message, and exit with status 1.

class InputError(Exception):pass

def main():
    ...
    except ValueError:
        raise InputError("Usage: {} directory old-ext new-ext".format(__file__))
    ...

if __name__ == '__main__':
    try:
        main()
    except InputError as e:
        print(str(e))
        sys.exit(1)

To amend the bug, I would use a completely different approach.
A more *nix and Python approach.

*nix encourages regex's, and Python has str.format, but you can use the both of them!
They are both micro-languages but regex's are for pattern matching where Python's format is for output formatting.
I would argue having two dedicated micro-languages, is far better than anything we manually program.

import sys
import re
import os
from os.path import join

class InputError(Exception):pass

def main():
    try:
        work_dir, regex, format_ = sys.argv[1:]
    except ValueError:
        raise InputError("Usage: {} directory regex format".format(__file__))

    regex = re.compile(regex)

    for filename in os.listdir(work_dir):
        if regex.match(filename) is not None:
            newfile = format_.format(*regex.findall(filename)[0])
            os.rename(join(work_dir, filename), join(work_dir, newfile))
            print('Replaced {} with {}'.format(filename, newfile))

if __name__ == '__main__':
    try:
        main()
    except InputError as e:
        print(str(e))
        sys.exit(1)

This is as complex as your previous code. However you can now do things like:

$ mkdir temp
$ touch temp/txt.boo
$ python change.py temp "(.*)\.(txt|boo)" ".{1}_file.{0}"
Replaced txt.boo with .boo_file.txt
$ ls temp
.boo_file.txt
$ python change.py temp "(.*)\.(txt|boo)" ".{1}_file.{0}"
Replaced .boo_file.txt with .txt_file..boo_file
$ ls temp
.txt_file..boo_file
$ python change.py temp
Usage: change.py directory regex format
err$

As I was asked

  Wouldn't the fnmatch module be better suited for matching a pattern in a filename then a regular expression.

I thought I should make a pro's and con's for each method:

Regex

Pros

Well know micro-language
Allows an extremely large amount of customisation to the query
Easy to implement

Cons

Larger input

glob / fnmatch

Pros

Simple input
Easy to implement

Cons

No capture groups
Good luck with substitution '{0[:-4]}.boo'.format('hello.txt')
Some inputs are impossible to have reliable output. *file*

glob based regex

So as the main fallback is that you can't have capture-groups in glob,
you can add them.
E.g:

re.compile(fnmatch.translate().replace(r'\(', '(').replace(r'\)', ')'))

Pros

Easy for people who don't know regex
Smaller input, but not as small is glob

Cons

Hard to implement well, without becoming regex where .* is substituted with *.

inp = '\(*\).txt' # Matches r'\\(.*\\)\.txt'.
fnmatch.translate(inp).replace(r'\(', '(').replace(r'\)', ')'))

However if we were to use re.sub.

inp = '(*).txt' # Matches r'(.*).txtZ'
re.sub(r'\\(.)', lambda m: m.group(1), fnmatch.translate(inp))

inp = r'(*)\.txt' # Might as well be regex.
re.sub(r'\\(.)', lambda m: m.group(1), fnmatch.translate(inp + '\\'))

And then there is the edge-case for '[a-z]*'.
As the docs say:

  For a literal match, wrap the meta-characters in brackets. For example, '[?]' matches the character '?'.

But that make '[a-z][*]' turn into '[a-z][*]' not '[a-z]*'.

Conclusion

I chose re as more people know it.
You can extract information out of it with ease.
And is super easy to implement.

If you wanted to use glob & regex, you might as well use regex.

And glob is kinda broken:

>>> '{0[:-4]}.boo'.format('hello.txt')
TypeError: string indices must be integers
>>> '{0[-4]}.boo'.format('hello.txt')
TypeError: string indices must be integers


Project Euler 22: Assigns scores for names that are imported from text file Project Euler 22

  Using atext file containing over five-thousand first names, and you
  will calculate a score for each name. Begin by reading the names from
  the file and sorting them in alphabetical order. Then, you will
  compute an alphabetical value for each name where A is 1, B is 2, C is
  3 and so on. The alphabetical value of a name is just the sum of the
  values of the letters in the name. To compute the name-score for a
  name, you simply multiply this alphabetical value by its position in
  the sorted list.

  For example, when the list is sorted into alphabetical order, COLIN,
  which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the
  list.

So, the name-score for COLIN would be 938 * 53 = 49714.
What is the sum total of all the name-scores in the file?

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

public class ScoringNames {
    BufferedReader x = null;
    String location = "C:\\Users\\xxxxxxxi\\Dropbox\\"
                    + "College\\COSC 1430\\Scoring Names\\names.txt";

    ArrayList<String> names = new ArrayList<String>();
    static ArrayList<Integer> scores = new ArrayList<Integer>();
    static int ns[];

    public void fillNS(){
        for (int x = 0; x < ns.length; x++){
            ns[x] = scores.get(x) * (x+1);
        }
    }

    public void printNS(){
        for (int x = 0; x < ns.length; x++)
            System.out.print(ns[x] + ", ");
    }

    public void readFile(){ //Opens file, and prints every line.
        try{
            x = new BufferedReader(new FileReader(location));
        } catch(FileNotFoundException e) {
            e.printStackTrace();
        }

        try{
            String name = x.readLine();
            while(name != null){
                //System.out.println(name);
                names.add(name);
                name = x.readLine();
            }
        } catch(IOException e) {
            e.printStackTrace();
        }
    }

    public void sortNames(){ //Sort names array in alphabetical order
        Collections.sort(names);
    }

    public void printNames(){
        for(String counter: names)
            System.out.println(counter);
    }

    public int alphValue(char x){
        return (x - 'A' + 1);
    }

    public void returnSize(){
        System.out.println(names.size());
    }

    public int nameScore(String name){
        int score = 0;
        char[] tempName = name.toCharArray();
        for (char i : tempName){
                score += alphValue(i);
            }

        return score;
    }

    public void addScores(){
        for(String x : names){
            scores.add(nameScore(x));
        }
    }

    public void printScores(){
        for(int counter: scores)
            System.out.println(counter);
    }

    public int totalNS(int[] x){
        int sum = 0;
        for(int i = 0; i < x.length; i++){
            sum += x[i];
        }
        return sum;
    }

    public static void main(String[] args) {
        ScoringNames abc = new ScoringNames();
        abc.readFile();
        abc.sortNames();
        //abc.printNames();
        abc.addScores();
        //abc.printScores();
        ns = new int[scores.size()];
        abc.fillNS();
        //abc.printNS();
        //System.out.println(ns[937]); //"COLIN"
        System.out.println("The sum total of all name scores is: " +
                            abc.totalNS(ns));
    }

}

Reading the file: you declare the BufferedReader as an instance variable while it is only used locally. Don't do that: variables should always have the smallest scope possible. In addition, resources should normally be closed in the same scope that opens them (which brings me to the point that you never close the buffered reader.)

Furthermore, you put the opening and reading in two different try-catch constructs. That makes no sense. If the first fails, you cannot expect the second to work.

Thus, using "classic" code, you should put it together as a try-with-resources block, which automatically closes the opened resource, something like this:

try (BufferedReader reader = new BufferedReader(new FileReader(location))) {
    String name;
    while((name = reader.readLine()) != null) { // classic construct ;-)
        names.add(name);
    }
}
catch(IOException e) {
    // Do something useful. Especially, do NOT continue program
    // execution, as you don't have any data anyway!
}

But as this is 2017 and the library is quite mature, you should really simply use java.nio.Files:

Files.readAllLines(Paths.get(location))

is all you need.

There are quite a few more problems in your code (especially the mixup of static and instance variables), but alas my time is limited right now.


Determine which range a character falls into I am categorizing terms depending on what letter the term starts with.  What is the cleanest way to do so?

var parentGroup,
    startsWith = "H"; // Just simplifying and giving a static example here.

switch(startsWith) {
    case "A":
    case "B":
    case "C":
    case "D":
    case "E":
    case "F":
        parentGroup = "A-F";
        break;
    case "G":
    case "H":
    case "I":
    case "J":
    case "K":
    case "L":
    case "M":
        parentGroup = "G-M";
        break;
    case "N":
    case "O":
    case "P":
    case "Q":
    case "R":
        parentGroup = "N-R";
        break;
    case "S":
    case "T":
    case "U":
    case "V":
    case "W":
    case "X":
    case "Y":
    case "Z":
        parentGroup = "S-Z";
        break;
    default:
        parentGroup = "0-9";
}

Those "parent groups" look a lot like regular expressions, specifically character sets.  You could perform regular expression matches for patterns like ^[A-F].

function parentGroup(char) {
    var groups = ['A-F', 'G-M', 'N-R', 'S-Z', '0-9'];
    for (var i = 0; i < groups.length; i++) {
        if (char.match('^[' + groups[i] + ']')) {
            return groups[i];
        }
    }
}

document.getElementById('in').addEventListener('keyup', function(e) {
    document.getElementById('out').textContent = parentGroup(e.target.value);
});

Enter text, starting with a digit or uppercase letter: <input id="in" type="text" size="10">

Parent group:


List implementation in C I tried to implement a Python-esque list in C. Having not really used C in anger, I'd like some pointers on style and error handling in particular.

Header

#ifndef __TYPE_LIST_H__
#define __TYPE_LIST_H__

/*  Generic list implementation for holding a set of pointers to a type
    (has to be consistently handled by the element_match and element_delete
    functions)
*/

typedef struct list_s list_t;

#include <stdbool.h>
#include <stdint.h>

extern const uint16_t default_capacity;

list_t* list_create(
    uint16_t    initial_capacity,
    bool        (*element_match )(const void* a, const void* b),
    void        (*element_delete)(void* element));

void list_delete(list_t* list);

bool    list_append(list_t* list, void* element);
void*   list_pop(list_t* list);
bool    list_remove(list_t* list, void* element);
int16_t list_index(list_t* list, void* element);
bool    list_contains(list_t* list, void* element);
bool    list_empty(list_t* list);

#endif

Source

#include <type/list.h>
#include <stdio.h>
#include <stdlib.h>

const uint16_t default_capacity = 256;

struct list_s
{
    uint16_t length;
    uint16_t capacity;
    void**   elements;
    bool     (*element_match )(const void* a, const void* b);
    void     (*element_delete)(void* element);
};

list_t* list_create(
    uint16_t    initial_capacity,
    bool        (*element_match )(const void* a, const void* b),
    void        (*element_delete)(void* element))
{
    list_t* list = (list_t*) malloc(sizeof(list_t));
    if (!list) return NULL;

    if (!initial_capacity) {
        initial_capacity = default_capacity;
    }

    list->elements = (void**) malloc(sizeof(void*) * initial_capacity);
    if (!list->elements) return NULL;

    list->length         = 0;
    list->capacity       = initial_capacity;
    list->element_match  = element_match;
    list->element_delete = element_delete;

    return list;
}

void list_delete(list_t* list)
{
    if (!list) return;

    if (list->element_delete) {
        unsigned i;
        for (i = 0; i< list->length; i++) {
            list->element_delete(list->elements[i]);
        }
    }
    else {
        fprintf(stderr, "WARNING: no element_delete specified");
    }
    free(list);
}

bool list_append(list_t* list, void* element)
{
    if (!list || !element)
        return false;
    if (list->length >= list->capacity) {
        // expand the elements array
        list->capacity *= 2;
        list->elements = realloc(list->elements, sizeof(void*) * list->capacity);
        if (!list->elements) {
            return false;
        }
    }
    list->length += 1;
    list->elements[list->length] = element;
    return true;
}

void* list_pop(list_t* list)
{
    if (!list || list_empty(list)) {
        return NULL;
    }
    void* element = list->elements[list->length];
    list->elements[list->length] = NULL;
    list->length -= 1;
    return element;
}

bool list_remove(list_t* list, void* element)
{
    if (!list || !list->element_match) {
        return false;
    }
    unsigned i;
    bool found = false;
    for (i = 0; i < list->length; i++) {
        if (!found && list->element_match(list->elements[i], element)) {
            found = true;
            list->length -= 1;
        }
        if (found) {
            // shift all subsequent elements back one
            list->elements[i] = list->elements[i + 1];
        }
    }
    return found;
}

int16_t list_index(list_t* list, void* element)
{
    int16_t i;
    for (i = 0; i < list->length; i++) {
        if (list->element_match(list->elements[i], element)) {
            return i;
        }
    }
    return -1;
}

bool list_contains(list_t* list, void* element) {
    return (list_index(list, element) != -1);
}

bool list_empty(list_t* list)
{
    return (list->length == 0);
}

Surprising name

default_capacity is in the public .h file

In a header for list_this and list_that, finding default_capacity is not good and a name-space collision headache.  Suggest list_default_capacity instead.

0 allocation

Be careful about allocating 0 memory (possible with default_capacity == 0 and list_create(0, ...)).  Receiving NULL in that case does not certainly indicate an out-of-memory condition.

// list->elements = (void**) malloc(sizeof(void*) * initial_capacity);
// if (!list->elements) return NULL;

list->elements = malloc(sizeof list->elements[0] * initial_capacity);
if (list->elements == NULL && initial_capacity == 0) {
  return NULL;
}

default_capacity not needed

With generic list code, I'd expect the ability to create a 0 length list and not have 0 indicate "use a default value".


Adding 2 linked lists The problem I have is to find the sum of 2 linked lists. Each linked list node contains 1 digit that represents a number.

My algorithm works but I was wondering if there is a more efficient (speed and memory wise) to solve this problem OR maybe some minor tweaks I can do to reduce space and runtime.

Example: 7 -> 5 -> 6 = 756

I am trying to find the sum of 2 linked lists.

def addlist(LL1, LL2):
    storage = []
    multiplier = 1
    total = 0
    while LL1 != None:
        storage.append(LL1.data)
        LL1 = LL1.next
    for i in storage[::-1]:
        total += i*multiplier
        multiplier *= 10
    storage = []
    multiplier = 1
    while LL2 != None:
        storage.append(LL2.data)
        LL2 = LL2.next
    for j in storage[::-1]:
        total += j*multiplier
        multiplier *= 10
    return total

Don't repeat yourself

Your method has the same code duplicated twice in it. You should always try to eliminate this kind of duplication, for example like this:

def addlists(LL1, LL2):
    return sumlist(LL1) + sumlist(LL2)

def sumlist(LL1):
    storage = []
    multiplier = 1
    total = 0
    while LL1 != None:
        storage.append(LL1.data)
        LL1 = LL1.next
    for i in storage[::-1]:
        total += i*multiplier
        multiplier *= 10
    return total

Simplify

The logic can be simplified, a lot:

def sumlist(ll):
    total = 0
    while ll:
        total *= 10
        total += ll.data
        ll = ll.next
    return total

I also simplified the None comparison, instead of if ll != None you can write simply if ll

Naming

The convention is to use lowercase variable names, so it would be better to change LL1 and LL2.


Refactor or simple code RoR I have a GiftCard class where I have method can_deliver? and deliver! that I think can be refactored to better looking code :

  def can_deliver?
    (self.sent_at.nil? && self.scheduled_at.nil?) || (self.sent_at.nil? && self.scheduled_at && self.scheduled_at < Time.now)
  end

  def deliver!
    return unless self.can_deliver?
    begin
      Notifier.gift_card_code_mail(self).deliver
      self.sent_at = Time.now
      self.save
    rescue Exception
      logger.error "Could not send email gift card ##{self.id}"
      self.line_item.order.comments.create!(:content => "Can not send gift card mail")
    end

    begin
      Notifier.gift_card_delivered(self).deliver
    rescue Exception
      logger.error "Could not send deliver confirmation email gift card #{self.id}"
      self.line_item.order.comments.create!(:content => "Can not send confirmation delivery of gift card")
    end

  end

Some notes:

self: You write self.attribute to access attributes. I won't say that's bad practice, not at all, mainly because it's easier to see if you're accessing local variables or instance methods. However, in Ruby it's idiomatic not to use self in this case.
variable.nil?: this is something we often see but 99% of the time is unnecessary verbose. You want to know if a variable is not set? write !variable. The only case a explicit nil? is needed is when you want to tell false from nil, not the case here.
Layout: Don't write long lines, 80/100 is a sound limit. It usually pays off in form of clarity also: in can_deliver? for example, if you break on the || operator the boolean expression is much more clear.
Early returns: return unless self.can_deliver?. Again, I won't say that's bad, in a language that has no syntax for guards (like other languages have), it's a handy way to do early returns when pre-conditions are not met. As a rule of thumb, however, I'd recommend to write a full conditional. Yeah, I know, it's more verbose and you get an extra indentation level, but on the other hand the layout of the function/method helps understanding what the method it's doing.
The cool thing about the way you wrote can_deliver? (using an expression instead of a bunch of imperative returns) is that you can apply boolean algebra. Notice here than (!p && !q) || (!p && q && q < t) -> !p && (!q || q < t). Of course this kind of simplifications must only be done when the resulting expression is at least as declarative as the original (we are not trying to save some NAND gates here). If you read it out loud and it makes sense then it's ok.
You have two (and probably more throughout the code) almost identical begin/rescue blocks. That's a call for abstraction (it this case an abstraction using block wrappers).
Don't write rescue Exception, that's a common pitfall. Check this SO question.
Shouldn't deliver! return something? how would the caller know if it was successful? you should always return something, either a value (a boolean seems fit in this case) or, yes, return nil but raise an exception on error. Personally I like to return values and leave exceptions for really exceptional things (like, I don't know, the hard disk exploded).

Applying all these points, and with a declarative approach in mind, I'd write:

class GiftCard
  def can_deliver?
    !sent_at && (!scheduled_at || scheduled_at < Time.now)
  end

  def deliver!
    can_deliver? && send_card_code_email && send_gift_card_email
  end

private

  def comment_on_exception(msg)
    yield
  rescue => exc
    logger.error(msg)
    line_item.order.comments.create!(:content => msg)
    false
  end

  def send_card_code_email
    comment_on_exception("Could not send email gift card #{id}") do
      Notifier.gift_card_code_mail(self).deliver
      update_attribute(:sent_at, Time.now)
    end
  end

  def send_gift_card_email
    comment_on_exception("Could not send deliver confirmation email gift card") do
      Notifier.gift_card_delivered(self).deliver
    end
  end
end

If you found some of these advices useful, take a look at the RubyIdioms page I maintain (and its RubyFunctionalProgramming companion). Comments most welcome.


Implementation of std::map I have decided to make a basic C++ implementation of the std::map class, and I was checking that it is fine, as I am not sure if the operator[] is done correctly: should I be using the has_key function? e.t.c

template < typename _Key, typename _Ty, typename _Cmp = std::less<_Key>, typename _Alloc = std::allocator< std::pair<const _Key, _Ty> > > class map
{
public:
    typedef map<_Key, _Ty, _Cmp, _Alloc> _Myt;
    typedef _Key key_type;
    typedef _Ty mapped_type;
    typedef _Cmp compare_type;
    typedef _Alloc allocator_type;
    typedef std::pair<const key_type, mapped_type> value_type;
    typedef value_type *pointer;
    typedef const value_type *const_pointer;
    typedef value_type *iterator;
    typedef const value_type *const_iterator;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;

    map()
        : size_(0), capacity_(20), data_(_Alloc().allocate(20))
    {
    }

    map(const _Myt &_Rhs)
        : size_(_Rhs.size_), capacity_(_Rhs.size_ + 20), data_(_Alloc().allocate(_Rhs.size_))
    {
        int count = 0;
        for (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count)
        {
            _Alloc().construct(&data_[count], *i);
        }
    }

    ~map()
    {
        if (!empty())
        {
            for (iterator i = begin(); i != end(); ++i)
            {
                _Alloc().destroy(i);
            }
            _Alloc().deallocate(data_, capacity_);
        }
    }

    _Myt &insert(const value_type &_Value)
    {
        if (++size_ >= capacity_)
        {
            reserve(capacity_ * 2);
        }
        _Alloc().construct(&data_[size_ - 1], _Value);
        return *this;
    }

    bool has_key(const key_type &_Key)
    {
        for (iterator i = begin(); i != end(); ++i)
        {
            if (i->first == _Key)
            {
                return true;
            }
        }
        return false;
    }

    mapped_type &operator[](const key_type &_Key)
    {
        if (has_key(_Key))
        {
            for (iterator i = begin(); i != end(); ++i)
            {
                if (i->first == _Key)
                {
                    return i->second;
                }
            }
        }
        size_type op = size_;
        insert(value_type(_Key, mapped_type()));
        return data_[op].second;
    }

    _Myt &reserve(size_type _Capacity)
    {
        int count = 0;
        if (_Capacity < capacity_)
        {
            return *this;
        }
        pointer buf = _Alloc().allocate(_Capacity);
        for (iterator i = begin(); i != end(); ++i, ++count)
        {
            _Alloc().construct(&buf[count], *i);
        }
        std::swap(data_, buf);
        for (iterator i = &buf[0]; i != &buf[size_]; ++i)
        {
            _Alloc().destroy(i);
        }
        _Alloc().deallocate(buf, capacity_);
        capacity_ = _Capacity;
        return *this;
    }

    bool empty()
    {
        return size_ == 0;
    }

    iterator begin()
    {
        return &data_[0];
    }

    iterator end()
    {
        return &data_[size_];
    }
private:
    pointer data_;
    size_type size_, capacity_;
};

Readability

With your lengthy template statement, I'd put the class statement onto the next line:

template </*...*/>
class map

Naming standards

According to this answer, identifiers in the form _Identifier are reserved:

  7.1.3 Reserved identifiers

  Each header declares or defines all identifiers listed in its
  associated subclause, and optionally declares or defines identifiers
  listed in its associated future library directions subclause and
  identifiers which are always reserved either for any use or for use as
  file scope identifiers.

  All identifiers that begin with an underscore and either an uppercase
  letter or another underscore are always reserved for any use.

  [...]

Const-correctness

You have iterators, but you should also have const iterators:

const_iterator cbegin() const
{
    return &data_[0];
}

const_iterator cend() const
{
    return &data_[size_];
}

empty() should be const:

bool empty() const
{
    return size_ == 0;
}

has_key() should be const and use the aforementioned const iterators:

bool has_key(const key_type &_Key) const
{
    for (const_iterator i = cbegin(); i != cend(); ++i)
    {
        if (i->first == _Key)
        {
            return true;
        }
    }
    return false;
}


Awaiting multiple HTTP Requests Scenario : Sending a POST to 2 different endpoints (not related to or dependent on each other).

I'm really just not sure if I went about this correctly, and whether or not the responses will have returned from the context before the method returns. I have read some about async/await and the context for which it operates, etc., but I'm still not sure.

class Program
    {
        static void Main(string[] args)
        {
            Task.Run(async () =>
            {
                await SendRequests(cookie, request1, request2);
            })
            .GetAwaiter()
            .GetResult();

        }

static async Task<List<HttpResponseMessage>> SendRequests(Cookie cookie, HttpRequestMessage punchRequest, HttpRequestMessage request2)
        {
            List<HttpResponseMessage> responseMessages = new List<HttpResponseMessage>();

            CookieContainer cookies = new CookieContainer();
            HttpClientHandler handler = new HttpClientHandler();
            handler.CookieContainer = cookies;
            cookies.Add(cookie);

            using (var httpClient = new HttpClient(handler))
            {
                var response1 = await httpClient.SendAsync(request1);
                var response2 = await httpClient.SendAsync(request2);

                responseMessages.AddRange(new [] { response1 , response2 });

                return responseMessages;
            }
        }

    }

I'm wondering if :

Task.Run( async () => ....) is correct here, as well as GetAwaiter/GetResult
Can the SendRequests method ever return before the requests finish / get resolved?

Task.Run(async () =>
{
    await SendRequests(cookie, request1, request2);
})

is a very long-winded way of writing

SendRequests(cookie, request1, request2)

.GetAwaiter().GetResult() is also a long-winded way of writing .Result, but since you're ignoring the return value it's probably necessary.

  Can the SendRequests method ever return before the requests finish / get resolved?

Of course. Otherwise it would return List<HttpResponseMessage> rather than Task<List<HttpResponseMessage>>. However, assuming that wasn't the question you actually intended to ask...

The doc for SendAsync says

  The returned task object will complete once the entire response including content is read.

Since you await both of the tasks, the responses must finish before the SendRequests task will finish. (Of course, if the first one throws an exception then the second won't even be sent).

It's not clear to me whether the intention was for the requests to be made in parallel. That seems to be implied by

  to 2 different endpoints (not related to or dependent on each other).

In that case you would want to create the tasks and then wait for them both:

var responseTask1 = httpClient.SendAsync(request1);
var responseTask2 = httpClient.SendAsync(request2);
await Task.WhenAll(responseTask1, responseTask2);

responseMessages.AddRange(new [] { responseTask1.Result, responseTask2.Result });

return responseMessages;

Although I have to say that I don't understand the purpose of creating responseMessages in the outer scope.


Quickly check whether file name is in column in an SQL Table and move to new folder I have a table that in one of the columns exists a list of file names.  The names comes from other tables and the files in a folder.

Not all the files are used, may be attached to parcels that no longer are active.  My list is of only the active parcels.

After creating the table I want to go through the folder of files and move the files that are being used(exist in the table) to another folder.

Currently I iterate the files in the folder and test whether each file one at a time returns a record or not using an SQL command.

This works, but the consistent checking back to the database is slow.

Here is the code as it sits now:

param(
    [string] $src,
    [string] $dest,
    [string] $table
    )

$sql_instance_name = 'db'
$db_name = 'DB2'
$sql_user = 'user'
$sql_user_pswd = 'password'

Get-ChildItem -Path $src -Recurse -File | ForEach-Object  {
    $query = "select * from " + $table + " WHERE FILE_NAME Like '" + $_.BaseName + $_.Extension +  "'"
    #write-output $query

    $expcsv = invoke-sqlcmd -Username $sql_user -PASSWORD $sql_user_pswd -Database $db_name -Query $query -serverinstance $sql_instance_name
    if($expcsv -ne $null)

    {
        $nextName = Join-Path -Path $dest ( $_.BaseName  +  $_.EXTENSION)
        Write-Output $nextName
        $_ | Move-Item -Destination   $nextName
    }
}

Is there a way to load the data into memory, and search that instead of going back and forth from the database? I have to assume it would be quicker.

Output from invoke-sqlcmd is Formatted table i.e. something like PSCustomObject[] array (or collection). Hence, one could address its columns as .FILE_NAME properties and apply comparison operators -in, -contains, -match etc. (elaborated from my original comment):

param(
    [string] $src,
    [string] $dest,
    [string] $table
    )

$sql_instance_name = 'db'
$db_name = 'DB2'
$sql_user = 'user'
$sql_user_pswd = 'password'

$query = "select * from $table"
$expcsvS = invoke-sqlcmd -Username $sql_user -PASSWORD $sql_user_pswd `
    -Database $db_name -Query $query -serverinstance $sql_instance_name

Get-ChildItem -Path $src -Recurse -File | ForEach-Object  {

    if ( $_.Name -in  $expcsvS.FILE_NAME )
    {
        $nextName = Join-Path -Path $dest -ChildPath $_.Name
        Write-Output $nextName
        $_ | Move-Item -Destination $nextName
    }
}

Note that I use $_.Name instead of ($_.BaseName + $_.Extension) as for files, the following code snippet always returns True.

(Get-ChildItem -Recurse -File |
    Where-Object { $_.Name -ne ($_.BaseName + $_.Extension) }) -eq $null

Also note that if ( $_.Name -in $expcsvS.FILE_NAME ) {} is equivalent to any of (incomplete list):

if ( $expcsvS.FILE_NAME -match "^$($_.Name)$") {}
if ( $expcsvS.FILE_NAME -contains $_.Name ) {}


Validating the presence of properties in a document How can I reduce cyclomatic complexity of validation and refactor it better way?

Class Document
  def initialize(opts)
    @opts = opts
    return ArgumentError unless valid?
  end

  def valid?
    return false if @opts.nil?
    return false if @opts[:property_1].nil?
    return false if @opts[:property_2].nil?
    return false if !@opts[:property_4].nil? && @opts[:property_3].nil?
    # etc. 12 times more, otherwise valid will return true
    true
  end

  def usage_example
   if @opts[:property_3]
      "#{@opts[:property_3]} #{@opts[:property_1]}"
   else
      "#{@opts[:property_4]} #{@opts[:property_2]}"
   end
  end
end

I am trying to avoid duplication of return false if and somehow perhaps list parameters that I want to verify

Possible interpretation of what I trying to reach is "verify set of rules before processing file"

If your tests are about mandatory members in @opts you can do this:

MandatoryProperties = [:property_1, :property_2, ...]

def valid?
  @opts && MandatoryProperties.all? { |k| !@opts[k].nil? }
end


Thread-Safe Integer Sequence I would like to give an Integer to whatever demands it. For that I use the following code

public class IntIDGenerator {

    private static int sequence = 1;

    public synchronized static int generate(){
        sequence++;
        return sequence;
    }

}

It is thread-safe because the synchronized term in the method generate(), but I have the feeling that it is possible to implement this generation in a better way. I was thinking in AtomicInteger, but I will have, more or less, the same problem. Any hint?

And what's wrong with :

public final class SDGIntIDGenerator {

    private static final AtomicInteger sequence = new AtomicInteger(1);

    private SDGIntIDGenerator() {}

    public static int generate(){
        return sequence.getAndIncrement();
    }

}

Atomic Integer is thread safe.
Put private constructor so no instances can be made.
Only static methods means helper class => make class final.

Edit :

While @bowmore is correct you could want more generators for each class, you could do the following :

public final class SDGIntIDGenerator {

    private static final ConcurrentHashMap<Class,AtomicInteger> mapper = new ConcurrentHashMap<Class,AtomicInteger>();

    private SDGIntIDGenerator () {}

    public static int generateId (Class _class) {
        mapper.putIfAbsent(_class, new AtomicInteger(1));
        return mapper.get(_class).getAndIncrement();
    }
}

With this implementation you could ask an id for each class.
This is because the ConcurrentHashMap is also thread safe for some methods.

Important note : Your generator will reset himself after server restart so usage for generating an id for storing in database is a bad idea.

You could also just return the AtomicInteger.
It doesn't matter if you are using a lot of threads and every thread knows that instance of the AtomicInteger.
The AtomicInteger will stay threadsafe.

Footnote : Wrote in java 6, with higher java you could refactor the instantiation of the ConcurrentHashMap.


Load an OpenGL buffer from file The function's job is to load a vertex attribute buffer or an element buffer from a specified path, and upload it to OpenGL. Also, optionally, return the number of vertices/indices loaded through an output parameter.

Signature:

GLuint loadBufferFromFile(std::string const& bufferPath, unsigned char vertexElementCount, GLenum vertexFormat, GLenum bufferType=GL_ARRAY_BUFFER, GLuint *vertexCount=NULL, GLenum usageHint=GL_STATIC_DRAW);

Body:

GLuint loadBufferFromFile(std::string const& bufferPath, unsigned char vertexElementCount, GLenum vertexFormat, GLenum bufferType, GLuint *vertexCount, GLenum usageHint)
{
    const std::unordered_set<GLenum> VALID_VERTEX_FORMATS = {GL_FLOAT, GL_UNSIGNED_INT, GL_UNSIGNED_BYTE};
    //bufferType and usageHint will be validated by OpenGL

    if(vertexElementCount < 1 || vertexElementCount > 4)
    {
        throw std::invalid_argument("Vertex element count must be in range <1,4>");
    }

    if(bufferType == GL_ELEMENT_ARRAY_BUFFER && vertexElementCount != 1)
    {
        throw std::invalid_argument("Buffer of type GL_ELEMENT_ARRAY_BUFFER must have element count of 1");
    }

    if(VALID_VERTEX_FORMATS.find(vertexFormat) == VALID_VERTEX_FORMATS.end())
    {
        throw std::invalid_argument("Invalid vertex format");
    }

    std::ifstream file;
    file.open(bufferPath, std::ios::binary | std::ios::in);

    if(!file.is_open())
    {
        throw std::runtime_error(std::string("Buffer file ") + bufferPath + " could not be opened");
    }

    file.seekg(0, file.end);
    unsigned int length = file.tellg();
    file.seekg(0, file.beg);

    if(vertexCount != NULL)
    {
        std::size_t vertexSize;

        switch(vertexFormat)
        {
            case GL_FLOAT:
                vertexSize = sizeof(GLfloat);
                break;
            case GL_UNSIGNED_INT:
                vertexSize = sizeof(GLuint);
                break;
            case GL_UNSIGNED_BYTE:
                vertexSize = sizeof(GLubyte);
                break;
        }

        vertexSize *= vertexElementCount;
        *vertexCount = length/vertexSize;
    }

    char *buffer = new char [length];
    file.read(buffer, length);
    file.close();

    GLuint bufferID;
    glGenBuffers(1, &bufferID);

    glBindBuffer(bufferType, bufferID);
    glBufferData(bufferType, length, buffer, usageHint);

    delete[] buffer;
    return bufferID;
}

Specific questions:

Is it appropriate to fine-tune data types when it is not strictly necessary, like I did with vertexElementCount? int would have also worked just fine.
Is this level of error handling/validation appropriate?
Is it good to use a const collection for validation in this way? Are there runtime costs beyond the act of validation itself?
If yes, unordered_set or vector? On one hand, a set seems a logical choice for this, on the other, wisdom of the ancients says "Use vector for everything unless you absolutely can't!"
Are those appropriate exceptions to use?
Even though in this case I can be certain it will not lead to a memory leak (nothing in between new and delete throws exceptions), directly using dynamic allocation rubs me the wrong way. Can I avoid it in a reasonable way?

As for your questions:

Just use int, unless this is critical code where benchmarks have shown that integers are noticeably slower. Furthermore: your char will support 255 vertices which isn't a lot, I've loaded models with millions of vertices.
This level of error checking is possibly an indication that your code smells. You have a function that accepts many parameters, perhaps you can split it into multiple functions or a class type of structure.
Myself, I make everything const unless it cannot be const.
If the size is known at compile time, how about std::array instead of std::vector? As for std::unordered_set it seems too fancy for the job (e.g., a self balancing tree with 3 items, whoop! whoop!), but I have no strong arguments.
No opinion. Myself, I never use C++ exceptions - due to my lack of understanding / education. In other languages I never directly use the build-in Exception types, I always subclass my own - if anything it helps the library user understand if they are library errors or system errors.
You can place your new'ed memory in a std::unique_ptr or use the resize features of std::vector or std::string

Couple more random things:

file.close(); is optional, the std::ifstream will also close the resource (if it was open).
You're not testing for OpenGL related errors.
I don't like 'out' arguments, such as vertexCount. Just return a std::tuple with multiple arguments, or a struct.
Does your file contain binary data? You're reading it from disk, and directly upload it to the GPU without parsing/validation? If anything, make sure you've actually read the amount of bytes that tellg claims are available.
std::ifstream has a constructor, use it.


Reduce the number of code if possible when creating a folder My code below creates a folder based on the passed data from my client-side(VueJs) and checks if there's already an existing folder and deletes it if there is otherwise it will create a new one.

My problem here is that I think my code is too long and unreadable although it accomplishes the task that I want to happen.

Can someone help me to make this code better?

router.post('/album', (req, res) => {
    let sql = "INSERT INTO GALLERY SET ALBUM = ?, DESCRIPTION = ?";
    let body = [req.body.ALBUM, req.body.DESCRIPTION]
    myDB.query(sql, body, (error, results) => {
        if (error) {
            console.log(error);
        } else {
            let directory = `path\\public\\${req.body.ALBUM}`;
            if (fse.existsSync(directory)) {
                fse.removeSync(directory, err => {
                    if (err) {
                        console.log(err);
                    } else {
                        console.log("Success");
                    }
                })
            } else {
                fse.mkdirpSync(directory, err => {
                    if (err) {
                        console.log(object);
                    } else {
                        console.log("Success");
                    }
                })
            }
        }
    })
})

The built in file system package (fs) provides you with a commands to create directories.

fs.mkdirSync(path[, options]) for synchronous

fs.mkdir(path[, options], callback) for asynchronous

According to their documentation, you can add an option for recursively creating a folder. It also notes

"Calling fs.mkdir() when path is a directory that exists results in an error only when recursive is false."

With this information, you should be able to force it to always create the folder using only this logic:

const fs = require('fs')
fs.mkdir( directory, { recursive: true }, (err) => {
  if (err) throw err;
});


MemoryCache as a message broker? I'm in the middle of a project that was built around Microsoft's Message Queue service. During development all of our machines are on a domain and we were able to create a public queue accessible from the server and client.

When moving this to our test server, I discovered that both the test server and production servers are running in workgroup mode, no public queues available.

I'm experimenting with creating a webservice broker backed by a MemoryCache. Here is what I've got so far. Each key is posted into a FIFO queue due to the needs of the project.

Has anyone else done something similar? What about concurrency? Any other gotchas I should be concerned about?

UPDATED: Added suggested changes, and handled differences resulting from use of ConcurrentQueue and Lazy instantiation.

    [WebMethod]
    public bool Push(string key, string value)
    {
        if (String.IsNullOrWhiteSpace(key) || String.IsNullOrWhiteSpace(value)) return false;

        // input validation removed for brevity

        var queue = GetQueue(key);
        queue.Enqueue(value);
        return true;
    }

    [WebMethod]
    public string Pop(string key)
    {
        var queue = GetQueue(key);
        string result = "";
        if (queue.TryDequeue(out result))
        {
            return result;
        }
        return null;
    }

    [WebMethod]
    public List<string> RemoveAll(string key)
    {
        var queue = GetQueue(key);
        var list = queue.ToList();
        queue.Clear();
        return list;
    }

    private ConcurrentQueue<string> GetQueue(string key)
    {
        var cache = MemoryCache.Default;
        var queue = (Lazy<ConcurrentQueue<string>>) (cache.AddOrGetExisting(key.ToLowerInvariant(),new Lazy<ConcurrentQueue<string>>() , new CacheItemPolicy
        {
            AbsoluteExpiration = ObjectCache.InfiniteAbsoluteExpiration,
            SlidingExpiration = TimeSpan.FromMinutes(5)
        }) ?? cache[key.ToLowerInvariant()]);
        return queue.Value;
    }

I also added an extension for the ConcurrentQueue to clear it.

public static class ConcurrentQueueExtensions
{
    public static void Clear<T>(this ConcurrentQueue<T> queue)
    {
        T item;
        while (queue.TryDequeue(out item))
        {
            // do nothing
        }
    }
}

What you have here is, IMHO, excellent.

Couple nitpicks:

I don't get why RemoveAll is returning the original content instead of void - also I'm expecting an exception to be thrown in GetQueue if the specified key doesn't exist.
This part (in the Pop(string) method):

var queue = GetQueue(key);
string result = "";

Would look more consistent if written like this:

var queue = GetQueue(key);
var result = string.Empty;

Or, since it's used as an out parameter value on the next line (and therefore is compiler-enforced to be initialized after the call to TryDequeue(out string)), simply like this:

var queue = GetQueue(key);
string result;

As for the Clear extension method, there's a potential tiny little issue here - see this MSDN thread:

  ConcurrentQueue<T>'s implementation is based on a particular lock-free algorithm that doesn't permit atomically clearing of the collection, hence why no Clear method is exposed.  As such, you have two primary options.

  The first is simply to create a new ConcurrentQueue<T> instead of clearing the original, and then swap in the new for the original.

  The second is to continually remove from the collection until it's empty, e.g. T ignored; while(cq.TryDequeue(out ignored));. Which you choose is largely dependent on the needs of your application.

  The former will be faster, but you also run the risk of losing some items you didn't intend to lose (then again, if the whole point is to empty the collection, that might not matter), and it only works if you have access to all of the variables holding references to the queue.

  The latter is effective, but it runs the risk of running indefinitely if other threads are concurrently appending; it's also more expensive that simply allocating a new queue.


Parsing speech out of text I'm working on an experiment to parse speech out of an emote in a text roleplaying game (MUD) so that if you can't hear it correctly, or if it's in a different language, you won't understand it. This works correctly, but I was just wanting to make sure it was as clear and efficient as possible.

import java.util.Scanner;
import java.util.Random;

public class EmoteParser {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter an emote: ");
        String emote = scanner.nextLine();

        System.out.println("Original emote:\n" + emote);
        System.out.println("\nParsed emote:\n" + jumbleEmoteSpeech(emote));
    }

    public static String jumbleEmoteSpeech(String emote) {
        StringBuilder out = new StringBuilder();
        int quote1Location = emote.indexOf('"');

        if (quote1Location == -1) {
            out.append(emote);
        }
        else {
            int quote2Location;
            int currentIndex = 0;
            boolean found = true;
            do {
                quote2Location = emote.indexOf('"', quote1Location + 1);
                if (quote2Location == -1 || quote2Location < currentIndex) {
                    out.append(emote.substring(currentIndex));
                    found = false;
                }
                else {
                    out.append(emote.substring(currentIndex, quote1Location + 1));
                    out.append(jumble(emote.substring(quote1Location + 1, quote2Location)));
                    currentIndex = quote2Location;

                    quote1Location = emote.indexOf('"', currentIndex + 1);
                }
            } while (found);
        }

        return out.toString();
    }

    public static String jumble(String text) {
        StringBuilder out = new StringBuilder();
        Random generator = new Random();

        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            if (Character.isLetter(ch)) {
                if (Character.isUpperCase(ch)) {
                    out.append((char)('A' + generator.nextInt(26)));
                }
                else {
                    out.append((char)('a' + generator.nextInt(26)));
                }
            }
            else if (Character.isDigit(ch)) {
                out.append((char)('0' + generator.nextInt(10)));
            }
            else {
                out.append(text.charAt(i));
            }
        }

        return out.toString();
    }
}

Also, is there any real benefit to using '"' vs "\""? I think '"' is more readable, and any performance difference is probably optimized out anyway.

The jumble method

In the jumble method, you are looping over the character by having an index going from 0 to the length of the input array.

for (int i = 0; i < text.length(); i++) {
    char ch = text.charAt(i);
    // ...
}

Since you don't use the index apart from retrieve the character, you couls just use toCharArray() and loop directly over the characters:

for (char ch : text.toCharArray()) {
    // ...
}

Then, you are appending characters based on their codepoint. For this, you are doing

out.append((char) ('A' + generator.nextInt(26))); // same for 'a' and '0'

Instead of having this (ugly) cast, you could directly use appendCodePoint with

out.appendCodePoint('A' + generator.nextInt(26));

Additionally, the code path to jumble a character can lead to potential bugs:

if (Character.isLetter(ch)) {
    if (Character.isUpperCase(ch)) {
        // ...
    } else {
        // ...
    }
} else if (Character.isDigit(ch)) {
    // ...
} else {
    // ...
}

The problem is that isLetter returns true for characters that are not only uppercase or lowercase characters. For example, it would return true for all those weird characters classified as "Lo" as per Unicode (and OTHER_LETTER in Java). It would also return true for those classified "Lm" (MODIFIER_LETTER in Java), like "OL CHIKI AHAD" ᱽ. Since I think that, for example, in the case of the Hebrew letter "BET", ב, you don't want to consider it lowercase (which your code would, since it is a letter not uppercase), you can remove that check completely and have:

if (Character.isUpperCase(ch)) {
    sb.appendCodePoint('A' + generator.nextInt(26));
} else if (Character.isLowerCase(ch)) {
    sb.appendCodePoint('a' + generator.nextInt(26));
} else if (Character.isDigit(ch)) {
    sb.appendCodePoint('0' + generator.nextInt(10));
} else {
    sb.append(ch);
}

This way, only character that have case (upper or lower) will be taken into account in those branches. But still, there are a lot of lowercase letters (and uppercase letters) different than a-z, like ῲ or ⅎ or even ⱙ (which is apparently "GLAGOLITIC SMALL LETTER IOTATED BIG YUS"). In those case, they will be replaced by a Latin small character, which may or may not be what you want. If you truly want to jumble only Latin letters, it would be best to test the character against 'a' and 'z' (conversely for uppercase). And you know what? This is not just letters. There are a lot of digits that aren't 0-9, like ٨ (Arabic 8) or ᧗ (New Tai Lue 7) or even ꧓ (which is apparently Javanese 3). Therefore, if you just want to concentrate on Latin letters and Roman digits, you can just use

if (ch >= 'A' && ch <= 'Z') {
    sb.appendCodePoint('A' + generator.nextInt(26));
} else if (ch >= 'a' && ch <= 'z') {
    sb.appendCodePoint('a' + generator.nextInt(26));
} else if (ch >= '0' && ch <= '9') {
    sb.appendCodePoint('0' + generator.nextInt(10));
} else {
    sb.append(ch);
}

The last concern is about the Random object. You are creating one each time this method is executed. It would be preferable to create only one and reuse the same everytime. For example, you can have a constant

private static final Random RANDOM = new Random();

The jumbleEmoteSpeech method

You should always prefer to return early from methods when it is possible. In this case, if there are no quotes in the String, you return it unchanged.

StringBuilder out = new StringBuilder();
int quote1Location = emote.indexOf('"');
if (quote1Location == -1) {
    out.append(emote);
} else {
    // ...
}
return out.toString();

You could write this more concisely with

int quote1Location = emote.indexOf('"');
if (quote1Location == -1) {
    return emote;
}
// ...

This accomplishes two things:

There is no StringBuilder created: we don't need one
The code is more readable because the else part isn't needed anymore: it shifts the rest with one indentation less.

Also, prefer to declare variables at the moment of use. In this case, you are declaring int quote2Location; before the while loop:

int quote2Location;
do {
    quote2Location = emote.indexOf('"', quote1Location + 1);
    // ...
} while (...);

Instead, you can just have:

do {
    int quote2Location = emote.indexOf('"', quote1Location + 1);
    // ...
} while (...);


java class to read csv files Here is my class to read a csv file and I was wondering if there is any improvements that I should do. I feel there are some performance improvements or in exception handling because I just took IO exceptions.

package com.mypackage.utils;
import com.opencsv.CSVParserBuilder;
import com.opencsv.CSVReader;
import com.opencsv.CSVReaderBuilder;
import com.opencsv.enums.CSVReaderNullFieldIndicator;

import java.io.File;
import java.io.IOException;
import java.nio.file.Paths;
import java.util.*;

public class FileReader {

    private String path;
    private CSVReader reader;
    private List<String> linesList;
    private Set<List<String>> splitLinesSet;

    public FileReader(String path) {
        this.path = path;
    }

    public boolean readFile() {

        this.splitLinesSet = new HashSet<>();

        try {
            File file = Paths.get(path).toFile();
            reader = new CSVReaderBuilder(new java.io.FileReader(file))
                    .withCSVParser(new CSVParserBuilder()
                            .withSeparator('|')
                            .withFieldAsNull(CSVReaderNullFieldIndicator.NEITHER).build())
                    .build();
            read();
            reader.close();
        } catch (IOException e) {
            System.err.println("Error in reading CSV: " + e.getMessage());
            return false;
        }

        return true;
    }

    public Set<List<String>> getSplitLinesSet() {
        return splitLinesSet;
    }

    private void read() throws IOException {
        String[] lines;
        while ((lines = reader.readNext()) != null) {
            linesList = new ArrayList<>();
            Collections.addAll(linesList, lines);
            splitLinesSet.add(linesList);
        }
    }
}

I tend to advocate not passing things around which need to be closed, thus my advice is:

inline the read method
remove the reader field, and
... declare the same as a local variable
perferably, declare that local reader variable in a try-with-resources block and throw out the explicit close()-call

Note that these changes are just about robustness and maintainability and will not affect performance or error handling.

Edit, after the comment asking for code edit. (Note: sorry, I am a newbie in the code review community, I hope this does not break any principle here.)

public class FileReader {

    private String path;
    private List<String> linesList;
    private Set<List<String>> splitLinesSet;

    public FileReader(String path) {
        this.path = path;
    }

    public boolean readFile() {

        this.splitLinesSet = new HashSet<>();
        File file = Paths.get(path).toFile();

        try (
            CSVReader reader = new CSVReaderBuilder(new java.io.FileReader(file))
                    .withCSVParser(new CSVParserBuilder()
                            .withSeparator('|')
                            .withFieldAsNull(CSVReaderNullFieldIndicator.NEITHER).build())
                    .build();
            ) {
            String[] lines;
            while ((lines = reader.readNext()) != null) {
                linesList = new ArrayList<>();
                Collections.addAll(linesList, lines);
                splitLinesSet.add(linesList);
            }
        } catch (IOException e) {
            System.err.println("Error in reading CSV: " + e.getMessage());
            return false;
        }

        return true;
    }

    public Set<List<String>> getSplitLinesSet() {
        return splitLinesSet;
    }
}

Note: this was just syntactic shuffling of lines in a text editor - I have not put this through an IDE or a compiler, but I think it shows the principles.


Converting a List of arcs into Adjacency list representation for graph using dictionary I was reading up on implementing Graphs in Python and I came across this Essay at python.org about graphs, so I decided to implement it, but with weighted edges.

I start with arcs and their cost using list of lists and then iterate through it building a dictionary (Adjacency list format) that represents the Undirected Weighted Graph. I am looking for suggestions on how to improve the following code. Here I need to check every time if a vertex already exists in the dictionary using an if x in dict.keys() statement, which takes linear time for each node.

data=[['A','B',5],
  ['A','C',4],
  ['B','C',2],
  ['B','D',3],
  ['C','D',10],
  ['E','F',1],['F','C',6]]

graph={}

for row in data:
    if row[0] in graph.keys():
        graph[row[0]][row[1]]=row[2]
        if row[1] not in graph.keys():
            graph[row[1]]={}
            graph[row[1]][row[0]]=row[2]
        else:
            graph[row[1]][row[0]]=row[2]

    else:
        graph[row[0]]={}
        graph[row[0]][row[1]]=row[2]
        if row[1] not in graph.keys():
            graph[row[1]]={}
            graph[row[1]][row[0]]=row[2]
        else:
            graph[row[1]][row[0]]=row[2]

print graph

The output of the above code is:

>>{'A': {'C': 4, 'B': 5},
   'C': {'A': 4, 'B': 2, 'D': 10, 'F': 6},
   'B': {'A': 5, 'C': 2, 'D': 3},
   'E': {'F': 1},
   'D': {'C': 10, 'B': 3},
   'F': {'C': 6, 'E': 1}}

Overall this is pretty good. Here are a few suggestions for making it even better:

You have a lot of repeated code in your if branches. Since this code will run on either iteration, it’s better to pull it out of the branches. This reduces code repetition, and makes it clearer that this code will always run. Here’s what it reduces to:

for row in data:
    if row[0] not in graph.keys():
        graph[row[0]]={}
    if row[1] not in graph.keys():
        graph[row[1]]={}
    graph[row[0]][row[1]]=row[2]
    graph[row[1]][row[0]]=row[2]

Next you have the problem that you need to initialise every vertex with one empty dictionary. Rather than doing this by hand, you can use collections.defaultdict from the standard library. You specify a “default factory” method, and whenever you try to access a key which hasn’t already been set, it fills in the default for you.

Now the code becomes:

import collections

graph = collections.defaultdict(dict)

for row in data:
    graph[row[0]][row[1]]=row[2]
    graph[row[1]][row[0]]=row[2]

It can be a bit unwieldy to follow these numeric indices around. You can use tuple unpacking at the top of the for loop to name the individual parts of the row:

for vertex0, vertex1, weight in data:
    graph[vertex0][vertex1] = weight
    graph[vertex1][vertex0] = weight

It would be better to wrap your graph-making code in a function, graph_from_data(), so that you can reuse it in other modules.

You should also move the bits of this code that can’t be reused into an if __name__ == '__main__' block – this means the same file can be both a module and a script. If I do an import from this file, I won’t get an example graph printed as a side effect.


Searching in a sorted 2D matrix If I was at an interview, and wrote this code, what would you think? Please be brutal.

Time it took to wrote it: 13 minutes

Problem:

  Write an efficient algorithm that searches for a value in an m x n
  matrix. This matrix has the following properties:

  Integers in each row are sorted from left to right. The first integer
  of each row is greater than the last integer of the previous row. For
  example,

  Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

  Given target = 3, return true.

 public boolean searchMatrix(int[][] matrix, int target) {
    int lastCol = matrix[0].length-1;
    int row=0;
    while(row!=matrix.length && lastCol>=0){
        if(matrix[row][lastCol]==target){
            return true;
        }
        if(matrix[row][lastCol]>target){
            lastCol--;
            if(binarySearch(matrix[row], 0, lastCol, target)!=-1){
                return true;
            }
        }
        row++;
    }
    return false;
}
public int binarySearch(int[] arr, int low, int high, int target){
    while(low<=high){
        int mid = (low + high)/2;
        if(arr[mid]==target){
            return mid;
        }
        else if(arr[mid]<target){
            low = mid+1;
        }
        else if(arr[mid]>target){
            high = mid-1;
        }
    }
    return -1;
}

Space complexity = O(1)
Time Compexity = O(log(n!))

Your algorithm is not efficient (thats the brutal part of the answer).

Searching in a list of  t values is a task that can be accomplished using O(log(t)) comparisons. Here we have t=m*n values so it should be accomplished using O(log(m*n)) = O(log(m))+O(log(n)) comparisons. I suspect your algorithm may execute the while loop about matrix.length times so it is not O(log(m)) (where m is the number of rows).

The algorithm could work in the following way:

if the searched value is smaller then the first column in the first row then the searched value is not contained in the matrix.
Then do a binary search on the first column of the matrix to find the largest  entry smaller or equal to the searchd value
if the value found macthes you are done.
otherwise do a binary search on the row found.
if the value found matches the searched value you are done
otherwise the searched value is not in the matrix

Annother way is to treat the problem like a single dimension sorted array as it is proposed in the comment of @Azar.

Even a small piece of code can have a lot of errors so it does make sense to try to use library methods to accomplish this task and not implement the binary search by yourself (but I don't know if this is the intention of the poser of the problem).

This blog entry discusses an example of a buggy implementation in Java. It references the following SUN  bug report because there was an errornous implementation of the binary search even in the JDK.


Flatten double-linked list Consider this interview question:

  Given a Node with a reference to a child, its next, its previous, and a variable for its value (\$\frac{1}{2}\$ tree, \$\frac{1}{2}\$ doubly linked list structure), you have to find a way to flatten the structure.

1 = 2 = 3 = 5
    |       |
    6 = 7   8
        |
        9

  (reference down is child and reference across is next)

  this above diagram becomes: 1 - 2 - 6 - 7- 9 - 3 - 5 - 8 but:

  2 still has child reference to 6
  7 still has child reference to 9
  5 still has child reference to 8

Here is my code:

class Node(object):
    def __init__(self, value, next_node=None, prev=None, child=None):
        self.value = value
        self.next = next_node
        self.prev = prev
        self.child = child

    def __repr__(self):
        return str(self.value)

one = Node(1)
two = Node(2)
three = Node(3)
five = Node(5)
six = Node(6)
seven = Node(7)
eight = Node(8)
nine = Node(9)
one.next = two
two.prev = one
two.next = three
two.child = six
three.prev = two
three.next = five
five.prev = three
five.child = eight
six.next = seven
seven.prev = six
seven.child = nine

def flatten(head):
    if not head: return head

    c = flatten(head.child)
    n = flatten(head.next)
    if c:
        head.next = head.child
        head.child.prev = head
    if c and n:
        tail = c
        while tail.next:
            tail = tail.next
        tail.next = n
        n.prev = tail
    return head

n = flatten(one)
while n:
    print "%d -" % (n.value,),
    n = n.next

I don't like the while loop. I could store tail and pass it around. Any better solution?

Your current implementation is quite nice.

The only way you are going to avoid using the while loop to find the right-most node is if you have each individual branch maintain its branch's tail Node. This is a [sort of] good approach to the problem. However, once you reach this point, a Node really starts becoming more than just a Node: it now has information about the entire structure instead of what is directly around it.

So instead of modifying the Node class, you could create a Tree class.

This change makes sense:

Right now you manually create your 'tree'. This approach is not very portable. A Tree class can handle its own creation.
You need to store information about the entire branch structure somewhere. Inside a Node doesn't feel right.
You don't really flatten a Node, you flatten a tree of nodes. Thus, it again makes sense to move the flatten function inside a Tree class (or at least take a Tree parameter).

Here is a skeleton version of my Tree class. I have stubbed out all my methods except flatten as that is the function in question:

class Tree(object):
    def __init__(self, root=None):
        self.root = root
        self.tail = root
        self.length = 1 if root else 0

    def __iter__(self):
        ''' Allows iteration through the tree using `for node in tree`. '''
        pass

    def __getitem__(self, index):
        ''' Fetches the `Node` at the passed index. '''
        pass

    def grow(self, nodes):
        ''' Appends node/nodes/Tree onto itself. Be careful when adding `Node`
            we need to append a *copy* of a `Node`, not the reference. '''
        pass

    def graft(self, tree, node_pos=0):
        ''' Grafts in another tree to this one. By default the new tree
            is grafted to the root of the tree. '''
        pass

    def flatten(self):
        ''' Returns the flattened version of itself. '''
        flat = Tree()
        for next in self:
            flat.grow(next)
            if next.child:
                flat.grow(next.child.flatten())
        return flat

In this version of flatten, we keep the recursive feel as we call a method with the same method declaration. However, we are not doing true recursion because the methods are bound to different objects, and thus are different methods.

In any case, the flatten function is really quite simple:

Create the new Tree we are going to modify and return.
Loop through the Nodes of the current tree.
Append the current Node.

3.1. If that Node has a child Tree, append the flattened version of that Tree.
Return the final flattened Tree.

Here is my Tree class plus your Node class in action:

one, two, three, four, five, six, seven, eight, nine = [Node(num) for num in xrange(1,10)]

tree = Tree(one)
tree.grow([two, three, five])

# Graft the new `Tree` to the 3rd `Node`.
tree.graft(Tree(eight), 3)

branch = Tree(six)
branch.grow(seven)

# Graft the new `Tree` to the 1st `Node`.
branch.graft(Tree(nine), 1)

tree.graft(branch, 1)

def flatten(tree):
    ''' A non-class version of the `flatten` function. '''
    flat = Tree()
    for next in tree:
        flat.grow(next)
        if next.child:
            flat.grow(flatten(next.child))
    return flat

print ' - '.join([str(node.value) for node in flatten(tree)])
print ' - '.join([str(node.value) for node in tree.flatten()])


ArrayList Implementation in Java Can someone please evaluate my code and let me know how I can improve it?

public class ArrayListImplementation {

static class ListNode<T> {
    private T value;

    public ListNode(T val) {
        this.value = val;
    }

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

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(this.value);
        return sb.toString();
    }
}

static class List<T> {
    private ListNode<T>[] node;
    private int listSize;
    private int initialCapacity;

    public List(int size) {
        node = new ListNode[size];
        initialCapacity = size;
    }

    public int size() {
        return listSize;
    }

    public boolean isEmpty() {
        return listSize == 0;
    }

    public T get(int index) {
        if(index >= initialCapacity) {
            throw new ArrayIndexOutOfBoundsException();
        }

        return node[index].getValue();
    }

    public void add(T val) {
        if(listSize == initialCapacity) {
            System.out.println("No space to add a new list element");
            return;
        }

        ListNode<T> head = null;
        if(listSize == 0) {
            head = new ListNode<>(val);
            node[0] = head;
            listSize++;
            return;
        }

        ListNode<T> cur = new ListNode<>(val);
        node[listSize++] = cur;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        for(int i = 0; i < initialCapacity - 1; ++i) {
            sb.append(node[i].getValue() + ", ");
        }
        sb.append(node[initialCapacity - 1].getValue() + " ]");
        return sb.toString();
    }

    public void clear() {
        node = new ListNode[initialCapacity];
        listSize = 0;
        return;
    }

    public boolean remove(T value) {
        boolean result = false;
        for(int i = 0; i < initialCapacity; ++i) {
            if(node[i].getValue() == value) {
                result =  remove(node[i], i);
                if(result) {
                    listSize--;
                }
            }
        }
        return result;
    }

    private boolean remove(ListNode<T> toBeRemoved, int index) {
        if(index < 0 || index >= initialCapacity) {
            return false;
        }

        if(initialCapacity > 1) {
            int prevSize = initialCapacity;
            ListNode<T>[] copyNode = node;

            node = new ListNode[--initialCapacity];
            for(int i = 0; i < index; ++i) {
                node[i] = copyNode[i];
            }

            for(int i = index + 1; i < prevSize; ++i) {
                node[i-1] = copyNode[i];
            }
        }
        else {
            this.clear();
        }
        return true;
    }
}

public static void main(String[] args) {
    List<Integer> list = new List<Integer>(5);
    System.out.println(list.isEmpty());
    list.add(5);
    list.add(10);
    list.add(15);
    System.out.println(list.get(0));
    System.out.println(list.get(2));
    System.out.println(list.size());
    list.add(20);
    System.out.println(list.size());
    list.add(25);
    System.out.println(list.get(4));
    System.out.println(list.remove(20));
    System.out.println(list.remove(45));
    System.out.println(list.remove(5));
    System.out.println(list.remove(25));
    System.out.println(list.remove(10));
    System.out.println(list.remove(15));
    //System.out.println(list.get(5)); //ArrayIndexOutOfBoundsException
    list.clear();
    System.out.println(list.size());
}}

In your ListNode::toString() the use of StringBuilder is useless overhead as you just append one single string. You could strip it down method to just this:

public String toString() {
    if (this.value == null) { // beware of null!
        return "null";
    }
    return this.value.toString();
}

In your List::add(T) method you should throw an Exception (maybe an ArrayIndexOutOfBoundsException with a proper message) if the list is full (if(listSize == initialCapacity) {) instead of writing a note to System.out. Otherwise the calling code of your implementation wouldn't notice the problem. See Fail Fast Principle.
In your add(T) method, why are there two different paths for the first and the other items, when the do exactly the same?
Is it by intention, that you reduce the intial/maximum size of your internal array in the remove(ListNode<T> toBeRemoved, int index) method?

node = new ListNode[--initialCapacity];  // << newSize = initialCapacity -1

It seems a bit strange to me.

In your remove methods you use initialCapacity where you rather should use listSize (except from the line mentioned in 4a).
Within the remove you could reuse the add method. I would refactor it to something like this:

public boolean remove(T value) {
    boolean result = false;
    for(int i = 0; i < listSize; ++i) { // note: only check elements added
        if(node[i].getValue() == value) {
            result =  remove(node[i], i);
            if(result) {
                listSize--;
            }
            // break; // note: exit loop if you only want to remove first occurence.
        }
    }
    return result;
}

private boolean remove(ListNode<T> toBeRemoved, int deleteIdx) {
    if(deleteIdx < 0 || deleteIdx >= listSize) { // note: if no element -> exit
        return false;
    }

    if(listSize > 1) { // note: listSize relevant here
        ListNode<T>[] oldNode = node;

        node = new ListNode[initialCapacity]; // note: same size here
        int sourceIdx = 0;
        for(int targetIdx = 0; targetIdx < listSize; targetIdx++) {
            if (targetIdx == deleteIdx) {
                sourceIdx++; // skip deleted element
            }
            node[targetIdx] = oldNode[sourceIdx++];
        }
    }
    else {
        this.clear();
    }
    return true;
}