Confusion over using generics in MVC project Consider the following:

Remote service accepts SecondAction=Search and SecondAction=Update. For SecondAction=Search sending a Query parameter is sufficient enough. For SecondAction=Update, I need to send back a set of additional parameters named AdditionalQuery1 and AdditionalQuery2.

The ApiKey and Action properties are always the same. The SecondAction is different. I want the model to be as reusable as possible and use less code as possible.

I want to be able to reuse the the majority of the Request and only have it to SpecialData instead of Data to send those AdditionalQueries for when I have to do a SecondAction=Update.

public class Request<T>
{
    public string ApiKey { get; set; }
    public Details<T> Details { get; set; }
}

public class Details<T> {
    public string Action { get; set; }
    public string SecondAction { get; set; }
    public MoreDetails<T> MoreDetails { get; set; }
}

public class MoreDetails<T> {
    public T Data { get; set; }
}

public class Data {
    public string Query { get; set; }
}

public class SpecialData : Data {
    public string AdditionalQuery1 { get; set; }
    public string AdditionalQuery2 { get; set; }
}

I've confused myself to the point I'm creating it like

 var Obj = new Request<Details<MoreDetails<SpecialData>>> {
      ApiKey = "12345",
      Details = new Details<MoreDetails<Data>>() {
           Action = "Search"
      }

doesn't look right. It doesn't seem right that I have to make all the others a generic type as well.

First of all, I appreciate the fact that you want to keep your code DRY as many developers are not concerned with this.  Also, I like the idea of having the generic Data type.  This makes your code flexible so that in the future new, more derived types of Data can be created without affected significant portions of unrelated code.  That being said, there are some things I would consider.

Style Notes:

Use consistent syntax conventions

On some lines, you have an opening curly on a new line, on others, it is on the same line as the function block / signature.  Either way is fine, just make sure you're consistent.

For generic types, give them more descriptive names than T to improve readability

Presumably, your T is a Data type (more on this later), so name your generic type parameter: TData, instead of T.  This gives a more clear understanding of what is expected.

Programming Notes:

As far as your use of Generics goes, I would use something more like this (and I'll explain why):

public class Request<TData> where TData : Data {

    public Request() {
        this.RequestDetail = new Details<TData>();
    } // end default constructor

    public string ApiKey { get; set; }
    public Details<TData> RequestDetail { get; set; }

} // end class Request{TData}

public class Details<TData> where TData : Data {

    public Details() {
        this.DetailData = new MoreDetails<TData>();
    } // end default constructor

    public string Action { get; set; }
    public string SecondAction { get; set; }
    public MoreDetails<TData> DetailData { get; set; }

} // end class Details{TData}

public class MoreDetails<TData> where TData : Data {

    public TData RequestData { get; set; }

} // end class MoreDetails{TData}

public class Data {

    public string Query { get; set; }

} // end base class Data

public class SpecialData : Data {

    public string AdditionalQuery1 { get; set; }
    public string AdditionalQuery2 { get; set; }

} // end derived class SpecialData

Then, in your implementation:

Request<Data> newRequest = new Request<Data>();
newRequest.ApiKey = "12345";
newRequest.RequestDetail.Action = "Search";
newRequest.RequestDetail.DetailData.RequestData = new Data(); //You could also use SpecialData

What I did:

1. Use Generic Type Constraints

Using Generic type constraints is a great way to both enhance the readability and maintainability of your code because you'll have some basic compile-time checking.  It also tells future developers what your expectations are.

See here for more on this subject: http://msdn.microsoft.com/en-us/library/d5x73970.aspx

2. Give more specific names to properties and fields

Your naming of properties being the same as the class names is confusing.  I renamed some of the properties to make the code easier to understand.  In addition to this, I would think of more descriptive names for your classes than Detail and MoreDetail as these don't really help understand the code or how it should be used.  Without knowing more about what your final aim is, I can't really provide more useful names, but you should consider being more explicit.

3. Instantiate defaults for complex types in constructors

You are passing generic type arguments for your initial request, which doesn't seem like what you want.  All of your generics ultimately are interested in what TData will be, not the property chain all the way down.  The generic type argument only specifies the type of, not the actual value of the property (which is why I have an additional assignment in my implementation code) that actually creates a new instance of the Data class.

By instantiating each property within the constructor, the object creation is simpler in your implementation.  Additionally, your implementation should not have to be concerned with the finer details of how the class and it's property chains are initialized.  The fact that your implementation code has to go so many levels deep in your properties may be a code smell.  Also, I am unclear on the usefulness of the MoreDetail class.

4. Simplify object creation

The object initializer syntax you're using is helpful sometimes, but when you are creating a complex object, it's best to KISS to improve the readability of the code (remember, this isn't JavaScript ;) ).

Let me know if I need to add any clarification on these points.


Reading data from a CSV and pushing it to a Salesforce application I'm trying to write code that reads data from a CSV and pushes it to a Salesforce application using the API. My code processes the data in a for loop, but it takes a long time (3 hours) to run the function. What can I do to optimize my code to run faster?
Here's an example of my code which reads Patient Diagnosis data from a flatfile which us more than 200k records. Inside the for loop, I query the patient list which has 100k+ records, transform the object then add it to a list for bulk processing. My code looks like this:
Iterating over ptdiag which contains flatfile data
for (int i = 0; i < ptdiags.Count; i += BATCH_SIZE)
{
  var batchContents = SFToBTMapping.Bulk_PtDiag_Content(ptdiags.Skip(i).Take(BATCH_SIZE).ToList(),sfPatients);
  var batch = BulkUpsert(job.Id, batchContents);
}

Function that transforms the object. Here I query sfpatients to link a patientid to the diagnosis object
    public static string Bulk_PtDiag_Content(List<Ptdiag> ptdiags, List<SfPatient__c> sfpatients)
    {
        string res = "Patient__c,DiagKey__c,NickName__c" +
            ",Sequence__c,ShortDescr__c,PTDiagKey__c" + Environment.NewLine;

        foreach (var d in ptdiags)
        {
            var sfd = Map_BTSQL_Patientdiag_To_SF_Patientdiag(d);
            sfd.Patient__c = sfpatients.FirstOrDefault(c => c.PatientKey__c == d.Ptkey.ToString())?.Id;

            res += string.Join(",", sfd.Patient__c, sfd.DiagKey__c, sfd.NickName__c
                                , sfd.Sequence__c, sfd.ShortDescr__c.Replace(",",""), sfd.PTDiagKey__c);
            if (ptdiags.Last() != d)
                res += Environment.NewLine;
        }

        return res;
    }

Method that creates a mapping for Ptdiag
    public static SfPatientDiag__c Map_BTSQL_Patientdiag_To_SF_Patientdiag(Ptdiag d)
    {
        return new SfPatientDiag__c
        {
            DiagKey__c = d.Diagkey.ToString(),
            Diagnosis__r = new SfDiagnosis__c { Diagnosis_Key__c = d.Diagkey.ToString() },
            NickName__c = d.Nickname,
            Patient__r = new SfPatient__c { PatientKey__c = d.Ptkey.ToString() },
            Sequence__c = d.Sequence != null ? Convert.ToDouble(d.Sequence) : 0,
            ShortDescr__c = d.Shortdescr,
            PTDiagKey__c = d.Ptdiagkey.ToString()
        };

    }

In addition to the post by @aepot, I made the following changes which reduced the completion time significantly.
I used a dictionary instead of a list to query patient Id. Querying a large list of objects in for loop is what really slowed down the processing. Here's what the code looks like now:
for (int i = 0; i < ptdiags.Count; i += BATCH_SIZE)
{
  var batchContents = SFToBTMapping.Bulk_PtDiag_Content(ptdiags.Skip(i).Take(BATCH_SIZE).ToList(), sfPatients.ToDictionary(p => p.PatientKey__c));
  var batch = BulkUpsert(job.Id, batchContents);
}

public static string Bulk_PtDiag_Content(List<Ptdiag> ptdiags, Dictionary<string, SfPatient__c> sfpatients)
        {
            var sb = new StringBuilder();
            sb.AppendLine("Patient__c,DiagKey__c,NickName__c,Sequence__c,ShortDescr__c,PTDiagKey__c");

            foreach (Ptdiag d in ptdiags)
            {
                SfPatientDiag__c sfd = Map_BTSQL_Patientdiag_To_SF_Patientdiag(d);

                sfd.Patient__c = sfpatients.GetValueOrDefault(d.Ptkey.ToString()) != null ? sfpatients[d.Ptkey.ToString()].Id : "";

                sb.Append(string.Join(",", sfd.Patient__c, sfd.DiagKey__c, sfd.NickName__c
                                    , sfd.Sequence__c, sfd.ShortDescr__c.Replace(",", ""), sfd.PTDiagKey__c));
                if (ptdiags.Last() != d)
                    sb.AppendLine();
            }

            return sb.ToString();
        }


Optimizing a function with nested loops and if condition private  void find_tile(float[] x, float[] z, int nRigidBodies)  {
    int serial[]=new int[nRigidBodies];
    int numTiles=4;
    for(int i=0;i<nRigidBodies;i++)
    {
        // Check for the loaction of each tile to find which one should be switched on...
        //currently only supports 4
        for(int j=0;j<numTiles;j++)
        {
            if ((x[i] > tileCoords[j][0]) && (x[i] < tileCoords[j][1]) && (z[i] > tileCoords[j][2]) && (z[i] < tileCoords[j][3]))
            {
                serial[i]=j+1;
                break;
            }
        }
    }

We have a optitrack system that tracks objects in a room and the number of objects is represented by nRigidBodies and their x-y cordinate by the x[] and z[] array passed here.

Also we have a fixed number of Tiles which are fixtures on the ceiling represented by numTiles and the bounds of these tiles are in tileCoords.

If an object is directly under one of these fixtures, we switch the fixture on.So I create an array serial[] which is of the same size as nRigidBodies.For every object we check if is is within the bounds of that fixture and if it we assign the fixture number to the serial array.Later we just take out all the fixture number from the array( coz these should only be lit up ) and send them a message to light up and the ones not in here are switched off.

The condition where the object is not within any of the fixtures is fine since it is checked later in the code and taken care of.

Sample Input
    float[] x= {1.5, -0.5, 3.5}
    float[] z= {2.5, -1.5, 3.2}
    nRigidBodies= 3
    numTiles=4
    tileCoords={{0.5,1.5,1.5,2.5},{-0.5,0.5,0.5,1.5},{0.5,1.5,0.5,1.5},{-0.5,0.5,-0.5,0.5}}

Expected Output
   serial[]={1,2,0}

I have a simple function that checks for if each object is within the bounds of the cordinates or not.If it is, we assign the number to a variable.

Currently the inner loop generally only has only 4 iterations so it doesn't matter much.However in the future it might run for upto 50 iterations with the outer loop running for 5 iterations max.The code is a time sensitive piece which controls lights in real time.Too much time in computing this function would result in lights appearing to be lagged.

It would be of great help if someone can guide me on how to optimize the function above for faster computation.

I was thinking of using threads to run all of the outer loops at once.If there is something better which can be achieved with single threaded model,I would love to stick to it as that might be making it really complicated.

Disclaimer: I have not tested any of these optimizations. Some of these optimizations could potentially even harm the speed - or they could already be covered by the JVM. Do your own benchmarking.

Helping the Compiler/JVM
If you don't need to override this method, declare it final. The compiler might inline the method if it thinks it helps. Additionally, declare constants as final - such as numTiles.

Preventing repeated lookups
You need to access x[i], tilecoords[j], z[i] and such multiple times. Consider storing those in temporary variables. Don't forget to test to see if it is actually faster to do so. An example (with really bad variable names - you might want to pick better names than xi and zi

for(int i=0;i<nRigidBodies;i++)
{
    // Check for the loaction of each tile to find which one should be switched on...
    //currently only supports 4
    float xi = x[i];
    float zi = z[i];
    for(int j=0;j<numTiles;j++)
    {
        if ((xi > tileCoords[j][0]) && (xi < tileCoords[j][1]) && (zi > tileCoords[j][2]) && (zi < tileCoords[j][3]))
        {
            serial[i]=j+1;
            break;
        }
    }
}

Fixing bugs
int serial[]=new int[nRigidBodies]; creates a new int array with a size of nRigidBodies. int's default value is 0. Thus, the entire array will be filled with 0. Given that your innerloop starts at index 0 and sets the "found" index into the array, it's possible it's setting 0 over the default value. That's not so important. What is important is the reverse implication: If the serial array contains a 0 at a given index, you do not know whether this is because no tile-index was found, or because the tile-index that was found was the first one.


Python simple int subclass The below is a class designed to implement Rememember the Milk's task priorities. I'm using it partly as an exercise in "Pythonic" programming, so it's fairly simple already, but advice on how to make it simpler or more Pythonic would be particularly appreciated.

I'm using Python 2.6.5 in case it makes any difference.

class Pri(int):    # Subclass int to get handy comparison functions etc.
    '''Task priority'''

    public_from_internal = {1: 1, 2: 2, 3: 3, 4: 'N'}
    internal_from_public_str = {'N': 4, '1': 1, '2': 2, '3': 3}
    _dict = dict()

    def __new__(cls, level):
        try:
            level = Pri.internal_from_public_str[str(level)]
        except KeyError:
            raise ValueError, "Pri must be 'N', '1', '2', or '3'"

        # If there's already an instance of this priority, don't create a new one.
        if level in Pri._dict: return Pri._dict[level]
        else: return super(Pri, cls).__new__(cls, level)

    def __init__(self, level):
        super(Pri, self).__init__()
        Pri._dict[self] = self

    def __repr__(self): return "Pri('" + str(Pri.public_from_internal[self]) + "')"

    # Priority 1 is clearly greater than priority 3, so invert cmp
    def __cmp__(self, other): return (-cmp(int(self), int(other)))

Some selected output, for the curious:

>>> Pri(1)
Pri('1')
>>> Pri('N')
Pri('N')
>>> Pri(4)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "rtm.py", line 10, in __new__
    raise ValueError, "Pri must be 'N', '1', '2', or '3'"
ValueError: Pri must be 'N', '1', '2', or '3'
>>> Pri._dict
{Pri('1'): Pri('1'), Pri('N'): Pri('N')}
>>> Pri(1) > Pri(2)
True
>>> bool(Pri('N'))
True
>>> repr(Pri("2"))
"Pri('2')"
>>> print repr(Pri('N'))
Pri('N')
>>> Pri(1)._dict
{Pri('1'): Pri('1'), Pri('2'): Pri('2'), Pri('N'): Pri('N')}

class Pri(int):    # Subclass int to get handy comparison functions etc.

Abbreviating words in class names makes it harder to follow. Just call it Priority

    '''Task priority'''

    public_from_internal = {1: 1, 2: 2, 3: 3, 4: 'N'}
    internal_from_public_str = {'N': 4, '1': 1, '2': 2, '3': 3}
    _dict = dict()

Naming this _dict doesn't give me a hint about what its used for

    def __new__(cls, level):
        try:
            level = Pri.internal_from_public_str[str(level)]

I don't like stringifying anything that gets passed in here. You really only want to support strings and ints not things that happen to stringify into the correct types.

        except KeyError:
            raise ValueError, "Pri must be 'N', '1', '2', or '3'"

        # If there's already an instance of this priority, don't create a new one.
        if level in Pri._dict: return Pri._dict[level]
        else: return super(Pri, cls).__new__(cls, level)

Use the following construct instead:

try:
   return Pri._dict[level]
except KeyError:
   return super(Pri,cls).__new__(cls, level)

I think its clearer, and it will be slightly faster.

    def __init__(self, level):
        super(Pri, self).__init__()
        Pri._dict[self] = self

I do this is __new__ and not have an __init__ function.

    def __repr__(self): return "Pri('" + str(Pri.public_from_internal[self]) + "')"

I don't like putting the method name and implementation on the same line. I think it makes it look clutered. I'd also recommend using return "Pri(%s)" % Pri.public_from_internal[self] as I think its clearer as to the result.

    # Priority 1 is clearly greater than priority 3, so invert cmp
    def __cmp__(self, other): return (-cmp(int(self), int(other)))

You inherited from int to get comparisons. But then you have to reimplement the comparisons anyways. Now you also have all the other stuff like adding/multipyling/subtracting/etc which don't make sense to apply to priorities. Basically, there is no reason to inherit from int here, and many reasons not to.

How I'd do this

class Priority(object):
    priorities_by_name = {}
    @classmethod
    def from_string(cls, name):
         return cls.priorities_by_name[name]

    priorities_by_number = {}
    @classmethod
    def from_number(cls, number):
         return cls.priorities_by_number[number]

    def __init__(self, name, number):
        self.priorities_by_name[name] = self
        self.priorities_by_number[number] = self
        self.name = name
        self.number = number

    def __repr__(self):
        return "Priority<%d>" % self.number

    def __cmp__(self, other):
        return -cmp(self.number, other.number)

Priority.First = Priority('1', 1)
Priority.Second = Priority('2', 2)
Priority.Third = Priority('3', 3)
Priority.None = Priority('N', 4)

Priority.__init__ = None # Prevent any future creations

I explicitly call class method to get a priority from either the string or number. I dislike overloading the one constructor to take either.
For a small number of items, I prefer to create them all upfront. It makes the construction simpler
I can access Priority objects at Priority.First (etc)

Truth be told I probably wouldn't implement a Priority class, instead I'd keep track of the priority as an int.


Monkey-patching native JavaScript constructors I've written a small utility for monkey-patching native JavaScript constructor functions. For example, you can use it to modify input arguments before returning an instance (this can be useful for unit tests).

There is much more detail about the utility on GitHub, so it may be useful to read through the readme on there.

I would be interested to know if I've hugely over-engineered this. There may be simpler techniques that I could take advantage of. Any comments are appreciated.

Here is the code:

var patch = (function () {
    /*jshint evil: true */

    "use strict";

    var global = new Function("return this;")(), // Get a reference to the global object
        fnProps = Object.getOwnPropertyNames(Function); // Get the own ("static") properties of the Function constructor

    return function (original, originalRef, patches) {

        var ref = global[originalRef] = original, // Maintain a reference to the original constructor as a new property on the global object
            args = [],
            newRef, // This will be the new patched constructor
            i;

        patches.called = patches.called || originalRef; // If we are not patching static calls just pass them through to the original function

        for (i = 0; i < original.length; i++) { // Match the arity of the original constructor
            args[i] = "a" + i; // Give the arguments a name (native constructors don't care, but user-defined ones will break otherwise)
        }

        if (patches.constructed) { // This string is evaluated to create the patched constructor body in the case that we are patching newed calls
            args.push("'use strict'; return (!!this ? " + patches.constructed + " : " + patches.called + ").apply(null, arguments);");
        } else { // This string is evaluated to create the patched constructor body in the case that we are only patching static calls
            args.push("'use strict'; return (!!this ? new (Function.prototype.bind.apply(" + originalRef + ", [{}].concat([].slice.call(arguments))))() : " + patches.called + ".apply(null, arguments));");
        }

        newRef = new (Function.prototype.bind.apply(Function, [{}].concat(args)))(); // Create a new function to wrap the patched constructor
        newRef.prototype = original.prototype; // Keep a reference to the original prototype to ensure instances of the patch appear as instances of the original
        newRef.prototype.constructor = newRef; // Ensure the constructor of patched instances is the patched constructor

        Object.getOwnPropertyNames(ref).forEach(function (property) { // Add any "static" properties of the original constructor to the patched one
            if (fnProps.indexOf(property) < 0) { // Don't include static properties of Function since the patched constructor will already have them
                newRef[property] = ref[property];
            }
        });

        return newRef; // Return the patched constructor
    };

}());

And here's an example usage (this is a real-world use case for working around a bug in date parsing in PhantomJS):

Date = patch(Date, "DateOriginal", {
    constructed: function () {
        var args = [].slice.call(arguments);
        if (typeof args[0] === "string" && /^\d{4}\/\d{2}$/.test(args[0])) {
            args[0] = args[0] + "/02"; // Make sure the argument has a 'day'
        }
        return new (Function.prototype.bind.apply(DateOriginal, [{}].concat(args)));
    }
});

There are some more examples, and details of the arguments to patch in the GitHub readme.

I don't see any good reason why you're using some of these hacks. It took me a while to understand what you were doing and I was pretty much forced to step through it in debugger. Going to review this line by line and point out simplifications and patterns as I see fit. I'll be batching together all my suggestions into a counter proposal in this jsbin, using the unit tests from your repo.
To start, it seems quite unneccessary and non standard to get the global scope your way (and I'm going to later argue you shouldn't need it)...
var global = new Function("return this;")();

Just do what every other package does and get scope at the start of your wrapper
(function(global) {  })(this); //or use self w/e

I'm not a fan of your fnProps idea. I would prefer you store has = Object.prototype.hasOwnProperty; and filter out items on the Function prototype as follows:
var has = Object.prototype.hasOwnProperty();
/* .... */
//To avoid storing generic function properties (like length) on newRef
Object.getOwnPropertyNames(ref).forEach(function(key) {
    if(!has.call(Function, key)) newRef[key] = ref[key];
});

I'm biased here, but as a past Mootools developer I keep comparing your function with Class.refactor. Personally I would prefer you add a reference to the original function on newRef - maybe as some property _original or let the user handle storing the original. I'm not a fan of adding a global for the original function.
A question, why do you not pass this to your constructors? If you're wrapping some classes this seems like it may make usuage less intuitive.
Update (still at work and can't look into removing the new Function() approach yet but I think I found a great change... You can rewrite the extremely confusing bind.apply(...) like this (unit tests passing):
newRef = Function.apply(null, args);

I'm not a minifier but theres no good reason to do !!this ? x : y
Counter proposal:
I believe you should drop the arity requirement and drop the global - instead inform the user they should cache the original locally. I've rewritten the code with these considerations in mind. Here's a jsbin with these changes (note I haven't removed the global to respect your test cases):
var patch = (function (global) {
    /*jshint evil: true */

    "use strict";
    var has = Object.prototype.hasOwnProperty,
        slice = Array.prototype.slice,
        bind = Function.bind;
    return function (original, patches) {
        var args = [],
            newRef, // This will be the new patched constructor
            i;

        patches.called = patches.called || original; // If we are not patching static calls just pass them through to the original function

        if (patches.constructed) { // This string is evaluated to create the patched constructor body in the case that we are patching newed calls
            newRef = function(/*args*/) {
                return (this && this !== global ? patches.constructed : patches.called).apply(this, arguments);//note called with context
            };
        } else { // This string is evaluated to create the patched constructor body in the case that we are only patching static calls
            newRef = function(/*args*/) {
                return this && this !== global  ? new (bind.apply(original, [].concat({}, slice.call(arguments))))
                                                : patches.called.apply(this, arguments);
            };
        }

        // Create a new function to wrap the patched constructor
        newRef.prototype = original.prototype; // Keep a reference to the original prototype to ensure instances of the patch appear as instances of the original
        newRef.prototype.constructor = newRef; // Ensure the constructor of patched instances is the patched constructor

        Object.getOwnPropertyNames(original).forEach(function (property) { // Add any "static" properties of the original constructor to the patched one
            if (!has.call(Function, property)) { // Don't include static properties of Function since the patched constructor will already have them
                newRef[property] = original[property];
            }
        });

        return newRef; // Return the patched constructor
    };

})(this);

Edit - missed an easy code size optimization:
newRef = function(/*args*/) {
    if(this && this !== global) {
        return patches.constructed ? patches.constructed.apply(this, arguments)
                                   : new (bind.apply(original, [].concat({}, slice.call(arguments))))// create the patched constructor body in the case that we are only patching static calls;
    } else {
        return patches.called.apply(this, arguments);
    }
};


Median-of-medians/quickselect filter in C I wrote a quick-select filter in C on Wednesday. (The code is below.)

It is a filter in the UNIX tradition:

It reads from standard input k, the rank of the integer to select, n, the number of elements, and then n integers.
It outputs the kth highest integer.

(A perhaps better design would take k as an argument—but a bigger gripe of mine is having to give n! Bonus points if an answer can show me how to avoid reading n from stdin or as an argument. I would read until EOF, but then I would have to deal with a growing array, I think.)

For the unfamiliar, quickselect can find the kth highest integer in O(n) time. The naïve selection algorithm sorts in place and then accesses element k, for O(n lg n) runtime. Quickselect does not sort large lists and achieves linear performance.

kth_largest.c

/*d. ben knoble 2019.10.02*/

/*
 * PROGRAM
 *
 * k_largest
 *
 * Finds the kth largest element of an array in O(n) time.
 *
 * Reads from standard input
 *
 * - k: which element to find
 * - n: number of elements
 * - n elements
 *
 * Outputs kth largest element to standard out.
 *
 * IMPLEMENTATION
 *
 * see kth_largest function
 */

#include <assert.h>
#include <err.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int compare_longs(const void *a, const void *b) {
    long x = *(long *)a;
    long y = *(long *)b;
    if (x < y)
        return -1;
    else if (x > y)
        return 1;
    return 0;
}

void sort(long *a, size_t n) {
    qsort(a, n, sizeof(long), compare_longs);
}

size_t med_index(size_t i) {
    return (size_t)(floor(i/2));
}

void swap(long *a, long *b) {
    long t = *a;
    *a = *b;
    *b = t;
}

size_t partition(long pivot, long *array, size_t n_elts) {
    // find the pivot
    size_t pos = -1;
    for (size_t i = 0; i < n_elts; ++i) {
        if (array[i] == pivot) {
            pos = i;
            break;
        }
    }
    assert(pos >= 0);
    swap(&array[pos], &array[n_elts-1]);
    // now pivot is at the end of the array

    size_t i = 0;
    for (size_t j = 0; j < n_elts; ++j) {
        if (array[j] < pivot) {
            swap(&array[j], &array[i]);
            ++i;
        }
    }
    swap(&array[i], &array[n_elts-1]);

    return i;
}

long kth_largest(size_t k, long *array, size_t n_elts) {
    size_t n_sublists = n_elts/5;
    long *medians = malloc(n_sublists * sizeof(long));
    if (medians == NULL) { err(1, NULL); }

    // sort sublists of 5 elements
    for (size_t i = 0; i < n_sublists; ++i) {
        size_t start = i*5;
        size_t left = n_elts - start < 5 ? n_elts - start : 5;
        sort(&array[start], left);
        if (left == 5)
            medians[i] = array[start + 3];
        else
            medians[i] = array[start + med_index(left)];
    }

    // determine pivot (possibly recursively)
    long pivot;
    if (n_sublists < 5)
        pivot = medians[med_index(n_sublists)];
    else
        pivot = kth_largest(med_index(n_sublists), medians, n_sublists);

    // partition
    size_t rank = partition(pivot, array, n_elts);
    if (k < rank)
        return kth_largest(k, array, rank-1);
    else if (k > rank)
        return kth_largest(rank - k, &array[rank+1], n_elts-(rank+1));
    // else k == rank
    return pivot;
}

int main(int argc, char **argv) {
    size_t k;
    size_t n_elts;
    scanf("%zd", &k);
    scanf("%zd", &n_elts);
    long *array = malloc(n_elts * sizeof(long));
    if (array == NULL) { err(1, NULL); }
    for (size_t i = 0; i < n_elts; ++i)
        scanf("%ld", &array[i]);

    printf("%ld\n", kth_largest(k, array, n_elts));
}

Major stuff

Consider const

Design: kth_largest() has a side effect of re-arranging array. this is surprising and not part of "Finds the kth largest element of an array in O(n) time."  I'd expect code to do the job without the side effect

// long kth_largest(size_t k, long *array, size_t n_elts) {
long kth_largest(size_t k, const long *array, size_t n_elts) {

Small size error

Code may call err(1, NULL); when n_elts < 5 as malloc(0) can return NULL.  I'd expect code to work for sizes 1 to 4 also.

Doubtful O() claim

"Finds the kth largest element of an array in O(n) time."    Perhaps when n >>> k, but not in general.  I'd expect O(n*k).  So perhaps

Finds the kth largest element of an array in O(n) time when k <<< n
otherwise O(n*k)

No error check

Do not trust user input follows the rules nor allocations always succeed.

long *array = malloc(n_elts * sizeof(long));
if (array == NULL) {
  Handle_Error();
}

for (size_t i = 0; i < n_elts; ++i) {
  // scanf("%ld", &array[i]);
  if (scanf("%ld", &array[i]) != 1) {
    Handle_Error();
  }
}

Minor stuff

object vs type

Rather than size to the type, size ot the object.  Easier to code right, review and maintain.

// qsort(a, n, sizeof(long), compare_longs);
qsort(a, n, sizeof *a, compare_longs);

// long *medians = malloc(n_sublists * sizeof(long));
long *medians = malloc(sizeof *medians * n_sublists);

No need for floating point math

i/2 will already have "floor" the quotient before the floor().  Absolutely no need for floor() and with its potential loss if precision for large i.

// return (size_t)(floor(i/2));
return i/2;

size_t is an unsigned type
Enable all warnings

pos >= 0 is always true below.  A well enabled compilers would have warned.

size_t pos = -1;
...
assert(pos >= 0);

Match specifier and type

"%zd" does not match a size_t.  "%zu" does.  Also implies useful warnings were not enabled.  Save time - enable warnings.  See also How to use “zd” specifier with printf()?/

// scanf("%zd", &k);
// scanf("%zd", &n_elts);
scanf("%zu", &k);
scanf("%zu", &n_elts);

Read until EOF

"I would read until EOF, but then I would have to deal with a growing array, I think." --> Yes, good idea.  Confident this is up to D. Ben Knoble abilities, so will not post code.

Design idea: pass the k as an argv[] and the array via stdin.


Checking if an element exists in an array efficiently and return it I am writing a function for my node/angular app that will prompt the user with a random question that he was not asked before.

To achieve this I wrote this function:

function setQuestion() {
            var q; // question we will eventually ask the user
            for (q in questions) {
                if (!(q._id in questionsUserAlreadyAnswered)) {
                    /* the user has NOT answered this question yet -> so we can ask him now! */
                    $scope.title = q.description;
                    $scope.questionToAsk = q;
                    return;
                }
            }
            /* if we got here it means the user has already answered ALL the questions */
            $scope.title = 'None';
            $scope.questionToAsk = 'None';
}

Here questions is an array of questions (Strings) and so is questionsUserAlreadyAnswered.

I am wondering if this is efficient enough, since I have many questions in the database and the user possibly answered many of them before, so essentially I iterate over all the questions I asked him.(?) twice.

Another way, in addition to the ones Joseph mentioned, you could have a list of questions, and simply remove a question when you ask it.

I.e. something like:

function setQuestion() {
  $scope.question = null;

  if(questions.length) {
    var i = Math.random() * questions.length | 0; // get random index
    $scope.question = questions.splice(i, 1)[0]; // remove question and use it
  }
}

And when the question's answered:

questionsUserAlreadyAnswered.push($scope.question);

This way, you don't need to check multiple arrays.

If you need a "master list", you can do init things like so:

var allQuestions = [...],
    unasweredQuestions = allQuestions.slice(0), // copy array
    answeredQuestions = [];

On another note: Don't use for..in to iterate JavaScript arrays. It doesn't work the same as for..in in other languages. Use a regular for loop or the forEach function.


Should I be using Regex to uppercase uncommon characters? I've written a function for converting strings to upper case. It currently works by replacing each character using a Regex pattern with a hash:

# Special upcase function that handles several Norwegian symbols.
def norwegian_upcase(string)
    string.upcase.gsub(/[æøåäâãàáëêèéïîìíöôõòóüûùúý]/, {
        'æ' => 'Æ',
        'ø' => 'Ø',
        'å' => 'Å',
        'ä' => 'Ä',
        'â' => 'Â',
        'ã' => 'Ã',
        'à' => 'À',
        'á' => 'Á',
        'ë' => 'Ë',
        'ê' => 'Ê',
        'è' => 'È',
        'é' => 'É',
        'ï' => 'Ï',
        'î' => 'Î',
        'ì' => 'Ì',
        'í' => 'Í',
        'ö' => 'Ö',
        'ô' => 'Ô',
        'õ' => 'Õ',
        'ò' => 'Ò',
        'ó' => 'Ó',
        'ü' => 'Ü',
        'û' => 'Û',
        'ù' => 'Ù',
        'ú' => 'Ú',
        'ý' => 'Ý'
    })
end

I have the feeling that it's horribly inefficient to be using Regex like this, and that I should probably be using another method. Can anyone suggest a better way to replace single characters, or is Regex fit for the task?

One-to-one substitution is precisely what tr is for.

def norwegian_upcase(string)
  string.upcase.tr('æ-ý','Æ-Ý')
end

That being said, the unicode_utils gem provides a method for this:

def norwegian_upcase(string)
  UnicodeUtils.upcase(string, :no)
end

I don't know Norwegian, but you can supply language subtags :nb (Norwegian Bokmal) or :nn (Norwegian Nynorsk) if they would behave differently than general :no (Norwegian).


Constructing constrained/validated objects I'm trying to do some rudimentary DDD in validating my objects to ensure they are of a particular type. I.e. an Email object would always look like "my@example.com" and a NaturalNumber is always greater than 0.

However, I'm struggling to make it reusable. The closest I've got is a factory:

open class ConstrainedStringFactory<T>(private val creator: (String) -> T, private val validator: (String) -> Boolean) {
    operator fun invoke(value: String?): T? = value?.let { if (validator.test(it)) creator.apply(it) else null }
}

This can then be included as a companion object by any class wishing to verify it's type:

class Email private constructor(val email: String) {
    companion object Factory: ConstrainedStringFactory<Email>(::Email, { EMAIL_REGEX.matches(it) }) {
        @JvmStatic
        private val EMAIL_REGEX = "^.+@.+\\..+".toRegex()
    }
}

class NonBlankString private constructor(val value: String) {
    companion object Factory : ConstrainedStringFactory<NonBlankString>(::NonBlankString, String::isNotBlank)
}

This does exactly what I want: creating a new object is either valid or it's null (which can be checked safely):

val email = Email("invalid") ?: throw IlllegalArgumentException

Where this falls down is on generalisation. If I have a list of Spring Converter objects, for instance, I need to convert each individually:

Converter<String, NonBlankString> { value ->
    NonBlankString(value) ?: throw IllegalArgumentException("The string cannot be empty")
},
Converter<NonBlankString, String> { nonBlank->
    nonBlank.toString()
},
Converter<String, Email> { value ->
    Email(value) ?: throw IllegalArgumentException("The email is not valid")
},
Converter<Email, String> { email ->
    email.toString()
}

This seems like a lot of duplication given the objects have the same signature. And it can occur in other places. Is there some way to use an interface or a parent class to make this generalise better?

Ignoring any language limitations, something similar to the following which would reduce all the boilerplate is what I'm after:

class Email private constructor(val email: String) extends ConstrainedString(email, { EMAIL_REGEX.matches(it) }) {
}

class NonBlankString private constructor(val value: String) extends ConstrainedString(value, String::isNotBlank) {
}

Converter<ConstrainedString, String> { value ->
    value.toString()
}

Remark on you DDD

I've never thought this is possible:

val email = Email("invalid") ?: throw IlllegalArgumentException

Kotlin was created with the intention of null-safety / explicit nullability, and your factory violates it. It allowes classes to be instanceated directly as NULL - this is really weird and for people admiring and working with Kotlin it's very confusing.

Improve current solution

I don't see an improvement for your current solution. I can only recommend to make a Factory class which would genereate all the boilterplate code for all of your generates classes, including converters. But I have a suggestion...

Suggestion

I would go away from extending a companion object and define 'Nullable' Builders, which inherit from generic one:

abstract class NullableValue<T, D>(
    private val init: () -> T,
    private val value: D,
    private val check: (D) -> Boolean
) {
    fun isValid(): Boolean = check(value)

    fun getOrNull(): T? = if (isValid()) init() else null
}

Define class and the builder:

class Email(val email: String)

class NullableEmail(val email: String) : NullableValue<Email, String>(
    init = { Email(email) },
    value = email,
    check = { "^.+@.+\\..+".toRegex().matches(it) }
)

class NonBlankString(val string: String)

class NullableNonBlankString(val string: String) : NullableValue<NonBlankString, String>(
    init = { NonBlankString(string) },
    value = string,
    check = String::isNotBlank
)

And you can use them:

    NullableEmail("").getOrNull() // will be null
    NullableNonBlankString("abc").getOrNull() // will be NonBlankString.class

    Converter<NonBlankString, String> { value ->
        value.toString()
    }

If you want more reusability, we can use strategy pattern:

interface Nullable<T> {

    fun isValid(): Boolean

    fun getOrNull() : T?
}

abstract class NullableValue<T, D> (
    private val init: () -> T,
    private val value: D,
    private val check: (D) -> Boolean
) : Nullable<T>  {
    override fun isValid(): Boolean = check(value)

    override fun getOrNull(): T? = if (isValid()) init() else null
}

class NullableEmail(val email: String) : Nullable<Email> by NullableByRegex<Email> (
    init = { Email(email) },
    value = email
)


Pouring water between two jugs to get a certain amount in one of the jugs (2) I have been practicing recursion lately and I came up with this code to solve the water jug problem, given two jugs of volume jug1 and jug2, where jug1 < jug2, obtain a volume t, where t < jug2.

The algorithm below basically always pours from the smaller jug into the bigger jug, how would you improve the solution ?

I think I get the minimum number of steps this way... am I correct ?

jug1 = 5
jug2 = 7
t = 4

def jugSolver(amt1, amt2):

    print(amt1, amt2)

    if (amt1 == t and amt2 == 0) or (amt1 == 0 and amt2 == t):
        return

    elif amt2 == jug2:
        jugSolver(amt1, 0)

    elif amt1 != 0:
        if amt1 <= jug2-amt2:
            jugSolver(0, amt1+amt2)
        elif amt1 > jug2-amt2:
            jugSolver(amt1-(jug2-amt2),amt2+(jug2-amt2))

    else:
        jugSolver(jug1, amt2)

jugSolver(0,0)

Your code is not a “good” practice at recursion.  Every “recursive” call to jugSolver is the last statement that is executed in the current call, thus the whole function can easily be replaced by a simple loop:

print(amt1, amt2)
while amt1 != t  and  amt2 != t:
    if amt2 = jug2:
        amt2 = 0
    elif amt1 != 0:
        if amt1 <= jug2 - amt2:
            amt1, amt2 = 0, amt1+amt2
        else:
            amt1, amt2 = amt1 - (jug2-amt2), jug2
    else:
        amt1 = jug1
    print(amt1, amt2)

Your assumption that pouring from the smaller jug into the bigger jug always results in the minimum number of steps is flawed.  Consider t=2.  Your way:

5, 0
0, 5
5, 5
3, 7
3, 0
0, 3
5, 3
1, 7
1, 0
0, 1
5, 1
0, 6
5, 6
4, 7
4, 0
0, 4
5, 4
2, 7

Compare with:

0, 7
5, 2

So you’ll need to relook at solving the problem with different possible moves.


Hacker Rank - Lonely Integer This is the problem statement for Lonely Integer.

  There are N integers in an array A. All but one integer occur in
  pairs. Your task is to find out the number that occurs only once.

  Input Format

  The first line of the input contains an integer N indicating number of
  integers.   The next line contains N space separated integers that
  form the array A.

  Constraints

  1 <= N < 100
  N % 2 = 1 ( N is an odd number )
  0 <= A[i] <= 100, ∀ i ∈ [1, N]

  Output Format

  Output S, the number that occurs only once.

  Example 1

  Input

1
1

  Output

1

  We see only 1 element and that element is the answer (1).

  Example 2

  Input

3
1 1 2

  Output

2

  We see 3 elements, 1 is repeated twice. The element that occurs only
  once is 2.

  Example 3

  Input

5
0 0 1 2 1

  Output

2

  We see 5 elements, 1 and 0 are repeated twice. And the element that
  occurs only once is 2.

//I did not do the constraints
#include <vector>
#include <iostream>
#include <algorithm>

int main() {
    int size;
    std::cin >> size;
    if (size == 1) {
        int lone;
        std::cin >> lone;
        std::cout << lone << '\n';
    } else {
        std::vector<int> numbers(size);
        int index = 0;
        while (std::cin && index != size) {
            std::cin >> numbers[index++];
        }
        std::sort(numbers.begin(),numbers.end());
        for (std::size_t i = 1; i < numbers.size(); ++i) {
            if (numbers[i-1] != numbers[i] && numbers[i] != numbers[i+1]) {
                std::cout << numbers[i] << '\n';
                break;
            }
        }
    }
}

Is this fast enough for extremely large elements? How to make this faster?
Can this be done efficiently without sorting?
How can I improve this code?

Disclaimer : this is not a proper code review.

A different algorithm

There is a O(n) in time and O(1) in space algorithm (and one can easily see that a smaller complexity cannot be achieved).

You just need to XOR all elements so that the one in pairs cancel each other and you are left with the lonely integer.


Formatting a string in Python with three possible replacement fields I'm looking for a much simpler way of formatting a string in Python which will have a different number of replacement fields in different cases. Here's what I'm doing now, which is working fine:

if '{yes}' in reply and '{value}' in reply:
    reply = reply.format(yes=get_yes(), value=value)
elif '{no}' in reply and '{value}' in reply:
    reply = reply.format(no=get_no(), value=value)
elif '{yes}' in reply:
    reply = reply.format(yes=get_yes())
elif '{no}' in reply:
    reply = reply.format(no=get_no())
elif '{value}' in reply:
    reply = reply.format(value=value)

The only problem is that this code has a Cognitive Complexity of 11 on Code Climate, which is higher than the allowed value of 5, and so I'm trying to find out a way of reducing it.

Additional information about variables and methods

reply is a string with will have one of the following combinations of replacement fields:

{yes} and {value}
{no} and {value}
{yes} only
{no} only
{value} only
no replacement field

get_yes() randomly returns a string that has the same meaning as "yes" ("yeah", "yep" etc.)
get_no() randomly returns a string that has the same meaning as "no" ("nah", "nope" etc.)
value is a numeric value (integer or float)

Build a kwargs dictionary, rather than using an if-else.
You don't have to treat yes and no as mutually exclusive.
You could use a 'key, function' list to create a dictionary comprehension that builds the dictionary for you.

This can lead to:

kwargs = {}
if '{value}' in reply:
    kwargs['value'] = value
if '{yes}' in reply:
    kwargs['yes'] = get_yes()
if '{no}' in reply:
    kwargs['no'] = get_no()
reply = reply.format(**kwargs)

params = [
    ('value', lambda:value),
    ('yes', get_yes),
    ('no', get_no)
]

def format_format(format, params):
    return format.format({
        key: fn()
        for key, fn in params
        if f'{{{key}}}' in format
    })

reply = format_format(reply, params)


Reverse Polish Notation calculator in Scala I wrote an RPN solver in Scala. I'd love to get some feedback on approaches to make this feel more idiomatic.

object ReversePolishNotation {
  private object Operator extends Enumeration {
    val Divides = "/"
    val Times = "*"
    val Plus = "+"
    val Minus = "-"
  }

  import Operator._

  private val stringToOperator = Map[String, (Double, Double) => Double] (
    Divides -> {_ / _},
    Minus -> {_ - _},
    Times -> {_ * _},
    Plus -> {_ + _}
  )

  private def foldFunc(acc: List[Double], tok: String) = acc match {
    case Nil | List(_) => tok.toDouble :: acc
    case head::next::rest => tok match {
      case op @ (Divides | Minus | Times | Plus) => stringToOperator(op) (next, head) :: rest
      case s: String => s.toDouble :: acc
    }
  }

  def solve(tokens: Seq[String]) =
  tokens.foldLeft(List[Double]())(foldFunc) match {
    case head::Nil => head
    case Nil => throw new Exception("The stack cannot be empty!")
    case head::next::rest => throw new Exception("The stack should only have one value!")
  }
}

Operator

The main issue about this implementation is that Operator is declared as Enumeration, but indeed does not represent an enum: all the vals are String constants, but not instances of the enumerated type. And this usage is not very appropriate.

Well, enums in Scala are rather different from Java and we cannot easily associate items of an enum with methods: that is what you are trying to do with stringToOperator Map. Generally, it's OK, it works, it remains readable, but the Operator type somehow disappears in the code. If you comment out some lines like this

//  private object Operator extends Enumeration {
val Divides = "/"
val Times = "*"
val Plus = "+"
val Minus = "-"
//  }

//  import Operator._

the code will still compile and work: looks like Operator is not really meaningful in this implementation.

I suggest to create a dedicated type that will provide a means of evaluation of expressions expecting two Double args:

abstract class Operator(operation: (Double, Double) => Double) {
  def eval(left: Double, right: Double): Double = operation.apply(left, right)
}

This type is instantiated with target arithmetic operations, each in a dedicated object:

case object Divides extends Operator({ _ / _ })
case object Times extends Operator({ _ * _ })
case object Plus extends Operator({ _ + _ })
case object Minus extends Operator({ _ - _ })

Now we need to parse a raw token, represented initially as a String. A token can correspond to a numeric value or to an operator. We can use Scala's Either construct to represent this choice:

private def parseToken(tok: String): Either[Double, Operator] = tok match {
  case "/" => Right(Divides)
  case "*" => Right(Times)
  case "+" => Right(Plus)
  case "-" => Right(Minus)
  case _ => Left(tok.toDouble)
}

Consequently, the foldFunc is reduced to one-level matcher for cases from this Either reference:

private def foldFunc(acc: List[Double], tok: String) = parseToken(tok) match {
  case Left(num) => acc :+ num
  case Right(op) => op.eval(acc.head, acc.tail.head) :: acc.tail.tail
}

Exceptions

Exception type is too general and is discouraged to be thrown from any method. Try to find semantically more appropriate existing types. For example, in solve function, if the stack is empty or contains more than two elements, it is in an invalid state. There exists IllegalStateException for that and it might be used.

I'd also suggest more informative messages in the exceptions and probably add more checks for the cases when numbers or operators appear in unexpected positions.


XOR linked list implementation - Follow Up This question is a follow up question to the XOR linked list implementation.
I am posting a new code here with taking into consideration the suggestions of Toby Speight and Deduplicator. Please advise how the code efficiency can be improved.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

struct StNode {
    int value;
    uintptr_t both;
};
typedef struct StNode StHexNode;

StHexNode *add(StHexNode *lastNode, int value)
{
    StHexNode *newNode = malloc(sizeof(struct StNode));
    newNode->value = value;

    //latest node's [both]=pointer value pointing previous node:
    newNode->both = (uintptr_t)lastNode;
    //calculating previous node [both]:
    lastNode->both = (uintptr_t)newNode ^ lastNode->both;
    return newNode;
}

StHexNode *get(StHexNode *headNode, unsigned int index)
{

    StHexNode *prevNode;
    StHexNode *currNode;
    uintptr_t tmp;

    //cur=1, prev=0
    currNode = (struct StNode *) ((headNode->both) ^ 0);
    prevNode = headNode;

    for(int i=2; i<=index; i++)
    {
        tmp = (uintptr_t)prevNode;
        prevNode = currNode;
        currNode = (struct StNode *) (currNode->both ^ tmp);
    }
    return currNode;
}

int free_list(StHexNode *headNode)
{
    StHexNode *prevNode;
    StHexNode *currNode;
    uintptr_t tmp;
    int ctr=0;

    //case: there is a only head node in the list
    if(headNode->both == 0)
    {
        free(headNode);
        return ++ctr;
    }

    //prev=head, curr=second_node
    currNode = (struct StNode *) ((headNode->both) ^ 0);
    prevNode = headNode;

    while(currNode->both != (uintptr_t)prevNode)
    {
        tmp = (uintptr_t)prevNode;
        free(prevNode);
        ctr++;
        prevNode = currNode;
        currNode = (struct StNode *) (currNode->both ^ tmp);
    }
    //last node
    free(currNode);
    ctr++;

    return ctr;
}

int main(void)
{
    unsigned int i;

    //I named first node as headNode, and last node as tailNode
    //create head node with both=0 since there is no previous node to it
    StHexNode *headNode = malloc(sizeof(struct StNode));
    StHexNode *tailNode = headNode; //last node pointer in the list

    //lets add 100 nodes after head
    //special handling of both value at head node
    for(headNode->both = 0, i=100; i<200; i++)
    {
        tailNode = add(tailNode, i);
        //printf("last node value:%d\n", tailNode->value);
    }

     //get index=50 node value
     StHexNode *iNode = get(headNode, 50);
     printf( "result: %d\n",  iNode->value);

     //free memory
     printf("we released %d list\n", free_list(headNode));

    }

Don't use a different name for a struct and its typedef
Why is struct StNode typedef'ed to StHexNode? What does the Hex mean here, I don't see anything hexadecimal or hexagonal in the rest of the code? You can use exactly the same name for a struct as for its typedef, so I would just use that:
typedef struct StNode StNode;

You can also combine the typedef with the struct definition:
typedef struct StNode {
    ...
} StNode;

Use typedefs consistently
I see you use StHexNode in some places, and struct StNode in others. Be consistent and only use the typedef'ed variant.
Avoid repeating type names if possible
In this line:
StHexNode *newNode = malloc(sizeof(struct StNode));

Besides the inconstent use of the typedef, you repeat the type twice. That makes this error prone (if you make a mistake on the right side it will compile without errors but it will probably be wrong), and if you ever have to change the type of the variable newNode, you would have to do it in at least two places. It is better to avoid repeating the type name, but instead repeat the variable name:
StNode *newNode = malloc(sizeof(*newNode));

Prefer using compound assignment operators to avoid repetition
Use compound assignment operators if possible to save some typing, and also avoiding possible mistakes. For example, instead of:
lastNode->both = (uintptr_t)newNode ^ lastNode->both;

Prefer:
lastNode->both ^= (uintptr_t)newNode;

Simplifying get()
You can simplify the function get() somewhat. In particular, when looping over the elements of a list, try to start at index 0, and avoid making the start and end special cases. You can do this here like so:
StNode *get(StNode *headNode, unsigned int index)
{
    StNode *currNode = headNode;
    uintptr_t prev = 0;

    for (int i = 0; i < index; i++)
    {
        uintptr_t next = currNode->both ^ prev;
        prev = (uintptr_t)currNode;
        currNode = (StNode *)(next);
    }

    return currNode;
}

Note that you could even avoid the declaration of currNode if you change the name of headNode to currNode, but I would personally keep it as it is above, as it makes the role of the parameter and the local variable more clear.
Simplifying free_list()
The same goes for free_list(): you should not need to make a list of one element a special case. Also, why is free_list() calculating the number of elements of a list that will have been deleted by the time it returns?
void free_list(StNode *headNode)
{
    StNode *currNode = headNode;
    uintptr_t prev = 0;

    while (currNode)
    {
        uintptr_t next = currNode->both ^ prev;
        prev = (uintptr_t)currNode;
        free(currNode);
        currNode = (StNode *)(next);
    }
}

Use a unique and consistent naming scheme
If you want to use your XOR linked list in a real program, consider that names like StNode and get() are very generic and will likely conflict with other parts of a larger project. Maybe you need a binary tree implementation as well for example, and how are you going to name its function to retrieve an element at a given index? To solve this issue in C, come up with a unique prefix that you can use for all the struct and function names. For example, prefix everything with xllist_:
typedef struct xllist_node {
    ...
} xllist_node;

xllist_node *xllist_add(xllist_node *lastNode, int value);
xllist_node *xllist_get(xllist_node *headNode, usigned int index);
void xllist_free(xllist_node *headNode);

Of course you can argue about what the prefix should be exactly. I find something like xor_linked_list or XorLinkedList a bit too verbose, so xllist is a compromise: it still has list clearly in the name, and if you don't know what xl is you can look it up, and once you have seen what it means it is easy to remember that xl stands for XOR linked I hope.
Create a struct representing the whole list
You have a struct for a node, but not one for the whole list. That means the caller of your functions has to manually allocate the first list element, and it needs to keep track of both the head and tail node. It is much better if you create a struct representing the list:
typedef struct xllist {
    xllist_node *head;
    xllist_node *tail;
} xllist;

And then pass a pointer to this struct to functions like xllist_get(), xllist_add() and xllist_free(), like so:
xllist_node *xllist_add(xllist *list, int value) {
    xllist_node *newNode = malloc(sizeof(*newNode));
    newNode->both = (uintptr_t)xllist->tail;
    newNode->value = value;

    if (xllist->tail) {
        // Append it to the existing tail node
        xllist->tail->both ^= (uintptr_t)newNode;
        xllist->tail = newNode;
    } else {
        // The list was empty
        xllist->head = newNode;
        xllist->tail = newNode;
    }

    return newNode;
}

And you use it like so in main():
xllist myList = {NULL, NULL}; // declare an empty list

for (int i = 100; i < 200; i++)
{
    xllist_add(&myList, i);
}


Implementing a binary operation for the null object pattern Today I needed to implement a class for representing rectangular regions with some binary operations such as merging or intersection.

public class Region
{
    // Properties, such as top-left and bottom-right corner ...
    // Ctors ...

    public Region Merge(Region other)
    {
        // ...
    }

    public Region Insersect(Region other)
    {
        // ...
    }
}

Intersecting two instances of Region unfortunately does not always have a useful result. So my next step was to implement the notion of a NullRegion. It is no problem to implement the NullRegion itself. However, this would require Region to check against NullRegion, as those binary operations are commutative and the order should not matter. (i.e. nullRegion.Intersect(nonNullRegion)should yield the same result as nonNullRegion.Intersect(nullRegion), which is a NullRegion)

The first solution I can think of is to move the implementation of those methods into a seperate class. That way, I only the new class needs to know the NullRegion.

public class Region
{
    // Properties, such as top-left and bottom-right corner ...
    // Ctors ...

    public virtual bool IsNull { get { return false; } }

    public Region Merge(Region other)
    {
        return RegionMethods.Merge(this, other);
    }

    public Region Intersect(Region other)
    {
        return RegionMethods.Intersect(this, other);
    }

    private class NullRegion
    {
        public override bool IsNull { get { return true; } }
    }

    private static class RegionMethods
    {
        public static Region Merge(Region Region, Region otherRegion)
        {
            // ...
        }

        public static Region Intersect(Region Region, Region otherRegion)
        {
            // ...
        }
    }
}

Is this a good way to tackle the problem? What would be my alternatives?

The implementation of a NullRegion, shouldn't be done by a separate class, but by a static property of the same class.
If you overide Equals() and GetHashCode() you can just compare the objects to Region.NullRegion like

public class Region
{
    private static readonly Region nullRegion = new Region();

    private Region()
    {
        Left = 0;
        Top = 0;
        Width = 0;
        Height = 0;
    }
    public Region(Point point, Size size)
    {
        Left = point.X;
        Top = point.Y;
        Width = size.Width;
        Height = size.Height;
    }
    public static Region NullRegion
    {
        get
        {
            return nullRegion;
        }

    }
    public int Left { get; set; }
    public int Top { get; set; }
    public int Width { get; set; }
    public int Height { get; set; }

    public Region Merge(Region other)
    {
        if (this == Region.NullRegion || other == Region.NullRegion)
        {
            return Region.NullRegion;
        }
        // default Merge() implementation here
    }
    public Region Intersects(Region other)
    {
        if (this == Region.NullRegion || other == Region.NullRegion)
        {
            return Region.NullRegion;
        }
        // default Intersects() implementation here

    }
    public override bool Equals(object obj)
    {
        //Implementation of your Equals() here
        return base.Equals(obj);
    }
    public override int GetHashCode()
    {
        //Implementation of your GetHashCode() here
        return base.GetHashCode();
    }
}


HTML table representing a database table and a sidebar I have an HTML table representing a database table and a sidebar which holds different anchors ready to perform CRUD operations on click.

Because the hrefs in the anchors aren't general valid for all columns I have written a script which automatically inserts the id of a selected column into the hrefs:

/localhost/image/var/edit => /localhost/image/4/edit

The code I have written works but it isn't very clean and smart.  Could somebody take a look and say where I have space of improvement?

<script type="text/javascript" src="{{ asset('bundles/acme/js/jquery.js'></script>
<script type="text/javascript">
$('table tr').click(function(){
    $('.selected').removeClass('selected');
    $(this).addClass('selected');
    var name = $(this).find('td:nth-child(2)').html();

    $('.image_bar ul li a').each(function(){
        var oldUrl = $(this).attr('href');
        var newUrl = oldUrl.replace('var', name);
        $(this).attr('href', newUrl);
    });
});
</script>

I do not like too much this:

var name = $(this).find('td:nth-child(2)').html();

I would generally use html5 data attribute on the tr row to pass the id.

example:

bla	bla	bla

bla	bla	bla

var selectedId = $(this).data("id");


Using case and switch macros for strings I'd like this reviewed.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SWITCH(S) char *_S = S; if (0)
#define CASE(S) } else if (strcmp(_S, S) == 0) {switch(1) { case 1
#define BREAK }
#define DEFAULT } else {switch(1) { case 1

int main()
{
    char buf[256];

    printf("\nString - Enter your string: ");
    scanf ("%s", buf);

    SWITCH (buf) {
        CASE ("abcdef"):
            printf ("B1!\n");
            BREAK;
        CASE ("ghijkl"):
            printf ("C1!\n");
            BREAK;
        DEFAULT:
            printf ("D1!\n");
            BREAK;
    }
}

switch is usually assumed to have nearly O(1). I'm suggesting to introduce additional level for parsing. It is known as lexical analysis. You parse you fixed set of cases to enum values and then switch as you want.

enum { B1, C1, D1 } token_t;

token_t lexer(const char *s)
{
    // TODO: consider hash table here
    static struct entry_s {
        const char *key;
        token_t token;
    } token_table[] = {
        { "abcdef", B1 },
        { "ghijkl", C1 },
        { NULL, D1 },
    };
    struct entry_s *p = token_table;
    for(; p->key != NULL && strcmp(p->key, s) != 0; ++p);
    return p->token;
}

int main()
{
    char buf[256];

    printf("\nString - Enter your string: ");
    scanf ("%s", buf);

    switch(lexer(buf)) {
        case B1:
            printf ("B1!\n");
            break;
        case C1:
            printf ("C1!\n");
            break;
        case D1:
            printf ("D1!\n");
            break;
    }
}

Note that your SWITCH(S) will work only in C++ since C doesn't allow variables definition in the middle of blocks. Usually such macro uses something like:

#define BEGIN_SEPARATION(S, T) { const char *_tail = (T), *_sep = (S); \
    size_t _sep_len = strlen(_token); \
    for(const char *_next = strstr(_tail); _tail != NULL; _tail = (_next != NULL) ? _next + _sep_len : NULL) {
#define SEPARATION_TOKEN() (_next == NULL ? strdup(_tail) : strndup(_tail, _next - _tail))
#define END_SEPARATION } }

And as far as I know it's common practice to wrap macro arguments (i.e _S = (S);).


Avoiding object slicing within abstractions and their derivations I've created a rudimentary example of the issue I'm inquiring about: Object slicing. I followed a post on Stack Overflow which provided a similar template - and for all intents and purposes, this works. I was just wondering if this would get me into a trouble longer down the line? Is there anything here that jumps out at you as dangerous and/or wrong?

The heart of the logic is in main(). I'm pushing a Circle object into a Shapes* vector, then push the new Shapes* element into a Circle vector. The issue I had WITHOUT the assignment operators, was that the compiler couldn't decide how to convert Shape* to Circle.

Please let me know if there are any glaringly obvious improvements.

class Shape {
public:
    virtual Shape& operator=(const Shape& s) {
        assign(s);
        return *this;
    }

    virtual std::string getName() = 0;
    virtual         int getEdges() = 0;

protected:
    std::string name;
    int         edges;

    void assign(const Shape& s) {
        this->name = s.name;
        this->edges = s.edges;
    }
};

class Circle : public Shape {
private:
    int radius;
public:
    Circle() { name = "Circle"; edges = 1; }
    Circle(int rad) { name = "Circle"; edges = 1; radius = rad; }

    virtual Circle& operator=(const Shape& s) {
        if (const Circle* c = dynamic_cast<const Circle*>(&s))
            assign(*c);
        else{
            std::cout << "BAD ASSIGNMENT IN CIRCLE.";
                    //THROW ERROR HERE INSTEAD OF THE ABOVE COUT
            }
        return *this;
    }

    std::string getName() { return name; }
            int getEdges() { return edges; }
            int getRadius() { return radius; }
           void setRadius(int r) { radius = r; }

protected:
    void assign(const Circle& c) {
        Shape::assign(c);
        this->radius = c.radius;
    }

};

int main() {
    std::vector<Shape*> shapes;
    std::vector<Circle> circs;
    Circle c2(5); //Creates a circle with 5 for the radius.

    shapes.push_back(&c2); //Pushing the 5-radius circle into the Shapes* vector
    Circle c3; //Creates a circle with default constructor (which does NOT define radius)
    c3 = *shapes[0]; //Now, the overloaded assignment operator. Look at Circle::assign(const Shape&) function
    circs.push_back(c3); //We push our newly assigned circle to our Circle vector
    std::cout << "c3 radius: " << circs[0].getRadius(); //This will be 5!
}

Allowing a Shape to be assigned to a circle does not sound like it is very safe. I suppose there are situations where it can be used but I would advice against it in the general case
Also I would use Curiously Recurring Template Pattern to get around having to write the assignment operator-er in every derived class.
class Shape
{ // STUFF
};

template<typename T>
class ShapeCopyable: public Shape
{
    T& operator=(const Shape& s)
    {
        T const& c = dynamic_cast<T const&>(s);  // Throws on bad cast.
        assign(c);

        return *this;
    }
};
class Circle: public ShapeCopyable<Circle>
{
    // Stuff
};

In addition to what @Chris Jester-Young covered (so everything he said):
The Base class of a hierarchy with virtual methods should also have a virtual destructor. Otherwise you are going to start having issues with memory management when you start dynamically creating objects on the fly.
class Shape {
public:
    virtual ~Shape() {}

Don't define the copy constructor or assignment operator if nothing special needs to be done. Let the compiler generated version do the work for you. Unless you have something special in the destructor or have RAW pointer members this is unlikely. PS you should not have RAW pointer members either.
    // Remove this:
    virtual Shape& operator=(const Shape& s);

Don't like getters/setters. They break encapsulation and expose the internal implementation of the object. You should consider why you need to pass the state of the object out (is the function that uses the values really a member function).
Interactions on the object should usually be done internally to the object. This will get rid of most of your needs for getters and setters. If you still have a need after the analysis fine.
    // Don't like them.
    // Make but sometimes you need them but minimze your
    // exposure by using methods that manipulate the object rather
    // than moving the manipulation to an external actor.
    std::string getName() { return name; }
            int getEdges() { return edges; }
            int getRadius() { return radius; }
           void setRadius(int r) { radius = r; }

A vector of pointers. Red flag who owns the pointers.
    std::vector<Shape*> shapes;

A'hh you are pushing stack objects onto the vector.
    shapes.push_back(&c2);

Maybe it should be a vector of reference wrapper to Shape std::vector<std::reference_wrapper<Shape>>.
Getting a circle from a shape.
    c3 = *shapes[0];

Not sure that should really happen. The interface to Shape should be how you manipulate the object. Needing to convert the object to a circle seems unnecessary in most situations (you should probably have virtual functions that do the actions you need). Sometimes things have unique actions then you need to convert them back.But in these situations just use dynamic_cast directly (this also shows you are doing the conversion very explicitly).
Based on comments below:

I will need to pull name's and description's to display to the user

Its easier to ask the object to display itself rather the pull details about the object and then display them.
The simplist example is just printing information to a stream:
// Original Way
Circle    c(5);
std::cout << "Circle: "  << c.getName()
          << " Edges: "  << c. getEdges
          << " Radius: " << c.getRadius()
          << "\n";

// What I would do is make the serialization of the object to a stream
// a member method that does the work.

class Shape
{
    virtual void print(std::ostream& stream) const = 0; // Can print a Shape
                                                  // Must be specialized for
                                                  // Specific types.

    friend std::ostream& operator<<(std::ostream& stream, Shape const& shape)
    {
        shape.print(stream);
        return stream;
    }
};

// Now you print like this:
Circle    c(5);
std::cout << c << "\n";

You don't need to expose the members just because you need serialization. Doing it this ways adds consistency so that all objects of a particular type are serialized in the same way. If you need to change what it looks like you have a single place in the code that needs modifying.
We can extend the above to other graphical representations.
struct DisplayInterface
{
     // This is an interface for drawing shapes on a display.
     // You can imagine it has the standard drawing functions.
     // But imagine a base set.
     void drawLine(Pt const& tr, Pt const& bl);
     void drawCircle(Pt const& tr center, unsigned int radius);
     void drawPolygon(std::vector<Pt> const& pts);
     void drawText(Pt const& bl, unsigned int fontSize, std::string const& str);
};

// Now in your drawing code you pass the DisplayInterface to the object
// So it can draw itself. So usually the drawing system provides an
// interface that all drawable objects need to implement.

struct Drawable
{
    virtual void display(DisplayInterface& di) = 0;
};

class Shape: public Drawable  // All shapes are drawable
{                             // But each shape must implement
                              // Its own display()
};

class Circle: public Shape
{
     virtual void display(DisplayInterface& di)
     {
          di.drawCircle(Pt(0,0), radius);
          di.drawText(Pt(0,15), 12, name);
     }
};


Choice of tables for a project to handle attendance I'm working on my students attendance system project. I have a list of students along with their ID (jntuno) and I need to create a database in MySQL for storing the daily attendance of each student for each subject.
Table: students
Fields:
slno int(5) auto increment,
jntuno char(15),
name char(50),
primary key(slno,jntuno).

Data:

This students table holds the list of students and their IDs.
Now I created another table:
Table: dailyatt
Fields:
date date,
subject char(10),
classesconducted int(2),
`11341A0501` int(2),
`11341A0502` int(2),
`11341A0503` int(2),
.
.
.
`11341A0537` int(2),
primary key(date,subject).

This table will look like:

+------------+-----------+-----------------+------------+-----------+-----------+
|date        |subject    |classesconducted |11341A0501  |11341A0502 |11341A0503 |....
+------------+-----------+-----------------+------=-----+-----------+-----------+
|            |           |                 |            |           |           |

Now every day upon entering the attendance on the PHP website, a new row will be created for each subject taught on that day.
But many said that the database model is not a good one. Can someone suggest a better model for this kind of problem?

Please use sensible names for your column names. Even though I read you explanation I can only vaguely guess what slno and jntunno might mean. I assume jntunno is some sort of student id (that's what I'm guessing from the student table - each student seems to have a unique one) - so what about studentid? I assume slno is simple primary id - so why no name it id?
Your dailyatt table has a column for each student (based on my assumptions above). I assume it is supposed to show which student has attended a specific class at a specific date. Now what happens if you add a new student - you will have to add a new column to your db schema, and another one, and another one ....

Furthermore the new students might not have been enrolled for older classes yet when you add a new column you have to choose a value for old attendances. So you start making special values for that case.

Also try creating a query like How many students have attended a specific class. It will end up looking like this select 11341A0501+11341A0502+... from dailyatt where ... - not very nice.

In other words: Yes, it's a bad idea for more than one reason.

When designing a schema and you try to think in terms of objects or concepts then a table should describe that object or concept - meaning the columns should be the properties of it and the rows should be the various instances of it. So I'd make three tables:

courses - describes courses (id, name, subject/description)

classes - describes classes (id, date and time, courseid) (so this table holds all the classes held for a specific course)

classattendance - student attendance for a specific class (id, classid, studentid)

Then you could do a select count(*) as numStudentsAttended from classattendance where classid = 1234 to find how many student attended a specific class for example.


Compile SASS files in a directory via Gulp.js tasks, one of which produces logging output If the default task is executed here, the file name to be compiled is passed to the argument of the CompileSass function. When the sass task is executed, the callback function to be executed at the end is passed by gulp.

The CompileSass function logs the file name when it is passed. Also, when anything other than the file name is passed, the log output will not be performed with the CompileSass function.

This is easily done by determining the argument with the typeof operator.

function CompileSass(filePath) {
    const time = process.hrtime();
    const isFilePath = typeof filePath === "string";
    if (isFilePath) { // same if condition
        console.log("compiling now");
    }
    return src(path["sass"])
        .pipe(sass({outputStyle: "expanded"}))
        .on("end", () => {
            if (isFilePath) { // same if condition
                console.log(`Compiled '${filePath}' now`);
            }
        })
        .pipe(dest("css"))
        .on("end", () => {
            if (isFilePath) { // same if condition
                const TaskTime = prettyTime(process.hrtime(time));
                console.log(`Finished compiled ${TaskTime}`);
            }
        });
}

exports.default = () => {
    watch(dir).on("all", (directory) => {
        CompileSass(directory);
    });
};

exports.sass = series(CompileSass); // in fact, there is other tasks in series function's argument

However, this if statement is repeated even though the log output conditions are the same. I wanted to consolidate this if statement in one place. But I couldn't come up with a good idea for that. I believe that increasing package dependencies leads to management complexity, so I am reluctant to introduce new packages whenever possible.

Is there a good way to make the conditional branch for log output common in the gulp method chain?

Interesting question;

some review remarks before addressing your actual question:

You never seem to pass filePath to src but use path["sass"] instead
I always suggest to pipe your console.log calls through a log function that accepts a severity parameter so that you can customize the level of logging, but that's probably overkill for Gulp

I would add a new function that does nothing, called doNothing() and then up front point an output function to either doNothing() or console.log().

function doNothing(){
  //Do nothing
}

function CompileSass(filePath) {
    const time = process.hrtime();
    const out = (filePath === "string") ? console.log : doNothing;
    out("compiling now");

    return src(path["sass"])
        .pipe(sass({outputStyle: "expanded"}))
        .on("end", () => {
            out(`Compiled '${filePath}' now`);
        })
        .pipe(dest("css"))
        .on("end", () => {
            out(`Finished compiling ${prettyTime(process.hrtime(time))}`);
        });
}

exports.default = () => {
    watch(dir).on("all", (directory) => {
        CompileSass(directory);
    });
};

exports.sass = series(CompileSass); // in fact, there is other tasks in series function's argument


Comments on my Java pattern for Mutable turned Immutable objects Commenting omitted to give you the idea.  I've been toying with this recently as a variant of the Builder pattern.  I've recently fallen in love with immutable objects for the benefits they give in larger concurrent systems.

Questions:

Is there a way to do this without having to instantiate two Objects? (ie. Something.Mutable extends Something but adds setters, while preserving final on the underlying fields once the object gets finalized?

If I have to instantiate two Objects, can I keep final on their somehow and not repeat myself in the contained Builder Object?

public class Something {
    private final int someInteger;
    private final String someString;
    public Something(int someInteger, String someString) {
        this.someInteger = someInteger;
        this.someString = someString;
    }
    public int getSomeInteger() { return someInteger; }
    public String getSomeString() { return someString; }

    public static class Mutable {
        private int someInteger;
        private String someString;
        public Something.Mutable() {}
        public int getSomeInteger() { return someInteger; }
        public String getSomeString() { return someString; }

        public Something.Mutable setSomeInteger(int someInteger) {
            this.someInteger = someInteger;
            return this;
        }
        public Something.Mutable setSomeString(String someString) {
            this.someString = someString;
            return this;
        }

        public Something build() {
            return new Something(someInteger, someString);
        }
    }
}

Here is an example of me using it:

Something something = new Something.Mutable()
        .setString("hi")
        .setInteger(42)
        .build();

If you really want to avoid object creation, you have no other choice as dropping final, e.g.:

public interface Something {

    public int getSomeInteger();
    public String getSomeString();

    public static class Mutable implements Something {
        private int someInteger;
        private String someString;
        private boolean open = true;

        public int getSomeInteger() {
            return someInteger;
        }

        public String getSomeString() {
            return someString;
        }

        public Something.Mutable setSomeInteger(int someInteger) {
            assert open;
            this.someInteger = someInteger;
            return this;
        }

        public Something.Mutable setSomeString(String someString) {
            assert open;
            this.someString = someString;
            return this;
        }

        public Something make() {
            open = false;
            return this;
        }
    }
}

But this pattern is brittle, and the Java runtime is pretty good in dealing with object creation these days, so if you don't write a graphic or math lib or so, you shouldn't care about.


Form validation - security and input specification So I'm working on a register form and I have four fields: name, username, email and password. I pick up the values of these fields in jQuery and depending on if all the fields are filled, I pass them onto a PHP script via ajax. Is that safe for form validations? I was worried about data getting manipulated by the user.

Further on in the php script, I check if all the posted values have data in them, only then will I proceed onto doing some validations... The validations are the parts where I'm worried that it's not the best and there are many flaws with it.

$name = $_POST['name'];
$username = $_POST['username'];
$email = $_POST['email'];
$password = $_POST['password'];

if (!preg_match("/^[A-Za-z '-]+$/i", $name)) {

    $errors = "Please enter a valid name.";

} else if (!preg_match("/^[A-Za-z]+\s[A-Za-z]+$/", $name)) {

    $errors = "Please enter your first and last name.";

} else if (strlen($username) <= 3 || strlen($username) > 15) {

    $errors = "Please pick a username between 4 - 15 characters. Be creative.";

} else if (!preg_match("/^[A-Za-z][A-Za-z0-9_.-]{4,15}$/", $username)) {

    $errors = "Please pick an alphanumeric username between 4 - 15 characters.";

} else if (filter_var($email, FILTER_VALIDATE_EMAIL) === false) {

    $errors = "Please enter a valid email.";

} else if (strlen($username )< 6 || strlen($username) > 32) {

    $errors = "Your password must atleast be 6 characters.";

} else {

    echo "valid";

}

Are these validation steps secure? Are there any loop holes that the user can manipulate the data?

The requirements for the fields are as follows - which im not so sure i hit on the head with my code: - The username should have alphanumeric characters with underscores (optional) - the name should have BOTH the first name and the last name

Thank you.

I take it you're trying to protect yourself from XSS attacks, injection and general mallicious input. You're well on your way (but do have a look here, there are some interesting links at the bottom).

That said, I'd say your validation needs work on a couple of (crucial) points:

Don't be too strict: /^[A-Za-z '-]+$/i for a name doesn't allow "pièrre joão", but it clearly is a name. Just match all unicode chars, and drop the i flag, or change [A-Za-z] to [a-z]. I'd suggest you using this code: $name = trim($name); preg_match('/^[\w \'-]+$/u', $name). read about the u modifier here
Be consistent: You're applying 2 patterns to $name: /^[A-Za-z '-]+$/i and /^[A-Za-z]+\s[A-Za-z]+$/ This means that, the second time dashes and accents aren't allowed. That's not good, not good at all. If needs must, explode the $name on ' ' (a space), and apply the first pattern to each name individualy. Or work on the regex some more.
/^[A-Za-z][A-Za-z0-9_.-]{4,15}$/: This doesn't allow a 4 char long username, but requers the username to be at least 5 chars long: [a-z] matches 1 char, [a-z0-9_.-]{4,15} followed by at least 4, at most 15 chars. Now that's not bad, but it's not what you want.
Validate the right things: near the end, you do some checks on the password, but you're using the $username variable... typo?
Don't limit the length of a password: strlen($username) > 32? Why? If the client wants to use a longer (and possibly stronger) password, let them do so...
If you're going to do some checks on the password, at least to make sure that they're using chars, numbers and symbols. Not just "somealllowercasepass", but "S0m3@llw@kkyp@55"

Like I said above, you're missing out on some things, too:

No where are you calling strip_tags to ensure any markup is being removed from input
The password validation isn't applied to the correct variable, and should be improved, too
Your error messages are waay too specific. That's a bad idea! If I had bad intentions, and tried to fill in the form, each time trying some XSS trickery, and you give me feedback as in: "username mustn't contain chars like <, >, /, \, #, %", I can move on and try to exploit the next input field, and make sure I fill in a valid username, until I find a field where you let your guard down...
Keep your error messages general: "Not all input was correct/the expected format/met the requirements". That should be enough. But as DmitriZaitsev says: be careful not to alienate/offend the end-users, or your queste for safety might backfire (and leave you with no data to protect). A simple way of validating the email address and not restricting the username is to use the email address as username. If google and SO do it, why can't you?


Merges given list of integer entries acccordingly I am developing a 2048 program in Python. As a part of that project, I am working on merging method that merges the given integer entries.

I am interested in some suggestion to improve my code.

def creating_resulting_list(length_line):
    """
    Function that create a resulting_list with equal number of \
    zeros as length of line
    """
    from itertools import repeat
    return list(repeat(0, length_line))

#BEGIN Test
#print creating_resulting_list(2) == [0, 0]
#print creating_resulting_list(0) == []
#END Test

def moving_non_zeros(line, resulting_list):
    """
    Function that moves non zero entries in line \
    to left most in resulting_list
    """
    if not all(line):
        index_resulting_list = 0
        for dummy_value in line:
            if dummy_value:
                resulting_list[index_resulting_list] = dummy_value
                index_resulting_list += 1
    else:
        resulting_list = line[:]
    return resulting_list

#BEGIN Test
#result_list = moving_non_zeros([4, 0, 4, 4], creating_resulting_list(4))

#result_list = moving_non_zeros([16, 16, 4, 4], creating_resulting_list(4))
#END Test

def locating_same_values(result_list):
    """
    Function that locates and merges the same values
    """
    for dummy_index, dummy_value in enumerate(result_list):
        if dummy_index+1 < len(result_list) and dummy_value == result_list[dummy_index+1]:
            result_list[dummy_index] += result_list[dummy_index+1]
            result_list[dummy_index+1] = 0
            if not len(result_list[dummy_index+1:]) > 2:
                return moving_non_zeros(result_list, creating_resulting_list(len(result_list)))
    return result_list

#BEGIN Test

print locating_same_values([16, 16, 4, 4])
print locating_same_values([2, 2, 2, 2, 2])
#END Test

def merge(line):
    """
    Function that merges a single row or column in 2048.
    """
    result_list = creating_resulting_list(len(line))
    result_list = moving_non_zeros(line, result_list)
    return locating_same_values(result_list)

I'm just going to review creating_resulting_list.

def creating_resulting_list(length_line):
    """
    Function that create a resulting_list with equal number of \
    zeros as length of line
    """
    from itertools import repeat
    return list(repeat(0, length_line))

#BEGIN Test
#print creating_resulting_list(2) == [0, 0]
#print creating_resulting_list(0) == []
#END Test

There's no need to use backslashes at the ends of lines inside a triple-quoted string.
The name creating_resulting_list doesn't help the reader understand what it does. What is a "resulting list" anyway? What this function does is to create a list of zeros. So a better name would be zeros_list or just zeros (see for example numpy.zeros, which is similar).
The argument is called length_line. But this is too specific: nothing in this function cares about lines. By avoiding dependencies like this, you can make code more self-contained and easier to understand in isolation. So I would call this argument just length.
Since the import statement is inside this function, it gets run every time the function is called. If you moved this statement to the top level of your module, then it would be run only once.
The test cases should be made automatically runnable, using the unittest or doctest modules. I'll show below how to do it using the latter.
The sequence documentation says:

  s * n or n * s    equivalent to adding s to itself n times

so you don't need itertools.repeat, you can just multiply.

Revised code with doctests:

def zeros(length):
    """Create and return a list of zeros with the given length.

    >>> zeros(2)
    [0, 0]
    >>> zeros(0)
    []

    """
    return [0] * length

The doctests can be run using python -m doctest program.py.


Using namedtuple for slice of class I am working with very large datasets in a distributed environment. In particular, I am writing some code in Python for analyzing web logs in Spark. Because of the nature of Map-Reduce computing and the size of the logs I am working with, I would like to restrict the amount of data being passed around as much as possible.

For any given analysis, I am likely to only be interested in a few fields out of the several dozen available, some of which are very large. I don't want to store the whole object in memory; I only want a pared-down version containing the fields I'm interested in.

A simple data structure like a list would be possible, but it would be convenient to be able to refer to fields by name rather than keep track of what position they've been placed in the list. A dict would allow this, but with the heavy overhead of storing key names for each log line. This led me to namedtuple.

So here's a simplified example of what I have in mind. I have four main concerns (but any other tips are welcome, as I am quite new to Python):

Is using namedtuple here the best choice? (As opposed to, possibly, another object with only a few fields initialized.)
Is this going to create a new namedtuple type for each line, thus creating a new list of field names each time and defeating the purpose of avoiding dict?
The parsing method makes me long for an auto-increment syntax, so perhaps I'm missing a more pythonic way of doing it
This method does not seem to offer a clean way of including individual values from the properties dictionary

The code:

import ast
from collections import namedtuple
from IPy import IP

class LogRecord:
    def __init__(self, line):
        self.parse(line)

    def parse(self, line):
        fields = line.split('\t')
        i = 0
        self.version = fields[i]

        i += 1
        self.date = fields[i]

        i += 1
        self.time = long(fields[i])

        i += 1
        self.ipAddress = IP(fields[i])

        i += 1
        self.url = fields[i]

        i += 1
        self.userAgentString = fields[i]

        i += 1
        self.properties = ast.literal_eval(fields[i])

        i += 1
        self.customerId = fields[i]

    def select(self, *fields):
        d = { key: getattr(self, key) for key in fields }
        Tuple = namedtuple('Tuple', fields)
        return Tuple(**d)

l = LogRecord("8.53\t2014-12-13\t1420007099253\t127.0.0.1\thttp://www.google.com/abc/123\tMozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/37.0.2062.120 Safari/537.36\t{'x': 11, 'y': 22}\tx97ag89x77d")

print l.select('version', 'url', 'customerId')

When run, it produces the following output:

Tuple(version='8.53', url='http://www.google.com/abc/123', customerId='x97ag89x77d')

Just a few ideas

You could use tuple unpacking to make parse more concise.

class LogRecord:
    def __init__(self, line):
        self.parse(line)

    def parse(self, line):
        fields = line.split('\t')
        self.version, self.date, time, self.ipAddress, self.url, self.userAgentString, properties, self.customerId = fields
        self.time = long(time)
        self.properties = ast.literal_eval(properties)

    def select(self, *fields):
        d = { key: getattr(self, key) for key in fields }
        Tuple = namedtuple('Tuple', fields)
        return Tuple(**d)

Alternatively, you could define a list of (name, function to apply) and iterate through both lists in the same with zip to fill a dictionary.

class LogRecord:
    def __init__(self, line):
        self.parse(line)

    def parse(self, line):
        identity = lambda x: x
        desc = [('version', identity), ('date', identity), ('time', long), ('ipAddress', identity), ('url', identity), ('userAgentString', identity), ('properties', ast.literal_eval), ('customerId', identity)]

        fields = line.split('\t')
        assert len(desc) == len(fields)
        self.values = {name: func(field) for (name, func), field in zip(desc, fields)}

    def select(self, *fields):
        d = { key: self.values[key] for key in fields }
        Tuple = namedtuple('Tuple', fields)
        return Tuple(**d)


Why is my Bubblesort implementation faster than my Quicksort code? Here is my Bubblesort code:

public static List<int> BubbleSort(List<int> _digitList)
      {
          List<int> digitList = _digitList;
          bool didSwap = true;

          while (didSwap)
          {
                didSwap = false;
                for (int i = 0; i < digitList.Count - 1; i++)
                {
                    if (digitList[i] > digitList[i + 1])
                    {
                        int temp = digitList[i];
                        digitList[i] = digitList[i + 1];
                        digitList[i + 1] = temp;

                        didSwap = true;
                    }
                }
          }
          return digitList;
      }

And here is my Quicksort Method, which is actually an implementation of the pseudocode on Wikipedia:

public static List<int> Quicksort(List<int> array)
        {
            if (array.Count <= 1)
            {
                return array; //An array of Zero ot one elements is already sorted
            }

            int pivot = 0;
            List<int> less = new List<int>();
            List<int> greater = new List<int>();

            for (int i = 1; i < array.Count;i++ )
            {
                if (array[i] <= array[pivot])
                {
                    less.Add(array[i]);
                }
                else
                {
                    greater.Add(array[i]);
                }
            }

            List<int> combined = Quicksort(less);
            combined.Add(array[pivot]);
            combined.AddRange(Quicksort(greater));

            return combined;

        }

So for the List = {211, 16, 42, 166, 192, 2, 13, 81, 6, 1, 5, 115, 17, 67}; I get following Stopwatch values.

Bubblesort:

  00:00:00.0002873

Quicksort:

  00:00:00.0003831

Does this mean my Quicksort code is poor or did I misunderstand the Stopwatch concept?

It is normal in production quality qsort code to switch to another sorting method (maybe a unrolled bubble sort) when the size of the input is small (often 8 is used).    QSort has very high overheads, but scales well, for a small input size the overheads are much more important than the scaling.

If you run your code on an input that is 1000 items long, then I expect that your qsort would be faster than your bubble sort.

Try writing a test problem that increases your input size in steps of 100 and then graph the results with both sorting methods.

The other way to look at it, is to find the largest input that each sort method can sort in say 5 seconds.

Also your qSort could be written to be a lot faster by not creating 3 new Lists, it is also very important to quickly choose a good item to privet on.   You do not even set the size of the list when you create them, hence each list will have to be reallocated and copied many times as you add items to it.

You have a qSort that is implemented is an inefficient way compared to a boubleSort that is close to the best implementation for boubleSort.

Yet as you confirmed in your comment the qSort does better when you have over 10000 items, slowing just how much better qSort scales.