Bash function to parse git status I have a function here and wondered how well this can be refactored.

I currently have this:

status=`git status 2>&1 | tee`
dirty=`echo -n "${status}" 2> /dev/null | grep "modified:" &> /dev/null; echo "$?"`
untracked=`echo -n "${status}" 2> /dev/null | grep "Untracked files" &> /dev/null; echo "$?"`
ahead=`echo -n "${status}" 2> /dev/null | grep "Your branch is ahead of" &> /dev/null; echo "$?"`
newfile=`echo -n "${status}" 2> /dev/null | grep "new file:" &> /dev/null; echo "$?"`
renamed=`echo -n "${status}" 2> /dev/null | grep "renamed:" &> /dev/null; echo "$?"`
deleted=`echo -n "${status}" 2> /dev/null | grep "deleted:" &> /dev/null; echo "$?"`
bits=''
if [ "${renamed}" == "0" ]; then
  bits=">${bits}"
fi
if [ "${ahead}" == "0" ]; then
  bits="*${bits}"
fi
if [ "${newfile}" == "0" ]; then
  bits="+${bits}"
fi
if [ "${untracked}" == "0" ]; then
  bits="?${bits}"
fi
if [ "${deleted}" == "0" ]; then
  bits="x${bits}"
fi
if [ "${dirty}" == "0" ]; then
  bits="!${bits}"
fi
if [ ! "${bits}" == "" ]; then
  echo " ${bits}"
else
  echo ""
fi

I have played with it a little bit but I'm not an expert with bash so refactoring this is a little tricky, here is my attempt:

gitstatus=(
  "renamed;renamed:;>"
  "dirty;modified:;!"
  "untracked;Untracked files;?"
  "ahead;Your branch is ahead of;*"
  "newfile;new file:;+"
  "deleted;deleted:;x"
)

bits=''

for status in "${gitstatus[@]}"; do

  value=(${status//;/ })
  check=`echo -n "${value[0]}" 2> /dev/null | grep "${value[1]}" &> /dev/null; echo "$?"`

  if [ "${check}" == "0" ]; then
    bits="${value[2]}${bits}"
  fi

done

if [ ! "${bits}" == "" ]; then
  echo " ${bits}"
else
  echo ""
fi

Porcelain format

As @Vogel612 noted, the --porcelain format is the right one to use for scripting:

  The porcelain format is similar to the short format, but is guaranteed not to change in a backwards-incompatible way between Git versions or based on user configuration. This makes it ideal for parsing by scripts.

For the purposes of reviewing your code, though, I'll stick with the human format.

Redirection

There seems to be unusual concern placed on the handling of the standard error streams.  For the most part, you shouldn't need to worry about standard error that much.  As a rule of thumb, standard error contains out-of-band error messages that aren't really part of the output, and therefore aren't worth parsing unless you are interested in capturing those messages.  It may or may not be a good idea to redirect it to /dev/null.

As an example of that concern, I see git status 2>&1.  What sorts of messages might be in git's standard error.  One example would be

fatal: Not a git repository (or any of the parent directories): .git

Is that something that we would be interested in parsing?  Not really.  Is that a message that we want to make sure that the user never sees?  Maybe.  Therefore, standard error should either be left alone or redirected to /dev/null; lumping it together with standard output produces little benefit.

The standard error redirection in echo -n "${status}" 2> /dev/null is just superfluous.  Echoing a string should never produce anything on standard error.  As for grep … &> /dev/null, consider doing grep -q instead.

I don't understand why you need to | tee.

One pass, no buffering

Instead of buffering the $status and doing many command substitutions with echo -n "${status}" … | grep …, I suggest doing it all in one pass in pure Bash.

git status | (
    unset dirty deleted untracked newfile ahead renamed
    while read line ; do
        case "$line" in
          *modified:*)                      dirty='!' ; ;;
          *deleted:*)                       deleted='x' ; ;;
          *'Untracked files:')              untracked='?' ; ;;
          *'new file:'*)                    newfile='+' ; ;;
          *'Your branch is ahead of '*)     ahead='*' ; ;;
          *renamed:*)                       renamed='>' ; ;;
        esac
    done
    bits="$dirty$deleted$untracked$newfile$ahead$renamed"
    [ -n "$bits" ] && echo " $bits" || echo
)


Priority Queue with update-able values Here is my attempt to implement a minimum priority queue class in Python using the heapq module. I plan to use it in graph search algorithms so the values associated with each key are update-able.

Note: Any obsolete values related to an updated key are kept until they are on the top of the queue, at which time they are ignored.

from heapq import heappush, heappop, heapify

class PriorityQueueUpdateable(object):
    """
    Updateable Priority Queue implemented with heapq module and standard python dictionary
    """
    def __init__(self):
        self._heap = []
        self._dict = dict()
        heapify(self._heap)

    def _clear_heap(self):
        """
        Removes obsolete entries from heap
        """
        value, key = self._heap[0]
        while (key not in self._dict) or (self._dict[key] != value):
            heappop(self._heap)
            if not self._heap:
                break
            value, key = self._heap[0]

    def pop(self):
        if not self:
            raise IndexError("Queue is empty")

        self._clear_heap()

        value, key = heappop(self._heap)
        del self._dict[key]

        self._clear_heap()

        return key, value

    def peek(self):
        if not self:
            raise IndexError("Queue is empty")
        self._clear_heap()
        value, key = self._heap[0]
        return key, value

    def __contains__(self, key):
        return key in self._dict

    def __getitem__(self, key):
        return self._dict[key]

    def __len__(self):
        return len(self._dict)

    def __setitem__(self, key, value):
        self._dict[key] = value
        heappush(self._heap, (value, key))

The code passes this simple test

pq = PriorityQueueUpdateable()
pq[1]= 0.1
pq[1]= 2
pq[1]= 0.2
pq[2] = 6
pq[2] = 0.1
pq[2]= 0.001
assert pq[1] == 0.2
assert pq[2] == 0.001

assert 2 in pq
assert 1 in pq

assert len(pq) == 2
assert pq.pop() == (2, 0.001)
assert pq.pop() == (1, 0.2)

I would appreciate any feedback on improving my code. Thanks.

1. Bug

You can't pop an item from the queue if it's the only item:

>>> q = PriorityQueueUpdateable()
>>> q[1] = 1
>>> q.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "cr163560.py", line 41, in pop
    self._clear_heap()
  File "cr163560.py", line 25, in _clear_heap
    value, key = self._heap[0]
IndexError: list index out of range

The problem is in the pop method: it calls _clear_heap after popping the item (as well as before). But at this point there might be no items left in the queue. In your simple test, you add both keys to the queue multiple times, so that when you pop an item it's never the last item (because there are more items with the same key remaining in the queue).

2. Review

The Python library documentation has a section "Priority Queue Implementation Notes" which gives some advice on implementing a priority queue using a heap. This is well worth reading.
The docstring for the class doesn't give much of a clue as to how to use it. Docstrings should be written from the user's point of view, and shouldn't include implementation details (like "implemented with heapq module") — these are only needed by developers and so can be mentioned in comments.
There are no docstrings for the __init__, pop and peek methods.
It would be convenient if the __init__ method accepted an optional iterable of (key, priority) pairs. This would make it easier to create priority queues.
In __init__, there's no need to call heapq.heapify — this does nothing on an empty heap.
Using __setitem__ to add an item to the queue seems strange — normally one would expect a method adding something to a queue to be named something like push, append, or put. (Compare heapq.heappush, collections.deque.append, queue.Queue.put.)
The second argument to __setitem__ is named value, but this is misleading — actually it's the priority of the key.
Priorities work in reverse — if you want an item to have a higher priority then you have to give it a lower value (this happens because Python's heaps are min-heaps). It would probably suit more applications if priorities worked in the usual way. (You'd have to negate the priority values to make higher values mean higher priorities.)
You give a test case, which is great! It would be convenient to turn this into a unit test (perhaps using the unittest module) so that it can be automatically run.


How clean is this mustache template for a listing page? This was our old site that I am redesigning.

Someone else hardcoded with inline CSS and javascript in tables.

I wanted to make it dynamic, so I added Mustache and made this template:

{{#labs}}

{{{lab}}}

      {{#stadt}}
        {{{stadt}}}

      {{/stadt}}

      {{#telefon}}
        {{{telefon}}}

      {{/telefon}}

      {{#webseite}}

          {{{webseite}}}

      {{/webseite}}

{{/labs}}

Here is some of the JSON file:

{ "labs" : [
{
    "lab":"Ri&szlig;mann Zahntechnik GmbH",
    "stadt":"D-06917 Jessen",
    "telefon":"+49 (0) 3537 21 38 61",
    "webseite":"www.rissmann-zahntechnik.de"
  },

Would it make a big enough difference to not have the full word as the name?  So maybe like "l" instead of "lab" and "w" instead of "webseite", etc.

Here is the result of the listings:

The even spacing between the icon and the values was achieved by this CSS rule:

.lab i { width: 27px; }

Also, does it make sense to have it in a single
 tag, or should I consider placing each value in its own
?

By using excessive markup for presentational purposes, the template is the exact opposite of clean.

{{{telefon}}}

vs.

{{{telefon}}}

If you're not able to do this because of a library you're depending on, my recommendation is to find a better library.

By moving away from tables, you've committed a sin that's just as bad as using tables for layout:  you're using non-tabular markup for tabular data.  It is understandable that you don't want it to look like a table (either for aesthetic or responsive reasons), but tables don't have to look like tables any more than a list has to look like a list.

Go back to using tables and make adjustments to your CSS instead:

http://jsfiddle.net/SGK8Q/

What the markup should end up looking similar to this:

            Lab
            Contact
            Phone
            Website

            ABC
            Johnny
            555-1234
            http://abc.example.com/

            DEF
            Billy
            555-1234
            http://def.example.com/

            GHI
            Dave
            555-1234
            http://abc.example.com/

The CSS:

table, tbody, tr, td, th {
    display: block;
}

thead {
    display: none;
}

/* everything past here is optional */
tr + tr {
    margin-top: 1em;
}

.name {
    font-size: 1.2em;
    font-weight: bold;
}

.url {
    color: blue;
    text-decoration: underline;
}


Setting the positions of nodes based on a layout I have a bit of code that looks like this:

    for (Node n : g.getNodes().values()){
        n.setPosition(new Position(new Double(lo.getX(new Integer(n.getId()))).intValue(), new Double(lo.getY(new Integer(n.getId()))).intValue()));
    }

Essentially all I'm wanting to do is for each node in the collection, fetch and assign the position for that node from the layout.

Let me explain:

Node has an id of type int which is returned by n.getId().
The Layout lo will return the X and Y positions of the node by calling getX(Integer id) and getY(Integer id). The type returned is double.
A Node has a Position object which has constructor (int, int).

So:

In order to pass the id into the layout i need to use new Integer(id)
In order to convert the returned double to int I need to first upgrade the double to Double using new Double and then use .intValue() to convert it to an int.

It all seems ridiculous and verbose.

I am the one writing the Position and Node classes, so I can change the constructor and method signatures and return types if want. The Layout class is an external library, so I'll have to work with their signatures.

For example, an easy fix would be to create a Position(double x, double y) constructor, and do the double -> Double -> int conversion in the constructor.

public Position (double x, double y) {
    this.x = new Double(x).intValue();
    this.y = new Double(y).intValue();
}

This would change the code to:

    for (Node n : g.getNodes().values()){
        n.setPosition(new Position(lo.getX(new Integer(n.getId())),lo.getY(new Integer(n.getId()))));
    }

I could also create a second getter on Node to return Integer.

public Integer getIdAsInteger(){
    return new Integer(this.id);
}

Is this a good idea?

This would reduce the code to:

    for (Node n : g.getNodes().values()){
        n.setPosition(new Position(lo.getX(n.getIdAsInteger()),lo.getY(n.getIdAsInteger())));
    }

Finally, I could also create an additional setter setPosition(double x, double y).

public void setPosition(double x, double y) {
    this.position = new Position(x, y);
}

which would reduce the code to:

    for (Node n : g.getNodes().values()){
        n.setPosition(lo.getX(n.getIdAsInteger(),lo.getY(n.getIdAsInteger()));
    }

The question is - is this the right way to go about structuring my code? It still seems very verbose, and a lot of boiler plate, I'm wonder if there's another much simpler design pattern that addresses this.

If you have the control over the Position class, why not have a setPosition which takes the layout as a parameter? This would render the loop to be:

for (Node n: g.getNodes().values) {
    n.setPosition(lo);
}

This way you hide the conversion within the method, but it is still clear that your position is set relative to the layout, lo.  How you implement the setPosition() isn't then as interesting, but you could then easily do something like:

public void setPosition(Layout lo) {

    Position newPos = new Position(
        new Double(lo.getX(this.id)),
        new Double(lo.getY(this.id)));

    setPosition(newPos());
}

This assumes that the id is available as an Integer within the Node class, but you'll get the gist of the idea and can surely complete it.


Loading sub items of TreeView in background I am working with a TreeView (default control from .Net Framework) that displays hierachical data. Data are bound to the view using MVVM pattern with the HierarchicalDataTemplate.

<HierarchicalDataTemplate DataType="{x:Type models:TreeItemViewModel}" ItemsSource="{Binding Children, Mode=OneWay}">
    <TextBlock Text="{Binding Name}" />
</HierarchicalDataTemplate>

The child items are loaded automatically when the view requests the child collection. To stay responsive, the child items are loaded in background up to a specific depth:

public class TreeItemViewModel : ViewModelBase
{
    private readonly ObservableCollection<TreeItemViewModel> myChildren = new ObservableCollection<TreeItemViewModel>();
    private const int PRELOADING_DEPTH = 1;

    public string Name { get; set; }
    public bool IsLoaded { get; set; }
    public bool IsLoading { get; set; }

    public ObservableCollection<TreeItemViewModel> Children
    {
        get
        {
            ThreadPool.QueueUserWorkItem(o => EnsureChildrenAreLoaded(myChildren, 0));
            return myChildren;
        }
    }

    public void EnsureChildrenAreLoaded(ObservableCollection<TreeItemViewModel> childrenToFill, int depth)
    {
        if (!IsLoaded && !IsLoading)
        {
            IsLoading = true;
            var children = LoadChildren().ToArray();
            App.RunOnGuiThread(() =>
            {
                foreach (var child in children)
                    childrenToFill.Add(child);
                IsLoaded = true;
                IsLoading = false;
            });
        }
        if (depth < PRELOADING_DEPTH)
            foreach (var child in myChildren)
                child.EnsureChildrenAreLoaded(child.myChildren, depth + 1);
    }

    protected virtual IEnumerable<TreeItemViewModel> LoadChildren()
    {
        // logic for loading sub items
        return Enumerable.Empty<TreeItemViewModel>();
    }
}

RunOnGuiThread:

    public static void RunOnGuiThread(Action action)
    {
        if (Current == null || Current.Dispatcher == null)
            action();
        else
            Current.Dispatcher.Invoke(action);
    }

Is that a proper solution? Has it any disadvantages / potential for improvements?

I do not see your full UI then maybe you're using it (to display a busy indicator?) but, from what I have here, it seems that IsLoading is just a repetition for IsLoaded and as such it should be dropped. Any reason for EnsureChildrenAreLoaded() to be public and TreeItemViewModel not to be sealed?

EnsureChildrenAreLoaded() might be:

var children = LoadChildren().ToArray();
App.RunOnGuiThread(() =>
{
    foreach (var child in children)
        childrenToFill.Add(child);

    IsLoaded = true;
});

However we now have the problem to preload the children. My major concern here is that you're queuing an action in the pool each time you read the property. Not such big overhead but avoidable. Also I'd move this responsibilities to separate methods:

void LoadChildrenAndUpdateUi(ObservableCollection<TreeItemViewModel> childrenToFill)
{
    IsLoaded = true;

    var children = LoadChildren().ToArray();
    App.RunOnGuiThread(() =>
    {
        foreach (var child in children)
            childrenToFill.Add(child);
    });
}

And:

ObservableCollection<TreeItemViewModel> EnsureChildrenAreLoaded(
    ObservableCollection<TreeItemViewModel> childrenToFill, int depth)
{
    if (depth >= PRELOADING_DEPTH)
        return;

    if (!IsLoaded)
        ThreadPool.QueueUserWorkItem(_ => LoadChildrenAndUpdateUi(myChildren));

    foreach (var child in myChildren)
        child.EnsureChildrenAreLoaded(child.myChildren, depth + 1);

    return myChildren;
}

Our getter will then be:

public ObservableCollection<TreeItemViewModel> Children
    => EnsureChildrenAreLoaded(myChildren, 0);

Major difference is that we're going through the children to determine if they have to be loaded in the calling UI thread but we're queuing an action in the thread pool only when required. Note that we're using only one property to track the state (IsLoaded, which should be private). I set its value to true before effectively reading children to avoid multiple parallel requests, name is now somehow misleading and should be changed to something meaningful (_isVisited or something like that).

What next? If PRELOADING_DEPTH might ever be 0 or loading time may be really long then I'd add a dummy item to the child collection (to display the expand/collapse indicator), something like:

public TreeItemViewModel()
{
    Children.Add(new TreeItemViewModel { Name = "Loading..." });
}

Removed before you start adding new items:

children.Clear();
foreach (var child in children)
    childrenToFill.Add(child);

But, well, you already have a busy indicator then you don't need this at all!

Edit: if you're using IsLoading in your UI then, unfortunately, you can't drop it that easily. I think you have two options: replace IsLoading and IsLoaded with an enum like enum LoadingStatus { NotLoaded, Loading, Loaded } used in conjunction with a value converter to hide/show the busy indicator or use ordering (as you already doing) to avoid locks (because fortunately you have only one thread for writing):

var children = LoadChildren().ToArray();
App.RunOnGuiThread(() =>
{
    foreach (var child in children)
        childrenToFill.Add(child);

    IsLoaded = true;
    IsLoading = false;
});

Set IsLoading in the UI thread to avoid race conditions (both read and write will be then done in the same UI thread):

if (!IsLoaded && !IsLoading)
{
    IsLoading = true;
    ThreadPool.QueueUserWorkItem(_ => LoadChildrenAndUpdateUi(myChildren));
}

Final notes.

If your depth is limited to direct children then you  may simplify your implementation (just invoke the lazy load method when you populate the list). You may also want to try to use a LazyAsync<T> implementation (I saw a nice one somewhere...can't find/remember where).

WPF supports asynchronous binding with a simple IsAsync=true in the binding expression. You may want to experiment with that, see MSDN for details


NodeJS conditional request before the real request In my code I have to login a user with username and password. But if the user sends his e-mail instead of his username, I have to resolve it with another request.

This is what the code looks like:

exports.auth = (request, response, next) ->
  username = request.body.username
  if request.body.email
      users.findByEmail request.body.email, (error, result) ->
          return next new InternalServerError(error) if error
          username = result[0].username
          auth.auth username, request.body.password, (error, result) ->
              return next new InternalServerError(error) if error
              response.json responseData
  else
      auth.auth username, request.body.password, (error, result) ->
          return next new InternalServerError(error) if error
          response.json responseData

As you can see there are 3 duplicate lines.

Does anyone know a good code style do make this better? Maybe with Promises? Async Waterfall? Waitfor?

Promises would make sense to me, but first step would be to extract stuff into functions.

You don't really need promises for this, though. Here's one way to just do it with plain callbacks:

exports.auth = (request, response, next) ->
  getUsername = (request, cb) ->
    email = request.body.email
    return cb null, request.body.username unless email

    users.findByEmail email, (error, result) ->
      return cb new InternalServerError(error) if error
      cb null, result[0].username

  getUsername (err, username) ->
    return next err if err
    auth.auth username, request.body.password, (err, json) ->
      return next err if err
      response.json json


Printing a text rectangle I'm starting C as my first language and am just under halfway done the book I'm using. However, I commonly hear about 'bad' programmers and 'bad' code whenever I encounter any sort of programming related discussion on the internet.

I've done some examples that do work as they should but, I want to make sure that when I eventually am able to contribute to projects on GitHub, etc. that I'm not screwing everything up and writing unmaintainable code.

Do these examples follow common best practices? I did have comments but took them out as the code should be easy enough to understand and it's the actual code I'm wondering about.

/*make a box*/
#include <stdio.h>
int main(void)
{
    int i = 0;
    int long length = 0;
    int long width = 0;
    printf("Enter Box dimensions (LxW):");
    scanf("%ld %ld", &length, &width);
    for(i = 0; i <= width; i++)
    {
        printf("*");
    }
    for(i = 0; i <= length; i++)
    {
        printf("\n*");
        for(int a = 0; a <= (width-2); a++)
        {
            printf(" ");
        }
        printf("*");
    }
    printf("\n");
    for(i = 0; i <= width; i++)
    {
        printf("*");
    }
    return 0;
}

Dimensions and looping

It looks like you have some off-by-one errors.  This is not a 1×7 box by any definition that I can think of:

Enter Box dimensions (LxW):1 7
********
*      *
*      *
********

In C, the idiomatic way to write a loop that does something n times is for (int i = 0; i < n; i++) { … }.    (Sometimes, the situation calls for for (int i = 1; i <= n; i++) { … } instead, but that's rarer.)  You start your counters at 0, which is good, but you used <= in your termination conditions, which is weird.

Functions

It's a good habit to make a function for any chunk of code that has an identifiable purpose.  Here, it makes sense to define a void printBox(int length, int width) function.  If you need to modify the program to take command-line parameters instead of keyboard input, then you can still call the same function.

By the way, int long is a bit unconventional.  Unless you have a specific reason to do otherwise, just use int.

Smarter library use

You're basically using printf() where the simpler putchar() function will do.  The vertical lines, though, can be better written using a smarter call to printf().  (Consult the documentation for printf().)

Error checking

Functions like scanf() can fail due to invalid user input.  You should be in the habit of checking the return value.

Suggested solution

#include <stdio.h>

void printBox(int length, int width) {
    // Top
    if (length >= 1) {
        for (int i = 0; i < width; i++) {
            putchar('*');
        }
        putchar('\n');
    }

    // Sides
    for (int i = 0; i < length - 2; i++)
    {
        printf("*%*s\n", width - 1, "*");
    }

    // Bottom
    if (length >= 2) {
        for (int i = 0; i < width; i++) {
            putchar('*');
        }
    }
    putchar('\n');
}

int main(void)
{
    int length, width;
    printf("Enter Box dimensions (LxW):");
    if (2 != scanf("%d %d", &length, &width)) {
        // Indicate input error
        return 1;
    }
    printBox(length, width);
}


Simple class for 2D  1D array index conversion I made a class to convert the index between 2D and 1D arrays.
For example,
between

{1,3,5,7,9,11} and {{1,3},{5,7},{9,11}}

When i is 0, xy should be (0,0)
When i is 1, xy should be (0,1)
When i is 2, xy should be (1,0)

And so on...

I would be able to convert between the i-index and the xy-index to find get the equivalent location. I feel like this piece of code may be too long for its purpose.

class IndexConv {
    public:
    IndexConv(int rows, int cols);
    bool check_i(int i) const;
    bool check_xy(int x, int y) const;
    pair<int, int> to_xy(int i) const;
    int to_i(int x, int y) const;
    private:
    const int rows_;
    const int cols_;
};

IndexConv::IndexConv(int rows, int cols)
    :rows_(rows), cols_(cols) {}

bool IndexConv::check_i(int i) const
{
    return i>=0 || i<rows_*cols_;
}

bool IndexConv::check_xy(int x, int y) const
{
    return x>=0 && y>=0 && x<rows_ && y<cols_;
}
pair<int, int> IndexConv::to_xy(int i) const
{
    if(!check_i(i)) throw out_of_range("IndexConv: i out of bounds.");
    int x = i/cols_;
    int y = i-x*cols_;
    return make_pair(x,y);
}

int IndexConv::to_i(int x, int y) const
{
    if(!check_xy(x,y)) throw out_of_range("IndexConv: xy out of bounds.");
    int i = x*cols_+ y;
    return  i;
}

Use modulus

Instead if this i-x*cols_ you can use the modulus operator i % cols_.

Use a unsigned type.

If you use unsigned there is no need to check for x >= 0 && y >= 0. Also you can con throw the exception directly in check. And you just need check_xy.

    void IndexConv::check(unsigned x, unsigned y) const
    {
        if(x >= rows_ || y >= cols_)
            throw std::out_of_range("IndexConv: parameter out of bounds.");
    }

    pair<int, int> IndexConv::to_xy(unsigned i) const
    {
        int x = i / cols_;
        int y = i % cols_;
        check(x, y);
        return make_pair(x, y);
    }

    int IndexConv::to_i(unsigned x, unsigned y) const
    {
        check(x, y);
        return x * cols_ + y;
    }

EDIT: Changed the answer to keep check_xy. Keeping check_i can map (0,2) to 2 when it should throw an exception (Following your example).


Monoidal tree interview in Haskell I was working on the following interview question:

  Given an array of integers, return a new array such that each element
  at index i of the new array is the product of all the numbers in the
  original array except the one at i.

  For example, if our input was [1, 2, 3, 4, 5], the expected output
  would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the
  expected output would be [2, 3, 6].

  Follow-up: what if you can't use division?

I decided to do the followup question in Haskell:

{-# LANGUAGE ViewPatterns, PatternSynonyms #-}
import Control.Monad (join)
import Control.Arrow ((***))
import Data.Sequence (Seq)
import qualified Data.Sequence as Seq
import Data.Monoid (Product(..), getProduct)

mapTuple = join (***)

pattern Empty   <- (Seq.viewl -> Seq.EmptyL)
pattern x :< xs <- (Seq.viewl -> x Seq.:< xs)

data Tree a = Leaf a | Branch a (Tree a, Tree a)
label :: Tree a -> a
label (Leaf a) = a
label (Branch a _) = a

{- Create a complete binary tree, such that each subtree contains the concat of all
 - elements under it. -}
makeTree :: Monoid a => Seq a -> Tree a
makeTree Empty = undefined
makeTree (label :< Empty) = Leaf label
makeTree s =
  let midpoint = Seq.length s `div` 2 in
  let subseq = Seq.splitAt midpoint s in
  let subtrees = mapTuple makeTree subseq in
  let subtreeLabels = mapTuple label subtrees in
  let label = uncurry mappend subtreeLabels in
  Branch label subtrees

{- Zippers. -}
data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a)
type Breadcrumbs a = [Crumb a]
type Zipper a = (Tree a, Breadcrumbs a)

goLeft :: Zipper a -> Zipper a
goLeft (Branch x (l, r), bs) = (l, LeftCrumb x r:bs)
goLeft (Leaf _, _) = error "Nothing to go left into"

goRight :: Zipper a -> Zipper a
goRight (Branch x (l, r), bs) = (r, RightCrumb x l:bs)
goRight (Leaf _, _) = error "Nothing to go right into"

-- Concat of all elements except the one corresponding to the given crumbs
concatAllExcept :: Monoid a => Breadcrumbs a -> a
concatAllExcept = concatAllExceptRev . reverse where
  concatAllExceptRev [] = mempty
  concatAllExceptRev ((LeftCrumb _ subtree) : xs) =
    concatAllExceptRev xs <> label subtree
  concatAllExceptRev ((RightCrumb _ subtree) : xs) =
    label subtree <> concatAllExceptRev xs

-- Return a list of zippers pointing to the leafs of the tree
dfsList :: Tree a -> [Zipper a]
dfsList t =
  reverse $ dfsListHelper (t, []) [] where
    dfsListHelper zipper@(Leaf _, _) accum = zipper : accum
    dfsListHelper zipper@(Branch _ _, _) accum =
      -- Since this is a Branch node, both [goLeft] and [goRight] will work.
      let l = goLeft zipper
          r = goRight zipper in
      dfsListHelper r (dfsListHelper l accum)

{- Produces a list such that the ith element is the concat of all elements in the
 - original list, excluding the ith element. -}
concatAllExceptEach :: Monoid a => [a] -> [a]
concatAllExceptEach = map (concatAllExcept . snd) . dfsList . makeTree . Seq.fromList

answer :: [Integer] -> [Integer]
answer = map getProduct . concatAllExceptEach . fmap Product

main = do
  print $ answer [3, 10, 33, 4, 31, 31, 1, 7]
  print $ answer [1, 2, 3, 4, 5]
  print $ concatAllExceptEach ["A", "B", "C", "D"]

Algorithm runs in Θ(n log n) which I believe is optimal. New to Haskell so all feedback welcome.

Welcome! Here are my thoughts what could be improved:

For top-level declarations, always do include types. I'm pretty sure in a few weeks it'll be difficult to realize what

mapTuple = join (***)

means without knowing that it's type is

mapTupple :: (b' -> c') -> (b', b') -> (c', c')

Also as you don't need arrows anywhere else, it makes sense to specialize the type to avoid accidental errors and get nicer error messages.
I'd put a newline betweek 'data...' and 'label'. Keeping consistent style helps readability very much.
You don't need to nest 'let' expressions. You can write just

let midpoint = Seq.length s `div` 2
    subseq = Seq.splitAt midpoint s
    ...
in Branch label subtrees

Instead of creating a sequence and then converting it into a balanced tree, you can convert a list directly into a balanced tree in O(n). This is a nice exercise on its own!
Use Haddock markup in comments, you can then generate nice documentation very easily.

  Algorithm runs in Θ(n log n) which I believe is optimal.

Are you sure?


JW Player + Brightcove Integration The following code gets video renditions from Brightcove using the media API. It then generates an ordered source list for the JW Player and selects the default rendition based on a pre-set bitrate.

function buildSourcesFromBrighcoveID(brightcoveID, onComplete) {
    var sources = [];
    var brightcoveAPI = 'http://api.brightcove.com/services/library';
    var parameters = {
      command: 'find_video_by_id',
      video_id: brightcoveID,
      video_fields: 'renditions',
      media_delivery: 'http',
      token: 'jskS1rEtQHy9exQKoc14IcMq8v5x2gCP6yaB7d0hraRtO__6HUuxMg..'
    };

    // Get renditions
    $.ajax({
      dataType: "jsonp",
      url: brightcoveAPI,
      data: parameters
    }).done(function(data){

      var targetRate = 800000; // Bps
      var lowestDiff;
      var closestRate;

      // Sort them by encoding rate, higher rate first
      data.renditions.sort(function(a, b) {
        return parseFloat(b.encodingRate) - parseFloat(a.encodingRate);
      });

      // Get the closest encoding rate to target
      var currentRate = data.renditions[0].encodingRate;
      var lowestDiff = Math.abs(currentRate - targetRate);

      $.each (data.renditions, function(id, rendition){
        var diff = Math.abs(rendition.encodingRate - targetRate);
        if (lowestDiff > diff) {
          lowestDiff = diff;
          closestRate = rendition.encodingRate;
        }
      });

      // Build sources for the player
      $.each (data.renditions, function(id, rendition){
        var newItem = {
          file: rendition.url,
          label: Math.round(rendition.encodingRate / 1000) + ' Kbps'
        }

        // Set default rendition
        if (rendition.encodingRate == closestRate) {
          newItem["default"] = true;
        }

        sources.push(newItem);

      });

      if (onComplete) onComplete(sources);
    });

    return sources;
  }

  function loadVideoPlayer(sources) {

    var playerInstance = jwplayer("player");
    playerInstance.setup({
      sources: sources,
      width: 727,
      height: 455,
      autostart: true
    });

  }

buildSourcesFromBrighcoveID('1520880903001', loadVideoPlayer);

Codepen

Questions

How can I be sure buildSourcesFromBrighcoveID completed before doing anything else? I currently run the function that builds the player from within the first function to be sure the Ajax completed, but I would like them to be independent.
Could I build the sources array in a more efficient way? I am currently iterating the renditions 3 times (to sort, to search for the best rendition and to build the sources array).

These two declarations are useless:

  var lowestDiff;
  var closestRate;

As you re-declare them later:

  var currentRate = data.renditions[0].encodingRate;
  var lowestDiff = Math.abs(currentRate - targetRate);

And, on that note, you shouldn't use the var keyword when you reference an already defined variable. However, in this case, the first block can be removed, making the second block the variable declaration.

The following block can be simplified:

  $.each (data.renditions, function(id, rendition){
    var newItem = {
      file: rendition.url,
      label: Math.round(rendition.encodingRate / 1000) + ' Kbps'
    }

    // Set default rendition
    if (rendition.encodingRate == closestRate) {
      newItem["default"] = true;
    }

    sources.push(newItem);

  });

into the following:

  $.each(data.renditions, function(id, rendition){
    sources.push({
      file: rendition.url,
      label: Math.round(rendition.encodingRate / 1000) + ' Kbps',
      default: (rendition.encodingRate == closestRate)
    });
  });

  How can I be sure buildSourcesFromBrighcoveID is completed before doing anything else? I currently run the function that builds the player from within the first function to be sure the Ajax completed, but I would like them to be independent.

You should make the function a promise and use a done callback to ensure the function has been completed successfully before continuing. Read this Stack Overflow question for more information.

  Could I build the sources array in a more efficient way? I am currently iterating the renditions 3 times (to sort, to search for the best rendition and to build the sources array).

Each loop does a different thing, so I'm not 100% sure whether they can be slimmed.


Schema.org structure for a news aggregator individual post I'm building a news aggregator website. This is my current schema structure for a single news article. There can be more than one article per page. I'm trying to have every possible piece of data structured. Am I missing something? How can this structure be schema.org-optimized for a news article post?

    <meta itemprop="inLanguage" content="es-419" />
    <meta itemprop="dateModified" content="2015-03-02T19:03Z" />
    <meta itemprop="keywords" content="correa, obama, whitehouse" />
    <meta itemprop="commentCount" content="41" />
    <meta itemprop="description" content="Excerpt of the news text goes here..." />
    <meta itemprop="isBasedOnUrl" content="http://eluniverso.com/2015/03/01/noticia3.html" />

        Headline goes here

    <time datetime="2015-03-02T17:43Z" itemprop="datePublished">Mar 2</time>

Complete article goes here. Two or three lines perhaps. Maybe more.

    politics
    67

        <meta itemprop="bestRating" content="5">
        <meta itemprop="worstRating" content="1">
        4.1/5 based on 249 votes

        <meta itemprop="logo" content="/logos/eluniverso.png" />

            El Universo

Related News 1

Related News 2

Related News 3

HTML5+Microdata

In case of meta/link:

If the value is a URI, you have to use link instead of meta.

So this

<meta itemprop="isBasedOnUrl" content="http://eluniverso.com/2015/03/01/noticia3.html" />

should be

<link itemprop="isBasedOnUrl" href="http://eluniverso.com/2015/03/01/noticia3.html" />

and this

<meta itemprop="logo" content="/logos/eluniverso.png" />

should be

<link itemprop="logo" href="/logos/eluniverso.png" />

Your thumbnail img is missing the required alt attribute.

Schema.org

In addition to (or instead of) headline it can be beneficial to provide name. The headline property can only be used for CreativeWork (and sub-types), while the name property is defined for every type. It’s likely that many consumers look for and make use of name but not headline.

You could provide both properties, separated with a space, on the same element, i.e.,

If the link in Organization is about this organization, you might want to use the url property.
The WebPage could reference the NewsArticle via the mainEntity property (if the page is only about a single news article; otherwise the NewsArticle could reference its WebPage with the reverse mainEntityOfPage property).

While you could use Microdata’s itemref attribute to reference it without changing the markup structure, it’s not necessary if markup changes are possible. You could specify WebPage on a container div (or the body, if it’s the only/current web page), e.g.:

Related News 1

Related News 2

Related News 3


Random distributions in Go with inheritance I am currently discovering Golang, and I try to implement some random variable generation functions similar to R functions.

To avoid code repetition, I'd like to use inheritance, which is quite complex with Go at first sight.

Each variable implements a x.R() method, which generate a random value following x distribution.

I'd like to implement x.Rn(n int), which simply returns an array of n random values. It is therefore the same for any random variable, as it simply calls x.R() n times.

So far, my implementation is as following:

// Continuouser Implements a continous law
type Continuouser interface{
    R() float64
    D(value float64) float64
    P(value float64) float64
}
// Continuous A Continuous law
type Continuous struct{
    Continuouser
}
// Rn Generate n draws of a continuous random variable
func (c Continuous) Rn(n int) (res []float64){
    if (n < 0){
        panic(errors.New("n must be positive"))
    }
    res = make([]float64,n)
    for i := 0; i < n; i++{
        res[i] = c.R()
    }
    return
}

And here is how I implement a law :

// NewBern Generate a new variable following a Bern(p) law
func NewBern(p float64) (x *Bern){
    x = &Bern{Discrete{},p,1.-p}
    // Discrete.discreter self reference X
    x.Discrete = Discrete{x}
    return
}

// R Generate a random value following the same Bernouilli distribution as x
func (x Bern) R() int64 {
    var u = NewStdUnif()
    // maybe there is a more idomatic way link int(u.R()<p)
    if u.R() < x.p {
        return 1
    }
    return  0
}

So, x does embed an anonymous continuous struct, which in turn embeds a reference to x, that implements the method R().

You can have access to the full repo here on GitHub.

It does work and avoid code redundancy, but is that the idiomatic Golang way?

Style comments

Don't panic. Return the incorrect value of n in your error using fmt.Errorf.
Use gofmt on your code. (Have your favorite editor call it on-save.)
There is no better way to convert a bool to an int than what you have.
Replace var u = … by u := ….
No need to use named returned parameters in Rn.

On your main question

What you have works, but consider if one caller of your library does:

cont := Continuous{}
cont.Rn(42)

If you can't guess, try it; it's a good way to learn =) Anyway, you don't want that to happen. So you can do this several ways. Before I'm going into two idiomatic options, let's talk about your interface definitions:

Rn only needs something that implements R, so you could probably have an interface only for this. Let's call this interface Law.
Your Continuouser should simply be called Continuous or ContinuousLaw (because it describes what a continuous law does). In its definition, replace the R() float64 by Law.
Your Continuous should be called MultiDrawer or something. The only reason you're defining it is because you want to draw multiple values; so name it accordingly.

Option 1:

func Rn(law Law, n int) []float64

It's very simple; what you're saying here is "give me a Law, I can give you n random values from it".

Option 2:

interface MultiDrawer {
    Rn(n int) []float64
}

struct multiDrawer { // unexported: you don't want callers to touch this directly
    Law
}

func NewMultiDrawer(law Law) MultiDrawer {
    return &multiDrawer(law)
}

func (md *multiDrawer) Rn(n int) []float64 {
    // your code using md.R()
}

You're saying something similar here: "give me a Law and I give you a MultiDrawer". It's better if you want to have a concept of a MultiDrawer variable that you'll later pass around or reuse.


Redirect http to https, non-www to www and "/index.php" to "/" Is this htaccess code the best/proper way to:

Send all http traffic to https
Send any visits to index.php to the URL that doesn't show "index.php"
Send all non-www traffic to www

This code works to do those things I mentioned, I just want to make sure it's the most proper/efficient way to do it and/or it's ordered correctly...

Options +FollowSymlinks
RewriteEngine on
RewriteCond %{HTTPS} off
RewriteRule ^(.*)$ https://%{HTTP_HOST}%{REQUEST_URI} [L,R=301]
RewriteCond %{THE_REQUEST} ^.*/index.php
RewriteRule ^(.*)index.php$ https://www.example.com/$1 [R=301,L]
rewritecond %{http_host} ^example.com [nc]
rewriterule ^(.*)$ https://www.example.com/$1 [r=301,nc]

Keep your code consistent. If you are using RewriteRule, use the same capitalisation format in all declarations. Same for setting the flags (R, L, NC etc.); or the variables and so on.

I personally prefer to give an extra newline between any new set of RewriteCond segment, so that I would be able to easily identify groups later on. As well as, adding comments never hurt anybody.

Prefer to handle the requests/paths at as late stage as possible.

Lastly, if you have just one domain name to handle; you can merge the https and naked-domain rules in a single one. The final ruleset would be:

Options +FollowSymlinks

RewriteEngine On

RewriteCond %{HTTPS} off [NC,OR]
RewriteCond %{HTTP_HOST} !^www\.example\.com$ [NC]
RewriteRule ^ https://www.example.com%{REQUEST_URI} [R=301,L]

RewriteCond %{THE_REQUEST} ^.*/index\.php [NC]
RewriteRule ^(.*)index\.php$ https://www.example.com/$1 [R=301,L]


Refactor to remove goto Is it possible to implement this function without goto, while keeping the code correct and readable?

using iter = std::string::const_iterator;

// Skip multiline comment in a source string.
// Initial iterator is at the first character after the "/*"
iter skipMultilineComment( iter i, iter fileEnd )
{
    while( true )
    {
        const char c1 = *i;
        if( c1 != '*' )
        {
            i++;
            if( i != fileEnd )
                continue;
            break;
        }

        // Found '*' character
    FoundAsterisk:
        i++;
        if( i == fileEnd )
            break;
        const char c2 = *i;
        if( c2 == '*' )
        {
/* Found another '*' character; can be more: ****/
            goto FoundAsterisk;
        }
        if( c2 != '/' )
        {
            i++;
            if( i != fileEnd )
                continue;
            break;
        }
        // Finally, found the closing token, "*/"
        i++;
        return i;
    }
    logError( "fatal error C1071: unexpected end of file found in comment" );
    throw E_INVALIDARG;
}

P.S. That’s not a test assignment or something, it’s production code. The input is GLSL, but the comments there are the same as in C++.

Yes, of course. (It's always possible to eliminate unstructured constructs by use of structured programming.) I recommend Kernighan & Plauger's The Elements of Programming Style for developing your own sense of structured programming.

Come on this journey with me!

Step 1: That confusing if at the top of the loop.

while (true) {
    const char c1 = *i;
    if( c1 != '*' )
    {
        i++;
        if( i != fileEnd )
            continue;
        break;
    }

c1 is never used again, so we can eliminate it. Then, breaking the loop means going to the end of the loop and setting a "don't do this loop again" flag; so let's make that flag; we'll call it done. Then continueing the loop means going to the end without setting that flag. So at this point we have

template<class It>
It skipMultilineComment(It it, It fileEnd)
{
    bool done = false;
    while (!done) {
        if (*it != '*') {
            ++it;
            done = (it == fileEnd);
        } else {
            // Found '*' character
        FoundAsterisk:
            ++it;
            if (it == fileEnd) break;
            if (*it == '*') {
                /* Found another '*' character; can be more: ****/
                goto FoundAsterisk;
            } else if (*it != '/') {
                ++it;
                if (it != fileEnd) continue;
                break;
            }
            // Finally, found the closing token, "*/"
            ++it;
            return it;
        }
    }
    logError( "fatal error C1071: unexpected end of file found in comment" );
    throw E_INVALIDARG;
}

Notice that I've cleaned up some whitespace style and renamed i (traditionally a name for an integer loop control variable) to it (traditionally a name for an iterator). I've also made the function a template so that I can get rid of that global-scope typedef at the top.

Okay, let's pull out the next break... or, no, let's skip down to that similar continue/break tangle at the bottom of the loop, and sort that out. Same transformation as before. I'll just show the loop, because nothing outside it has changed.

    while (!done) {
        if (*it != '*') {
            ++it;
            done = (it == fileEnd);
        } else {
            // Found '*' character
        FoundAsterisk:
            ++it;
            if (it == fileEnd) break;
            if (*it == '*') {
                /* Found another '*' character; can be more: ****/
                goto FoundAsterisk;
            } else if (*it == '/') {
                // Finally found the closing token, "*/"
                ++it;
                return it;
            } else {
                ++it;
                done = (it == fileEnd);
            }
        }
    }

Notice that I am also habitually untangling your if/else blocks. You don't want to have if (a == x) ... else if (a != y) ... else if (a == z) ... because that's just plain confusing. if/else chains should read like switch statements: one handler per interesting value. So here we have one handler for *it == '*', and one handler for *it == '/', and then one catch-all "else" handler.

Let's follow that guideline and refactor the outer if (*it != '*') as well.
Notice that once we do that, we don't need the comment // Found '*' character anymore, because it's obvious from the code itself. Getting to remove pointless comments is one of the most satisfying parts of the refactoring process!

    while (!done) {
        if (*it == '*') {
        FoundAsterisk:
            ++it;
            if (it == fileEnd) {
                done = true;
            } else if (*it == '*') {
                goto FoundAsterisk;
            } else if (*it == '/') {
                // Finally found the closing token, "*/"
                ++it;
                return it;
            } else {
                ++it;
                done = (it == fileEnd);
            }
        } else {
            ++it;
            done = (it == fileEnd);
        }
    }

Okay, let's tackle that goto. The fundamental algorithm here is, "While we're looking at a * character, increment it. But if we reach the end of the string, then stop." Normally we'd spell that as

while (it != fileEnd && *it == '*') { ++it; }

Let's see if we can shoehorn that line of code into our function in a natural way.

    while (!done) {
        if (*it == '*') {
            while (it != fileEnd && *it == '*') {
                ++it;
            }
            if (it == fileEnd) {
                done = true;
            } else if (*it == '/') {
                // Finally found the closing token, "*/"
                ++it;
                return it;
            } else {
                ++it;
                done = (it == fileEnd);
            }
        } else {
            ++it;
            done = (it == fileEnd);
        }
    }

Notice that every path to the bottom of the outer loop now ends with done = (it == fileEnd) (except in one case where we already know it == fileEnd and so we just set done = true). So basically we just keep going until it == fileEnd. That's our loop condition.

    while (it != fileEnd) {
        if (*it == '*') {
            while (it != fileEnd && *it == '*') {
                ++it;
            }
            if (it == fileEnd) {
            } else if (*it == '/') {
                // Finally found the closing token, "*/"
                ++it;
                return it;
            } else {
                ++it;
            }
        } else {
            ++it;
        }
    }

Okay, but, now we've got a loop within a loop. You know what? Maybe what we really want here is a simple state machine: Either we've just seen a *, or we haven't. If we have, and the next character is /, then we're done. Otherwise, keep going. That would code up like this:

template<class It>
It skipMultilineComment(It it, It fileEnd)
{
    for (bool seenStar = false; it != fileEnd; ++it) {
        if (*it == '/' && seenStar) {
            return it + 1;
        }
        seenStar = (*it == '*');
    }
    logError( "fatal error C1071: unexpected end of file found in comment" );
    throw E_INVALIDARG;
}

Yes. I like that better. But wait, we can do better than that! All we seem to be doing is looking for the string "*/" inside a longer string. That's string search, and there are library functions for that!

#include <string.h>

const char *skipMultilineComment(const char *it, const char *fileEnd)
{
    if (const char *p = memmem(it, fileEnd - it, "*/", 2)) {
        return p + 2;
    }
    logError( "fatal error C1071: unexpected end of file found in comment" );
    throw E_INVALIDARG;
}

or in C++17,

std::string_view skipMultilineComment(std::string_view text)
{
    size_t pos = text.find("*/");
    if (pos != text.npos) {
        return text.substr(pos + 2);
    }
    logError( "fatal error C1071: unexpected end of file found in comment" );
    throw E_INVALIDARG;
}


Reading certain values from an object I'm trying to read certain values from an object.  What would be the best practice to do so?

$jira_object = json_decode(trim($jira_value->data));
$this->_displayName = $jira_object->user->displayName;
$this->_issueID = $jira_object->issue->id;
$this->_issueKey = $jira_object->issue->key;
$this->_issueFieldSummary = $jira_object->issue->fields->summary;
$this->_issueFieldProgress = $jira_object->issue->fields->progress;
$this->_issueFieldType = $jira_object->issue->fields->issuetype;
$this->_issueFieldUpdated = $jira_object->issue->fields->updated;
$this->_issueFieldCreated = $jira_object->issue->fields->created;
$this->_issueFieldPriority = $jira_object->issue->fields->priority;
$this->_issueFieldStatus = $jira_object->issue->fields->status;
$this->_issueFieldAssignee = $jira_object->issue->fields->assignee;
$this->_issueFieldProject = $jira_object->issue->fields->project;

How could I make this shorter?

This is shorter, but not necessarily better or more readable.

$jira = json_decode(trim($jira_value->data), true);

$this->displayName = $jira['user']['displayName'];
$this->issueID = $jira['issue']['id'];
$this->issueKey = $jira['issue']['key'];

foreach ($jira['issue']['fields'] as $key => $val) {
   $key = ucfirst($key);
   $this->{"issueField$key"} = $val;
}


Binary Tree Maximum Turns Given any binary tree, what is the maximum number of turns possible in any path from root to any leaf?

A turn is when the path involves moving from left branch to right or vice-versa; i.e. the number of angels in a path. A straight line path has no turns.

The best I could get is the code below and it works with good performance, looking for better implementation

public class Tree
{
    public int x;
    public Tree l;
    public Tree r;
}

private int leftTurns(Tree T, int turns)
{
    if (T == null)
        return 0;

    return turns += Math.Max(
            leftTurns(T.l, 0),
            rightTurns(T.r, 1));
}

private int rightTurns(Tree T, int turns)
{
    if (T == null)
        return 0;

    return turns += Math.Max(
            leftTurns(T.l, 1),
            rightTurns(T.r, 0));
}

public int solution(Tree T)
{
    // write your code in C# 6.0 with .NET 4.5 (Mono)
    return Math.Max(
            leftTurns(T.l, 0),
            rightTurns(T.r, 0));
}

My concerns:

The semi-duplicate functions leftTurns() & rightTurns()
The readability of the algorithm
Is recursion necessary?

The code duplication is easily eliminated by passing an additional parameter:

    public int solution(Tree T)
    {
        return Math.Max(
            turn(T.l, 0, false),
            turn(T.r, 0, true)
        );
    }

    private int turn(Tree T, int turns, bool it_was_right) {
        if (T == null) {
            return 0;
        }
        return turns += Math.Max(
            turn(T.l, it_was_right, !it_was_right),
            turn(T.r, !it_was_right, it_was_right)
        );
    }

Now it is obvious that for the recursive calls an additional parameter is redundant. Making a helper function with only two parameters is a good exercise.

Recursion seems to be necessary. I cannot imagine a strictly iterative approach. At the end of the day you must check every path.

A small nitpick. You don't compute angels in the path (that would be quite hard indeed); you compute angles. Sorry, can't resist.


Simple Hangman game in Java I'm teaching myself Java and I had some basic questions on how well I am writing my code for readability. I feel like sometimes I'm just writing code that works, and I'm not that proud of myself when I have finished. I'm not asking you to rewrite my code; I'm just asking for some pointers on how optimize my code for readability.

import javax.swing.*;
import java.awt.event.*;
import java.awt.*;

public class Hangman implements ActionListener{
    JFrame frame;
    JTextField userInput;
    JLabel textContents;
    String word = "horse";
        int correctGuesses;
    int incorrectGuesses;
    String guessesLeft;
    boolean lose = false;
    StringBuilder wordsGuessedCorrectly;
    JLabel letters;

    Hangman() {
        incorrectGuesses = 0;
        correctGuesses = 0;
        guessesLeft = "You have " + (6 - incorrectGuesses) +" chances left to guess a " + word.length() + " letter word";
        wordsGuessedCorrectly = new StringBuilder();

        frame = new JFrame("A Hangman Game");
        frame.setSize(300,125);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setLayout(new GridLayout(3, 1));

        userInput = new JTextField();
        userInput.addActionListener(this);
        frame.add(userInput);

        textContents = new JLabel();
        textContents.setText(guessesLeft);
        textContents.setHorizontalAlignment(JLabel.CENTER);
        textContents.setBorder(BorderFactory.createLineBorder(Color.BLUE));
        frame.add(textContents);

        letters = new JLabel("The letters you guess correctly go down here!");
        letters.setHorizontalAlignment(JLabel.CENTER);
        letters.setBorder(BorderFactory.createLineBorder(Color.RED));
        frame.add(letters);

        frame.setVisible(true);

    }

    String seperateLetter(String a, int x, int y) {
        return a.substring(x, y);
    }

    void testLetter(String a) {
        if (word.contains(a) && wordsGuessedCorrectly.toString().contains(a) == false && correctGuesses != (word.length() - 1)) {
            correctGuesses++;
            wordsGuessedCorrectly.append(a);
            letters.setText(wordsGuessedCorrectly.toString());
            textContents.setText("Correct Guess!");
        }
        else if (word.contains(a) && wordsGuessedCorrectly.toString().contains(a)) {
            textContents.setText("You've already guessed this letter!");
        }
        else if (word.contains(a) && wordsGuessedCorrectly.toString().contains(a) == false && correctGuesses == (word.length() - 1)) {
            lose = true;
            textContents.setText("You Win!");
            wordsGuessedCorrectly.append(a);
            letters.setText(wordsGuessedCorrectly.toString());
        }
        else if (word.contains(a) == false && incorrectGuesses == 5){
            textContents.setText("You lose!");
            lose = true;
        }
        else {
            incorrectGuesses++;
            textContents.setText("Incorrect Guess! You have " + (6 - incorrectGuesses)  + " left.");
        }
    }

    public void actionPerformed(ActionEvent ae) {
        if (lose == false) {
            testLetter(seperateLetter(userInput.getText(), 0 , 1));
            userInput.setText("");
        }
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                new Hangman();
            }
        });
    }
}

Just quickly, here's some feedback:

I think your set up code is fine (where you're creating the JFrames etc), it's very boiler platey, but that's java.
But you shouldn't put that logic in the constructor. Put it in an init() method, called after construction.
Do use scope declarations, ie. make that Hangman() constructorpublic Hangman(). Same with void testLetter is this method meant to be public or private? Make it explicit so that others (and yourself, in six months!) know how the code is meant to be used.
Consider separating your Swing/GUI logic, and your game logic to different classes. ie, something like HangmanApp (your main class) contains a HangmanGui and a HangmanLogic.
You have magic numbers all through your code. For example this line is particularly bad: textContents.setText("Incorrect Guess! You have " + (6 - incorrectGuesses)  + " left.");
What if you want to change the number of guesses? Ideally these configurations would be set in a properties file, but for a small application setting them at the top of the class is fine.
Your if else branching in testLetter is scary. As it currently is, I can't immediately see what each branch is for. Comments would help on each branch, but I would move 'test if the letter fits' logic, and 'what should I do if letter is correct/incorrect' logic, into their own private methods.

eg. something like:

void testLetter(String a) {

     if (evaluateGuess(a)){   //returns true if guess is correct
         handleCorrectGuess(a);
     }
     else (
         handleIncorrectGuess(a);
     }

}

You don't need to use a == comparison on booleans. Use a descriptive variable name and ! operator instead. ie. if (!gameLost){... or if(gameStillInProgress){...


Finding the nearby points from an array I have the following code that takes a Point and a given tolerance value and looks for all other Points that fall within the tolerance from a Point array. Now this code is quite slow, does anyone know a faster way of doing this?

Also if you have any tips on how I can improve my coding style, if needed, that would be great.

private Point[] FindNearbyPoints(Point[] points, Point initialPoint, int tolerance)
{
    return points.Select(p => p)
                 .Where(p => (p.X >= initialPoint.X - tolerance && p.X <= initialPoint.X + tolerance) &&
                             (p.Y >= initialPoint.Y - tolerance && p.Y <= initialPoint.Y + tolerance))
                 .ToArray();
}

How many points are we talking about that makes performance slow?  If its a crazy amount, you could use a Range Partitioner and a Parallel.For.  But I would suggest outputting as a List<Point> rather than an array so that each parallel thread can merge the subset of points.  I'd rather not get into details about in this answer though.

One alternative is to check X or Y against the tolerance once:

private Point[] FindNearbyPoints(Point[] points, Point initialPoint, int tolerance)
{
    tolerance = Math.Abs(tolerance);
    return points.Select(p => p)
                 .Where(p => (Math.Abs(p.X - initialPoint.X) <= tolerance) &&
                             (Math.Abs(p.Y - initialPoint.Y) <= tolerance))
                 .ToArray();
}

You could try making that an extension method in a public static class, such as:

public static Point[] FindNearbyPoints(this Point[] points, Point initialPoint, int tolerance)
{
    tolerance = Math.Abs(tolerance);
    return points.Select(p => p)
                 .Where(p => (Math.Abs(p.X - initialPoint.X) <= tolerance) &&
                             (Math.Abs(p.Y - initialPoint.Y) <= tolerance))
                 .ToArray();
}

A bigger consideration is whether the return type must be Point[].  You might see some performance boost if you went with IEnumerable<Point>.  In fact the extension method could be more reachable if you changed the input signature a bit too.  Something like:

public static IEnumerable<Point> FindNearbyPoints(this IEnumerable<Point> points, Point initialPoint, int tolerance)
{
    tolerance = Math.Abs(tolerance);
    return points.Select(p => p)
                 .Where(p => (Math.Abs(p.X - initialPoint.X) <= tolerance) &&
                             (Math.Abs(p.Y - initialPoint.Y) <= tolerance));
}

Other than that, your coding style looks fine.  Give these changes a try and see if performance is still an issue.  If it is, I'll try to find time to work up an example using a range partitioner.


A get_extents helper function for Boost.MultiArray in C++ This is a follow-up question for A filled_multi_array Template Function for Boost.MultiArray in C++. Based on G. Sliepen's answer, there is another get_extents template function mentioned for handling retrieving boost::detail::multi_array::extent_gen<NumDims> type size information from a multi_array. I am trying to implement this get_extents template function here.
template<class T, std::size_t NumDims>
auto get_extents(const boost::multi_array<T, NumDims>& input) {
    boost::detail::multi_array::extent_gen<NumDims> output;
    std::vector<size_t> shape_list;
    for (size_t i = 0; i < NumDims; i++)
    {
        shape_list.push_back(input.shape()[i]);
    }
    std::copy(shape_list.begin(), shape_list.end(), output.ranges_.begin());
    return output;
}

I am trying to copy shape content into the output object. In general cases, boost::detail::multi_array::extent_gen object is always constructed by boost::extents[][][].... However, I am not sure how to use boost::extents in this context and I fill the values of shape information into output.ranges_ instead. It works with the following testing code.
auto filled_multi_array1 = filled_multi_array(boost::extents[3][4][2], 1.0);
auto filled_multi_array2 = filled_multi_array(get_extents(filled_multi_array1), 2.0);

//  Checking shape
std::cout << "filled_multi_array2.shape()[0]:" << filled_multi_array2.shape()[0] << std::endl;
std::cout << "filled_multi_array2.shape()[1]:" << filled_multi_array2.shape()[1] << std::endl;
std::cout << "filled_multi_array2.shape()[2]:" << filled_multi_array2.shape()[2] << std::endl;

for (decltype(filled_multi_array2)::index i = 0; i != filled_multi_array2.shape()[0]; ++i)
    for (decltype(filled_multi_array2)::index j = 0; j != filled_multi_array2.shape()[1]; ++j)
        for (decltype(filled_multi_array2)::index k = 0; k != filled_multi_array2.shape()[2]; ++k)
            std::cout << filled_multi_array2[i][j][k] << std::endl;

All suggestions are welcome.
The summary information:

Which question it is a follow-up to?
A filled_multi_array Template Function for Boost.MultiArray in C++

What changes has been made in the code since last question?
The extent_gen function implementation is the main part in this question.

Why a new review is being asked for?
The shape_list which type is std::vector<size_t> in get_extents function is used just for copying shape data into output.ranges_. The reason why I create a std::vector for this operation is that there is neither .begin() function nor .end() function in input.shape(). Something like std::copy(input.shape().begin(), input.shape().end(), output.ranges_.begin()); doesn't work. If there is any possible improvement, please let me know.

Avoid unnecessary temporary variables
There still is no need for the temporary vector shape_list, just use std::copy_n:
boost::detail::multi_array::extent_gen<NumDims> output;
std::copy_n(input.shape(), NumDims, output.ranges_.begin());

Please take some time to look at the list of all the STL algorithms. There are lots of useful functions there that will save you a lot of time. You don't have to remember them all, but get a feel for the type of functionality it provides, and next time you have a problem you might remember that some existing algorithm might solve it for you. The World Map of C++ STL Algorithms is also a great resource to build intuition for it.


Josephus permutation - follow up Follow up of this question

Changes:

The pop_min function now panics if the tree is empty.
Moved the size attribute to the Tree struct.
Applied most of the suggestions given by the answers.
Added some other functions.
Refactored some functions.
Moved everything to the same file.

extern crate itertools;
use itertools::Unfold;
use std::cmp::Ordering;

pub fn permutation(size: u32, m: u32) -> Box<Iterator<Item = u32>> {
    let mut tree = Tree::new(1, size);
    let x = Unfold::new(1, move |a| {
        *a = (*a + m - 2) % tree.size + 1;
        Some(tree.pop_rank(*a))
    });
    Box::new(x.take(size as usize))
}

#[derive(Debug)]
struct Node {
    data: u32,
    left: Tree,
    right: Tree,
}

#[derive(Debug)]
struct Tree {
    size: u32,
    root: Option<Box<Node>>,
}

impl Tree {
    fn new(from: u32, to: u32) -> Tree {
        if from > to {
            return Tree { root: None, size: 0, };
        }
        let mid = from + (to - from) / 2;
        let node = Node {
            data: mid,
            left: Tree::new(from, mid - 1),
            right: Tree::new(mid + 1, to),
        };

        Tree {
            size: 1 + node.left.size + node.right.size,
            root: Some(Box::new(node)),
        }
    }

    fn find_rank(&mut self, rank: u32) -> &mut Tree {
        let r = self.root
                    .as_mut()
                    .expect("rank out of range")
                    .left
                    .size + 1;

        self.size -= 1;
        match rank.cmp(&r) {
            Ordering::Equal => self,
            Ordering::Less => self.as_mut().left.find_rank(rank),
            Ordering::Greater => self.as_mut().right.find_rank(rank - r),
        }
    }

    fn as_mut(&mut self) -> &mut Box<Node> {
        self.root.as_mut().unwrap()
    }

    fn as_ref(&self) -> &Box<Node> {
        self.root.as_ref().unwrap()
    }

    fn empty(&self) -> bool {
        self.root.is_none()
    }

    fn delete_node(&mut self) {
        *self = self.root
                    .take()
                    .map(|mut x| {
                        if x.left.empty() {
                            x.right
                        } else if x.right.empty() {
                            x.left
                        } else {
                            x.data = x.right.pop_min();
                            Tree {
                                root: Some(x),
                                size: self.size,
                            }
                        }
                    })
                    .expect("Can't delete None");
    }

    fn pop_min(&mut self) -> u32 {

        if self.empty() {
            panic!("underflow");
        }

        if self.as_ref().left.empty() {
            let data = self.as_ref().data;
            *self = self.root.take().unwrap().right;
            data
        } else {
            self.size -= 1;
            self.as_mut().left.pop_min()
        }
    }

    fn pop_rank(&mut self, rank: u32) -> u32 {
        let ranked = self.find_rank(rank);
        let data = ranked.as_ref().data;
        ranked.delete_node();
        data
    }
}

This mostly looks OK, but I really don't like

*self = self.root
            .take()
            .map(|mut x| {
                if x.left.empty() {
                    x.right
                } else if x.right.empty() {
                    x.left
                } else {
                    x.data = x.right.pop_min();
                    Tree {
                        root: Some(x),
                        size: self.size,
                    }
                }
            })
            .expect("Can't delete None");

You can shift up the expect to get

let mut node = self.root.take().expect("Can't delete None");
*self =
    if node.left.empty() {
        node.right
    } else if node.right.empty() {
        node.left
    } else {
        node.data = node.right.pop_min();
        Tree {
            root: Some(node),
            size: self.size,
        }
    };

which is already much nicer. Then deal with the error and naming:

fn delete_root_node(&mut self) {
    let mut root = self.root.take().expect("Empty tree has no root");
    *self =
        if root.left.empty() {
            root.right
        } else if root.right.empty() {
            root.left
        } else {
            root.data = root.right.pop_min();
            Tree {
                root: Some(root),
                size: self.size,
            }
        };
}

Then I'd flatten it back out

fn delete_root_node(&mut self) {
    let mut root = self.root.take().expect("Empty tree has no root");

    if root.left.empty() {
        *self = root.right
    } else if root.right.empty() {
        *self = root.left
    } else {
        root.data = root.right.pop_min();
        self.root = Some(root);
    };
}

Rust's tools are great, but they shouldn't be abused. In this case, a simple imperative style reads much nicer than the semi-functional transformations, so should be preferred.

More rightward drift can be dealt with in find_rank:

fn find_rank(&mut self, rank: u32) -> &mut Tree {
    let right_offset = self.as_mut().left.size + 1;

    self.size -= 1;
    match rank.cmp(&right_offset) {
        Ordering::Equal => self,
        Ordering::Less => self.as_mut().left.find_rank(rank),
        Ordering::Greater => self.as_mut().right.find_rank(rank - right_offset),
    }
}

Now, find_rank is doing something really horrible:

self.size -= 1;

This breaks the Tree's invariants. Much better would be to call this pop_rank and move pop_rank inside of it. You can make this a bit nicer by having pop_root return a u32 and just depending on that, though.

Then we have a nice chain of functions

fn pop_rank(&mut self, rank: u32) -> u32 {
    let left_size = self.as_mut().left.size;
    self.size -= 1;

    match rank.cmp(&(1 + left_size)) {
        Ordering::Equal   => {
            self.size += 1;
            self.pop_root()
        },
        Ordering::Less    => self.as_mut().left.pop_rank(rank),
        Ordering::Greater => self.as_mut().right.pop_rank(rank - 1 - left_size),
    }
}

fn pop_root(&mut self) -> u32 {
    let mut root = self.root.take().expect("Empty tree has no root");
    let data = root.data;

    if root.left.empty() {
        *self = root.right
    } else if root.right.empty() {
        *self = root.left
    } else {
        root.data = root.right.pop_min();
        self.root = Some(root);
        self.size -= 1;
    };

    data
}

fn pop_min(&mut self) -> u32 {
    if self.as_ref().left.empty() {
        let data = self.as_ref().data;
        *self = self.root.take().unwrap().right;
        data
    } else {
        self.size -= 1;
        self.as_mut().left.pop_min()
    }
}

The restoring of self.size in pop_rank before calling pop_root might slightly increase computational burden but it means that each function only relies on the data structure's basic invariants to work properly.

Note that pop_min doesn't actually need to panic! as that's captured by self.as_ref's auto-panic.

as_ref and as_mut are misleading names since they actually give handles to root; better would be get_root and get_root_mut. I'd also swap pop_min for pop_first for clarity.

I'd also change m to step in permutation.

I've been transfixed by this problem for a while now, so I'm going to introduce my thoughts about it. Very little of what follows has anything to do with your implementation, but hopefully someone at least finds it a little interesting.

It's worth noting that Box-heavy structures tend to be slow. A much more efficient tree structure to work with could be a Vec<Vec<usize>> like so:

tree[0]               13
tree[1]        8               5
tree[2]    4       4       4       1
tree[3]  2   2   2   2   2   2   1
tree[4] 1 1 1 1 1 1 1 1 1 1 1 1 1

tree[0..3] are used to guide you to an index in the bottom. "Using" the fifth value would result in the tree modified like so

tree[0]               12
tree[1]        7               5
tree[2]    4       3       4       1
tree[3]  2   2   1   2   2   2   1
tree[4] 1 1 1 1 0 1 1 1 1 1 1 1 1

Then it's worth noting that you never actually need to read the right branches on traversal, so those can be discarded:

tree[0]               13
tree[1]        8               .
tree[2]    4       .       4       .
tree[3]  2   .   2   .   2   .   1
tree[4] 1 . 1 . 1 . 1 . 1 . 1 . 1

Then move the size into the data structure itself, since that needs to be read frequently in the algorithm and not actually during traversal.

tree[0]        8               .
tree[1]    4       .       4       .
tree[2]  2   .   2   .   2   .   1
tree[3] 1 . 1 . 1 . 1 . 1 . 1 . 1

I've found that just this gives a noticeable but underwhelming speed-up factor of 3-4x; I was expecting with all the Boxing for that to be closer to 10. The problem seems to be that the branches are still unpredictable and the behaviour is still cache-thrashing; the main improvement came not from the change in format but from not writing to the right branch (not the eliding step but just not writing to it). Plus, allocators are likely to put all those boxed values next to each other, and the lack of space efficiency doesn't really hurt when doing psuedo-random access anyway.

Then note that with something like a (14345577, 15347)-permutation, \$\log 14345577\$ is much greater than \$\log 15347\$. You can use this to your advantage by ignoring the top of the tree:

tree[ 0]             8388608 ...
tree[ 1]           4194304 ...
...
tree[ 8]       32768 ...
tree[ 9]     16384 ...
...
tree[22]   2 ...
tree[23] 1 ...

You can actually discard tree[0..8]; jumps are normally going to be no greater than steps of 15347 times the "sparsity" of the data. When the sparsity gets so large that you are taking jumps that large, you can "recompact" the whole array in \$O(n)\$ time. Since you only need to do this when density drops somewhere below 50%, this is a relatively cheap way of moving from a total \$O(n \log n)\$ to \$O(n \log m)\$ time complexity (resizing each time capacity halves results in only \$O(n)\$ extra work).

Note that the top level then becomes a bunch of roots into sub-trees, not a single tree. Thus you can't ignore the right-nodes, or you'll be losing the size of the tree. Conceptually, those right nodes are calculated from the node above, so if there's no node above you aren't able to drop the value.

An extreme example would be a (10000000, 3)-permutation, where the entire tree is clearly overkill. This tree trimming works well there.

Then it's worth looking at those bottom rows, to see if we can do something more intelligent about them:

tree[X]                            64   ...
...
tree[X]    4       4       4       4    ...
tree[X]  2   .   2   .   2   .   2   .  ...
tree[X] 1 . 1 . 1 . 1 . 1 . 1 . 1 . 1 . ...

Despite the elided right branches, this is still a ton of data to express 64 bits of data. In fact, it uses 63 times that amount of data even after elision. Much more effective is to have an actual 64 bit integer.

0b1111111111111111111111111...

This can still be efficiently binary searched by utilizing a specialized routine, bit shifts, masks and u64::count_ones. In fact, on newer x86 processors you don't even have to; Jukka Suomela points out that it's as simple as

pub fn position_nth_set_bit(value: u64, mut bit: u32) -> u32 {
    // Holy smokes
    bmi_pdep_64(1 << bit, value).trailing_zeros()
}

Sadly I think right now I need to use asm!, but that's no show-stopper. If pdep isn't available, the binary search with count_ones is still pretty fast - but it's certainly not nearly as fast.

In fact, this also makes the compacting step that we need to elide the top of the tree much simpler; the bit-set acts as a mask over our values that we can just iterate.

Let's quickly calculate what the overhead is. Our entire tree looks like

roots           x              x
tree[X]     x       .       x
tree[X]   x   .   x   .   x   .
tree[X]  x . x . x . x . x . x .
masks    bbbbbbbbbbbbbbbbbbbbbbbb
values   VVVVVVVVVVVVVVVVVVVVVVVV  ← We don't need this until after compacting

values costs a usize per output value, but can actually be ignored until the first compaction as before then it's an identity map (values[k] == k at first).

masks introduces one further bit per value.

If you look at tree and roots the right way, you can see you can "slide" the xs down the right branches to fill exactly one row (I'll re-use this property later). The bottom-most tree[X] is at the 128 level (since masks.count_ones() works at the 64 level), so that's a usize of bits spent per 128 values.

Ergo we have 1-2 extra bits per value, and only half of the values actually need to be stored. So our space complexity is pretty close to n * usize::BITS / 2. If m is expected to approach n in size or space matters more than the move from \$O(n \log n)\$ to \$O(n \log m)\$, you can instead use masks without trimming the top of the tree, so no values array is needed, to get a space cost of roughly just 2 * n bits.

A pleasing hybrid might be obtained by making tree a little bit taller, so one has to resize slightly less frequently. Two extra layers means two extra branches per iteration but delays resizing until the density is about 1/8, leaving memory consumption of about n * usize::BITS / 8 while still having \$O(n \log m)\$ operations. Plus, doing the first resize early hurts as before it values is not used and the later resizes are smaller. On the other hand, a few extra branches is expensive when the branches are unpredictable, so it actually makes sense to keep the tree shallow and do a linear search over the roots. It's worth noting that resizing can make the tree smaller and isn't actually expensive, so the trade to do it later isn't so clear-cut. The precise parameters are tunable.

This is starting to feel optimal, since \$\log m\$ is about the smallest cost for a jump one can normally reasonably expect and we're approaching a small number of bits of overhead. However, we might be able to make the data structure more optimal. One possible improvement is to take the "compact" view of the tree we used to calculate its size: slide each value down the "right-hand slide":

roots           a              b
tree[X]     c       ↘       d
tree[X]   e   ↘   f   ↘   g   ↘
tree[X]  x ↘ x ↘ x ↘ x ↘ x ↘ x ↘
masks    bbbbbbbbbbbbbbbbbbbbbbbb
values   VVVVVVVVVVVVVVVVVVVVVVVV

to get

tree     x e x c x f x a x g x d · · · b
masks    bbbbbbbbbbbbbbbbbbbbbbbb
values   VVVVVVVVVVVVVVVVVVVVVVVV

Note that traversal is now just a binary search over a sub-range of the array. This might look tough to traverse, but it's actually a fairly mechanical transformation.

Generating this is more tough, but it does have the lovely property that each modulo is

1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, ...

which you can take the \$\log_2\$ of to get

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, ...

OEIS helpfully adds that,

  a(n) is the number of 0's at the end of n when n is written in base 2

and then you note that n >> (n.trailing_zeros() + 1) gives how many times you've seen this value before, which lets you deal with the leftover parts.

Note that the modulo is for a "cropped" root, and so you need to take the min against the top-level modulo you're using, and you also need to add 7 before then to multiply all the modulos by 128 (because the bottom groups of 64 are dealt with in masks).

With my implementation, for very large \$m\$ (same order of magnitude as \$n\$), the tree pruning is entirely ineffective (and is just pointless overhead), so the only performance gains come from the change in how iteration happens, the move to iteration over a contiguous vector and the masks array removing the last few layers of the tree. The move to a contiguous vector is actually rather ineffective as a speed enhancer since the Boxes are probably contiguous anyway and the major overhead is in the unpredictable branching. There's roughly a factor 6 improvement over your code here.

For "medium"-sized \$m\$ (eg. \$n\$ is 14345577, \$m\$ is 15347), tree pruning comes into play and speed improves 3-fold. Your code does not, so the speed advantage increases. There's roughly a factor 20 improvement over your code here.

For small \$m\$ (eg. 3), the tree pruning pushes further increases speed significantly, resulting in massive decreases in time. Further, the BMI instructions at the bottom of the tree end up improving speed significantly. However, your code also becomes very predictable, since branches repeat frequently, so the cost there actually falls too and the overall relative speed improvement is not as great as the time reduction alone would imply. There's roughly a factor 32 improvement over your code here.

Honestly I was hoping for more, but I can see why the improvements were only this good. It should be possible to improve this a lot by using a B-tree instead of a binary tree, by effectively replacing

roots           x              x
tree[X]     x       .       x
tree[X]   x   .   x   .   x   .
tree[X]  x . x . x . x . x . x .
masks    bbbbbbbbbbbbbbbbbbbbbbbb
values   VVVVVVVVVVVVVVVVVVVVVVVV

with

roots       x       x       x       x
tree[X]       .       .       .
tree[X]  x x x . x x x . x x x .
masks    bbbbbbbbbbbbbbbbbbbbbbbb
values   VVVVVVVVVVVVVVVVVVVVVVVV

which should improve branch predictability by using intermittent unrolled linear searches. However, the reduction from doing this the "obvious" way is slight as you still end up with poorly predictable branches over spread-out locations.

Ideally, one should reorganize the values as

roots                      x x x x
tree[X]  x x x|x x x|x x x|
masks    bbbbbbbbbbbbbbbbbbbbbbbb
values   VVVVVVVVVVVVVVVVVVVVVVVV

instead.

Another oversight I've been purposefully ignoring is SIMD. Small SIMD vectors for usize-sized data makes this relatively weak, but lower down the tree a u16x8 vector is likely extremely useful, and basically makes an 8-wide B-tree optimal. Newer AVX instructions would do far better, and allow the whole tree to be heavily vectorized. I'm going to continue to ignore this, though, 'cause SIMD with Rust is not ideal right now.