Generating a data validation list and sorting it alphabetically The following code clears 11 columns that contain lists that are used for data validation on another worksheet. This list is constantly changing due to records being added/removed from the source data. Basically I'm checking every value in a column, and if it meets all of my criteria I'm adding it to my data validation column (after making sure it doesn't already exist there).

Once I've populated my 11 columns, I sort each one alphabetically. This is the portion of my code that I don't like. While it doesn't explicitly select anything, I can see on my worksheet the last column that was sorted because it is selected.

What I'm wondering is if there's a better way to dynamically generate this list alphabetically without having to use .Sort - possibly populating an array and then sorting it alphabetically? I've never sorted an array in VBA, so I'm not sure 1. If it's even more efficient and 2. What is the best method to sort an array, if that's the approach I should take here?

Code:

Option Explicit
Sub PopulateAllDataValidationLists()

    Dim sht As Worksheet, sht2 As Worksheet
    Dim i As Long, listcol As Long

    Set sht = Worksheets("Sheet 1")
    Set sht2 = Worksheets("Data Validation")

        Application.ScreenUpdating = False

        sht2.Range("A2:K500").ClearContents

        For i = 1 To 11
            listcol = sht.Rows("1:1").Find(What:=sht2.Cells(1, i).Value, LookAt:=xlWhole).Column

            For j = 2 To sht.Cells(sht.Rows.Count, listcol).End(xlUp).Row
                If IsError(Application.Match(sht.Cells(j, listcol).Value, sht2.Range(ColumnLetter(i) & ":" & ColumnLetter(i)), 0)) And _
                sht.Cells(j, listcol).Value <> "" And _
                sht.Cells(j, listcol).Value <> "UNK" And _
                sht.Cells(j, listcol).Value <> "xxx" And _
                sht.Cells(j, listcol).Value <> "yyy" And _
                sht.Cells(j, listcol).Value <> "zzz" And _
                sht.Cells(j, listcol).Value <> "yxz" And _
                sht.Cells(j, listcol).Value <> "zyx" And _
                Len(sht.Cells(j, listcol).Value) <= 3 Then
                    sht2.Cells(sht2.Cells(sht2.Rows.Count, i).End(xlUp).Row + 1, i).Value = sht.Cells(j, listcol).Value
                End If
            Next j

        Next i

        'Sort all alphabetically
        For i = 1 To 11
            Worksheets("Data Validation").Sort.SortFields.Clear
            Worksheets("Data Validation").Sort.SortFields.Add Key:=Range(ColumnLetter(i) & "2"), SortOn:=xlSortOnValues, Order:=xlAscending, DataOption:=xlSortNormal

            With Worksheets("Data Validation").Sort
                .SetRange Range(ColumnLetter(i) & "2:" & ColumnLetter(i) & sht2.Cells(sht2.Rows.Count, i).End(xlUp).Row)
                .Header = xlNo
                .MatchCase = False
                .Orientation = xlTopToBottom
                .SortMethod = xlPinYin
                .Apply
            End With
        Next i

        Application.ScreenUpdating = True

End Sub
Function ColumnLetter(colnum As Long) As String

    ColumnLetter = Split(Cells(1, colnum).Address, "$")(1)

End Function

An example of data in a column:

I would refactor your code and add  Worksheets("Data Validation").Range("A1").Select to the end to clear the selection.

Refactored Code

Changes:

ColumnLetter(): Removed
sht2: Replaced using a With block.
For j: Changed to For item.  item.Value is much easier to distinguish than sht.Cells(j, listcol).Value
.Range("A1").Select:  Added to clear the dreaded selected column
Cell reference fully qualified for the Sort ranges (I am surprised that the code would run without Worksheets("Data Validation") being the ActiveSheet.
sht2.Range("A2:K500").ClearContents: Replaced made dynamic using sht2.Range("A1:K1").CurrentRegion.Offset(1).ClearContents

Sub PopulateAllDataValidationLists()
    Dim sht As Worksheet
    Dim i As Long, listcol As Long
    With Worksheets("Data Validation")
        Application.ScreenUpdating = False

        .Range("A1:K1").CurrentRegion.Offset(1).ClearContents
        Dim columnName As String
        Dim InvalidValues As Variant

        InvalidValues = Array("UNK", "xxx", "yyy", "zzz", "yxz", "zyx")

        Dim rColumn As Range, item As Range
        For i = 1 To 11
            columnName = .Cells(1, i).Value
            With Worksheets("Sheet 1")
                listcol = .Rows("1:1").Find(What:=columnName, LookAt:=xlWhole).Column
                Set rColumn = Range(.Cells(1, listcol), .Cells(.Rows.Count, listcol).End(xlUp))
            End With

            For Each item In rColumn
                If item.Value <> "" Then
                    If IsError(Application.Match(item.Value, .Columns(i), 0)) And _
                       IsError(Application.Match(item.Value, InvalidValues, 0)) And _
                       Len(item.Value) <= 3 Then
                        .Cells(.Cells(.Rows.Count, i).End(xlUp).Row + 1, i).Value = item
                    End If
                End If
            Next

            .Sort.SortFields.Clear
            .Sort.SortFields.Add Key:=.Cells(2, i), SortOn:=xlSortOnValues, Order:=xlAscending, DataOption:=xlSortNormal
            Dim target As Range
            Set target = Range(.Cells(2, i), .Cells(.Rows.Count, i).End(xlUp))

            With .Sort
                .SetRange target
                .Header = xlNo
                .MatchCase = False
                .Orientation = xlTopToBottom
                .SortMethod = xlPinYin
                .Apply
            End With
        Next i
        .Range("A1").Select
    End With

    Application.ScreenUpdating = True

End Sub

Other Method

There are many ways that you can sort the data:

System.Collection.ArrayList : ArrayList Class (System.Collections) | Microsoft Docs, VBA for smarties: ArrayList
System.Collections.SortedList: SortedList Class (System.Collections) | Microsoft Docs, VBA voor smarties: SortedList, VBScript Scripting Techniques: SortedLists - Rob van der Woude
Bubble Sort: VBA Arrays - Bubble Sort - BetterSolutions.com
Quick Sort: VBA Arrays - Quick Sort - BetterSolutions.com

Here is an example of how you can use an ADODB.Recordset to create a table in memory to sort and potentially filter the data.

RSSort: Class

Option Explicit
Public FieldName As String
Private Const adVarChar = 200
Private Const adOpenKeyset = 1
Private Const adUseClient = 3
Private Const adLockPessimistic = 2
Private rs As Object

Private Sub Class_Initialize()
    FieldName = "Values"
    Set rs = CreateObject("ADODB.Recordset")

    With rs
        .Fields.Append FieldName, adVarChar, 255
        .CursorType = adOpenKeyset
        .CursorLocation = adUseClient
        .LockType = adLockPessimistic
        .Open
    End With
End Sub

Public Sub AddNew(ByVal item As Variant)
    rs.AddNew FieldName, item
End Sub

Public Property Get Filter() As String
    Filter = rs.Filter
End Property

Public Property Let Filter(ByVal sFilter As String)
    rs.Filter = sFilter
End Property

Public Sub Sort(Optional SortAscending As Boolean = True)
    rs.Sort = FieldName & IIf(SortAscending, " ASC", " DESC")
End Sub

Public Function ToArray() As Variant
    Dim data As Variant, results As Variant
    If rs.RecordCount = 0 Then
        ReDim results(1 To 1, 1 To 1)
        ToArray = results
        Exit Function
    End If
    rs.MoveFirst
    data = rs.GetRows(rs.RecordCount)
    ReDim results(1 To UBound(data, 2) + 1, 1 To 1)

    Dim r As Long

    For r = 1 To UBound(data, 2)
        results(r + 1, 1) = data(0, r)
    Next

    ToArray = results
End Function

Demo Code

Sub RSSorterPopulateAllDataValidationLists()
    Application.ScreenUpdating = False

    Dim data As Variant
    Dim c As Long

    With Worksheets("Data Validation")
        .Range("A1:K1").CurrentRegion.Offset(1).ClearContents
        For c = 1 To 11
            data = getValidationValues(.Columns(c), "", "UNK", "xxx", "yyy", "zzz", "yxz", "zyx")
            .Cells(2, c).Resize(UBound(data)).Value = data
        Next
    End With
End Sub

Function getValidationValues(MatchColumn As Range, ParamArray InvalidValues() As Variant) As Variant()
    Dim sorter As New RSSorter
    Dim col As Range
    Dim ColumnHeader As String
    ColumnHeader = MatchColumn.Cells(1, 1).Value
    Dim vExcluded As Variant
    vExcluded = InvalidValues

    With Worksheets("Sheet 1")
        Dim item As Range
        Set col = .Rows("1:1").Find(What:=ColumnHeader, LookAt:=xlWhole)
        If Not col Is Nothing Then
            For Each item In Range(col.Cells(2, 1), .Cells(.Rows.Count, col.Column).End(xlUp))
                If item.Value <> "" Then
                    If IsError(Application.Match(item.Value, MatchColumn, 0)) And _
                       IsError(Application.Match(item.Value, vExcluded, 0)) And _
                       Len(item.Value) <= 3 Then
                        sorter.AddNew item
                    End If
                End If
            Next
        End If
    End With
    sorter.Sort
    getValidationValues = sorter.ToArray
End Function

Edit

shtreplaced with With Worksheets("Sheet 1")
Constants (adOpenKeyset, adUseClient, adLockPessimistic) added to completely convert from early binding to late binding.
The ADODB library "Microsoft ActiveX Data Objects x.x Library" removed from original workbook


A clone_ptr that does not require T to have a clone method Here is my clone pointer template:

#include <functional>
#include <utility>
#include <iostream>

template<typename T>
struct clone_ptr
{
    clone_ptr() : ptr(nullptr), cloner(nullptr) {}
    clone_ptr(clone_ptr&& other) noexcept
        : clone_ptr()
    {
        swap( other );
    }
    clone_ptr(const clone_ptr& other)
    {
        ptr = other.cloner(other.ptr);
        cloner = other.cloner;
    }
    void swap( clone_ptr& other ) noexcept
    {
        using std::swap;
        swap( ptr,    other.ptr    );
        swap( cloner, other.cloner );
    }

    clone_ptr& operator=( const clone_ptr& other )
    {
        clear();
        ptr = other.cloner(other.ptr);
        cloner = other.cloner;
        return *this;
    }
    clone_ptr& operator=( clone_ptr&& other )
    {
        clear();
        swap(other);
        return *this;
    }

    T* operator->() { return ptr; }
    const T* operator->() const { return ptr; }
    T& operator*() { return *ptr; }
    const T& operator*() const { return *ptr; }

    operator bool() const { return ptr; }

    bool operator<(const clone_ptr& other) const
    {
        if(!ptr) return other.ptr;
        if(!other.ptr) return false;
        return (*ptr) < (*other.ptr);
    }
    bool operator==(const clone_ptr& other) const
    {
        if(!ptr) return !other.ptr;
        if(!other.ptr) return false;
        return (*ptr) == (*other.ptr);
    }

    std::ostream& output(std::ostream& os) const { if(ptr) os << *ptr; else os << "<nullptr>"; return os ; }

    template<typename T2=T, typename ...Ts>
    void make( Ts&& ...ts )
    {
        clear();
        ptr = new T2( std::forward<Ts>(ts)... );
        cloner = [](T* p) -> T* { return new T2( * (T2*) p ); };
    }

    void clear() { delete ptr; ptr=nullptr; cloner=nullptr; }

    ~clone_ptr() { clear(); }

private:
    T* ptr;
    std::function<T*(T*)> cloner;
};

template<typename T, typename T2=T, typename ...Ts>
clone_ptr<T> make_cloned( Ts&& ...ts )
{
    clone_ptr<T> p;
    p.template make<T2>( std::forward<Ts>(ts)... );
    return p;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const clone_ptr<T>& p) { return p.output(os); }

It is primarily intended to preserve polymorphism, esp. when stored in a container. It "forwards" operator< and operator== so containers can be sorted etc. based on the contained object.

Have I missed/forgotten anything?

Prefer to use Copy and Swap Idiom

clone_ptr& operator=( const clone_ptr& other )
{
    clear();
    ptr = other.cloner(other.ptr);
    cloner = other.cloner;
    return *this;
}

Or

clone_ptr& operator=(clone_ptr copy)
{
    copy.swap(*this);
    return *this;
}

No need to clear on move assignment

clone_ptr& operator=( clone_ptr&& other )
{
    // clear();   No need to do that.
                  The destructor of `other` will do that at some point.
    swap(other);
    return *this;
}

Easier to write as:

clone_ptr& operator=(clone_ptr copy)
{
    copy.swap(*this);
    return *this;
}

Personally I don't see the point in havin output() and operator<<

I would just combine them into operator<< and make it a friend (also declare it in the class).


Grouping a Pandas Dataframe by two parameters I have a .csv file of 8k+ rows which looks like this:

                       state                   assembly           candidate  \
0  Andaman & Nicobar Islands  Andaman & Nicobar Islands     BISHNU PADA RAY
1  Andaman & Nicobar Islands  Andaman & Nicobar Islands  KULDEEP RAI SHARMA
2  Andaman & Nicobar Islands  Andaman & Nicobar Islands      SANJAY MESHACK
3  Andaman & Nicobar Islands  Andaman & Nicobar Islands        ANITA MONDAL
4  Andaman & Nicobar Islands  Andaman & Nicobar Islands             K.G.DAS

                                party  votes
0              Bharatiya Janata Party  90969
1            Indian National Congress  83157
2                     Aam Aadmi Party   3737
3        All India Trinamool Congress   2283
4  Communist Party of India (Marxist)   1777

The end dataframe I wanted to get was one which contains all the states as rows and two columns - one which has votes received by a particular party ("Bhartiya Janata Party", in this case) in that row's state and another which has the total votes from the state. Like this:

      State                Total Votes   BJP Votes
Andaman & Nicobar Islands       190328     90969.0
Andhra Pradesh                48358545   4091876.0
Arunachal Pradesh               596956    275344.0
Assam                         15085883   5507152.0
Bihar                         35885366  10543023.0

My code works but I'm pretty sure there's a much better way to get this done using fewer lines of code and without creating too many dataframes. Here's my code:

dff = df.groupby(['party'])[['votes']].agg('sum')
dff = dff.sort_values('votes')

BJP_df = df[df["party"]=="Bharatiya Janata Party"]
#print(BJP_df.head())

group = BJP_df.groupby(['state'])[['votes']].agg('sum')
state = df.groupby(['state'])[['votes']].agg('sum')

result = pd.concat([state, group], axis = 1, sort=False)
result.columns = ["Total Votes","BJP Votes"]

Any tips, suggestions, pointers would be very much appreciated.

In all your code was not too bad. You can groupby on 2 items:

votes_per_state = df.groupby(["state", "party"])["votes"].sum().unstack(fill_value=0)

state Aam Aadmi Party All India Trinamool Congress    Bharatiya Janata Party  Communist Party of India (Marxist)  Indian National Congress    other
Andaman & Nicobar Islands 3737    2283    90969   1777    83157   0
Andhra Pradesh    0   0   85  0   0   100

Then you can define which party you're interested in, and manually assemble a DataFrame

party_of_interest = "Bharatiya Janata Party"
result = pd.DataFrame(
    {
        party_of_interest: votes_per_state[party_of_interest],
        "total": votes_per_state.sum(axis=1),
    }
)

state Bharatiya Janata Party  total
Andaman & Nicobar Islands 90969   181923
Andhra Pradesh    85  185

If you want you can even add a percentage:

result = pd.DataFrame(
    {
        party_of_interest: votes_per_state[party_of_interest],
        "total": votes_per_state.sum(axis=1),
        "pct": (
            votes_per_state[party_of_interest]
            / votes_per_state.sum(axis=1)
            * 100
        ).round(1),
    }
)

state Bharatiya Janata Party  total   pct
Andaman & Nicobar Islands 90969   181923  50.0
Andhra Pradesh    85  185 45.9


It's almost Friday, right? This is my final post for my CS1 saga.  Mostly all I had to do was just "class-ify" my past project in this post.  Here are the requirements:

  Make all data members private and use constructors, accessors and
  mutators. Enhancement: Build data verification into the member functions.

I'm mostly concerned with me doing OO programming correctly.  I wasn't very good with it in my Java days way back yonder, and I'm not sure it's that good now either.  Focus in this area would be appreciated.

classyDayOfWeek.cpp:

/**
 * @file classyDayOfWeek.cpp
 * @brief Computes the day of the week given a certain date
 * @author syb0rg
 * @date 12/10/14
 */

#include <cctype>
#include <iostream>
#include <limits>

const std::string weekDays[] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

/**
 * The class associated with date values and calculating the day of the week
 */
class Date
{
public:
    int dayOfWeek();
    void getInput();
    bool isLeapYear();
    int getCenturyValue();
    int getYearValue();
    int getMonthValue();
private:
    unsigned day = 0;
    unsigned month = 0;
    unsigned year = 0;
};

/**
 * Makes sure data isn't malicious, and signals user to re-enter proper data if invalid
 */
unsigned getSanitizedNum()
{
    unsigned input = 0;
    while(!(std::cin >> input))
    {
        // clear the error flag that was set so that future I/O operations will work correctly
        std::cin.clear();
        // skips to the next newline
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
        std::cout << "Invalid input.  Please enter a positive number: ";
    }
    return input;
}

/**
 * Safetly grabs and returns a lowercase version of the character (if the lowercase exists)
 */
char getSanitizedChar()
{
    // absorb newline character (if existant) from previous input
    if('\n' == std::cin.peek()) std::cin.ignore();
    return std::tolower(std::cin.get());
}

/**
 * Determines if the year stored in the Date instance is a leap year
 */
bool Date::isLeapYear()
{
    return (year >= 1582) && (!(year % 400) || (!(year % 4) && (year % 100)));
}

/**
 * Finds the century, divides by 4, and returns the remainder.
 */
int Date::getCenturyValue()
{
    return (2 * (3 - div(year / 100, 4).rem));
}

/**
 * Computes a value based on the years since the beginning of the century.
 */
int Date::getYearValue()
{
    int mod = year % 100;
    return (mod + div(mod, 4).quot);
}

/**
 * Returns a value based on the given hash tables (requires invoking the isLeapYear function)
 */
int Date::getMonthValue()
{
    const static int NON_LEAP_VALS[] = { 0xDEAD, 0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5 };
    const static int LEAP_VALS[] = { 0xDEAD, 6, 2, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5 };
    return (isLeapYear()) ? LEAP_VALS[month] : NON_LEAP_VALS[month];
}

/**
 * Compute the sum of the date's day plus the values returned by getMonthValue, getYearValue, and getCenturyValue.
 */
int Date::dayOfWeek()
{
    return div(day + getMonthValue() + getYearValue() + getCenturyValue(), 7).rem;
}

/**
 * Get's input safely and stores the input in the instances members
 */
void Date::getInput()
{
    std::cout << "Enter the month (1-12): ";
    month = getSanitizedNum();

    std::cout << "Enter the day (1-31): ";
    day = getSanitizedNum();

    std::cout << "Enter the year: ";
    year = getSanitizedNum();
}

int main()
{
    Date date;
    do
    {
        date.getInput();
        std::cout << "The day of the week is " << weekDays[date.dayOfWeek()] << std::endl;

        std::cout << "Run the program again (y/N): ";  // signify n as default with capital letter
    } while ('y' == getSanitizedChar());
}

It seems unusual to have a member function that takes input, also considering that most of the work already done in the class is computational-based. Consider getting the input in main() and constructing a Date object from this, or overload operator>>.
This output should be written to std::cerr instead:

std::cout << "Invalid input.  Please enter a positive number: ";

This also makes it clear to the reader that this is not a standard output, but an erroneous one.
You have some magic numbers in isLearYear() and getCenturyValue().  Any of them can be in the respective functions as consts.
You don't need to initialize the private variables; that's for the constructor or initializer list.
Any member function, such as getCenturyValue(), that does not modify any data members should be const:

int Date::getCenturyValue() const
{
    return (2 * (3 - div(year / 100, 4).rem));
}

This not only makes the intent clearer, but also prevents any accidental modification of data members by giving a compiler error.
You could move your two free functions next to main() to avoid possible confusion with the member functions (at least while everything exists in one file).


Number database using binary trees I recently got interested in Go and wrote a database server which uses a binary tree for data storage for fun. As I have no prior experience in Go, I'd like to gather a bit feedback on my code and would like to know how I can improve/optimize it.

File: BinaryTree.go

package BinaryTree

//import "fmt"

type SearchTree struct {
    value *int
    left, right *SearchTree
}

func (r SearchTree) getNode(i int) *SearchTree {

    if r.value != nil && *r.value == i {
        return &r
    }

    if r.left != nil {
        ref := r.left.getNode(i)
        if ref != nil {
            return ref
        }
    }

    if r.right != nil {
        ref := r.right.getNode(i)
        if ref != nil {
            return ref
        }
    }

    return nil
}

func (r SearchTree) Contains(n int) bool {
    node := r.getNode(n)
    return node != nil
}

func (r *SearchTree) Add(n int) {
    pointer := r

    for {

        if pointer.value == nil {
            pointer.value = &n
            return
        }

        if *pointer.value == n {
            return
        } else if *pointer.value < n {
            if pointer.left != nil {
                pointer = pointer.left
            } else {
                pointer.left = &SearchTree{&n, nil, nil}
                return
            }
        } else {
            if pointer.right != nil {
                pointer = pointer.right
            } else {
                pointer.right = &SearchTree{&n, nil, nil}
                return
            }
        }

    }
}

File: server.go

package main

import (
    "fmt"
    "net"
    "log"
    "BinaryTree"
    "strconv"
)

var data BinaryTree.SearchTree

func generateAddr() *net.TCPAddr {
    addr, err := net.ResolveTCPAddr("tcp", "localhost:19800")

    if err != nil {
        log.Fatal(err)
    }

    return addr
}

func handleConnection(con net.Conn) {
    fmt.Println("handling connection")

    buffer := make([]byte, 256)
    for {
        numBytes, err := con.Read(buffer)

        if err != nil {
            con.Close()
            return
        }

        cmdTxt := string(buffer[:numBytes])

        n, err := strconv.Atoi(cmdTxt[1:numBytes])

        if err == nil {
            fmt.Println(n)
            switch (cmdTxt[0]) {
            case 'g':
                if data.Contains(n) {
                    con.Write([]byte{6})
                } else {
                    con.Write([]byte{25})
                }
            case 's':
                data.Add(n)
                con.Write([]byte{6})
            }

        }

    }
}

func startServer() {
    ln, err := net.ListenTCP("tcp", generateAddr())

    if err != nil {
        log.Fatal(err)
    }

    for {
        fmt.Println("wait for connection")

        conn, err := ln.Accept()
        if err == nil {
            go handleConnection(conn)
        }

    }
}

func main() {
    startServer()
}

This is a review of your binary tree implementation. I suppose it works, and it doesn't violate any major Go idioms. However, your algorithm for getNode sucks (\$O(n)\$ complexity), and there are a few minor WTFs.

I fail to understand why your SearchTree struct contains a value *int. Your design has no way for a user to get the value out of the tree, and changing the value would destroy the sorting. All you ever do is get a pointer to an argument (which was passed by value…), and then do annoying if value != nil tests. All of that is unnecessary once you use a simple value int.

As mentioned above, your getNode() is weird: Unless the current node contains the value, you recurse into both the left and right subtree. Since you insert the values in a sorted order, we can use the binary tree as an actual binary tree. The function then simplifies to:

func (node *SearchTree) getNode(i int) *SearchTree {
    if node.value < i {
        if node.left == nil {
            return nil
        }
        return node.left.getNode(i)
    }
    else if i < node.value {
        if node.right == nil {
            return nil
        }
        return node.right.getNode(i)
    }
    else {
        return node
    }
}

I also renamed the receiver argument from r to the less cryptic node, and changed the receiver type to *SearchTree. Previously, your function took a tree by value (i.e. copy), then returned a pointer to that copy, which appears to be a bit backwards.

Actually, we can use the same getNode() function for both search and insertion with a few variations. To do this, we return a pointer to the .left or .right entry, which is itself a pointer. We guarantee that the returned pointer will never be nil, and that it will be a pointer to nil if no element was found. Only if it points to nil will that pointer will be writable.

func (node *SearchTree) getNode(i int) **SearchTree {
    if node.value < i {
        if node.left == nil {
            return &node.left
        }
        return node.left.getNode(i)
    } else if i < node.value {
        if node.right == nil {
            return &node.right
        }
        return node.right.getNode(i)
    }
    return &node // not nil, not writable
}

func (node *SearchTree) Contains(n int) bool {
    return *(node.getNode(n)) != nil
}

// returns true if the tree was mutated as a result,
// and false if the number was already present
func (node *SearchTree) Add(n int) bool {
    target := node.getNode(n)
    if *target == nil {
        *target = &SearchTree{n, nil, nil}
        return true
    }
    return false
}

This double pointer may seem a bit jarring since we're already using one level of pointers. However, we want a pointer to that field in the parent node, which merely happens to contain a pointer type itself.

There is a remaining problem with your tree. Right now, declaring a variable of type SearchTree will assign a default value, which is a struct with all members assigned their default values – nil for pointers and 0 for integers. However, this means that the following code will always evaluate to true:

val empty SearchTree
empty.Contains(0) // true, oops!

The solution is to create a wrapper type containing a pointer to the search tree for the public interface. What was previously called SearchTree, we rename to node, and create type BinaryTree struct { root *node }. While not necessary, I'd also provide an explicit constructor NewBinaryTree().

This is the code I ended up with:

type BinaryTree struct {
    root *node
}

func NewBinaryTree() *BinaryTree {
    return &BinaryTree { nil }
}

type node struct {
    value int
    left, right *node
}

func (node *node) getNode(i int) **node {
    if node.value < i {
        if node.left == nil {
            return &node.left
        }
        return node.left.getNode(i)
    } else if i < node.value {
        if node.right == nil {
            return &node.right
        }
        return node.right.getNode(i)
    }
    return &node // not nil, not writable
}

func (tree *BinaryTree) Contains(n int) bool {
    root := tree.root
    if root == nil {
        return false
    }
    return *(root.getNode(n)) != nil
}

// returns true if the tree was mutated as a result,
// and false if the number was already present
func (tree *BinaryTree) Add(n int) bool {
    if tree.root == nil {
        tree.root = &node{n, nil, nil}
        return true
    }
    target := tree.root.getNode(n)
    if *target == nil {
        *target = &node{n, nil, nil}
        return true
    }
    return false
}

(see it live on ideone)


GPA calculator, implemented for a course This is from a Java course which I'm taking. The class StudentUtil, including method-declarations and comments, was provided by the instructor. I just had to finish the bodies of the two methods.

calculateGPA() computes the average performance of students. Every A-grade gives 4 points, every B-grade 3 and every C-grade 2 point.

calculateGPA() returns students which have performed within a specified range.

The StudentUtil class:

package modul;

import java.util.ArrayList;

public class StudentUtil {

    public static double[] calculateGPA(int[] studentIdList, char[][] studentsGrades) {
        double[] grades = new double[studentIdList.length];
        int i = 0;

        for (char[] studentGrade : studentsGrades) {
            double sumGrades = 0.0;

            for (char grade : studentGrade) {
                if (grade == 'A') {
                    sumGrades += 4;
                } else if (grade == 'B') {
                    sumGrades += 3;
                } else {
                    sumGrades += 2;
                }
            }
            grades[i++] = sumGrades / studentGrade.length;
        }

        return grades;
    }

    public static int[] getStudentsByGPA(double lower, double higher, int[] studentIdList, char[][] studentsGrades) {
        // perform parameter validation. Return null if passed parameters are not valid
        if (lower < 0.0) {
            return null;
        }

        if (higher > 4.0) {
            return null;
        }

        if (lower > higher) {
            return null;
        }

        if (studentIdList.length != studentsGrades.length) {
            return null;
        }
        // invoke calculateGPA
        double[] gpas = calculateGPA(studentIdList, studentsGrades);
        ArrayList<Integer> ids = new ArrayList<>();

        for (int i = 0; i < studentIdList.length; i++) {
            if (gpas[i] >= lower && gpas[i] <= higher) {
                ids.add(studentIdList[i]);
            }
        }
        // construct the result array and return it. You would need an extra for loop to compute the size of the resulting array
        int[] ret = new int[ids.size()];

        for (int i = 0; i < ret.length; i++) {
            ret[i] = ids.get(i);
        }

        return ret;
    }

}

My test class:

package modul;

import static java.lang.System.out;
import java.text.DecimalFormat;
import static java.lang.System.out;

public class Sandbox {

    public static void main (String[] args) throws Exception {
        int[] studentIdList = { 1001, 1002 };
        char[][] studentsGrades = { { 'A', 'A', 'A', 'B'  }, { 'A', 'B', 'B' } };

        double[] results = StudentUtil.calculateGPA(studentIdList, studentsGrades);

        for (double result : results) {
            out.printf("%.2f\n", result);
        }

        int[] ids = StudentUtil.getStudentsByGPA(3.2, 3.5, studentIdList, studentsGrades);

        for (int result : ids) {
            out.println(result);
        }
    }
}

It has passed the automated test.

But what do you think about the demand of returning null when the validation of getStudentsByGPA() fails? Would one really do that this way? Or would one throw some specific exception instead, IllegalArgumentException for example?

What do you think about my code in general? What would you have done else and why?

In order, with come code comments first:

The StudentUtil-class:

package modul;

Try to avoid naming things as misspelled words. "Module" would probably not be a good choice for a package name because "Module" has a meaning in programming in general, and since version 1.9 it even has a specific meaning in Java. This doesn't mean, however, that "Modul" is better.

import java.util.ArrayList;

public class StudentUtil {

    public static double[] calculateGPA(int[] studentIdList, char[][] studentsGrades) {
        double[] grades = new double[studentIdList.length];
        int i = 0;

        for (char[] studentGrade : studentsGrades) {
            double sumGrades = 0.0;

            for (char grade : studentGrade) {

Double for loop, great, and without incrementing variables, even better. The names "grade" and "studentGrade" leave me a bit confused though. "studentGrade" contains more than one grade? I would replace "studentGrade" with something like "singleStudentGrades".

                if (grade == 'A') {
                    sumGrades += 4;
                } else if (grade == 'B') {
                    sumGrades += 3;
                } else {
                    sumGrades += 2;
                }

Consider having an explicit if (grade == 'C') case, and making your else case throw an error. It's a simple way to make sure your input is only ever A, B, or C. Unless we want to assume that anything not given a letter grade (e.g. something never assigned a grade) defaults to a 2.

            }
            grades[i++] = sumGrades / studentGrade.length;
        }

        return grades;
    }

    public static int[] getStudentsByGPA(double lower, double higher, int[] studentIdList, char[][] studentsGrades) {
        // perform parameter validation. Return null if passed parameters are not valid
        if (lower < 0.0) {
            return null;

Note about the nulls at the end of my answer

        }

        if (higher > 4.0) {
            return null;
        }

        if (lower > higher) {
            return null;
        }

        if (studentIdList.length != studentsGrades.length) {
            return null;
        }
        // invoke calculateGPA
        double[] gpas = calculateGPA(studentIdList, studentsGrades);
        ArrayList<Integer> ids = new ArrayList<>();

        for (int i = 0; i < studentIdList.length; i++) {
            if (gpas[i] >= lower && gpas[i] <= higher) {
                ids.add(studentIdList[i]);
            }
        }
        // construct the result array and return it. You would need an extra for loop to compute the size of the resulting array

I don't understand this comment - is it justification for calling ids.size()? If so, it's not quite right. You could add a counter variable that gets incremented in your if clause above. That doesn't mean that you necessarily should, though - see below

        int[] ret = new int[ids.size()];

        for (int i = 0; i < ret.length; i++) {
            ret[i] = ids.get(i);
        }

Rather than this, consider List.toArray() - it'll save you the indexing. Check out this question: Converting 'ArrayList to 'String[]' in Java

        return ret;
    }

}

test-class:

package modul;

import static java.lang.System.out;
import java.text.DecimalFormat;
import static java.lang.System.out;

public class Sandbox {

    public static void main (String[] args) throws Exception {
        int[] studentIdList = { 1001, 1002 };
        char[][] studentsGrades = { { 'A', 'A', 'A', 'B'  }, { 'A', 'B', 'B' } };

        double[] results = StudentUtil.calculateGPA(studentIdList, studentsGrades);

        for (double result : results) {
            out.printf("%.2f\n", result);
        }

        int[] ids = StudentUtil.getStudentsByGPA(3.2, 3.5, studentIdList, studentsGrades);

        for (int result : ids) {
            out.println(result);
        }
    }
}

I encourage you to consider writing unit tests (I recommend JUnit). It'll make your tests easier to write and read. The above tests are ok, but I would definitely add tests to check that you get null when you expect to.

Overall:

Your code is overall quite clean and easy to follow. It's not quite production-level, but it is good for a Java course. Nice job!

Regarding returning null:

There is a large discussion around this issue. I think most people believe something along these lines: 1.) null should not be used in place of an error. This is because in general, methods should enforce their contracts loudly, i.e. if a method's job is to take a number greater than zero and return it times two, and it gets a number less than zero, it should complain. By returning null, you force programmers who use your code (if they're responsible) to write in code to handle the possible null case, because otherwise there's no guarantee that they will be aware of the error that made your method return null.

And 2.) null can be used as "no results", but it might be better to return an Option or an empty data structure instead. For more, check out this question Is it better to return NULL or empty values from functions/methods where the return value is not present?

For a class assignment, though, it may well be the case that using null is "ok" because its fast - and it doesn't require you to shift focus from whatever the point of this assignment is to spend time writing exception throwing code. Avoiding using null as an error, and instead throwing an exception, is a best practice, though, and as you grow as a programmer you may want to do so even if it's not required. Be careful though - if your code is auto-graded and it is expected that it will return null for a given input, an exception will probably cause it to be marked wrong. In this case I suggest writing code to your assignment's specification, and being content with knowing that were you writing code in the "real world", you'd do it differently


Dump hash in columns I tried to answer the question "How to print a hash in Perl, such that 3 key value pairs are printed on each line?" like this.

As I got an uncommented downvote, I'd like to ask: What's wrong with/How to improve:

use Modern::Perl;

my %h = ();
for (0..7) {
    $h{$_} = chr(65 + $_);
}
print %h, "\n";
my $cols = +$ARGV[0] || 5;
my $n = -$cols;
for my $key (keys %h) {
    print $key, ' => ', $h{$key}, 0 == ++$n % $cols ? "\n" : "\t\t";
}
print $n % $cols ? "\n------" : "------";

Wrong is too heavy word, and I don't why it get down voted, but minor improvements are possible.

Modern::Perl is not core module and it usually means strict, warnings, and perhaps autodie are used (plus some other tweaks).
chr() is not needed, and hash slice assignment works equally well, not to mention that it is perl idiom
keys %h may generate large in memory list for bigger hashes, and while .. each handles such cases better. There is a catch with each as it uses internal hash pointer which needs to be reset with keys %h if you want to start back from hash beginning (in non LIST context keys %h doesn't generate list).

use strict;
use warnings;

my %h;
@h{ 0 .. 7 } = "A" .. "H";
my $cols = 3;
my $n = -$cols;

keys %h;
while ( my ($k,$v) = each(%h) ) {
  print "$k => $v";
  print 0 == ++$n % $cols ? "\n" : "\t\t";
}
print "\n" if $n % $cols;
print "------";


Dropdown menu with submenu and heredocs I was recently going through and refactoring old code, and I eventually came across the code for my website's menu bar, so I started to refactor it.

I also recently was introduced to Heredocs, which I am very new to and not sure all the ins-and-outs yet.

Here is the refactored code for part of it (I am mostly interested in responses about this specific part of the menu, which is a dropdown menu that every logged in user gets that essentially has their name and then it drops down into some other options regarding themes):

<?php

    $showAdminPanel = ((hasPerms($_SESSION['users_perms'], $_SESSION['role_perms'], 8)) ? "
Admin Panel
":"");
    $devPerms = ((hasPerms($_SESSION['users_perms'], $_SESSION['role_perms'], 13)) ? "

Issues

Requests

Changelog

":"");

    $themes = "";
    foreach(scandir($assetsDir."themes/") as $file) {
        if((strcmp($file,".") != 0) && (strcmp($file,"..") != 0)) {
            $themes .= '
'.substr(ucfirst($file),0,-4).'
';
        }
    }

    echo <<<USERACCOUNTDROPDOWN

            {$_SESSION["user"]["name"]}

                {$showAdminPanel}

                    Themes

Default: Cosmo

                        {$themes}

                    Development

                        {$devPerms}

Logout

USERACCOUNTDROPDOWN;
?>

The reason that I am more interested in this section of the code rather than the entire menu bar is that, this part of it has some permissions baked in using the $devPerms variable, basically if user has perm ID 13 it creates a string which has links to specific parts of the website, if user does not, the string is blank.

This code works, but I feel like there is a better way to accomplish what I am trying to do here that will make it look cleaner.

My question is this: How would you have written this code? I would love to improve my Heredocs understanding as I believe it will improve my programming in general.

Excessive perens in your ternary - they don't help with readability, scrap em...

$showAdminPanel = hasPerms($_SESSION['users_perms'], $_SESSION['role_perms'], 8) ? "
Admin Panel
" : "";

For long ternary lines I sometimes like to put a line break and a tab before the ? and :.

$showAdminPanel = hasPerms($_SESSION['users_perms'], $_SESSION['role_perms'], 8)
    ? "
Admin Panel
"
    : "";

The second ternary operator contains invalid HTML.
 must be a child of
 or
, not another
.

Using strcmp seems like overkill in the scandir loop. it would be faster to just use an == operator. Also, it's generally better practice to creatte and append to an array than to a string. Every time you add to taht string in that loop, the entire string has to be loaded into memory all over again. It's much quicker to use a buffer liek this...

$themes = array();
foreach(scandir($assetsDir."themes/") as $file) {
    if($file == "." || $file == "..") continue;
    $themes[] = '
'.substr(ucfirst($file),0,-4).'
';
}
// Turn the buffer into a string
$themes = implode('', $themes);

There is no reason for a heredoc here since you're at the end of the script. Just close the php tag and put the stuff after that (replacing the curlies with <?php= and ;?>), that way you don't have the PHP interpreter interpreting things it doesn't need to interpret.


"ACM ICPC Team" challenge on Hackerrank... Easy? This challenge took me awhile to figure out, and it's characterized as "easy," so I'm sorta wondering what I missed.

Problem Statement
You are given a list of N people who are attending ACM-ICPC World Finals. Each of them are either well versed in a topic or they are not. Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics.
N = number of people = number of lines of input. 2 ≤ N ≤ 500
M = number of topics = number of bits per line. 1 ≤ M ≤ 500

Sample Input

4 5
10101
11100
11010
00101

Sample Output

5
2

My solution below uses a BitArray object, because all of the test cases except one have more than 32 topics.
I'm wondering if HackerRank wasn't expecting something a little more fundamental... Maybe some clever string twiddling hack that I don't know about?
Most of the test cases took about .86 seconds to execute, which seems quite slow to me.
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Text;

class Solution {
    static void Main(String[] args)
    {
        string input = Console.ReadLine();
        string[] inputs = input.Split(new char[] {' '});

        int numberOfMembers = int.Parse(inputs[0]);
        int numberOfTopics = int.Parse(inputs[1]);

        var bitArray = new BitArray[numberOfMembers];
        for (int n = 0; n < numberOfMembers; n++)
        {
            bitArray[n] = new BitArray(numberOfTopics);

            string memberTopics = Console.ReadLine();
            for(int m = 0; m < numberOfTopics; m++)
                bitArray[n].Set(m, memberTopics[m] == '1');
        }

        // Find the maximum number of topics that all the teams know.
        int maxTopics = 0;
        for(int i = 0; i < numberOfMembers - 1; i++)
            for (int j = i + 1; j < numberOfMembers; j++)
            {
                int numberOfTeamTopics = NumberOfSetBits(new BitArray(numberOfTopics).Or(bitArray[i]).Or(bitArray[j]));
                if (numberOfTeamTopics > maxTopics)
                    maxTopics = numberOfTeamTopics;
            }

        // Find the number of teams that know the maximum number of topics.
        int maxTeams = 0;
        for(int i = 0; i < numberOfMembers - 1; i++)
            for (int j = i + 1; j < numberOfMembers; j++)
            {
                int numberOfTeamTopics = NumberOfSetBits(new BitArray(numberOfTopics).Or(bitArray[i]).Or(bitArray[j]));
                if (numberOfTeamTopics == maxTopics)
                    maxTeams++;
            }

        Console.WriteLine(maxTopics);
        Console.WriteLine(maxTeams);
    }

    static int NumberOfSetBits(BitArray b)
    {
        int count = 0;
        for (int i = 0; i < b.Length; i++)
            if (b.Get(i))
                count++;
        return count;
    }
}

Some improvements:

Combine loops

int maxTopics = 0;
int maxTeams = 0;
for(int i = 0; i < numberOfMembers - 1; i++)
    for (int j = i + 1; j < numberOfMembers; j++)
    {
        int numberOfTeamTopics
            = NumberOfSetBits(new BitArray(numberOfTopics).Or(bitArray[i]).Or(bitArray[j]));

        if (numberOfTeamTopics > maxTopics)
        {
            maxTopics = numberOfTeamTopics;
            maxTeams = 1;
        }
        else if (numberOfTeamTopics == maxTopics)
        {
            maxTeams++;
        }
    }

Use a better algorithm for counting set bits

public static Int32 NumberOfSetBits(BitArray bitArray)
{
    Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];
    bitArray.CopyTo(ints, 0);
    Int32 count = 0;

    // fix for not truncated bits in last integer that may have been set to true with SetAll()
    ints[ints.Length - 1] &= ~(-1 << (bitArray.Count % 32));

    for (Int32 i = 0; i < ints.Length; i++)
    {
        Int32 c = ints[i];

        // magic (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)
        unchecked
        {
            c = c - ((c >> 1) & 0x55555555);
            c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
            c = ((c + (c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
        }
        count += c;
    }
    return count;
}

New execution time: 0.12 seconds.


Extract string between first occurring set of parenthesis I have this function and need to refactor it
Please refactor the code below to make it more concise, efficient and readable with good logic flow
function findFirstStringInBracket($str){
    if(strlen($str) > 0){
        $firstbracket = strstr($str, '(');
        if($firstbracket){
            $firstbracket = ltrim($firstbracket, '(');
            return strstr($firstbracket, ')', true);
        }else{
            return '';
        }
    }else{
        return '';
    }
}

I find my snippet below to be direct, concise, and readable (but I rarely have any trouble reading regex patterns).
The pattern literally matches the first occurring opening parenthesis, then captures one or more non-closing-parenthesis characters, then matches the required closing parenthesis.
A regex approach means a single function call solution and only one return in your custom function (which makes your code cleaner to read).
Other devs may prefer to avoid regex, but I think this is a perfect case for employing it.
One note of difference between my script and yours, is that if the closing parenthesis is missing in the input string with your script, your function will return false.  My script will always return a string.  (see here)
Code:
function findFirstStringInBracket(string $string): string
{
    return preg_match('~\(([^)]+)\)~', $string, $match) ? $match[1] : '';
}

Unless you are doing hundreds of thousands of iterations of this call, performance probably isn't an issue.  If it is a bottle neck, then you probably want to look at other ways to improve script performance.
(Demo with some test cases)
$strings = [
    'the(crow)bar',
    'foo()bar',
    'handlebar()',
    '()foofighters',
    '(foobar)',
    '()',
    'barfood',
    'barf(oo',
    'fooeybar)',
    ')foob(',
];

$result = [];
foreach ($strings as $string) {
    $result[$string] = preg_match('~\(([^)]+)\)~', $string, $match) ? $match[1] : '';
}
var_export($result);

Output:
array (
  'the(crow)bar' => 'crow',
  'foo()bar' => '',
  'handlebar()' => '',
  '()foofighters' => '',
  '(foobar)' => 'foobar',
  '()' => '',
  'barfood' => '',
  'barf(oo' => '',
  'fooeybar)' => '',
  ')foob(' => '',
)


Obtaining information about the logged in user I currently have a special service to obtain information about the logged in user. I have an interface

/**
 * The service operates on the data of an authorised user.
 */
public interface AuthorizationService {
    User getUser();
    String getUserId();
    String getUsername();
    boolean isLogged();
}

and implementation

@Service("authorizationService")
public class AuthorizationServiceImpl implements AuthorizationService {
    private final UserSearchService userSearchService;
    /**
     * {@inheritDoc}
     */
    @Override
    public User getUser() {
        return userSearchService.getUserByUsername(this.getUsername());
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public String getUserId() {
        return userSearchService.getUserByUsername(SecurityContextHolder.getContext().getAuthentication().getName()).getId();
    }
...
}

and for example, when I use the method to create messages, I do so

@Override
public String createMessage(
        @NotNull @Valid final SendMessageDTO sendMessageDTO
) throws ResourceNotFoundException, ResourceConflictException {
    log.info("Called with sendMessageDTO {}", sendMessageDTO);

    final UserEntity user = this.findUser(this.authorizationService.getUserId());
    final MessageEntity message = this.sendMessageDtoToMessageEntity(sendMessageDTO);

    message.setSender(user);

    ...
}
    private UserEntity findUser(final String id) throws ResourceNotFoundException {
        return this.userRepository
                .findByUniqueIdAndEnabledTrue(id)
                .orElseThrow(() -> new ResourceNotFoundException("No user found with id " + id));
    }

However, I do not know if this is a good way to obtain information about the logged-in user?
Instead of a DTO User object, I could return an entity(I have a rule that I do not return entity service methods) and then I would not have to use the findUser () method to search for a user. What do you think about it?
Is my way of getting a DTO User logged in user or ID a safe way?

Usually the logged in user and it's common used information is stored in the session. And the session is usually wrapped in a Context class (like SecurityContextHolder itself). This is done because you can decouple your code from the session or from the servlet api (or whatever api you're using). It also makes it easier to test.

Most of web pages do show your user information when you're logged in, e.g. your avatar on this page on the top. So for every request you do not have to look up the user's information.

I'd introduce a Context class which provides a setUser and getUser method.

Beside that:

AuthorizationService: Authorization means: Is the user allowed to do x. (While authentication means: Is the user really the user he pretends to be). Or in other words: The name of the type is misleading.
getUser(): This method calls this.getUsername() -> I don't see the code of this one, bit I assume it looks up the username by SecurityContextHolder. This means, the AuthorizationService is tightly coupled Spring Security, which is bad. Same for getUserId() -> it's better to pass the arguments and put the responsibility to the presentation layer (which includes security usually)


binary search using recursion I implemented a binary search algorithm using recursion in Java
package com.soloworld.binarysearch;

/**
 *
 * @author soloworld
 */
public class BinarySearch {

   private int[] array;

    public BinarySearch(int[] array) {
        this.array = array;
    }

    public int recursivesearch(int[] array,int startindex,int endindex,int key) {
        if(endindex>0) {
            int middle =(startindex+ endindex)/2;
            System.out.println("middle "+middle);
            if(array[middle]== key) return middle;
            else if (key <array[middle]) {
                return recursivesearch(array, startindex, middle-1, key);
            } else if(key > array[middle]) {

               return recursivesearch(array, middle+1, endindex, key);
            }
        }
        return -1;
    }

}

it worked, all i want to know is have  i done it in correct way or there any way to optimize this

It's always good to use guard conditions.  Instead of wrapping all of your logic in a code block, check for conditions when you don't have to execute and return early.  Like so:

public int recursivesearch(int[] array,int startindex,int endindex,int key) {
    if (endindex<=0){
       return -1;
    }

    // everything else here
}

It's much easier to read if you structure your code like this: also much less error-prone.

Next, you are missing some guards.  What happens if you array is empty?  What happens if the value you are looking for is larger or smaller than any values in the array?  You have to check for these conditions and handle them individually.  You are also trusting that the user has passed a proper index in.

Also, I would make it easier to use by having the public method not require start and end index, calculating them from the length, and then passing it into the actual search method which is protected.

Finally, you were not properly detecting a missing value.  You were returning -1 if endIndex<=0, but the proper condition is endIndex<startIndex.  Yours ends in an infinite loop for items such as:

recusivesearch([1,2,3,4,6], 0, 4, 5)

Keep in mind that java is not my language of choice, so this might be best viewed as pseudo-code:

public int search(int[] array, int key) {
    if (array.length == 0){
        return -1;
    }

    if (key < array[0] || key > array[array.length-1]){
        return -1;
    }

    return this.recursiveSearch(array, key, 0, array.length-1);
}

protected int recursiveSearch(int[] array, int key, int startIndex, int endIndex){
    if (endIndex<startIndex){
        return -1;
    }

    int middleIndex = startIndex + (endIndex-startIndex)/2;
    if (array[middleIndex] == key){
        return middleIndex;
    }
    if (key < array[middleIndex]){
        return recursiveSearch(array, key, startIndex, middleIndex-1);
    }
    return recursiveSearch(array, key, middleIndex+1, endIndex);
}

Nitpicks

Your definition of middle was prone to integer overflow.  I adjusted the definition to fix that issue.

Watch out for your use of whitespace.  In the long run, consistent whitespace makes code maintenance much easier.  Java problem has some general standards, which I'm guessing at.

Same with capitalization.  I believe Java prefers camelCase.  Some people prefer snake_case.  Pick one and stick to it: you don't do either, and it makes it harder to read your variable names.

Naming variables is also important.  You have startindex and endindex, and then middle.  You should at least go for consistency:

startIndex, endIndex, middleIndex

Or

start, end, middle

Since these variables contain indexes, I would probably go for the former, but for shorter names I would also consider the latter acceptable.  Either way, Keep your names consistent.


Parsing a C++ function declaration with Perl 6 grammar I wrote a Perl 6 grammar to parse a C++ function. My final goal would be to parse an entire header. The aim is not to correct C++ syntax errors, but to parse valid C++.

Do you have some advice or improvements?

#!/usr/bin/env perl6

grammar FUNCTION {
    token TOP       { [ <attr> \s+ ]? <type> [ \s* <type_mod> ]?
                        (\s+) <fname> (\s*) "("
                        (\s*) [<parameter> [ "," (\s*) <parameter> ]* ]? (\s*)
                        ')'(\s*) ';'
                    }

    token name      { \w+ }
    token namespace { [ "::" ]? [ <name> "::" ]* }
    token attr      { <name>  }
    token type      {  <namespace>? <name> }
    token type_mod  { [ \*|\& ]+ }
    token fname     { <name> }
    token variable  { <name> }
    token parameter { <type> [\s* <type_mod> ]? \s+ <variable> }
}

my $str = "const ::one::std::string ** ma1n( int&& i, two::std::string va1e_ );";
my $parsed = FUNCTION.parse($str);
say $parsed;

I'd expect to see many more tests of any program that addresses a problem as gnarly as parsing a C++ declaration.

Choosing a couple I've recently had cause to write (on Stack Overflow), I would immediately add

void (SENDER::*get_func())(double, double);

(from Passing pointers to member function as returned values to QObject::connect())
constexpr std::size_t len(const T(&)[length]);

(from Differentiate between array and pointer as function parameter)

Neither of these succeeded when I tried them.


Parallax animation, running well on Chrome but slow on Safari I have the following script to create a parallax effect on the page using request animation frame, it runs well on Chrome, but on Safari is lagging, I think because I run too many calculations on each rAF.

  $('.parallax').each(function () {
    var section = $(this),
        elements = section.find('[data-parallax-ratio]');

    elements.data('parallax-current', 0);

    function animation() {
      var scrollPos = $(window).scrollTop(),
          offsetY = section.offset().top - 60;

      for (var i = 0; i < elements.length; i++) {
        var el = $(elements[i]),
        ratio = el.data('parallax-ratio'),
        current = el.data('parallax-current');

        var newPos = (offsetY - scrollPos) * ratio;

        var pos = current - ((current - newPos) * 0.08);

        el.css('transform', 'translateY(' + pos + 'px)');

        el.data('parallax-current', pos);
      }

      window.requestAnimationFrame(animation);
    }

    animation();

  });

The major issue that I see in your code is that you keep requestAnimationFrame no matter what. This obviously causes the browser to update the css of the element at any time.

Since your animation is based on scroll I would suggest to define an handler to window.onscroll.

While doing this you perhaps may wish to transform your animation method to be a plugin method that you would call for every parallax element.

Resulting code becomes something like this:

$.fn.parallaxAnimate = function() {
    var elements = this.find('[data-parallax-ratio]');

    var scrollPos = $(window).scrollTop(),
      offsetY = this.offset().top - 60;

    for (var i = 0; i < elements.length; i++) {
        var el = $(elements[i]),
            ratio = el.data('parallax-ratio'),
            current = el.data('parallax-current') || 0;

        var newPos = (offsetY - scrollPos) * ratio;
        var pos = current - ((current - newPos) * 0.08);

        el.css('transform', 'translateY(' + pos + 'px)');
        el.data('parallax-current', pos);
    }
}

    window.onscroll = function(){
        $('.parallax').parallaxAnimate();
    };

See a (ugly) fiddle

Edit: I was wrong on my previous attempt to solve smoothness and I was also wrong about subscribing onscroll

I tried to solve the problem that the OP is having as the animation is not smooth. On my previous attempt I tried to implement a scroll animation on a scroll event, and I got a warning on firefox (this is a free translation since I got my browser on portuguese unfortunately):

  This site appears to use a scroll-linked position effect. This may not
  work properly with asynchronous panning. See
  https://developers.mozilla.org/docs/Mozilla/Performance/ScrollLinkedEffects
  for more details...

And there you can read an explanation of what are the causes of this warning.

Meanwhile, on this same documentation page on Other effects, you can have a link to a useful site that implements many scroll effects, one of those being the parallax. All of this only with css...

I will post here one smaller example based on the implementation of the site, give props to that man please, not to me ;).

Base Layer

Base Layer

Background Layer


SQL stored procedure that returns a boolean value? CREATE PROCEDURE dbo.foo
AS
BEGIN
DECLARE @true BIT, @false BIT;
SET @true = 1;
SET @false = 0;

IF (some condition)
    Select @true;
ELSE
    Select @false;
END

SQL is not the language that I'm strongest in now, but the above stored procedure seems to be produce the desired functioning: returning the truth value of some condition.

Is there a better way to define this stored procedure?  By the way, it runs on MS SQL 2008.

Since SQL Server has no Boolean data type, and since the bit values 1 and 0 are widely used and understood to represent true and false in many programming languages, I would simply return 0x1 or 0x0 as appropriate. I don't think that actually declaring @true and @false variables adds anything to the code.

What might add something would be to return the value in an output parameter with a useful name:

CREATE PROCEDURE dbo.foo
    @IsTrue BIT OUTPUT
AS
BEGIN

IF (condition)
    SET @IsTrue = 0x1
ELSE
    SET @IsTrue = 0x0
END

Especially if your procedure is called from other TSQL code, it is much easier to use an output parameter in the calling code than a result set. But if you're calling it from some other language then you can make that decision based on the calling language and framework. An output parameter is the preferred way to return scalar values from a procedure: use SELECT for returning result sets and RETURN for indicating the status of the procedure execution itself (succeeded, failed, failed with reason X etc.).

And by 'useful name' I mean a name that indicates that the purpose of the variable is to store a true/false condition. Names starting with Is or Has are usually good. But please do not use a double-negative name: something like if @IsNotEnabled = 0x0 is extremely difficult to parse mentally without interrupting your thoughts. IsEnabled = 0x1 is far better.

And depending on your condition, you might be able to use CASE:

SET @result = CASE WHEN (condition) THEN 0x1
              ELSE 0x0
              END

Whether or not that's preferable in this specific case is probably a question of taste, but CASE seems more 'SQL-like' to me. But IF and CASE do different things so you can't always substitute one for the other.


Spring Boot methods to add and remove relationships I have a Spring Boot application and I wrote a piece of code to manage relationships between two entities.

The code consists mostly in these two methods:

@Override
    public void associateDocumentsToPersonRecord(Long personRecordId, AssociationDTO associationDTO) {
        PersonRecord personRecord = personRecordRepository.findById(personRecordId).orElse(null);
        if (personRecord == null)
            return;

        for (Long documentId : associationDTO.getDocumentsId())
            documentRepository
                    .findById(documentId)
                    .ifPresent(document -> personRecord.getDocuments().add(document));

        personRecordRepository.save(personRecord);
    }

    @Override
    public void removeAssociateDocumentsToPersonRecord(Long personRecordId, AssociationDTO associationDTO) {
        PersonRecord personRecord = personRecordRepository.findById(personRecordId).orElse(null);
        if (personRecord == null)
            return;

        for (Long documentId : associationDTO.getDocumentsId())
            documentRepository
                    .findById(documentId)
                    .ifPresent(document -> personRecord.getDocuments().remove(document));

        personRecordRepository.save(personRecord);
    }

One method is for adding relations, the other is to remove them.

I definitely get the smell of duplicated code and the only thing that changes is remove or add between the two methods.
How could I refactor this code in the most elegant way?

You may extract the action part as a method parameter (I am using BiConsumer in this case).

@Override
public void performActionOnRecords(Long personRecordId, AssociationDTO associationDTO, BiConsumer<PersonRecord,Document> action) {
    PersonRecord personRecord = personRecordRepository.findById(personRecordId).orElse(null);
    if (personRecord == null)
        return;

    for (Long documentId : associationDTO.getDocumentsId())
        documentRepository
                .findById(documentId)
                .ifPresent(document -> action.accept(personRecord,document));

    personRecordRepository.save(personRecord);
}

and call the methods as

performActionOnRecords(personId, associationDTO, (personRecord, document) -> personRecord.getDocuments().add(document)); // To add document

and,

performActionOnRecords(personId, associationDTO, (personRecord, document) -> personRecord.getDocuments().remove(document)); // To remove document


Print the N longest lines in a file I have implemented the "Find the N longest lines in a file" problem from CodeEval quoted below.

I got a full 100 score and 182ms execution time of their data set on the site so I consider the code to be working and effective. What I'm wondering is, is there something I can do to make this faster than it already is? Did I miss anything? Any other comments?

  Write a program which reads a file and prints to stdout the specified
  number of the longest lines that are sorted based on their length in
  descending order. Input sample:

  Your program should accept a path to a file as its first argument. The
  file contains multiple lines. The first line indicates the number of
  lines you should output, the other lines are of different length and
  are presented randomly. You may assume that the input file is
  formatted correctly and the number in the first line is a valid
  positive integer.

  For Example:

2
Hello World
CodeEval
Quick Fox
A
San Francisco

  Output sample:

  Print out the longest lines limited by specified number and sorted by
  their length in descending order.

  For example:

San Francisco
Hello World

The code:

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class NLongestLines {

    private final static Comparator<String> CMP = new Comparator<String>() {
        @Override
        public int compare(String arg0, String arg1) {
            return arg1.length() - arg0.length();
        }
    };

    private static void insertSorted(List<String> list, String string) {
        int max = list.size();
        int min = 0;
        int pivot = min + (max - min) / 2;

        // Binary search for insertion point.
        while (min < max) {
            int c = CMP.compare(string, list.get(pivot));
            if (c <= 0) {
                max = pivot;
            } else {
                min = pivot + 1;
            }
            pivot = min + (max - min) / 2;
        }

        list.add(min, string);
    }

    public static void main(String[] args) throws Exception {
        try (FileReader fr = new FileReader(args[0]);
             BufferedReader reader = new BufferedReader(fr)) {
            List<String> longestLines = new ArrayList<>();

            String line = reader.readLine();
            {
                int numLongestLines = Integer.parseInt(line);
                while (numLongestLines > 0 && (line = reader.readLine()) != null) {
                    numLongestLines--;
                    line = line.trim();
                    insertSorted(longestLines, line);
                }
            }

            int shortestLongLength = findShortestLongLine(longestLines);
            while ((line = reader.readLine()) != null) {
                line = line.trim();
                if (line.length() > shortestLongLength) {
                    insertSorted(longestLines, line);
                    longestLines.remove(longestLines.size() - 1);
                    shortestLongLength = findShortestLongLine(longestLines);
                }
            }

            for (String longLine : longestLines) {
                System.out.println(longLine);
            }
        }
    }

    private static int findShortestLongLine(List<String> longestLines) {
        return longestLines.get(longestLines.size() - 1).length();
    }
}

Edit/Addendum:

I have implemented and benchmarked the proposed solutions by Simon Forsberg (TreeSet) and RolfL (LinkedList).

The results can be seen here. The executive summary is that the original algorithm is significantly faster than the proposals in just about all test cases.

The source used for testing can be found here. Needs µbench from here.

the other lines are of different length and are presented randomly

I understand this as that all lines have different length. As such, I would make a different choice of data structure. Namely, a TreeSet<String>.

A TreeSet can be constructed with a Comparator, so I would use your existing comparator as the constructor for this TreeSet. Then I would use the descendingIterator() method to iterate x times over your elements in descending order.

Note: Even if there would be lines of the same length, you could still use a TreeSet but then you'd need to compare on both the length and the String itself, to avoid ignoring the insertion of an element that has the same length as a previous existing element. (If elements can be exactly identical, then TreeSet will not work well)

This will allow us to get rid of your insertSorted method and get rid of the potentially slow ArrayList.add(index, object) call which is \$O(n - index)\$


Basic T-SQL to compare two same length strings I've come up with the following T-SQL to compare similar same length strings.

Example usage would be:

OCR returns a value which is expected to be in the database.
PATINDEX is used to check the value's in the database, including matching for common errors (e.g. 0/O, I/1/l).
If multiple values are found, each match is scored for likeness to the original.

declare @t table (solution nvarchar(32), score bigint)

insert @t(solution)
select 'Portugal'
union select '9ortugal'
union select '9ortu8al'
union select 'Portu8al'
union select 'P0rtugal'
union select '90rtugal'
union select '90rtu8al'
union select 'P0rtu8al'
union select 'Portuga1'
union select '9ortuga1'
union select '9ortu8a1'
union select 'Portu8a1'
union select 'P0rtuga1'
union select '90rtuga1'
union select '90rtu8a1'
union select 'P0rtu8a1'

declare @answer nvarchar(32) = 'Portugal'

update @t
set score = cast(cast(cast(@answer as varchar) as varbinary(max)) as bigint) - (cast(cast(cast(solution as varchar) as varbinary(max)) as bigint) & cast(cast(cast(@answer as varchar) as varbinary(max)) as bigint))

select * from @t order by score --first result is the most similar

Results:

solution    score
Portugal    0
Portuga1    76
Portu8al    4653056
Portu8a1    4653132
P0rtugal    22236523160141824
P0rtuga1    22236523160141900
P0rtu8al    22236523164794880
P0rtu8a1    22236523164794956
9ortugal    4611686018427387904
9ortuga1    4611686018427387980
9ortu8al    4611686018432040960
9ortu8a1    4611686018432041036
90rtugal    4633922541587529728
90rtuga1    4633922541587529804
90rtu8al    4633922541592182784
90rtu8a1    4633922541592182860

SQL Fiddle

Notes:

Conversion to varchar because nvarchar seems to cause a loss of precision
Conversion to varbinary because doing varchar straight to numeric would result in a non-numeric issue for non-numeric characters.
Conversion to bigint to allow bitwise & arithmetic comparison
Use of - and & may be superfluous; perhaps just the - would be sufficient, but I feel (superstitious guess/don't have a strong enough understanding) that the & will help.

Concerns:

Errors at the start of the string have more impact than those later in the string.
Results look quite good on my test data, but not sure how predictable this would be in reality.
It would be nice to be able to weight the errors; e.g. O for 0 is very common; 6 for G or 8 for g less so; so the former should have a greater weighting (i.e. P0rtugal should be preferential to Portu8al; not just because of the character's position in the string).

Firstly, a stylistic point. SQL is typically written with keywords capitalised, SELECT instead of select for example.

Your table and variable names could use a little more meaning. Using @Countries or @CountryNames in place of the meaningless @t, for example.

You use NVARCHAR to hold your data, but immediately convert it to VARCHAR. I would recommend just using VARCHAR in your query, this allows you to remove the cast to VARCHAR's.

Lastly, the logic you use to set the score is a little convoluted, as you thought it might be. I would recommend using:

SET score = CAST(CAST(@SelectedCountry AS VARBINARY(MAX)) AS INT) - CAST(CAST(solution AS VARBINARY(MAX)) AS INT)

These changes would result in this:

DECLARE @CoutryNames TABLE (solution VARCHAR(32), score BIGINT)

INSERT INTO @CoutryNames(solution)
SELECT 'Portugal'
UNION SELECT '9ortugal'
UNION SELECT '9ortu8al'
UNION SELECT 'Portu8al'
UNION SELECT 'P0rtugal'
UNION SELECT '90rtugal'
UNION SELECT '90rtu8al'
UNION SELECT 'P0rtu8al'
UNION SELECT 'Portuga1'
UNION SELECT '9ortuga1'
UNION SELECT '9ortu8a1'
UNION SELECT 'Portu8a1'
UNION SELECT 'P0rtuga1'
UNION SELECT '90rtuga1'
UNION SELECT '90rtu8a1'
UNION SELECT 'P0rtu8a1'

DECLARE @SelectedCountry VARCHAR(32) = 'Portugal'

UPDATE @CoutryNames
SET score =
CAST(CAST(@SelectedCountry AS VARBINARY(MAX)) AS BIGINT)
- CAST(CAST(solution AS VARBINARY(MAX)) AS BIGINT)

SELECT * FROM @CoutryNames ORDER BY score --first result is the most similar

Here is the SQL Fiddle

The idea to use weighted errors got me thinking about how I would do it.

Here is what I came up with, you could pretty easily turn it into a function by adding the required boilerplate code and changing the SELECT @ErrorScore to RETURN @ErrorScore:

DECLARE @StringA VARCHAR(10) = 'bacon',
        @StringB VARCHAR(10) = 'bacon',
        @CharPosition TINYINT = 1,
        @ErrorScore INT = 0

DECLARE @LETTER_WEIGHTING TABLE(CorrectLetter CHAR(1), IncorrectLetter CHAR(1),LetterWeighting TINYINT)

INSERT INTO @LETTER_WEIGHTING
SELECT 'o','0',1 UNION ALL
SELECT 'o','Q',3 UNION ALL
SELECT 'g','6',2 UNION ALL
SELECT 'g','8',3

IF @StringA <> @StringB
BEGIN
    WHILE @CharPosition <= LEN(@StringA)
    BEGIN
        SELECT
        @ErrorScore +=
        CASE WHEN SUBSTRING(@StringA,@CharPosition,1) <> SUBSTRING(@StringB,@CharPosition,1)
        THEN
        ISNULL((
            SELECT TOP 1 LetterWeighting
            FROM @LETTER_WEIGHTING
            WHERE CorrectLetter = SUBSTRING(@StringA,@CharPosition,1)
            AND IncorrectLetter = SUBSTRING(@StringB,@CharPosition,1)
        ),5)
        *
        @CharPosition
        ELSE 0
        END

        SET @CharPosition+=1
    END
END

SELECT @ErrorScore

What this does is loop through all the characters of the first string and compare them with the appropriate character in the second string. If the characters do not match, then we use a lookup table of weightings for some errors or we use 5 as a base value if the correct/incorrect character pair is not in the lookup table. We then multiply the value in the previous step by the characters position in the string.

Here is an SQL Fiddle


How Does This Naive Stack Implementation Look? Consider this naive stack implementation in Elixir:

defmodule Stack do
  defstruct name: "", value: 0

  def init() do
    _s = []
  end

  def push(name, value, s) do
    s_new =  [%Stack{name: name, value: value}, s]
    {:ok,s_new}
  end

  def pop(s) do
    [h|tail] = s
    {:ok, h, tail}
  end

  def depth(s) do
    length(s)
  end

end

#Use:
# s = Stack.init()
# {:ok, s} = Stack.push("a",1,s)
# {:ok, item, s} = Stack.pop(s)
# l = Stack.depth(s)

Am I using structs correctly?  Any suggestions for more idiomatic code style?

The mechanical usage of the struct seems correct, but I'm having some conceptual issues with the original code.

First, the Stack structure models a single element instead of the entire structure. I find this weird, and it makes it impossible to implement custom protocols for the stack abstraction. Your module seems to partially abstract stack elements, and partially the entire stack structure.

Second, what is the purpose of key/value? Stack should work on arbitrary elements. What is in those elements should be left to the client of the structure, and not hardcoded as a requirement of theStack module.

Then, function push/3 accepts the abstraction as the last argument. This is contrary to the recommended conventions (subject as the first argument), and makes it impossible to use the abstraction with pipe operator |>.

Even if the last issue was fixed, pipes still won't work since push returns the result in format of {:ok, ...}. This is not needed, especially since there is no possible error outcome.

Notice that this doesn't hold for pop, which must return two values: last element pushed, and the modified structure (a stack containing remaining elements).

Disregarding the fact that stack really doesn't require an abstraction (Elixir list is already a stack), here's my take on it:

defmodule Stack do
  defstruct elements: []

  def new, do: %Stack{}

  def push(stack, element) do
    %Stack{stack | elements: [element | stack.elements]}
  end

  def pop(%Stack{elements: []}), do: raise("Stack is empty!")
  def pop(%Stack{elements: [top | rest]}) do
    {top, %Stack{elements: rest}}
  end

  def depth(%Stack{elements: elements}), do: length(elements)
end

This can then be used as:

iex(1)> Stack.new |> Stack.push(1) |> Stack.push(2) |> Stack.pop
{2, %Stack{elements: [1]}}


Parsing arguments for cd command This file manager has a code snippet that handles an argument of the "cd" console command. It converts the argument to a valid path, expands ~ and environment variables into the corresponding values:

std::vector<unicode_t> ConvertCDArgToPath( const unicode_t* p )
{
    std::vector<unicode_t> Out;

    std::vector<unicode_t> Temp;

    while ( p && *p )
    {
        unicode_t Ch = 0;

        if ( *p == '~' )
        {
            if ( LookAhead( p, &Ch ) )
            {
                if ( ( IsPathSeparator(Ch) || Ch == 0 ) && ApplyEnvVariable( "HOME", &Temp ) )
                {
                    // replace ~ with the HOME path
                    Out.insert( Out.end(), Temp.begin(), Temp.end() );
                    PopLastNull( &Out );
                }
            }
        }
        else if ( *p == '$' )
        {
            // skip `$`
            std::vector<char> EnvVarName = unicode_to_utf8( p+1 );
            for ( auto i = EnvVarName.begin(); i != EnvVarName.end(); i++ )
            {
                if ( IsPathSeparator( *i ) )
                {
                    *i = 0;
                    break;
                }
            }

            if ( ApplyEnvVariable( EnvVarName.data( ), &Temp ) )
            {
                // replace the var name with its value
                Out.insert( Out.end(), Temp.begin(), Temp.end() );
                PopLastNull( &Out );
                // skip var name
                p += strlen( EnvVarName.data() );
            }
        }
        else if ( IsPathSeparator(*p) )
        {
            if ( !LastCharEquals( Out, '/' ) && !LastCharEquals( Out, '\\' ) ) Out.push_back( DIR_SPLITTER );
        }
        else
        {
            Out.push_back( *p );
        }
        p++;
    }

    Out.push_back( 0 );

    return Out;
}

bool LookAhead( const unicode_t* p, unicode_t* OutNextChar )
{
    if ( !p ) return false;
    if ( !*p ) return false;
    if ( OutNextChar ) *OutNextChar = *(p+1);
    return true;
}

Is this code secure?
What is missing?
How can I deal with the duplicate code around the ApplyEnvVariable() calls?

What is missing

A compatibility with existing shells. There are certain expectations on how the expansion works; your code expands in an incompatible way; expect end-user complains:

Tilde is expanded only in the beginning of the word. You expand it anywhere.
Tilde may be followed by a login name, then the whole prefix is expanded to a home directory of that user. You do not expand the tilde-prefix.
There is no provision to escape tilde or $ from expanding.
There is no way to limit variable name before it hits the path separator.

How to deal with the duplicate code around ApplyEnvVariable() calls

I guess, the simplest way is to move the duplicated code directly into ApplyEnvVariable(). That would actually justify the name of the method: as of now it doesn't apply the variable but merely expands it.  Of course you'd need to pass Out.end() instead of Temp there.

Naming

It is very unusual to have variable names capitalized.


Recursive BFS solution for tree traversal I'm somewhat new to the wonderful world of Python, outside of simple codecademy-like challenges online.

This function was part of a project for school. It's tested and works, but I'm looking for some feedback. Did I over-think it? I don't think recursion was necessary, but I was in that mindset from the previous portion of the assignment which was a similar function for DFS.

Below is my code, the input format (a dictionary) and a visual representation of the tree that I used to test it:

def BFS(tree,level=["A"]):
  bfs_list = []
  if len(level) > 0:
    bfs_list += level
    sub_level = []
    for vertex in level:
      sub_level += tree[vertex]
    bfs_list += BFS(tree,sub_level)
  return bfs_list

#            ___A___
#           /       \
#          C         D
#        / | \     / | \
#       P  R  L   F  Q  S
#         / \       / \
#        O   E     G   H
#                 / \
#                N   M
#
tree = {"A" : ["C", "D"],
        "C" : ["P","R","L"],
        "R" : ["O","E"],
        "G" : ["N", "M"],
        "Q" : ["G", "H"],
        "D" : ["F", "Q", "S"],
        "P" : [],
        "L" : [],
        "N" : [],
        "M" : [],
        "H" : [],
        "S" : [],
        "F" : [],
        "O" : [],
        "E" : []}
print(BFS(tree))

You're off to a good start.  In cases like this, most of my comments come down to best-practices for coding standards.  I break down a few areas, starting from nitpicks to almost-bugs:

1. Spacing

In the python world it is worth familiarizing yourself with PEP8, which sets suggested standards for code formatting across the python world.  Yours looks pretty close to most of the standards, but one thing you are missing is your indentation.  2 spaces is pretty small: I would go for 4, which is the PEP8 recommendation.  Also, a space between parameters is recommended.  I.e. tree, level instead of tree,level.  Believe it or not, these things matter: in almost all cases, code is read more than it is written.  As a result, it is important for long-term maintenance to write code that is consistent and easy-to-read.

2. Doc strings

Doc strings are the preferred way of commenting your code.  Comments themselves should be used sparingly (you don't have any, which for a function of this size is fine), but doc strings should be used pretty much everywhere.  These are a formatted block of text, inside a comment, that comes right before your function definition (also classes and modules).  It describes the parameters, what the function does, and what it returns.  See here:

https://stackoverflow.com/a/24385103/1921979

3. Guard conditions

Instead of putting all of your code inside an indented block, this is one of many cases where a guard clause will make your code more readable.  At the top, put conditions on cases where you don't need to do any processing, and exit early.  I.e.:

if not level:
    return []
// everything else here

4. Recursion

Recursion here is perfectly fine.  You didn't overthink it or overdo it.  It actually fits perfectly in this case, and recursion is usually a harder concept to grasp, so anything that helps you practice it (without making the code a tangled mess) is a good choice.

5. Default parameter values

Your default value for the level parameter only works for your given example.  As a result, it is best to kill it.  Just make it a required positional parameter.

6. Error detection

Your code assumes that it is passed in a valid tree.  This is not a crazy assumption, but it will likely be a wrong assumption at some point in time.  In your current case, if someone passes in a broken tree, it will generally lead to an exception being raised.  This can be a good thing or bad thing depending on your viewpoint.  There are three ways I normally consider handling such an event (in order of preference):

Detect and raise an exception
Ignore and let python raise an exception
Silently ignore it

Here is a simple example of a tree that will fail:

tree = {"A" : ["C", "D"]}

Your current code opts for Option #2 above.  With the above example, python will raise a KeyError with a rather cryptic message: KeyError: 'C'.  This is not necessarily a bad thing.  Garbage In=Garbage Out.  However, the problem is that it might not be obvious what caused the error.  As a result I like to detect and raise my own exceptions to make it easier on whoever is using your method (Option #1):

for vertex in level:
    if tree not in vertex:
        raise ValueError('Broken tree: branch %s is referenced but not found in the tree' % (vertex))
    sub_level += tree[vertex]

This gives the user better information on where to start looking for the problem: most importantly, not in your function.  The third option would be to silently ignore such errors.  That would look something like this:

for vertex in level:
    if vertex not in tree:
        continue
    sub_level += tree[vertex]

This can be appealing because it makes your code play nicer if a broken tree comes its way.  The problem is that this can often end up hiding bugs, which just cause problems farther down the stack.  The farther your code gets before it crashes, the harder the problem tends to be to resolve.  So my default is to quit loudly if something is off.  That is what logging is for.


Recursive Windows Directory listing I wrote a PowerShell script for a superuser question:

  list of all files and directories under a path recursively, without recursing into junction points or links

I have a strong feeling that my code is way too complicated for such a simple task.

function Recurse($path) {

  $fc = new-object -com scripting.filesystemobject
  $folder = $fc.getfolder($path)

  foreach ($i in $folder.files) { $i | select Path }

  foreach ($i in $folder.subfolders) {
    $i | select Path
    if ( (get-item $i.path).Attributes.ToString().Contains("ReparsePoint") -eq $false) {
        Recurse($i.path)
    }
  }
}

$scriptPath = split-path -parent $MyInvocation.MyCommand.Definition
$outputlist = Recurse($scriptPath) | Out-File -Filepath .\outputlist.txt

Short instructions on how to use the script:

Paste the code into a text file and save it as PowerShell (.ps1) script
Place the script inside a folder to list all files+folder recursively without junction folder loops
Execute the script. A new file called outputlist.txt at the same location will appear

Questions:

Can I simplify this PowerShell script anyhow?
Is there a better Out-command where no blank spaces are appended after every line?

Here's a shot at it: (Requires PowerShell v3 or higher)

The idea here is to get all non-reparsepoint directories first.
For each directory, recurse into the subdirectory and then output the files at the current level.

In it's simplest form, it looks like this:

function Get-ChildItemNoReparsePoint($Path)
{
    Get-ChildItem -Path $Path -Attributes !ReparsePoint -Directory | foreach {
        Get-ChildItemNoReparsePoint $_.Fullname
    }
    Get-ChildItem -File $Path
}

A more full example is shown below:

We hook into the powershell help system by adding specially formatted comment.

By adding the [CmdletBinding()] attribute, we get access to the powershell common parameters (Get-Help about_Common_Parameters).

By adding the OutputType attribute, you get tab completion after the command in the pipeline. (try 'Get-ChildItemNoReparsePoint| Foreach <tab>')

The Parameter attribute enables usage of the function in a pipeline (together with the PSPath alias).

function Get-ChildItemNoReparsePoint
{
<#
.SYNOPSIS
    Gets all files of a directory recursivly, excluding reparse points
.OUTPUTS
    System.IO.FileInfo
.EXAMPLE
dir | Get-ChildItemNoReparsePoint
.EXAMPLE
Get-ChildItemNoReparsePoint ~/Documents | Foreach FullName | Set-Content thefiles.txt
.EXAMPLE
Get-ChildItemNoReparsePoint ~/Documents -OutVariable files | Foreach FullName | Set-Content thefiles.txt
$files | Group-Object Extension
#>
[CmdletBinding()]
[OutputType([System.IO.FileInfo])]
param(
    [Parameter(ValueFromPipelineByPropertyName)]
    [Alias('PSPath')]
    # Specifies a path to one or more locations.
    [string[]]$Path=$pwd
)
process
{
    Get-ChildItem -Path $Path -Attributes !ReparsePoint -Directory | Get-ChildItemNoReparsePoint
    Get-ChildItem -File $Path
}

Set-Content can be used instead of Out-File to bypass PowerShell's formatting step.

Get-NonReparsePointDirectoryFiles | foreach FullName | Set-Content -PassThru thefiles.txt


Get a collection of child positions for a given parent position I am trying to get a complete tree in a single loop using an iterative function. For instance, this is what I have:

var someVariable = GetAllChildPositions(posId) //Method called from a console method.

public ICollection<Position> GetAllChildPositions(int posId)
{
    ICollection<Position> posCollection = new Collection<Position>();
    posCollection= GetChildPos(posId,posCollection);
    return posCollection;
}

public ICollection<Position> GetChildPos(int posId, ICollection<Position> posCollection)
{
    var posObject= serviceRepo.Position.GetById(posId);
    posCollection.Add(posObject);
    if (serviceRepo.Position.GetAll().Where(x => x.ParentPosId == posId).Any())
    {
        var childPositions = serviceRepo.Position().GetAll().Where(x => x.ParentPosId == posId);
        foreach (var childPos in childPositions )
        {
            GetChildRows(childPos.Id, posCollection);
        }
    }
    return posCollection;
}

I am trying to get a list/collection child positions for a given parent position Id. This method works quite well and gets the job done albeit a little slowly. I am interested in knowing if there is a better way of doing this.

If Position and Position() in your code is the same and you supposed to call GetChildPos instead of GetChildRows in the inner loop then your code can be significantly simplified:

var someVariable = GetChildPos(posId).ToList();

public IEnumerable<Position> GetChildPos(int posId)
{
    yield return serviceRepo.Position.GetById(posId);

    foreach (var pos in serviceRepo.Position().GetAll()
                                              .Where(x => x.ParentPosId == posId)
                                              .SelectMany(x => GetChildPos(x.Id)))
    {
        yield return pos;
    }
}

Also it can improve performance because in your original code you do this instructions

serviceRepo.Position().GetAll().Where(x => x.ParentPosId == posId)

two times that can cause slowing down if some method in this chain is not lazy and executes heavy code even for Any().


Notify user of credential failure and make another attempt The below code works because of the do operator on line 24. Is there a more functional way to get the test to pass, or would you consider this an appropriate use of do?

import RxSwift

struct Token: Equatable {
    let rawValue: String
    static func ==(lhs: Token, rhs: Token) -> Bool {
        return lhs.rawValue == rhs.rawValue
    }
}

protocol Login {
    func getCredentials() -> Observable<(email: String, password: String)>
    func presentAuthFailure(_ error: Observable<Error>)
}

protocol Network {
    func getAuthToken(credentials: (email: String, password: String)) -> Observable<Token>
}

// MARK: - function Under Test
func checkCredentials(login: Login, network: Network) -> Observable<Token> {
    let credentials = login.getCredentials()
    let token = credentials.flatMap { network.getAuthToken(credentials: $0) }
        .do(onError: { login.presentAuthFailure(Observable.just($0)) }) // can this be done in some other way?
    return token.retry()
}

// MARK: - Test harness
class MockLogin: Login {
    func getCredentials() -> Observable<(email: String, password: String)> {
        assert(_credentials == nil)
        _credentials = PublishSubject()
        return _credentials!
    }

    func presentAuthFailure(_ error: Observable<Error>) {
        _ = error.subscribe(onNext: { [unowned self] error in
            assert(self._error == nil)
            self._error = error
        })
    }

    var _credentials: PublishSubject<(email: String, password: String)>?
    var _error: Error?
}

class MockNetwork: Network {
    func getAuthToken(credentials: (email: String, password: String)) -> Observable<Token> {
        assert(_token == nil)
        _token = PublishSubject()
        return _token!
    }

    var _token: PublishSubject<Token>?
}

func testTwoBadAttempts(login: MockLogin, network: MockNetwork) {
    checkCredentials(login: login, network: network).subscribe()

    assert(login._credentials != nil)

    let credentials = (email: "foo", password: "bar")
    login._credentials?.onNext(credentials)

    assert(network._token != nil)

    let error = NSError(domain: "testing", code: -1, userInfo: nil)
    network._token?.onError(error)

    assert(login._error != nil)

    network._token = nil
    login._error = nil

    login._credentials?.onNext(credentials)

    network._token?.onError(error)

    assert(login._error != nil)
}

let login = MockLogin()
let network = MockNetwork()
testTwoBadAttempts(login: login, network: network)

I found the solution to removing the do. I needed to move the error presentation into the flatMap and use materialize so that a network error wouldn't break the observable chain.

// MARK: - function Under Test
func checkCredentials(login: Login, network: Network) -> Observable<Token> {
    let credentials = login.getCredentials()
    let token = credentials.flatMap { (credential) -> Observable<Token> in
        let token = network.getAuthToken(credentials: credential)
            .materialize()
        let error = token.map { $0.error }.filter { $0 != nil }.map { $0! }
        login.presentAuthFailure(error)
        return token.map { $0.element }.filter { $0 != nil }.map { $0! }
    }
    return token
}