from __future__ import division


def list_of_chars(chars):
    if chars is None:
        return None
    size = len(chars)
    for i in range(size//2):
        chars[i], chars[size-1-i] = \
            chars[size-1-i], chars[i]
    return chars

"""
Explanation: <small><i>This notebook was prepared by Donne Martin. Source and license info is on GitHub.</i></small>
Solution Notebook
Problem: Implement a function to reverse a string (a list of characters), in-place.

Constraints
Test Cases
Algorithm
Code
Pythonic-Code
Unit Test
Bonus C Algorithm
Bonus C Code

Constraints

Can I assume the string is ASCII?
Yes
Note: Unicode strings could require special handling depending on your language


Since we need to do this in-place, it seems we cannot use the slice operator or the reversed function?
Correct


Since Python string are immutable, can I use a list of characters instead?
Yes



Test Cases

None -> None
[''] -> ['']
['f', 'o', 'o', ' ', 'b', 'a', 'r'] -> ['r', 'a', 'b', ' ', 'o', 'o', 'f']

Algorithm
Since Python strings are immutable, we'll use a list of chars instead to exercise in-place string manipulation as you would get with a C string.

Iterate len(string)/2 times, starting with i = 0:
Swap i and len(string) - 1 - i
Increment i



Complexity:
* Time: O(n)
* Space: O(1)
Note:
* You could use a byte array instead of a list to do in-place string operations
Code
End of explanation
"""


def reverse_string_alt(string):
    if string is None:
        return None
    return string[::-1]


def reverse_string_alt2(string):
    if string is None:
        return None
    return ''.join(reversed(string))

"""
Explanation: Pythonic-Code
This question has an artificial constraint that prevented the use of the slice operator and the reversed method.  For completeness, the solutions for these are provided below.  Note these solutions are not in-place.
End of explanation
"""


%%writefile test_reverse_string.py
from nose.tools import assert_equal


class TestReverse(object):

    def test_reverse(self):
        assert_equal(list_of_chars(None), None)
        assert_equal(list_of_chars(['']), [''])
        assert_equal(list_of_chars(
            ['f', 'o', 'o', ' ', 'b', 'a', 'r']),
            ['r', 'a', 'b', ' ', 'o', 'o', 'f'])
        print('Success: test_reverse')


def main():
    test = TestReverse()
    test.test_reverse()


if __name__ == '__main__':
    main()

%run -i test_reverse_string.py

"""
Explanation: Unit Test
End of explanation
"""


# %load reverse_string.cpp
#include <stdio.h>

void Reverse(char* str) {
    if (str) {
        char* i = str;	// first letter
        char* j = str;	// last letter
        
        // find the end of the string
        while (*j) {
            j++;
        }
        
        // don't point to the null terminator
        j--;
        
        char tmp;
        
        // swap chars to reverse the string
        while (i < j) {
            tmp = *i;
            *i++ = *j;
            *j-- = tmp;
        }
    }
}

int main() {
    char test0[] = "";
    char test1[] = "foo";
    Reverse(NULL);
    Reverse(test0);
    Reverse(test1);
    printf("%s \n", test0);
    printf("%s \n", test1);
    return 0;
}

"""
Explanation: C Algorithm
This is a classic problem in C/C++
We'll want to keep two pointers:
* i is a pointer to the first char
* j is a pointer to the last char
To get a pointer to the last char, we need to loop through all characters, take note of null terminator.

while i < j
swap i and j



Complexity:
* Time: O(n)
* Space: In-place
Note:
* Instead of using i, you can use str instead, although this might not be as intuitive.
C Code
End of explanation
"""


