Binary search in rotated sorted array Looking for code review, optimizations, good practice recommendations etc.

/**
 * This is utility class for operations on rotated one-d array.
 *
 * Note: a sorted array, reverse-sorted or a single element is array is not considered rotated sorted.
 * Eg:
 * [4, 5, 1, 2, 3] is condidered rotated.
 * While.
 * [1, 2, 3, 4, 5] is not considered rotated
 *
 *
 * Complexity: O (log n)
 */
public final class RotatedOneDSortedArray {

    private RotatedOneDSortedArray() { }

    /**
     * Searches for the value provided in the rotated sorted array.
     * If found, returns the index, of provided array, else returns -1.
     * If array is not rotated and sorted, then results are unpredictable
     *
     * Throws an exception if array is null.
     *
     * @param a the rotated sorted array
     * @param x the element to be searched
     * @returns the index at which the element is found, else returns -1
     */
    public static int binarySearchForRotatedArray(int[] a, int x) {
        int partitionIndex = findPartition(a, 0, a.length - 1);

        if (partitionIndex == -1) return -1;

        if (x >= a[0] && x <= a[partitionIndex]) {
            return binarySearch(a, 0, partitionIndex, x);
        } else {
            return binarySearch(a, partitionIndex + 1, a.length -1, x);
        }

    }

    private static int binarySearch (int[] a, int lb, int hb, int x) {
        assert a != null;

        if (lb > hb) return -1;

        int mid = (lb + hb)/2;

        if (a[mid] == x) return mid;

        if (a[mid] < x) {
            return binarySearch(a, mid + 1, hb, x);
        } else {
            return binarySearch(a, lb, mid - 1, x);
        }
    }

    /**
     * Returns the index of greatest element of the rotated sorted array.
     * if array is not rotated sorted, results are unprodictable
     *
     * @param a     the input array
     * @param lb    the lower bound
     * @param hb    the higher bound
     * @return      the index of the highest element in the array.
     */
    private static int findPartition(int[] a, int lb, int hb) {
        assert a!= null;

        if (lb == hb) return -1;

        int mid = (lb + hb)/2;

        if (a[mid] > a[mid + 1]) {
            return mid;
        }

        if (a[mid] > a[hb]) {
            // go right.
            return findPartition(a, mid + 1, hb);
        } else {
            // go left.
            return findPartition(a, lb, mid); // note i cannot do mid - 1
        }
    }

    public static void main(String[] args) {
        // even length of the array.
        int[] a1 = {6, 7, 8, 1, 2, 3};
        System.out.println("Expected -1, Actual : " + binarySearchForRotatedArray(a1, -1));
        int[] a2 = {6, 7, 8, 1, 2, 3};
        System.out.println("Expected 1, Actual : " + binarySearchForRotatedArray(a2, 7));
        int[] a3 = {6, 7, 8, 1, 2, 3};
        System.out.println("Expected 5, Actual : " + binarySearchForRotatedArray(a3, 3));
        int[] a4 = {6, 7, 8, 1, 2, 3};
        System.out.println("Expected 2, Actual : " + binarySearchForRotatedArray(a4, 8));
        int[] a5 = {6, 7, 8, 1, 2, 3};
        System.out.println("Expected 3, Actual : " + binarySearchForRotatedArray(a5, 1));

        // odd length of the array.
        int[] a6 = {4, 6, 7, 8, 1, 2, 3};
        System.out.println("Expected -1, Actual : " + binarySearchForRotatedArray(a6, -1));
        int[] a7 = {4, 6, 7, 8, 1, 2, 3};
        System.out.println("Expected 2, Actual : " + binarySearchForRotatedArray(a7, 7));
        int[] a8 = {4, 6, 7, 8, 1, 2, 3};
        System.out.println("Expected 6, Actual : " + binarySearchForRotatedArray(a8, 3));
        int[] a9 = {4, 6, 7, 8, 1, 2, 3};
        System.out.println("Expected 3, Actual : " + binarySearchForRotatedArray(a9, 8));
        int[] a10 = {4, 6, 7, 8, 1, 2, 3};
        System.out.println("Expected 4, Actual : " + binarySearchForRotatedArray(a10, 1));
    }
}

As mentioned in my comment, the structure you are dealing with is more commonly called a circular buffer. The Wikipedia link has several examples on how to efficiently provide thread safe read/write access (a producer/consumer queue), but what's more important is the idea that you can abstract the access to your circular buffer to an interface, so that callers deal with it like it's an ordinary list.

The interface might look something like this (sorry for my poor Java skills):

public interface IReadonlyList<T>
{
    // gets the item at the specified index
    T getItem(int index);

    // gets the length
    int length();
}

And the circular buffer implementation would simply offset the internal index before returning the requested value:

// note that _headOffset and _actualArray aren't
// assigned anywhere, it's just a concept

public class CircularBuffer<T> : IReadonlyList<T>
{
    private final int _headOffset;
    private final T[] _actualArray;

    public T getItem(int index)
    {
        var actualIndex = (index + _headOffset) % Length;
        return _actualArray[actualIndex];
    }

    public int length()
    {
        return _actualArray.Length;
    }
}

Wrapping the class in an interface like this allows you to use a general binary search algorithm you would use for a standard sorted list (and any other algorithm which would work on a non-circular buffer).


Calculating Pi in Python I have implemented a calculation of Pi in Python, just for the lulz.
But now I wonder if I could improve this more. Could you help me out? I do not program a lot in Python.

from time import time
from decimal import *

def faculty(m):
    k=m
    n=1
    while(n<m):
        k=k*n
        n+=1
    if(k>0):
        return k
    else:
        return 1

def ramanujan(b, n):
    return b+Decimal(faculty(4*n)*(1103+26390*n))/Decimal((faculty(n)**4)*396**(4*n))

def chudnovsky(b, n):
    return b+(((-1)**n)*(faculty(6*n))*(13591409+(545140134*n)))/(faculty(Decimal(3)*n)*(faculty(n)**3)*640320**(3*n+(Decimal(3)/Decimal(2))))

def calc(x, a, func):
    b=Decimal(0)
    n=Decimal(0)
    while(n<x):
        b = func(b, n)
        n=n+1
    return ((a*b)**(-1))

def calcrama():
    return calc(20, Decimal((2*Decimal(2).sqrt())/9801), ramanujan)

def calcchud():
    return calc(20, 12, chudnovsky)

def save(name, func):
    fobj = open(name, "w")
    t = time()
    pi = func()
    t = time() - t
    fobj.write("Time: "+str(t)+"\nPi: "+str(pi))
    fobj.close()

getcontext().prec = 1000

save("rama.txt", calcrama)
save("chud.txt", calcchud)

I find that your program is obfuscated and therefore incomprehensible to anyone except for perhaps an expert in those calculations methods.  You should pick more informative variable names than a, b, k, m, n, and x.

faculty(m) should be renamed factorial(m).  Ideally, you wouldn't need it — see below.

If you could verify that the denominator is always a divisor of the numerator, you should use // integer division.

Use more whitespace for readability.  Here, I would break with Python guidelines and be more generous with whitespace than usual.

Verbose comments, especially docstrings, would also be appreciated for complicated mathematics:

def chudnovsky(b, n):
    """
    Based on the identity

                    n
      1     inf (-1)  (6n)! (13591409 + 545140134n)
    ----- = SUM -----------------------------------
    12 PI   n=0              3       3n + 1.5
                   (3n)! (n!)  640320

    Returns the nth term of the sum.
    """
    return b + (
        ((-1)**n) * (factorial(6 * n)) *
        (13591409 + (545140134 * n))
    ) // (
        factorial(Decimal(3) * n) *
        (factorial(n)**3) *
        640320**(3 * n + (Decimal(3) / Decimal(2)))
    )

Many parts of that expression would be more efficiently computed based on their counterparts in the previous term, instead of starting from scratch.  You might want to build an generator  that caches those intermediate results.

Furthermore, you have very large numbers in both your numerators and denominators, especially factorials.  You can help keep those small by cancelling out the factorials in the numerator and denominator as soon as possible.

def ChudnovskyTerms():
    """
    Based on the identity

                      n
      1    inf 12 (-1)  (6n)! (13591409 + 545140134n)
    ---- = SUM --------------------------------------
     PI    n=0                3       3n + 1.5
                    (3n)! (n!)  640320

    yields successive terms of the sum.
    """
    term = 0
    sign = 1
    factorial_6_3 = 1         # = factorial(6 * n) / factorial(3 * n)
    numerator_sum = 13591409
    n_factorial_cubed = 1
    denominator = 640320**1.5

    while True:
        yield 12 * sign * factorial_6_3 * …

        term += 1
        sign *= -1
        for i in range(6):
            factorial_6_3 *= (6 * term - i)
        for i in range(3):
            factorial_6_3 //= (3 * term - i)
        numerator_sum += 545140134
        # etc.


Random iteration over an array using divide and conquer I have created a utility class which allows random iteration over an array.
The idea is pretty much a divide and conquer approach.

public class RandomIterator<T> implements Iterator<T> {

    //recursion stack
    private final LinkedList<int[]> offsets = new LinkedList<>();
    private final ThreadLocalRandom random = ThreadLocalRandom.current();
    private final T[] words;

    public RandomIterator(T[] words) {

        this.words = words;

        //add default lower and upper bound
        offsets.addLast(new int[]{0, words.length});
    }

    @Override
    public boolean hasNext() {
        return !offsets.isEmpty();
    }

    @Override
    public T next() {

        final int[] offset = offsets.removeFirst();

        final int upperBound = offset[1];
        final int lowerBound = offset[0];

        final T toReturn;

        if (lowerBound + 1 == upperBound) {

            //range contains only 1 index
            toReturn = words[lowerBound];
        } else {

            final int randomIndex = random.nextInt(lowerBound, upperBound);
            toReturn = words[randomIndex];

            if (randomIndex + 1 < upperBound)
                offsets.addLast(new int[]{randomIndex + 1, upperBound});
            if (randomIndex > lowerBound)
                offsets.addLast(new int[]{lowerBound, randomIndex});
        }

        return toReturn;
    }
}

You can see this in action here. It works fine, but I feel its not truly random. The original array used in the link above is a lexicographically sorted array of 2000 latin words. As we can see in the output there are multiple groups of words which appear to be in order. For e.g.. a range like this occurred in one run.

aberam
abeas
abditi
abdidimusque
abdideris
abdiderim
abdideras
abdideramus
abalienato

Suggestions will be much appreciated :)

EDIT

It seems I did not express my thoughts properly.
I do not want repetitions during the random iteration. The idea is basically to cover all the array indices once, but do it randomly. The example linked above does this. It uses the same lexicographically sorted array of latin words on each run, and randomly iterates it and writes out each word to the outputstream.
Randomness in the output can be defined as probability of occurrence of words with very small "distance" from each other.
For eg. the words "quote" and "quoted" have very small distance. My requirement is that word with very small distance should not occur close to each other in the output (random).

When I say the output is not truly random, I mean that I can observe groups of contiguous words in the output which have very small distance from each other. Hence the output gives the expression of not being truly random.

Bug?

    private final ThreadLocalRandom random = ThreadLocalRandom.current();

This doesn't look right.  What happens if your current thread copies your object and spawns a new thread?  It will copy the current random instance.

When you use it

            final int randomIndex = random.nextInt(lowerBound, upperBound);

You should instead say

            final int randomIndex = ThreadLocalRandom.current().nextInt(lowerBound, upperBound);

That way, even if your object exists in multiple threads, each one will access a separate instance of ThreadLocalRandom.

Your current implementation may return the same random result multiple times, which would give the "non-random" appearance that you're seeing.

Note that if you are using an old version of Java, there was apparently a bug that could cause this to happen even when called correctly.


Implementation of an UniqueIdentifier class I have a requirement to implement a generic UniqueIdentifier which can cover identifiers like OrderId, TrackingID, scannableId and other Ids. The ids, as they are now, are either Long or String.
Below is my implementation of the UniqueIdentifier class --

public class UniqueIdentifier {
    String stringValue;
    Long longValue;
    boolean isLong;
    boolean isString;

    public UniqueIdentifier(String value) {
        setStringValue(value);
        try
        {
            setLongValue(Long.parseLong(value));
        }
        catch(NumberFormatException nex)
        {
            setLong(false);
        }
    }
    public UniqueIdentifier(Long value) {
        setLongValue(value);
        setStringValue(Long.toString(value));
    }
    public String getStringValue() {
        return stringValue;
    }
    private void setStringValue(String stringValue) {
        this.stringValue = stringValue;
    }
    public Long getLongValue() {
        return longValue;
    }
    private void setLongValue(Long longValue) {
        this.longValue = longValue;
    }
    public boolean isLong() {
        return isLong;
    }
    private void setLong(boolean isLong) {
        this.isLong = isLong;
    }
    public boolean isString() {
        return isString;
    }
    private void setString(boolean isString) {
        this.isString = isString;
    }
}

Is there anything that i can do better here

I think this one screams for usage of generics.

ie.

public class UniqueIdentifier<T> {
    T theValue;
    public UniqueIdentifier( T t ) {
        theValue = t;
    }
    public T getValue() {
        return theValue;
    }
}

Can even be extened with a nice factory method.


Refactoring code finding if Binary Tree is BST I have written an code to find if a given tree is a BST. Need help in refactoring it. Some of the things I am looking are.

Getting Rid of temp variables (As suggested by Martin Fowler)
Combining leftTreeMax and RighTreeMin methods
Better naming of methods.

Also it will be great if someone can suggest other refactorings which i can do.

package com.cc.bst;

import com.cc.queue.Queue;
import com.cc.trees.BinaryTreeNode;

public class IsBinaryTreeBST {

public static boolean binaryTreeBST ( BinaryTreeNode root) {

    if (root == null) {
        return false;
    }
    int maxVal = leftTreeMax(root.getLeft());
    int minVal = rightTreeMin(root.getRight());
    int rootVal = root.getData();

    if (maxVal == 0 || minVal == 0 ) {
        return false;
    }

    if (rootVal > maxVal && rootVal < minVal) {
        return true;
    }

    return false;

}

private static int leftTreeMax (BinaryTreeNode node) {

    if (node == null) {
        return 0;
    }
    Queue nodeQueue = new Queue();
    nodeQueue.enqueue(node);
    int maxValue = node.getData();

    while (!nodeQueue.isEmpty()) {
        BinaryTreeNode tempNode = (BinaryTreeNode) nodeQueue.dequeue();
        BinaryTreeNode left = tempNode.getLeft();
        BinaryTreeNode right = tempNode.getRight();

        if (left != null ) {
            if (left.getData() > tempNode.getData()) {
                return 0;
            }
            nodeQueue.enqueue(left);
        }
        if (right != null) {
            if ( tempNode.getData() > right.getData()) {
                return 0;
            }
            nodeQueue.enqueue(right);
        }
        if (tempNode.getData() > maxValue) {
            maxValue = tempNode.getData();
        }
    }
    System.out.println("---------- maxVal -------->" +  maxValue);
    return maxValue;
}

private static int rightTreeMin(BinaryTreeNode node) {

    if (node == null) {
        return 0;
    }
    Queue nodeQueue = new Queue();
    nodeQueue.enqueue(node);
    int minValue = node.getData();

    while (!nodeQueue.isEmpty()) {
        BinaryTreeNode tempNode = (BinaryTreeNode) nodeQueue.dequeue();
        BinaryTreeNode left = tempNode.getLeft();
        BinaryTreeNode right = tempNode.getRight();
        System.out.println("---------- tempNode -------->" + tempNode.getData());

        if (left != null ) {
            System.out.println("---------- left -------->" + left.getData());

            if (left.getData() > tempNode.getData()) {
                return 0;
            }
            nodeQueue.enqueue(left);
        }
        if (right != null) {
            if ( tempNode.getData() > right.getData()) {
                return 0;
            }
            System.out.println("---------- right -------->" + right.getData());

            nodeQueue.enqueue(right);
        }
        if (tempNode.getData() < minValue) {
            minValue = tempNode.getData();
        }
    }
    System.out.println("---------- minVal -------->" +  minValue);

    return minValue;
}

}

1) You would like to get rid of the System.out.println() inside methods. Noone expects a method to write to the console unless the method has print in the name.

2) Just comparing the root with left tree max and right tree min can lead to wrong result. Consider,

    12
   /  \
  9    15
 / \
3   5

Here the left sub-tree is not a BST but 12 > 9 and 15 > 12. You must also ensure that left-subtree and right-subtree of root are also BST.

3) BinaryTreeBST is kind of redundant. Consider naming the class IsBSTCheck or IsBinarySearchTreeCheck. Also change the method name binaryTreeBST to isBST or isBinarySearchTree to reflect what the method does.


Path from the root to a given node in binary tree Based on the solution provided in this question , I have written non-recursive Java code to find the path form to a given element in a binary tree.  This code is working for all the elements except root.

Is this the correct implementation of the algorithm provided?
Please check and suggest the required changes for the code to look more elegant.

public void findPathFromRoot(Node rootNode,int key)
{
    Node temp = rootNode;
    Stack<Node> nodeStack = new Stack<Node>();
    nodeStack.push(rootNode);
    boolean present = true;

    Node topNode = rootNode;
    Node topNodeLeft,topNodeRight;

    while(true)
    {
        //three temp variables for top,left of top,right of top
        topNode = nodeStack.peek();
        topNodeLeft = topNode.lnode;
        topNodeRight = topNode.rnode;

    //if left of top is not null, push to stack. Check if the push values is equla to the required key
    //If it is the require element break
    if(topNodeLeft != null )
    {
        nodeStack.push(topNodeLeft);
        if(topNodeLeft.value == key)
            break;
    }

    //if right of top is not null, push to stack. Check if the push values is equal to the required key
    //If it is the require element break
    else if(topNodeRight != null)
    {
        nodeStack.push(topNodeRight);
        if(topNodeRight.value == key)
            break;
    }

    //If both the childs are null(ie leaf node) , pop the elements in stack, till the top node has some right child.
    else
    {
        Node lastPoppedNode;

        //pop the elements in stack, till the top node has some right child.
        do{
            lastPoppedNode = nodeStack.pop();
            topNode = nodeStack.peek();
        }while(topNode.rnode==null);

        //Now the top node would be the node with some right child
         topNodeRight = topNode.rnode;

         //Push that right child
        nodeStack.push(topNodeRight);

        //Check if the push values is equal to the required key
        //If it is the require element break
        if(topNodeRight.value == key )
        {
            break;
        }

        //To terminate the loop if no element is found....
        //it checks if the popped element is getting added again
        if( lastPoppedNode == topNodeRight)
        {
            present = false;
            break;
        }
    }
    }

    //Printing based on the boolean variable.
    if(present)
    {
    for(Node tempNode : nodeStack)
    {
        System.out.println(tempNode.value);
    }
    }
    else
    {
        System.out.println("Element is not present in the tree");
    }

}

Step 1: use an IDE to reformat this nicely

Step 2: remove pointless comments

For example:

// if left of top is not null, push to stack.
// Check if the push values is equla to the required key
// If it is the require element break
if (topNodeLeft != null) {
    nodeStack.push(topNodeLeft);
    if (topNodeLeft.value == key)
        break;
}

The comment explained in English exactly what the code does. This is pointless.
On closer look, pretty much all the comments in this code are pointless.

Step 3: rename variables to more readable names

For example:

lnode -> left
rnode -> right

Step 4: let your IDE guide you

Pay attention to the warnings and try to fix them.
For example IntelliJ tells this:

The variable temp is never used: delete it
The Node topNode = rootNode; initialization is pointless, skip the initialization

Step 5: remove unnecessary elements

Look at every variable with suspicion. What's the purpose of topLeftNode?
After the renaming above, we have this line:

        topNodeLeft = topNode.left;

Which doesn't make a whole lot of sense. Can't we use just topNode.left ? Yes we can.

Why is topNode declared outside of the while loop when it is only used inside the loop, and assigned on the first line of the loop?
It's better to declare it inside:

    while (true) {
        Node topNode = nodeStack.peek();

Step 6: look for bugs in simple (degenerate) cases

The method crashes with EmptyStackException if the tree has only one node.

Same thing if the tree has only two nodes with the child in left position.

While fixing these bugs, you might find more opportunities to improve. Give it a try.

With the above suggestions, the code becomes this:

public void findPathFromRoot(Node rootNode, int key) {
    Stack<Node> nodeStack = new Stack<>();
    nodeStack.push(rootNode);
    boolean present = true;

    Node topNodeRight;

    while (true) {
        Node topNode = nodeStack.peek();
        topNodeRight = topNode.right;

        if (topNode.left != null) {
            nodeStack.push(topNode.left);
            if (topNode.left.value == key) {
                break;
            }
        } else if (topNodeRight != null) {
            nodeStack.push(topNodeRight);
            if (topNodeRight.value == key) {
                break;
            }
        } else {
            Node lastPoppedNode;

            do {
                lastPoppedNode = nodeStack.pop();
                topNode = nodeStack.peek();
            } while (topNode.right == null);

            topNodeRight = topNode.right;

            nodeStack.push(topNodeRight);

            if (topNodeRight.value == key) {
                break;
            }

            if (lastPoppedNode == topNodeRight) {
                present = false;
                break;
            }
        }
    }

    if (present) {
        for (Node tempNode : nodeStack) {
            System.out.println(tempNode.value);
        }
    } else {
        System.out.println("Element is not present in the tree");
    }
}

Step 7: Stop and think

What algorithm are you actually trying to implement here?
The top answer on the question you linked suggests using pre-order traversal.
That's a good suggestion that will work, though it won't be the fastest for all possible trees.
I suggest to implement that algorithm first.


Parsing JSON to a Map and Set structure How do I make these line of codes more scala-ish (shorter?). I still get the Java feeling in it (which I want to stay away from).

import scala.collection.mutable
val outstandingUserIds: mutable.LinkedHashSet[String] = mutable.LinkedHashSet[String]()

val tweetJson = JacksMapper.readValue[Map[String, AnyRef]](body)
val userObj = tweetJson.get("user")
tweetJson.get("user").foreach(userObj => {
  userObj.asInstanceOf[Map[String, AnyRef]].get("id_str").foreach(idStrObj => {
    if (outstandingUserIds.exists(outstandingIdStr => outstandingIdStr.equals(idStrObj))) {
      outstandingUserIds.remove(idStrObj.asInstanceOf[String])
    }
  })
})

If you really want to inflict this JSON library on yourself, your code could be simplified to:

import scala.collection.mutable

val outstandingUserIds = mutable.LinkedHashSet[String]()

val tweetJson = JacksMapper.readValue[Map[String, AnyRef]](body)
for {
  userObj <- tweetJson.get("user")
  idStrObj <- userObj.asInstanceOf[Map[String, AnyRef]].get("id_str")
} outstandingUserIds -= idStrObj.asInstanceOf[String]

But I would recommend you use a better JSON library. For example, using the library that comes with the Play! framework:

(body \ "user" \ "id_str").asOpt[String].foreach {id =>
  outstandingUserIds -= id
}


Watch for CRUD state changes and make sure only one is active at once I'm using AngularJS and I have a watch task in my controller that needs to be dried up if possible.

Basically it watches for state changes in my front end. I have 3 buttons: add, edit, and delete which will toggle these states. I only want one to be active at once.

My buttons:

<button ng-click="actions.add === false ? actions.add = true : actions.add = false">Add</button>
<button ng-click="actions.edit === false ? actions.edit = true : actions.edit = false">Edit</button>
<button ng-click="actions.delete === false ? actions.delete = true : actions.delete = false">Delete</button>

Snippet from my controller:

$scope.actions = {
  add: false,
  edit: false,
  delete: false
}

$scope.$watch('actions', function() {

  if ($scope.actions.add === true) {
    $scope.actions.edit = false;
    $scope.actions.delete = false;
  }
  else if ($scope.actions.edit === true) {
    $scope.actions.add = false;
    $scope.actions.delete = false;
  }
  else if ($scope.actions.delete === true) {
    $scope.actions.add = false;
    $scope.actions.edit = false;
  }
});

I assume that when you say that you want your code to be "dried" up, you want your code to be more DRY, right?

Well right now, you are doing quite a bit of repeating: you've created individual conditional statements for each property of an object.

Your code would be much more DRY if you iterated through the object and checked the properties as you iterated.

Since we are handling an object, let's use a for/in loop:

for(var i in $scope.actions) {

}

In every conditional statement that you wrote, you checked to see if a property was equal to true.

That should be the first thing we check here:

for(var i in $scope.actions) {
    if($scope.actions[i])

    }
}

Notice how there is no === true at the end of the conditional? JavaScript already checks to see if the conditional reduces to true automatically.

Now we have to find a way to set the other two values in the object to false in a DRY way.

I think it would be best to create a function that takes in one argument that is the name of the property that should not be set to false, and then the function sets the other properties to false

That would look like this:

function setPropertiesToFalse(obj, except) {
    for(var i in obj) {
        if(i != except) {
            obj[i] = false;
        }
    }
}

Now the main code would look like this:

for(var i in $scope.actions) {
    if($scope.actions[i]) {
        setPropertiesToFalse($scope.actions, i);
        break;
    }
}

I added a break statement into your code because the original code uses if/else, so if a conditional were to pass, the rest would not be checked.


Made a monster array for a text based game with a class constructor C++ I created a class in a separate .h and .cpp file with the idea of having an array of 3 monsters with each monster having different stats( name; health; damage). The problem is that the constructor should change the properties but when I try to call them in the main file only the 3rd monster's properties are changed.
main.cpp
#include <string>
#include <iostream>
#include <Windows.h>
#include <stdio.h>
using namespace std;

#include "Player.h"
#include "Monsters.h"
#include "MonsterCluster.h"

int main()
{

    Player player;
    Monsters monster;
    MonsterCluster enemies;

    enemies = MonsterCluster(0, "Goblin", 20, 5);
    enemies = MonsterCluster(1, "Wraith", 50, 10);
    enemies = MonsterCluster(2, "Legionare", 80, rand() % 60+20);

    cout << enemies.monsterList[2].name << endl;
}

MonsterCluster.h
#pragma once
#include "Monsters.h"

class MonsterCluster :
    public Monsters
{
public:
    Monsters monsterList[3];

    MonsterCluster();
    MonsterCluster(int _monsterIndex, string _name, int _health, int _damage);

}

MonsterCluster.cpp
MonsterCluster::MonsterCluster()
{
    /*name = "";
    health = 2;
    damage = 3;*/
}

MonsterCluster::MonsterCluster(int _monsterIndex, string _name, int _health, int _damage)
{
    monsterList[_monsterIndex].name = _name;
    monsterList[_monsterIndex].health = _health;
    monsterList[_monsterIndex].damage = _damage;
}

Don't write using namespace std;.
You are passing std::string by value, which copies the string.  Generally you want to pass as const std::string&, or better yet std::string_view.  (Though in the case of a properly written constructor (see below) you might want to do something more advanced here.)

enemies = MonsterCluster(0, "Goblin", 20, 5);
enemies = MonsterCluster(1, "Wraith", 50, 10);
enemies = MonsterCluster(2, "Legionare", 80, rand() % 60+20);

You are assigning values to the same variable, overwriting the previous.
I think you're confusing the meaning of monsterList inside the class with uses of the entire class.  Each instance you create is populating a different element in the array, but you don't understand that these calls are creating different instances and not updating the previous instance!  You throw away the first two instances you create and only keep the third.
Have a Monster class with a constructor.  You don't show your Monsters but it appears to be a plain struct without a constructor, from how you're using it.
Then you don't need a class that's nothing but a collection of 3 Monsters.  That's just an array.
Something like:
Monster enemies[] = {
   { "Goblin", 20, 5 },
   { "Wraith", 50, 10 },
   { "Legionare", 80, rand() % 60+20 }
};

Note that each line is three parameters for the Monster constructor.


Binary search tree in C++ 17 using iterator pattern I am new to C++ and am attempting to write the following binary search tree using the iterator pattern (and std::optional in C++17):

#include <memory>
#include <optional>
#include <stack>

template <typename T>
class BinarySearchTree {
public:
  BinarySearchTree(T key)
  : key_(key),
    left_(nullptr),
    right_(nullptr) {}

  BinarySearchTree(const BinarySearchTree& bst) {
    key_ = bst.key_;
    left_ = std::make_unique<BinarySearchTree>(*bst.left_);
    right_ = std::make_unique<BinarySearchTree>(*bst.right_);
  }

  void insert(T key);

  T key() { return key_; }
  std::unique_ptr<BinarySearchTree> left() { return std::make_unique<BinarySearchTree>(*left_); }
  std::unique_ptr<BinarySearchTree> right() { return std::make_unique<BinarySearchTree>(*right_); }

private:
  T key_;
  std::unique_ptr<BinarySearchTree> left_;
  std::unique_ptr<BinarySearchTree> right_;
};

template <typename T>
void BinarySearchTree<T>::insert(T key) {
  auto insert = [key](auto& node) {
    if (node) {
      node->insert(key);
    } else {
      node = std::make_unique<BinarySearchTree>(key);
    }
  };

  if (key <= key_) {
    insert(left_);
  } else {
    insert(right_);
  }
}

template <typename T>
class BinarySearchTreeIterator {
public:
  BinarySearchTreeIterator(BinarySearchTree<T>& bst, bool forward)
  : bst_(std::make_unique<BinarySearchTree<T>>(bst)),
    forward_(forward) {}

  std::optional<T> operator*() { return current_; }

  void operator++() {
    while (bst_ || !stack_.empty()) {
      if (bst_) {
        stack_.emplace(std::make_unique<BinarySearchTree<T>>(*bst_));
        bst_ = std::make_unique<BinarySearchTree<T>>(*(forward_ ? bst_->left() : bst_->right()));
      } else {
        bst_ = std::make_unique<BinarySearchTree<T>>(*(stack_.top()));
        stack_.pop();
        current_ = bst_->key();
        bst_ = std::make_unique<BinarySearchTree<T>>(*(forward_ ? bst_->right() : bst_->left()));
        break;
      }
    }
  }

private:
  std::unique_ptr<BinarySearchTree<T>> bst_;
  bool forward_;
  std::stack<std::unique_ptr<BinarySearchTree<T>>> stack_;
  std::optional<T> current_;
};

I am not sure if my usage of std::unique_ptr is correct or idiomatic.

BinarySearchTree

Since the tree isn't balanced, worst case insertion complexity is \$\mathcal{O}(n)\$ (and not \$\mathcal{O}(\log n)\$ as likely intended). (Same for lookup, if such a method were to be added).
Calling left() or right() will create a copy of the whole left/right subtree. This is very likely not intended.
This class could profit a lot from a move constructor and a move assignment operator overload. (And while we're at it, add a copy assignment operator overload and a destructor to complete the rule of five.)
Is it really necessary to name the lambda the same as the enclosing function in BinarySearchTree::insert(T key)?
Also of note, only types that can be copied can be inserted into the BinarySearchTree. This means it is currently not possibly to store a move-only type (like std::unique_ptr) in the tree. (This capacity could be added with an overload accepting a T&&.
BinarySearchTree::insert(T key) creates unnecessary copies of key for each recursive call. Consider taking a const T& instead.`
left_ and right_ are often dereferenced without checking them for nullptr beforehand! This results in undefined behavior if they are nullptr!

BinarySearchTreeIterator

This iterator doesn't provide any iterator_traits or an end iterator. This means using it with standard library algorithms (or even a range based for loop) is not possible. More info on iterators and iterator_traits.
There are lots and lots of unnecessary copies (basically every time std::make_unique or bst_->left() or bst_->right() are called).
current_ will always have a value with this implementation, so making it std::optional<T> is misleading. Also, any modifications done to the value returned by operator*() won't be propagated to the original BinarySearchTree entry (as it returns an independent copy and not a reference).
This iterator traverses the tree in-order. Since there are also other traversal methods, like pre-order, post-order or level-order, it would be nice to indicate that in the name.

std::unique_ptr usage

Normally, a std::unique_ptr is used to express "I own this". So a signature like std::unique_ptr<BinarySearchTree<T>> BinarySearchTree::left() says "Call me, and you become the new owner of whatever I return".

Is this necessary in this case? No! After all, the caller just wants to access the existing object, and not acquire a new one.

So, how can this be expressed?

There are two variants:

Return a non-owning BinarySearchTree<T>*.

Pros:

Very lightweight.
Very simple (can still use std::unique_ptr for internal storage, so resources get cleaned up properly).

Cons:

If the BinarySearchTree<T> gets destroyed, but someone still has the pointer stored, the pointer is dangling.
Someone could prematurely call delete on the pointer (so the internal std::unique_ptr would be dangling).

Return a std::shared_ptr<BinarySearchTree<T>>.

Pros:

As long as the std::shared_ptr exists, the object will be valid.

Cons:

Might keep the tree (or subtrees) alive for far longer than intended.
Has a slight overhead.
Requires using std::shared_ptr for internal storage.
Might leak in case of cycles (not a problem here, just for the general case).

Of course, some of those problems can be avoided by appropriate use of std::weak_ptr.

Some more resources:

CppCon 2014 talk about smart pointers
CppCon 2016 talk about memory management (even talks specifically about trees and graphs)


Cython Fibonacci Sequence For my current job, I've been told that soon I'm going to be porting our Python code to Cython, with the intent of performance upgrades. In preparation of that, I've been learning as much about Cython as I can. I've decided that tackling the Fibonacci sequence would be a good start. I've implemented a Cython + Iterative version of the Fibonacci sequence. Are there any more performance upgrades I can squeeze out of this? Thanks!
fibonacci.pyx
cpdef fib(int n):
    return fib_c(n)

cdef int fib_c(int n):
    cdef int a = 0
    cdef int b = 1
    cdef int c = n
    while n > 1:
        c = a + b
        a = b
        b = c
        n -= 1
    return c

And how I test this code:
testing.py
import pyximport ; pyximport.install() # So I can run .pyx without needing a setup.py file #
import time

from fibonacci import fib

start = time.time()
for i in range(100_000):
    fib(i)
end = time.time()
print(f"Finonacci Sequence: {(end - start):0.10f}s (i=100,000)") # ~2.2s for 100k iterations

Using one less variable seems faster:
cdef int fib_c(int n):
    if n == 0:
        return 0
    cdef int a = 0
    cdef int b = 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Running your test on my machine:
Original = 2.934 s
Improved = 1.522 s


Send an email if a URL is down twice only We want to check if a URL is down or not. But sometimes, the environment is down for maintenance for 3-4 hours and we don't want to keep sending emails during that time.

I have written a shell script for performing a URL check and running it every 30 mins using a cronjob.

The actual requirements are:

Check if the URL is up.  If it is down, send an email.
Cronjob will execute the script again. If Step 1 sent an email, then send an email again asking if the environment is under maintenance.
Cronjob will execute the script again.  If it is still down, don't do anything.
Keep checking the URL, and if it is responding, don't do anything.  But if it goes down again, follow step 1-3.

The script works.  Could you please review and suggest if there is a nicer way of writing the script?  I'm learning shell script but don't know all the available options.

#!/bin/bash
#Checking urls from urls.txt
MAddr="jsing002@internalsvcs.pte.com"
TIME=`date +%d-%m-%Y_%H.%M.%S`
SCRIPT_LOC=/user/inf/ete4/eteabp4/eid_scripts/jsing002
for url in `awk '{print $1}' $SCRIPT_LOC/urls.txt`
do
    /usr/bin/wget -t 0 --spider --no-check-certificate $url > wget.output  2>&1
    HTTPCode=`(/usr/bin/wget -t 0 --spider --no-check-certificate $url) 2>&1 | grep HTTP| tail -1|cut -c 41-43`
        ENV=`(grep $url $SCRIPT_LOC/urls.txt | awk '{print $2}')`
        echo $HTTPCode
        E1=`/bin/grep -ise  'refused' -ise 'failed'  wget.output`
        if [ "$E1" != "" ] || [ $HTTPCode -ge 500 ]
            then
                    status="DOWN"
                    echo "Step 1"
                    echo "${ENV}""_DOWN"

                    if [ -f "${ENV}""_DOWN" ];
                        then
                            echo "step 2"
                            echo "Please check if $ENV in Maintanance window.The check for $url has failed twice.Next The next failure email will be sent if preceding test was SUCCESSFUL" | /bin/mail -s "Is $ENV in Maintanance Window ?" $MAddr
                            mv "${ENV}""_DOWN" "${ENV}""_DOWN""_2"
                            echo "Step 3"
                        elif [ -f "${ENV}""_DOWN""_2" ];
                            then
                                echo "this is elif statement"

                        else
                            echo "E1 is empty. Site is down"
                            echo "Site is down. $url is not accessible" | /bin/mail -s "$ENV is $status" $MAddr
                            touch  "${ENV}""_DOWN"
                        fi

            else
                        if [ $HTTPCode -eq 200 ]
                            then
                                status="UP"
                                echo $status
                                rm "${ENV}""_DOWN""_2"
                        fi
        fi
done

Content of urls.txt:
http://mer01bmrim:30270/rim/web         E2E-RIMLITE4
http://mer01csmap:18001/console         ABP_WL-E2E1
http://mer02sitap:18051/console         ABP_WL-E2E2
http://mer03sitap:18101/console         ABP_WL_E2E3

Quoting: Be in the habit of always double-quoting your variables when you use them, e.g. "$url" instead of $url.  Otherwise, nasty vulnerabilities could happen if a variable's value contains spaces or shell metacharacters.  URLs, especially, often contain special characters such as & and ?.
Structure: When processing input with multiple columns, one row at a time, the idiom to use is…

while read url env ; do
    # Do stuff here
done < "$SCRIPT_LOC/urls.txt"

If the columns are delimited by something other than whitespace…

while IFS=: read user pwhash uid gid gecos homedir shell ; do
    # Do stuff here
done < /etc/passwd

Status of wget: You run wget twice for each URL.  Instead of trying to get the HTTP status code, consider using just the exit status of wget to indicate success or failure.

if wget -q -t 0 --spider --no-check-certificate "$url" ; then
    # Handle success
else
    # Handle failure
fi

I've used the --quiet flag here.  Also, I think that an infinite timeout (-t 0) is a bad idea.
HTTP status interpretation: HTTP status codes other than 200 (e.g. 2xx or 3xx) could also indicate some kind of success.
Filesystem littering: You litter the current directory with temporary files wget.output and "${ENV}_DOWN" and "${ENV}_DOWN_2".  Perhaps you could append all the state to a single log file.
SCRIPT_LOC could probably be computed using $(dirname $0).


Ensure difference between sets An endpoint that my application interacts with allows you to specify which fields are returned in the JSON result. My application will then map the JSON to a POJO using Jackson. Quite often I add more fields in one place and forget to add it in the other which results in problems. I wrote a unit test to help make the process easier but I feel like there could be room for improvements.

Here's what I have so far:

private static final String[] POTENTIAL_FIELDS = new String[] { "field1", "field2" };

@Test
public void checkFields() {
    // get all constant fields
    Set<String> constantFields = Arrays.stream(POTENTIAL_FIELDS)
            .map(String::toLowerCase)
            .collect(Collectors.toSet());

    // get all private fields
    Set<String> reflectFields = Arrays.stream(FieldsModel.class.getDeclaredFields())
            .filter((field) -> !Modifier.isStatic(field.getModifiers()))
            .map(field -> field.getName().toLowerCase())
            .collect(Collectors.toSet());

    Set<String> symmetricDifference = Sets.symmetricDifference(constantFields, reflectFields);

    // check if there's a difference
    if (!symmetricDifference.isEmpty()) {
        Assert.fail(String.format("Difference: %s\n", String.join(",", symmetricDifference)));
    }
}

private static class FieldsModel {
    private int field1;
    private String field2;
}

The only non-standard imports are FieldsModel which is what the name suggests, and Sets which is from Guava (com.google.coom.collect.Sets). Here is a direct link to the method I used.

On the whole, I think this is a pretty neat solution to your problem.  A couple of observations...

case == CASE

You lower case everything.  Maybe this is exactly what you're after, but to me, fieldOne and fieldone aren't the same, so I'd want to know about that difference.

Developer time vs test time

symmetricDifference gives back a set of all of the differences, it doesn't discriminate between the left and the right side.  So, if you've added something to FieldsModel and something else to POTENTIAL_FIELDS they would both come back.  The developer then has to go and look at both and reconcile where the problem is.  In reality this might not be a problem because the developer has probably worked on one of the files recently, so would realise which one they'd missed, however it would be better if the test showed what was missing from where.  You could do something like this:

String inConstantButNotModel = constantFields.stream()
        .filter(i -> !reflectFields.contains(i))
        .collect(Collectors.joining(","));
String inModelButNotConstant = reflectFields.stream()
        .filter(i -> !constantFields.contains(i))
        .collect(Collectors.joining(","));

assertThat(String.format("ConstantsMissing: %s\nModelMissing: %s\n",
        inModelButNotConstant,
        inConstantButNotModel))
        .isEqualTo("ConstantsMissing: \nModelMissing: \n");

To give output along the lines of...

ConstantsMissing: field5,field4
ModelMissing: field3


PHP Shopping Website with Cart - Returning a HTML String Edit

If there is a better way to ask this question to avoid negative votes, please let me know.
I have looked into https://codereview.stackexchange.com/help/how-to-ask

How would I implement a class dedicated to returning html strings for a list of products/cart items?

Written as part of an interview assignment.
Simply this is a shopping website with some items a user may add or remove from their shopping cart.
This function is responsible for returning the html to display for the list of cart items.
Currently there is no dedicated class for returning html strings.
I feel I would be moving most of this code into another class, defeating the point.

Code:

function listItems()
{
    $formatter = new Formatter();
    $html = "";
    $id = 0;
    foreach ($_SESSION["Cart"] as $item) {
        if ($item["quantity"] > 0) {
            $html = $html .
                '

'.$this>getName($item) .'

Price: $' . $formatter->formatPrice($item) . '

Quantity: ' . $item["quantity"] . '

Total: $' . $this->getTotal($item) . '

                    <form class="removeForm" method="POST">
                        <input class="removeInput" type="hidden" name="removeId" value=' . $id . ' />
                        <input class="removeInput"  type="submit" name="removeButton" value="Remove from Cart" />
                    </form>

';
        }
        $id++;
    }

    $html = $html .
        '

Overall Total: $' . $this->getOverallTotal() . '

';

    return $html;
}

Formatter class method returns a number with 2 decimal point format.

Full Repository here if you want more to critique:

https://github.com/NathanielPather/Basic-Shopping-Cart/blob/Post-Code-Review/ShoppingCart.php

You might want to decompose it into smaller pieces that will be easier to follow and eventually modify.

You could also learn a bit about dependency injection. Creating new instances all around anytime you need them is not very good.

Here is a very simple rewrite of your code and a lot of pieces are missing but I hope it gives some general guideline.

It uses PHP 7.4 features, if you can't use those, of course ignore all the typehints, etc..

Also it might make sense to depend on interfaces instead of classes directly, but didn't want to go this far as I think it could be too much for you at one go.

Dont be shy to define structures.

class Product
{
  public int $id;
  public string $name;
  public float $price;

  public function __construct(int $id, string $name, float $price)
  {
    $this->id =  $id;
    $this->name = $name;
    $this->price = $price;
  }
}

Create product repository

class ProductsRepository
{
    /**
     * @param array<int> $ids
     * @return array<int, Product>
     */
    function getProducts(array $ids): array
    {
        // get it from somewhere
    }
}

Structure for item in cart holds a bit more.

class CartItem
{
  public int $productId;
  public string $name;
  public float $unitPrice;
  public int $quantity;
  public function __construct(int $productId, string $name, float $unitPrice, int $quantity = 1)
  {
    $this->productId = $productId;
    $this->name = $name;
    $this->unitPrice = $unitPrice;
    $this->quantity = $quantity;
  }
  public function getTotalPrice(): float
  {
    return $this->unitPrice * $this->quantity;
  }
}

Cart holds many items, allows to iterate them, and add them and it knows the product repository to allow it doing so.

class Cart
{
  private ProductsRepository $products;
  /** @var array<CartItem> */
  private array $items;
  public function __construct(ProductsRepository $products, array $items = [])
  {
    $this->products = $products;
    $this->items = $items;
  }
  public function getItems(): array
  {
    return $this->items;
  }

  public function getTotalPrice(): int
  {
    // count it here, or have it in property and make sure it is updated while adding items.
  }

  public function add(int $productId, int $quantity = 1)
  {
    if (isset($this->items[$productId])) {
      // already in cart => increase quatity
    } else {
      $product = $this->products->getProduct($productId);
      //handle product not exists, not on stock, etc.
      $this->items[$productId] = new CartItem($product->id, $product->name, $product->price, $quantity);
    }
  }
}

We will store cart in session, this will take care of it.

class CartSessionStorage
{
  // we need it for the Cart instances
  // and maybe we wont store product names in session but load them from products repo?
  private ProductsRepository $products;

  public function loadCart(): Cart
  {
    // load from session
  }
  public function saveCart(Cart $cart): void
  {
    // save to session
  }
}

Renderer knows the html structure and some localization/formatting rules.

class CartRenderer
{
  private Formatter $formatter;
  public function __construct(Formatter $formatter)
  {
    $this->formatter = $formatter;
  }
  public function renderCart(Cart $cart): string
  {
    $html = '';
    // your rendering here;
    foreach ($cart->getItems() as $item) {
    //you can use heredoc, but add some html escaping, nor heredoc nor your code handle it
    $html .=
      <<<HTML

write html here
and dont mind if u use {$item->getTotalPrice()}
      HTML;
    }
    return $html;
  }
}

Put it all together.

$products = new ProductsRepository();
$storage = new SessionCartStorage(products);
$formatter = new Formatter();
$renderer = new CartRenderer($formatter);

And there you go.

$cart = $storage->loadCart();

// form submission?
$cart->add($productId, $quantity);
$storage->saveCart($cart);

// render it
echo $renderer->renderCart($cart);


Encode a string using Caesar's Cipher My program is complete and running, but I would like second opinions on how I can make it more efficient. The program prompts the user for the message and the amount s/he would like to shift the letters. For the implementation part, is there another "faster" way to do it instead of having the if else if statements to run through and test my characters?

#include "stdafx.h"
#include <iostream>
#include <string>

using namespace std;

string encodeCaesarCipher(string str, int shift);

int main()
{
    string str, encoded_string;
    int shift;

    cout << "This program encodes a message in Caesar Cipher. \n\n";

    cout << "Please enter a message: ";
    getline(cin, str);

    cout << "\nHow many times do you want to shift the letter(s) in the message? ";
    cin >> shift;

    while (shift < 1)
    {
        cout << "You have entered an invalid number. \n";
        cout << "Please try again. \n";
        cout << "Enter a proper number for the amount of letter shifting: ";
        cin >> shift;
    }

    encoded_string = encodeCaesarCipher(str, shift);

    cout << "\nEncoded message: " << encoded_string << "\n\n";

    system("PAUSE");

    return 0;
}

string encodeCaesarCipher(string str, int shift)
{
    string temp = str;
    int length;

    length = (int)temp.length();

    for (int i = 0; i < length; i++)
    {
        if (isalpha(temp[i]))
        {
            for (int j = 0; j < shift; j++)
            {
                if (temp[i] == 'z')
                {
                    temp[i] = 'a';
                }
                else if (temp[i] == 'Z')
                {
                    temp[i] = 'A';
                }
                else
                {
                    temp[i]++;
                }
            }
        }
    }

    return temp;
}

Optimization difficulty  is about quadratic on the length of a function. I suggest a separate shift function, like

 char shift(char ch, int shift)
 {
            if (ch == 'z')
            {
                 return 'a';
            }
            else if (ch== 'Z')
            {
                return 'A';
            }
            else
            {
                return ch + 1;
            }
   }

And you can call it in the loop.

Anyhow this programme does not need speed up, runtime is dominated by input and output taking.

Avoid namespace std;, return 0, and system("pause").
The first causes name clashes, the second is not needed, the third is a portability issue and a security breach.

As a minor note, declare and assign length on the same line:

  int length = (int) str.length()

Following @Ryan 's suggestion, -25 can be used to merge 'z' and 'Z'. It then becomes so short to beg for a ternary:

 char shift(char ch, int shift)
 {
     return ch == 'z' || ch == 'Z' ? ch - 25 : ch + 1;
 }


Interview adjacency list graph problems in C++: proper graph implementation I know this type of question has been asked before. However, my reason for asking it is gaining insight into what is expected in a 45 min interview when asked to implement graph algorithms. I have never had to give an interview, but have been asked in several interviews, questions pertaining to graphs. Specifically adjacency lists implementations. Several times I have asked the interviewer if they would like me to just implement the algorithm, or if they would prefer the basic structure of the graph too. Most times the response was to provide some level of structure before implementing the algorithm.

Provided the information above, my review request is as follows:

Is my implementation of a graph (provided below) sufficient?
Would you as a reviewer of the code be appalled provided I wrote it in under 20 min?
How would you simplify the code below such that it would be suitable for an interview, and sufficient enough to convey that you could solve problems like depth or breadth first search with it?

namespace graph
{
  template <typename T>
  struct directed_node
  {
    typedef typename std::list<std::shared_ptr<directed_node<T>>> adjacency_t;

    explicit directed_node(const T &t) :
      m_t(t)
    {}

    void connect(std::shared_ptr<directed_node<T>> node,
      typename adjacency_t::iterator addr)
    {
      auto it = m_adjacents.begin();
      for (it = m_adjacents.begin(); it != m_adjacents.end(); ++it) {
        if (node->m_t == (*it)->m_t) {
          break;
        }
      }

      if (it == m_adjacents.end()) {
        m_adjacents.push_back(node);
        node->m_adjacent_addr = addr;
      }
    }

    T m_t;
    adjacency_t m_adjacents;
    typename adjacency_t::iterator m_adjacent_addr;
  };

  template <typename T>
  struct directed
  {
    typedef typename std::list<std::shared_ptr<directed_node<T>>> adjacency_t;
    adjacency_t m_adjacency_list;

    typename adjacency_t::iterator insert(typename
      std::shared_ptr<directed_node<T>> node)
    {
      auto it = m_adjacency_list.begin();
      for (it = m_adjacency_list.begin(); it != m_adjacency_list.end(); ++it) {
        if ((*it)->m_t == node->m_t) {
          return it;
        }
      }

      return m_adjacency_list.insert(m_adjacency_list.end(), node);
    }
  };

  template <typename T>
  std::shared_ptr<directed<T>> create_directed()
  {
    return std::make_shared<directed<T>>();
  }

  template <typename T>
  std::shared_ptr<directed_node<T>> connect_directed(directed<T> &g,
    const T &from, const T &to)
  {
    std::shared_ptr<graph::directed_node<T>> n1 =
    std::make_shared<graph::directed_node<T>>(from);
    auto it1 = g.insert(n1);
    if (it1 != g.m_adjacency_list.end()) {
      n1 = (*it1);
    }

    std::shared_ptr<graph::directed_node<T>> n2 =
      std::make_shared<graph::directed_node<T>>(to);
    auto it2 = g.insert(n2);
    if (it2 != g.m_adjacency_list.end()) {
      n2 = (*it2);
    }

    n1->connect(n2, it2);

    return n1;
  }
}

int main()
{
  std::shared_ptr<graph::directed<int>> g = graph::create_directed<int>();
  graph::connect_directed(*g, 1, 2);
  return 0;
}

I'll be honest: if you've completed a task in 20 minutes during an interview, I'll probably forgive a lot. I'd assume you made a lot of assumptions about the compilation environment, and you may or may not have had access to reference materials, and that your code is basically as close to pseudocode as it is to actual code. Anyone who can't at least give you that benefit of the doubt is probably someone you don't want to work for.

Given that, there are a few things I'd recommend working on.

Naming

They say that naming things is one of the hardest things in computer science. (And not just computer science - biology has a hold field of taxonomy that classifies and names things. It's hard work!) Looking at your code, it's not immediately obvious to me what the difference between a directed and a directed_node is. They both declare a list of things they're adjacent to, but one has an m_t member and an iterator.

Also, what is m_t? It looks like you're using m_ to represent member variables. That's not my favorite way of doing things, but it makes sense and is a common way of naming things, so I wouldn't ding you for it. But m_t tells me nothing beyond that it's a member of the struct. Is t in this case just an instance of T? I'd prefer something generic like value or data over t, if that's the case. But if you can clarify with a better name than any of those, all the better.

Information Hiding

It's often a good idea to hide the details of how something works from the code which calls it. That allows you to swap out something with the same interface but a different implementation. Given that, I'm wondering why all your member variables are public in directed_node and directed? You probably don't want code outside of the struct changing those values out from underneath you. So make them protected or private.

Simplify

I don't know if this is possible, but you've used std::shared_ptr<directed_node<T> in several places. Would it be possible to define it as a type? You'd probably have to do it twice - once in directed_node and once in directed, which feels wrong. Maybe it's not worth it. Likewise, you've defined adjacency_t twice but with the same definition (assuming that you use the same type for your directed_node and directed). That feels weird, but maybe it's unavoidable? Certainly, I wouldn't ding you for doing this in only 20 minutes. But in a real project, I'd expect to have a code review where we would figure out some way of simplifying that, if possible.


Possible optimizations for calculating squared euclidean distance I need to do a few hundred million euclidean distance calculations every day in a Python project.

Here is what I started out with:

#!/usr/bin/python
import numpy as np

def euclidean_dist_square(x, y):
    diff = np.array(x) - np.array(y)
    return np.dot(diff, diff)

This is quite fast and I already dropped the sqrt calculation since I need to rank items only (nearest-neighbor search). It is still the bottleneck of the script though. Therefore I have written a C extension, which calculates the distance. The calculation is always done with 128-dimensional vectors.

#include "euclidean.h"
#include <math.h>

double euclidean(double x[128], double y[128])
{
    double Sum;
    for(int i=0;i<128;i++)
    {
        Sum = Sum + pow((x[i]-y[i]),2.0);
    }
    return Sum;
}

This is the relevant part of the extension, the complete code for the extension is here.
Now this gives a nice speedup in comparison to the numpy version.

But is there any way to speed this up further (this is my first C extension ever so I assume there is)? With the number of times this function is used every day, every microsecond would actually provide a benefit.

Some of you might suggest porting this completely from Python to another language, unfortunately this is a larger project and not an option.

You can decrease Python's overhead by parsing the args tuple and creating the return value manually.

Try changing these portions of your code:

/* Parse the input tuple */
if (!PyArg_ParseTuple(args, "OO", &x_obj, &y_obj))
    return NULL;

<< code snipped >>

/* Build the output tuple */
PyObject *ret = Py_BuildValue("d", value);
return ret;

to this (untested) code:

/* Parse the input tuple manually */
if (PyTuple_GET_SIZE(args) != 2) {
    PyErr_SetString(PyExc_TypeError, "requires 2 arguments");
    return NULL;
}

x_obj = PyTuple_GET_ITEM(args, 0);
y_obj = PyTuple_GET_ITEM(args, 1);

<< code snipped >>

/* Return double as Python float */
return PyFloat_FromDouble(value);

Updates

Without any changes, your code takes ~340ns on my computer. Changing the argument processing and how the return value is created decreases the running time to ~295ns. Replacing pow() with multiplication didn't change the performance with my compiler (GCC 4.8.2). Changing the exponent to a non-integral value significantly increased the running time so I assume constant integer exponents are optimized by the compiler.

Next, I simplified the conversion of the numpy arrays by checking that the objects passed are numpy arrays. This avoids creating new objects. I also assumed that the data type is a "float64". Extra checks could be added if needed. With these changes, the running time is ~220ns. Code is below:

static PyObject *euclidean_euclidean(PyObject *self, PyObject *args)
{
    PyObject *x_obj, *y_obj;

    if (PyTuple_GET_SIZE(args) != 2) {
        PyErr_SetString(PyExc_TypeError, "requires 2 arguments");
        return NULL;
    }

    x_obj = PyTuple_GET_ITEM(args, 0);
    y_obj = PyTuple_GET_ITEM(args, 1);

    if (!PyArray_Check(x_obj) || !PyArray_Check(y_obj)) {
        PyErr_SetString(PyExc_TypeError, "requires array arguments");
        return NULL;
    }

    /* Get pointers to the data as C-types. */
    double *x    = (double*)PyArray_DATA(x_obj);
    double *y    = (double*)PyArray_DATA(y_obj);

    double value = euclidean(x, y);

    if (value < 0.0) {
        PyErr_SetString(PyExc_RuntimeError,
                    "Euclidean returned an impossible value.");
        return NULL;
    }

    /* Build the output tuple */
    return PyFloat_FromDouble(value);
}

If I remove the call to euclidean(), the running time is ~75ns. If I remove all the the argument parsing and just return the value 0.0, the running time is ~72ns. I did a few more tests to confirm running times and Python's overhead is consistently ~75ns and the euclidean() function has running time of ~150ns.


Batch save with progress reporting I reviewed this question that in my opinion uses a not so pretty batch-save so I tried improve it and this is what I came up with.

In this more generic solution that allows to reuse it I wanted to implement the using statement instead of manually disposing and recreating the context.

It is an extension that you can use on a collection of entities. It requires the size of the batch and a factory method for the context. The last parameter is for reporting progress.

Unlike the original solution this one works with double so it is able to report progress for collection that are smaller then 100 items.

Internally it uses two lambdas: one for checking if the batch should be saved and the other one for progress reporting. The context is wrapped with a using statement.

static class EnumerableExtensions
{
    public static void BatchSave<T, TContext>(
        this IList<T> items,
        int batchSize,
        Func<TContext> createContext,
        IProgress<double> progress
    )
        where T : class
        where TContext : DbContext
    {
        var count = 0;
        var lastPercentage = 0d;

        var nextBatch = new Func<bool>(() => ++count % batchSize == 0);

        var reportProgress = new Action(() =>
        {
            var percentage = Math.Round((double)count / (double)items.Count * 100d, 1);
            if (percentage > lastPercentage)
            {
                progress.Report(percentage);
                lastPercentage = percentage;
            }
        });

        var enumerator = items.GetEnumerator();
        while (enumerator.MoveNext())
        {
            using (var context = createContext())
            {
                context.Configuration.AutoDetectChangesEnabled = false;
                context.Configuration.ValidateOnSaveEnabled = false;

                do
                {
                    //context.Set<T>().Add(enumerator.Current);
                    Console.WriteLine("Add " + enumerator.Current);
                    reportProgress();
                } while (!nextBatch() && enumerator.MoveNext());
                //context.SaveChanges();
                Console.WriteLine("Save batch = " + count);
            }
        }
        reportProgress();
    }
}

class TestContext : DbContext { }

I needed to comment the two entity framework lines out so that it doesn't crash with the TestContext.

Example usage:

void Main()
{
    // convert items to string to satisfy the class constraint
    var items = Enumerable.Range(0, 23).Select(x => x.ToString()).ToArray();

    var batchSize = 10;

    var progress = new Progress<double>(percent => Console.WriteLine($"Progress {percent}"));
    items.BatchSave(batchSize, () => new TestContext(), progress);
}

Output:

Add 0
Add 1
Add 2
Add 3
Add 4
Add 5
Add 6
Add 7
Add 8
Add 9
Save batch = 10
Add 10
Progress 4,3
Add 11
Add 12
Add 13
Add 14
Add 15
Add 16
Add 17
Add 18
Add 19
Save batch = 20
Add 20
Add 21
Add 22
Save batch = 23
Progress 13
Progress 17,4
Progress 21,7
Progress 26,1
Progress 30,4
Progress 34,8
Progress 39,1
Progress 43,5
Progress 47,8
Progress 52,2
Progress 56,5
Progress 60,9
Progress 65,2
Progress 69,6
Progress 73,9
Progress 78,3
Progress 8,7
Progress 82,6
Progress 91,3
Progress 95,7
Progress 100
Progress 87

var count = 0;
var lastPercentage = 0d;

var nextBatch = new Func<bool>(() => ++count % batchSize == 0);

It was a clever usage of context capture but I think it ended up playing against you.

Your method has way too much responsibility. You should had at least another method to resolve the batching problem. Because you mixed the two things(batch + db stuff) you ended up by having this:

var enumerator = items.GetEnumerator();
while (enumerator.MoveNext())
{
    //...
    do{
       //...
    } while (!nextBatch() && enumerator.MoveNext());
}

And the first thing that I thought about was: "Why the hell is he advancing the enumerator twice? Why couldn't he use foreach instead?" And than I realized, without even parsing the code too much: "Ah it must be because of the batching stuff...".

It doesn't really matter if I got that right or not, I had to spend time to think about it, asking this kind questions is very useful actually. I would strongly suggest you next time you see yourself using enumerator.MoveNextto ask the same thing. Why aren't you using foreach?

Anyway, as I said you should separate those two concerns. A batch implementation would become like this:

public IEnumerable<IEnumerable<int>> Batch(int total, int batchSize){
    for(int i = 0; i < total; i += batchSize){
        var currentBatchSize = Math.Min(batchSize, total - i);
        yield return Enumerable.Range(i * batchSize, currentBatchSize);
    }
}

A similar thing could be said about reportProgress. You ended up by creating abstraction over a simple calculation that is to calculate the report progress(with a simple mathematical formula). It didn't really contribute in any positive way to the readability/maintainability of your code.

Putting that all into a new implementation would look like this:

public static IEnumerable<IEnumerable<int>> GetBatches(int total, int batchSize){
    for(int i = 0; i < total; i += batchSize){
        var currentBatchSize = Math.Min(batchSize, total - i);
        yield return Enumerable.Range(i, currentBatchSize);
    }
}

public static void BatchSave<T, TContext>(
    this IList<T> items,
    int batchSize,
    Func<TContext> createContext,
    IProgress<double> progress
)
    where T : class
    where TContext : DbContext
{
    var batches = GetBatches(items.Count, batchSize).ToList();
    int currentBatch = 0;
    foreach(var batch in batches){
        using (var context = createContext())
        {
            context.Configuration.AutoDetectChangesEnabled = false;
            context.Configuration.ValidateOnSaveEnabled = false;

            foreach(var i in batch){
                Console.WriteLine("Add " + items[i]);
            }
            //context.SaveChanges();
            progress.Report(++currentBatch * 100.0 / batches.Count);
            Console.WriteLine("Save batch = " + currentBatch);
        }
    }

    progress.Report(100);
}

This alternative might yet lack something. For example, if you are really a neat freak, maybe you would try to change the return result of GetBatches in someway to be more useful. One thing that could be useful is to know which batch is the current batch. Should the return be IEnumerable<IEnumerable<Tuple<int, int>>>(where tuple can be another classes with two integers if you want...). Would it be more useful to turn it to GetBatches<T>? with IEnumerable<IEnumerable<T>> return? Well I will leave that for you to decide, at least I am providing the foundations for it.

One another thing that might be worth pointing is that there isn't really a reason to createContext() multiple times, you can create it just one time, and just call SaveChanges per each batch. Or maybe there is an efficiency reason, that I am not aware of... but you have to prove it by measuring.


PHP, Is creating a class for templates to much? I am new to using classes heavily, and was wondering if going so far as to create a class specifically for templates was going to far. Here is a simplified version of my class template. Yes, I know I the use of unset is not necessary, but I like it there so don't give me any grief for it.

class template{
    private $templateString = "";
    private $templatePlaceholderStrings = array();
    private $templatePlaceholderValueStrings = array();

    function fillTemplateString($string){
        $this->templateString = $string;
        unset($string);
    }

    function fillTemplatePlaceholderStrings($array){
        $this->templatePlaceholderStrings = $array;
        unset($array);
    }

    function filltemplatePlaceholderValueStrings($array){
        $this->templatePlaceholderValueStrings = $arrray;
        unset($array);
    }

    function buildTemplate(){
        return preg_replace($this->templatePlaceholderStrings,
                    $this->templatePlaceholderValueStrings,
                    $this->templateString);
    }
}

This definitely wouldn't be going too far.  Any business logic that your program has to capture is best kept in a class.  Preferably, the class would have automated tests running against it as well to ensure that it is functioning properly.

In your example, the class isn't doing anything drastically different than what the preg_replace method does itself.  Rather than simply duplicating the built-in functionality of this method, I would suggest trying to think of what business goal you are trying to achieve and create methods that more closely mirror it.

class template {
    private $_templateText;

    // Initialize the template with this method, as an instance of
    // template doesn't make much sense without some text.
    public static function factory($templateText) {
        $template = new template();
        $template->_templateText = $templateText;

        return $template;
    }

    // This can be called as many times as needed.  Alternatively, you could add a
    // method that would take two arrays, with the idea that the two array's keys
    // are coupled and paired off.  If you choose to couple the two arrays, I would
    // recommend avoiding passing them in to two different methods.  Make the coupling
    // as obvious as possible by passing them in to the same method.
    public function replacePlaceholderTextWithString($placeholderText, $string) {
        // ...
    }

    // This could have some additional error handling code that would verify that
    // all placeholder text has been replaced and throw an exception if it hasn't.
    // Otherwise, it would simply format the template text based on what had
    // previously been passed in to replacePlaceholderTextWithString(...)
    public function getFormattedTemplateText() {
        // ...
    }
}

Lastly, I would add that a big advantage to using your own class for this is that you are able to change how you would like to implement this functionality in the future.  You could change from using preg_replace to using the MessageFormatter, or any number of other solutions.  It adds a great deal of flexibility and provides you the opportunity to put automated tests around it that can quickly notify you when it no longer works as expected.


Is this a good way of handling item reservations? I have a site were we sell unique items. When a user clicks to buy an item we have to reserve it. This prevents other buyers from purchasing the item while the first buyer is checking out.

When a buyer clicks the "Buy" button, he is redirected to the orders controller. The orders controller executes the following steps:

Verify item is available (not reserved, or sold).

If available, the item is marked as reserved, and its id is stored in the session.
If no, check if it is reserved, and if the current session has the item id (meaning the current user has made the reservation). If both conditions are true the buyer can complete his purchase. Otherwise, the buyer notified and presented with alternatives.

If buyer navigates away from the orders controller, the item is released back to the catalogue.

Are there any obvious pitfalls in my approach?

I have reservations about using the session to indicate the current user has reserved an item. Users don't have to register to check out.

I also feel like I'm repeating myself with @item.reserve!, the reserve! in item_reserver.rb.

Thoughts? Feedback?

application_controller.rb

include ItemReservation
before_action :release_item

items_controller.rb

# ensures item is available
before_action :verify_item_is_available, only: :show

orders_controller.rb

# ensures item is available
before_action :verify_item_is_available, only: [:new, :create]

def new
  reserve! @item
  @order = Order.new
end

controllers/concerns/item_reserver.rb

# before filter
def verify_item_is_available
  unless @item.available?
    redirect_to similar_item_path(@item) unless @item.reserved? && session[:reserved_item_id] == @item.id
  end
end

# before filter
def release_item
  if session[:reserved_item_id].present? && controller_name != 'orders'
    release! session[:reserved_item_id]
  end
end

def reserve!(item)
  if item.available?
    session[:reserved_item_id] = item.id if item.reserve!
  end
end

def release!(item_id)
  item = Item.find(item_id)
  if item.reserved?
    session[:reserved_item_id] = nil if item.release!
  end
end

item.rb

  def reserve!
    update!(availability: 'reserved')
  end

  def release!
    update!(availability: 'available')
  end

  def purchase!
    update!(availability: 'sold')
  end

Placing locks is inherently fragile, especially on a website.  HTTP is stateless, and a user could walk away or close the browser at any time, leaving a lock in place forever.

I would create a table of Lock objects, where each Lock refers to an item, states the quantity, and most importantly has a creation timestamp.  Locks that are too old can easily be purged or ignored.


Project Euler problem 2 in Haskell I have just started Haskell, and I want to check if my code is following the spirit of the language.

  By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

fibonacci :: [Int]
fibonacci = 1 : 1 : (next 1 1)
    where
    next x y = sxy : (next y sxy)
        where
        sxy = x + y

main = do
    putStrLn $ show $ sum $ filter odd $ takeWhile (< 4000000) fibonacci

Just a few things to point out.

There is a prelude function print that is defined print = putStrLn . show.

Additionally, using "do-notation" in this case is unnecessary as you aren't sequencing multiple IO actions.

main can be rewritten in a more point-free style using the function composition operator:

main = print . sum . filter odd . takeWhile (< 4000000) $ fibonacci

I might rewrite fibonacci like this (removes nested where clauses):

fibonacci :: [Int]
fibonacci = next 1 1
  where next x y = x : next y (x + y)

And here are a bunch of other ways to define fibonacci. One interesting way that is possible because of Haskell's laziness:

fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci)


Simple D3 code for drawing area charts I am quite new to D3 and JavaScript in general, so I'm sure there is a way to write the following in a lot less code:

function CalculatePeriodReturns(){
    periodReturns = [];
    [...]
    periodReturns.push({
        length: [...],
        mean: [...],
        pctile50: [pctile(0.25),pctile(0.75)],
        pctile90: [pctile(0.05),pctile(0.95)],
        pctile99: [pctile(0.005),pctile(0.995)],
        min: [...],
        max: [...]
    });
}

function DrawChart(){
    var margin = {top: 20, right: 100, bottom: 30, left: 100},
        width = $("#multiperiod_chart").width() - margin.left - margin.right,
        height = $("#multiperiod_chart").height() - margin.top - margin.bottom;

    var svg = d3.select("#multiperiod_chart").append("svg")
        .datum(periodReturns)
        .attr("width", width + margin.left + margin.right)
        .attr("height", height + margin.top + margin.bottom)
        .attr("id", "multiperiod_chart_svg")
        .append("g")
        .attr("transform",
              "translate(" + margin.left + "," + margin.top + ")");

    var x = d3.scaleLinear().range([0, width]);
    var y = d3.scaleLinear().range([height, 0]);

    x.domain(d3.extent(periodReturns, d=>d.length));
    y.domain([d3.min(periodReturns, d => d.min),
        d3.max(periodReturns, d => d.max)]);

    var area99 = d3.area()
        .x(d=>x(d.length))
        .y0(d=>y(d.pctile99[0]))
        .y1(d=>y(d.pctile99[1]))

    svg.append("path")
        .attr("class", "area")
        .attr("id", "area99")
        .attr("fill", "#565A68")
        .attr("d", area99);

    var area90 = d3.area()
        .x(d=>x(d.length))
        .y0(d=>y(d.pctile90[0]))
        .y1(d=>y(d.pctile90[1]))

    svg.append("path")
        .attr("class", "area")
        .attr("id", "area90")
        .attr("fill", "#7B7F8B")
        .attr("d", area90);

    var area50 = d3.area()
        .x(d=>x(d.length))
        .y0(d=>y(d.pctile50[0]))
        .y1(d=>y(d.pctile50[1]))

    svg.append("path")
        .attr("class", "area")
        .attr("id", "area50")
        .attr("fill", "#A1A3AA")
        .attr("d", area50);

    [...]

}

For a start, is there a way to create an accessor area(y0,y1) that takes the two d.pctileXX properties as attributes or similar? Maybe I can combine the three svg.append's as well?

You can simplify your area generators, as well as your code to append the paths, using an each to append the paths or an object to define the x and y methods in the area generator.

However, there is an simpler alternative: you are facing all those difficulties because of the structure of your data. If you change your data's structure for a more adequate one you can create a code which is way more idiomatic, therefore easier to read and, the most important, easier to maintain.

Right now, this is your data structure:

var periodReturns = [{
    pectile99: [x, y],
    pectile90: [x, y],
    pectile50: [x, y]
}, {
    pectile99: [x, y],
    pectile90: [x, y],
    pectile50: [x, y]
}, {
    etc...
}];

You will bend over backwards to create a multiarea chart with a data structure like this, because:

The data() methods accepts a data array in which each object is a datum;
You cannot easily get the objects' keys;

So, let's change that data structure. We'll created a nested data, with a key/value pair for the name, conveniently called name, and a key/value pair (containing an array) for the points, conveniently called values:

var data = [{
  pectile99: [0, 10],
  pectile90: [0, 40],
  pectile50: [0, 100]
}, {
  pectile99: [100, 40],
  pectile90: [100, 140],
  pectile50: [100, 30]
}, {
  pectile99: [200, 110],
  pectile90: [200, 10],
  pectile50: [200, 100]
}, {
  pectile99: [250, 90],
  pectile90: [250, 70],
  pectile50: [250, 140]
}, {
  pectile99: [300, 10],
  pectile90: [300, 30],
  pectile50: [300, 150]
}];

var nestedData = Object.keys(data[0]).map(function(d) {
  var obj = {
    name: d,
    values: []
  };
  for (var i = 0; i < data.length; i++) {
    obj.values.push(data[i][d])
  };
  return obj;
});

console.log(nestedData)

Now, since all the points can be accessed using the same property name, we can easily write just one area generator. Also, since each object in nestedData corresponds to just one area, we can write a single enter selection!

var areaGenerator = d3.area()
    .x(function(d) {
        return d[0]
    })
    .y1(function(d) {
        return d[1]
    })
    .y0(150);

var areas = svg.selectAll(null)
    .data(nestedData)
    .enter()
    .append("path")
    .attr("fill", function(d, i) {
        return color(i)
    })
    .attr("opacity", 0.5)
    .attr("d", function(d) {
        return areaGenerator(d.values);
    })

Here is the demo:

var data = [{
  pectile99: [0, 10],
  pectile90: [0, 40],
  pectile50: [0, 100]
}, {
  pectile99: [100, 40],
  pectile90: [100, 140],
  pectile50: [100, 30]
}, {
  pectile99: [200, 110],
  pectile90: [200, 10],
  pectile50: [200, 100]
}, {
  pectile99: [250, 90],
  pectile90: [250, 70],
  pectile50: [250, 140]
}, {
  pectile99: [300, 10],
  pectile90: [300, 30],
  pectile50: [300, 150]
}];

var svg = d3.select("svg");

var color = d3.scaleOrdinal(d3.schemeCategory10)

var prop;

var nestedData = Object.keys(data[0]).map(function(d) {
  var obj = {
    name: d,
    values: []
  };
  for (var i = 0; i < data.length; i++) {
    obj.values.push(data[i][d])
  };
  return obj;
});

var areaGenerator = d3.area()
  .x(function(d) {
    return d[0]
  })
  .y1(function(d) {
    return d[1]
  })
  .y0(150);

var areas = svg.selectAll(null)
  .data(nestedData)
  .enter()
  .append("path")
  .attr("fill", function(d, i) {
    return color(i)
  })
  .attr("opacity", 0.5)
  .attr("d", function(d) {
    return areaGenerator(d.values);
  })
<script src="https://d3js.org/d3.v4.min.js"></script>
<svg></svg>


Linq to sql performance I'm creating a system and I'm using EF with Linq. I create my Model (.edmx) and using it, I generated my database and my classes. Like the Usuario (user in Portuguese going to keep the names in Portuguese to avoid some misleading).

namespace SistemaBox.Model
{
    public partial class Usuario
    {
        public int Codigo { get; set; }
        public string Nome { get; set; }
        public string Sobrenome { get; set; }
        public string Senha { get; set; }
        public DateTime DataCriacao { get; set; }
        public DateTime DataUltimoLogin { get; set; }

        public virtual PermissaoGrupo CodigoPermissaoGrupo { get; set; }
    }
}

After this, I create my controller class:

namespace SistemaBox.Controller
{
    [Serializable]
    public class ZUsuario : Usuario
    {
        String connString = ConfigurationManager.ConnectionStrings["ConnectionString"].ToString();

        /// <summary>
        /// Cadastro e edição
        /// </summary>
        public void Cadastro()
        {
            if (Codigo != null && Codigo > 0)
            {
                // Cadastro
                using (DataContext db = new DataContext(connString))
                {
                    Table<Usuario> Usuarios = db.GetTable<Usuario>();
                    var query =
                        from usr in Usuarios
                        where usr.Nome == "Test"
                        select usr;

                    foreach (var usr in query)
                        Console.WriteLine("id = {0}, City = {1}", usr.Codigo, usr.Nome);
                }
            }
            else
            {
                // Edição

            }
        }
    }
}

Please ignore the fact that the class name is record and I'm doing a select. It is just for tests.

My question is about the controller. Is the right way to declare the connection String as global:

String connString = ConfigurationManager.ConnectionStrings["ConnectionString"].ToString();

and use the using like I'm doing?

Your connection string is actually a private class member. I would probably put private keyword explicitly to make it clear.

connString is going to be initialized each time the class instance is created. But the connection string is not going to change in run time so it worth to make connStrint a static member.


Scheduler built with observables I sometimes have to schedule some tasks and wanted to have my own reusable scheduler. Since I like the Rx, I build it on top of it.

Follow-up
There is a newer version of the Scheduler.

The Scheduler class is really simple. It's backed by a newer implementation of my old CronExpression.
There are currently only these two methods. The factory method Create creates a new scheduler that ticks at the specified intervals and provides schedules as DateTimes to the observers.
Jobs are scheduled with the Schedule extension. This one requires a cron-expression and the action to execute.
public static class Scheduler
{
    public static IObservable<DateTime> Create(TimeSpan interval, IDateTime dateTime)
    {
        return
            Observable
                .Interval(TimeSpan.FromSeconds(1))
                .Select(_ => dateTime.Now());
    }

    public static IDisposable Schedule(this IObservable<DateTime> schedules, string cronExpressionString, Action<DateTime> action)
    {
        var cronExpression = CronExpression.Parse(cronExpressionString);
        return
            schedules
                .Where(cronExpression.Contains)
                .Subscribe(action);
    }
}

The DateTime abstraction is supported by the IDateTime interface:
public interface IDateTime
{
    DateTime Now();
}

which is implemented as
public class LocalDateTime : IDateTime
{
    public DateTime Now() => DateTime.Now;
}

or
public class UtcDateTime : IDateTime
{
    public DateTime Now() => DateTime.UtcNow;
}

Example
In order to use it I just create a scheduler, specify what kind of timestamp it should generate and schedule some actions:
var scheduler = Scheduler.Create(TimeSpan.FromSeconds(1), new LocalDateTime());

scheduler.Schedule("0/1 * * * * * *", schedule =>
{
    Console.WriteLine($"DEBUG: {schedule} [{Thread.CurrentThread.ManagedThreadId}]");
});

scheduler.Schedule("0/5 * * * * * *", schedule =>
{
    Console.WriteLine($"ACTION: {schedule}");
});

The output is:

DEBUG: 13/04/2018 22:32:09 [10]
DEBUG: 13/04/2018 22:32:10 [12]
ACTION: 13/04/2018 22:32:10
DEBUG: 13/04/2018 22:32:11 [10]
DEBUG: 13/04/2018 22:32:12 [14]
DEBUG: 13/04/2018 22:32:13 [8]
DEBUG: 13/04/2018 22:32:14 [12]
ACTION: 13/04/2018 22:32:15
DEBUG: 13/04/2018 22:32:15 [8]
DEBUG: 13/04/2018 22:32:16 [12]
DEBUG: 13/04/2018 22:32:17 [8]

There seems to be no rocket science here but this might elusive. Can/should this scheduler by improved in any way?

public static IObservable<DateTime> Create(TimeSpan interval, IDateTime dateTime)
{
    return
        Observable
            .Interval(TimeSpan.FromSeconds(1))
            .Select(_ => dateTime.Now());
}

You forgot to plug interval parameter. And, I would consider renaming it resolution.

I wouldn't trust the values from selecting DatetTime::Now or DateTime::UtcNow:

// try running this for a while
var scheduler = Scheduler.Create(TimeSpan.FromSeconds(1), new LocalDateTime());
scheduler.Schedule("0/1 * * * * * *", schedule =>
{
    Console.WriteLine($"ACTION: {schedule}: {schedule:ss.fff}");
});

ACTION: 2018-04-13 6:28:29 PM: 29.987
ACTION: 2018-04-13 6:28:30 PM: 30.987
ACTION: 2018-04-13 6:28:32 PM: 32.001
ACTION: 2018-04-13 6:28:33 PM: 33.001

Depending on CronExpression::Contains implementation, the scheduler could be skipping task when DateTime.Now.Millisecond gets near 0 or 999.

I've attempted to solve that by adding index * interval to a snapshot of time, however this solution suffered a problem: The delay is cumulative, so the schedule's time will slowly deviate(fall behind) from the real time:

// dont use this
public static IObservable<DateTime> Create2(TimeSpan interval, IDateTime dateTime)
{
    var snapshot = dateTime.Now();
    var offset = interval.Ticks - snapshot.Ticks % interval.Ticks;

    return Observable.Interval(interval)
        .Delay(TimeSpan.FromTicks(offset))
        .Select(x => snapshot.AddTicks(interval.Ticks * (x + 1) + offset));
}

An better solution would be to provide a range of time, and check if expression fall between the range:

public static IDisposable Schedule2(this IObservable<DateTime> schedules, string cronExpressionString, Action<DateTime> action)
{
    var cronExpression = Regex.Match(cronExpressionString, @"^0/(?<s>\d+)");
    return
        schedules
            .Scan(default(TimeRange), (previous, x) => new TimeRange(previous?.End, x))
            .Where(cronExpression.Contains)
            .Subscribe(action);
}

public class TimeRange
{
    public DateTime? Start { get; }
    public DateTime End { get; }

    public TimeRange(DateTime? start, DateTime end)
    {
        this.Start = start;
        this.End = end;
    }
}


Implement PageObjects using TestNg in selenium I am trying to implement page objects with Page factory using TestNg and selenium. Please advice improvements in it.

Classes:

LoginPageObjects extends LoginPageLocators {
   private WebDriver driver;

   public LoginPageObjects(WebDriver driver)
   this.driver=driver;

   public HomePageObjects loginFunction(){
      // some code here
      return PageFactory.initElements(HomePageObjects.class);
   }
}

HomePageObjects extends HomePageLocators{
   private WebDriver driver;

   public HomePageObjects(WebDriver driver)
   this.driver=driver;

   public void verifyTitle(){
       // some code here
   }
}

public class LoginPageTest{

   LoginPageObjects loginPage=new LoginPageObjects();

   public void LoginPageTest(){
      HomePageObjects homepage=loginPage.loginFunction();
      Assert.assertTrue("HomePageTitle",homepage.verifyTitle());
   }
}

TestNGTests.class

public void firstTest() {
   LoginPageTest test=new LoginPageTest();
   test.loginPageTest;
   //other test code
}

`Testng.xml` calls the `TestngTests.class`
`Locators` class contains the `PageFactory` objects

Is LoginPageObjects also a LoginPageLocators?

LoginPageObjects extends LoginPageLocators

seems unlikely. Hence I would not make page object class extend locator class. I usually keep locator on the same page object class for sake of better cohesion. You may come across locators which are applicable for multiple page object classed but in any case page object class is not a page locator class.

public void verifyTitle(){

By and large convention has been to not keep verification/assertion in the page class. Only exception is the page object constructor which can be used to check is control is on write page.

Adding on to what Alexei already mentioned. Adding complete code example would help others to help you. Not everyone works with selenium/TestNG and would find it difficult to get context without complete code example.


A trait class to detect whether a template is specialized for a given type Today's question will just be about a small utility that I needed at some point for one of my projects: a template to detect whether a template is specialized for a given type. The utility uses std::void_t from C++17, but this alias template is simle enough to be implemented in you favourite C++ revision, whichever it is:

template<typename...>
struct voider
{
    using type = void;
};

template<typename... TT>
using void_t = typename voider<TT...>::type;

Here is the template utility I wrote to detect whether a template has a specialization for a given type, for SFINAE purpose:

template<
    template<typename...> class,
    typename,
    typename=void
>
struct is_specialized:
    std::false_type
{};

template<
    template<typename...> class Template,
    typename T
>
struct is_specialized<Template, T, std::void_t<decltype(Template<T>{})>>:
    std::true_type
{};

And here is a small example of how it can be used:

template<typename T>
struct foo;

template<>
struct foo<int> {};

template<>
struct foo<float> {};

int main()
{
    // Should print 1 1 0
    std::cout << is_specialized<foo, int>::value << ' '
              << is_specialized<foo, float>::value << ' '
              << is_specialized<foo, double>::value;
}

Is there any way I could improve this specialization trait? Any kind of review is welcome :)

I think there's an issue with wording here. What you're testing is if a given instantiation of a class template is default constructible. You're not testing if it's "specialized". You cannot check for that. How would you differentiate between:

template <typename T> struct foo { };
template <> struct foo<int> { };

// is foo<X> the primary or the specialization?

Back to your example - just because you cannot construct an object of a particular instantiation (e.g. foo<double>) doesn't mean that you can't name the type. You can do that just fine. That lets you simplify your trait down to:

template <typename, typename=void>
struct is_specialized : std::false_type
{};

template<typename T>
struct is_specialized<T, void_t<decltype(T{})>>
    : std::true_type
{};

Which you would use as is_specialized<foo<int>>::value (true) or is_specialized<foo<double>>::value (false).

But really, since we're just testing for constructibility, we should just use what's in the standard:

template <typename T>
using is_specialized = std::is_default_constructible<T>;


Should I hide or show this implementation? An animation is composed of frames. I have the following class:

class Frame
{
private:
    sf::IntRect rect;
    unsigned int duration;

public:
    Frame(sf::IntRect rect, unsigned int duration);

    unsigned int getDuration();
    sf::IntRect& getRect();
};

At the animation class I have the following function:

void Animation::addFrame(sf::IntRect rect, unsigned int duration) // public
{
    frames.push_back(Frame(rect, duration)); // ps: private std::vector<Frame> frames;
}

should it actually be:

void Animation::addFrame(Frame frame) // public
{
    frames.push_back(frame);
}

thus showing how animation is implemented underneath?
I'm also in doubt if the frame class shouldn't simply be a struct with rect and duration. Thanks a lot in advance!

Never lie in your code. If you say: addFrame, I expect that passing Frame should be absolutely fine. The first function you have to provide as this class' interface is addFrame(Frame const&). Then, if you firmly believe that having the (IntRect, uint) overload is really useful when writing real client code, add this overload. But (Frame const&) should go first (I mean when you think whether or not).

BTW, I'm not sure what the Frame is, but you should consider passing it by constant reference - that's idiomatic.


Animate a box, bouncing left and right I wrote the following code for move a box to right and return it to left, and repeat this action forever.

This code works, but is there a better solution?

function move(){
 let box = document.getElementById("box");
 if(box.style.left.replace("px","") < 180 && check == true){
   moveRight(box);
  }else if (box.style.left.replace("px","") == 180 || check == false)
    {

      if(box.style.left.replace("px","") > 0){
          check = false;
          moveleft(box);
      }else if (box.style.left.replace("px","") == 0){
            check = true;
        }
    }
}
function moveRight(box){
   if(box.style.left != ""){
     let temp = box.style.left.replace("px","");
     temp = parseInt(temp);
     box.style.left = temp+1+"px";
   }else{box.style.left = "1px";}
}
function moveleft(box){
   if(box.style.left != ""){
     let temp = box.style.left.replace("px","");
     temp = parseInt(temp);
     box.style.left = temp-1+"px";
   }else{box.style.left = "1px";}
}
var check = true;
setInterval(move,10);
#plan{
        width: 200px;
        height: 200px;
  background: #00C0FF;
        position: relative;
 }
 #box{
     width: 20px;
  height: 20px;
  background: red;
        position: absolute;

}
<!DOCTYPE html>

Please take care to use consistent indentation for your JavaScript, HTML, and CSS.  In particular, avoid mixing spaces and tabs.

Avoid using meaningless variable names such as check and temp.  In this case, you didn't even need temp, because:

  If parseInt encounters a character that is not a numeral in the specified radix, it ignores it and all succeeding characters and returns the integer value parsed up to that point. parseInt truncates numbers to integer values. Leading and trailing spaces are allowed.

Your sleep() function appears to be unused.  In any case, you should avoid having a while loop that simply wastes CPU power; setInterval() and setTimeout() are much more appropriate ways to control timing. For DOM-related updates and animations, though, you should use requestAnimationFrame().

The entire problem would be better solved using CSS animations, which are supported by a large proportion of modern browsers.  In fact, the set of browsers that support the let keyword (which you used) is a subset of the browsers that support CSS Animations.

@keyframes slide {
    from { left: 0; }
    to   { left: 180px; /* 200px - 20px */ }
}

#plan {
    width: 200px;
    height: 200px;
    background: #00C0FF;
    position: relative;
}

#box {
    width: 20px;
    height: 20px;
    background: red;
    position: absolute;
    animation: 3.6s linear infinite alternate slide;
}