high efficiency vector using right value reference and std::move

#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
class Element {
private:
    int number;
public:
    Element() : number(0) {
        cout << "ctor" << endl;
    }
    Element(int num) : number(num) {
        cout << "ctor" << endl;
    }
    Element(const Element& e) : number(e.number) {
        cout << "copy ctor" << endl;
    }
    Element(Element&& e) : number(e.number) {
        cout << "right value ctor" << endl;
    }
    ~Element() {
        cout << "dtor" << endl;
    }
    void operator=(const Element& item) {
        number = item.number;
    }
    bool operator==(const Element& item) {
        return (number == item.number);
    }
    void operator()() {
        cout << number;
    }
    int GetNumber() {
        return number;
    }
};

template<typename T>
class Vector {
private:
    T* items;
    int count;
public:
    Vector() : count{ 0 }, items{ nullptr } {

    }
    Vector(const Vector& vector) : count{vector.count} {
        items = static_cast<T*>(malloc(sizeof(T) * count));
        memcpy(items, vector.items, sizeof(T) * count);
    }
    Vector(Vector&& vector) :count{ vector.count }, items{ vector.items } {
        vector.items = nullptr;
        vector.count = 0;
    }
    ~Vector() {
    }
    T& operator[](int index){
        if (index<0||index>=count) {
            cout<<"invalid index"<<endl;
            return items[0];
        }
        return items[index];
    }
    int returnCount(){
        return count;
    }
    void Clear() {
        for (int i = 0; i < count; i++)
        {
            items[i].~T();
        }
        count = 0;
        items = nullptr;
    }

    void Add(const T& item) {
        T* newItems = static_cast<T*>(malloc(sizeof(T) * (count + 1)));
        int i;
        for (i = 0; i < count; i++)
        {
            new(&newItems[i])T(move(items[i]));
        }
        new(&newItems[count])T(move(item));
        for (int i = 0; i < count; i++)
        {
            items[i].~T();
        }
        count++;
        items = newItems;
    }
    bool Insert(const T& item,int index) {
        if (index < 0 || index >= count)
        {
            return false;
        }
        T* newItems = static_cast<T*>(malloc(sizeof(T) * (count + 1)));
        int i;
        for (i = 0; i < index; i++)
        {
            new(&newItems[i])T(move(items[i]));
        }
        new(&newItems[index])T(move(item));
        for (i = index; i < count; i++)
        {
            new(&newItems[i+1])T(move(items[i]));
        }
        for (i = 0; i < count; i++)
        {
            items[i].~T();
        }
        count++;
        items = newItems;
        return true;
    }
    bool Remove(int index) {
        if (index < 0 || index >= count)
        {
            return false;
        }
        T* newItems = static_cast<T*>(malloc(sizeof(T) * (count - 1)));
        int i;
        for (i = 0; i < index; i++)
        {
            new(&newItems[i])T(move(items[i]));
        }
        for (i = index + 1; i < count; i++)
        {
            new(&newItems[i-1])T(move(items[i]));
        }
        for (i = 0; i < count; i++)
        {
            items[i].~T();
        }
        count--;
        items = newItems;
        return true;
    }
    int Contains(const T& item) {
        for (int i = 0; i < count; i++)
        {
            if (items[i] == item)
            {
                return i;
            }
        }
        return -1;
    }
};

template<typename T>
void PrintVector(Vector<T>& v) {
    int count = v.returnCount();
    for (int i = 0; i < count; i++)
    {
        v[i]();
        cout << " ";
    }
    cout << endl;
}

int main() {
    Vector<Element> v;
    for (int i = 0; i < 4; i++) {
        Element e(i);
        v.Add(e);
    }
    PrintVector(v);
    Element e2(4);
    if (!v.Insert(e2, 10))
    {
        v.Insert(e2, 2);
    }
    PrintVector(v);
    if (!v.Remove(10))
    {
        v.Remove(2);
    }
    PrintVector(v);
    Element e3(1), e4(10);
    cout << v.Contains(e3) << endl;
    cout << v.Contains(e4) << endl;
    Vector<Element> v2(v);
    Vector<Element> v3(move(v2));
    PrintVector(v3);
    v2.Add(e3);
    PrintVector(v2);
    return 0;
}

output:

ctor
copy ctor
dtor
ctor
right value ctor
copy ctor
dtor
dtor
ctor
right value ctor
right value ctor
copy ctor
dtor
dtor
dtor
ctor
right value ctor
right value ctor
right value ctor
copy ctor
dtor
dtor
dtor
dtor
0 1 2 3 
ctor
right value ctor
right value ctor
copy ctor
right value ctor
right value ctor
dtor
dtor
dtor
dtor
0 1 4 2 3 
right value ctor
right value ctor
right value ctor
right value ctor
dtor
dtor
dtor
dtor
dtor
0 1 2 3 
ctor
ctor
1
-1
0 1 2 3 
copy ctor
1 
dtor
dtor
dtor

My Projects

I’ve decided to make a summary of my past projects here. I have spent most of my free time on iOS development, and also explored some web development using PHP and JavaScript. In the past summer I used JavaScript to work on an educational software for a CS professor here at Duke.

I’ve ordered them according to my personal preference:)

  1. DukeCSA

DukeCSA (on GitHub) is the iOS app started by Jay Wang (currently a senior at Duke) to fit the needs of Duke Chinese Student Association. I joined the team around Christmas 2015. It combined many useful functionalities:

  • events post – users can view upcoming and past events hosted by DukeCSA. They can sign up or comment on the events in the app.
  • Q&A – students can ask their peers about life at Duke. This section is like Quora for Duke.
  • Class Database – users can view a massive (1000+) collection of comments on courses offered here at Duke to help them make choices.
  • Crush – users can express their secret admiration to others. If there is a match, both users will get notifications.
  • Web event poster – a web interface for the CSA committee to post a new event. The event will then be saved to our database and all users will be notified. The user does not need to write any code.

short demos:
notification indication

web interface

Read more about iOS projects

 

2. JFLAP web

JFLAP (Java Formal Language and Automata Package) is an educational software about finite state machines, Moore and Mealy machines, Turing machines etc. I worked on building the online version of JFLAP and integrating JFLAP into OpenDSA (Data Structures and Algorithms) project.

The job included designing and implementing the user interface, optimizing and implementing the algorithms and migrating Java version to JavaScript. I learned about formal languages and automata as well as software development.

short demo:

more about JFLAPmore about OpenDSAdevelopment blog, web demo

 

3. 3D iOS games

I also learned about 3D iOS game development. Below are demo videos of them:

Marble Maze – gravity-controlled

Breakout

 

4. Tank Battle

This is a homework project in my software development class, but I treat it more than that. The game features elements such as stone, brick, grass and water. The player needs to protect the base and eliminate enemies. The game also uses permanent storage to present a leader board.

demo:


The design comes from the classic video game battle city.

 

5. Blog Post System

A blog post system written mainly with PHP. Responsive to both desktop and mobile devices. Users are able to view all posts without logging in and post articles or comments when logged in. Data is stored in MYSQL database. APIs are also built for possible iOS app development in the future.

demo: http://billyu.com (It’ll probably be more fun if you could read Chinese)

 

6. Wheeshare

(my first iOS app!). This is an iOS app that promotes sharing among Duke students. I completed this project with grant from Duke CoLab, my current employer.
On the platform, students are able to post their belongings to lend, or to browse through the available items and request to borrow with one click. Students can also easily manage their posts.

 

LeetCode 20. Valid Parentheses

Problem:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Solution:

public class Solution {
    public boolean isValid(String s) {        
        
        Stack<Character> stack = new Stack<>();
        
        for (int i =0; i<s.length(); i++){
            if (s.charAt(i) == ')' && (stack.isEmpty() || stack.pop() != '(')) return false;
            if (s.charAt(i) == '}' && (stack.isEmpty() || stack.pop() != '{')) return false;
            if (s.charAt(i) == ']' && (stack.isEmpty() || stack.pop() != '[')) return false;
            if (s.charAt(i) == '{' || s.charAt(i) == '(' || s.charAt(i) == '[') stack.push(s.charAt(i));
        }
        return stack.isEmpty();
    }
}

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

Problem:

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int[] preorder, inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        int n = preorder.length;
        return buildTree(0, n - 1, 0, n - 1);
    }
    
    private TreeNode buildTree(int pre1, int pre2, int in1, int in2) {
        if (pre2 < pre1) return null;
        if (pre2 == pre1) return new TreeNode(preorder[pre1]);
        TreeNode root = new TreeNode(preorder[pre1]);
        int pos = 0;
        for (int i = in1; i <= in2; i++) {
            if (inorder[i] == root.val) {
                pos = i;
                break;
            }
        }
        root.left = buildTree(pre1 + 1, pre1 + pos - in1, in1, pos - 1);
        root.right = buildTree(pre1 + pos - in1 + 1, pre2, pos + 1, in2);
        return root;
    }
}

LeetCode 150. Evaluate Reverse Polish Notation

Problem:

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution:

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<String> nums = new Stack<>();
        Stack<String> ops = new Stack<>();
        for (String token: tokens) {
            if (isOp(token)) {
                if (nums.isEmpty()) {
                    ops.push(token);
                }
                else {
                    String num1 = nums.pop();
                    String num2 = nums.pop();
                    int a = Integer.parseInt(num1);
                    int b = Integer.parseInt(num2);
                    if (token.equals("+")) {
                        nums.push(a + b + "");
                    }
                    else if (token.equals("-")) {
                        nums.push(b - a + "");
                    }
                    else if (token.equals("*")) {
                        nums.push(b * a + "");
                    }
                    else {
                        nums.push(b / a + "");
                    }
                }
            }
            else {
                nums.push(token);
            }
        }
        String last = nums.pop();
        return Integer.parseInt(last);
    }
    
    private boolean isOp(String s) {
        String ops = "+-*/";
        return ops.indexOf(s) > -1;
    }
}

LeetCode 127. Word Ladder

Problem:

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWordto endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution:

Today I knew that building an adjacency map is a stupid, stupid solution when you have way more elements than path.

public class Solution {
    
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        wordList.add(endWord);
        Queue<String> current = new LinkedList<String>();
        int step = 1;
        current.offer(beginWord);
        while (!current.isEmpty()) {
            int size = current.size();
            while (size > 0) {
                String word = current.poll();
                if (word.equals(endWord))
                    return step;
                for (int i = 0; i < word.length(); i++) {
                    char[] arr = word.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        arr[i] = c;
                        String check = new String(arr);
                        if (!check.equals(word) && wordList.contains(check)) {
                            current.offer(check);
                            wordList.remove(check);
                        }
                    }
                }
                size--;
            }
            step++;
        }
        return 0;
    }
}

LeetCode 25. Reverse Nodes in k-Group

Problem:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int count = countNodes(head);
        int num = count - count % k;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        int done = 0;
        while(done < num) {
            ListNode run = current;
            for (int i = 0; i <= k; i++)
                run = run.next;
            current.next = reverseK(current.next, k);
            for (int i = 0; i < k; i++)
                current = current.next;
            current.next = run;
            done += k;
        }
        return dummy.next;
    }
    
    private int countNodes(ListNode head) {
        int count = 0;
        ListNode current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }
    
    private ListNode reverseK(ListNode current, int k) {
        if (k == 1) {
            return current;
        }
        ListNode tail = current.next;
        ListNode head = reverseK(current.next, k - 1);
        tail.next = current;
        return head;
    }
}

LeetCode 77. Combinations

Problem:

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution:

Backtracking

public class Solution {
    List<List<Integer>> all;
    public List<List<Integer>> combine(int n, int k) {
        all = new ArrayList<List<Integer>>();
        List<Integer> option = new ArrayList<Integer>();
        choose(1, n, k, option);
        return all;
    }
    
    private void choose(int start, int n, int k, List<Integer> option) {
        if (k == 0) {
            List<Integer> copy = new ArrayList<Integer>(option);
            all.add(copy);
            return;
        }
        for (int i = start; i <= n - k + 1; i++) {
            option.add(i);
            choose(i+1, n, k-1, option);
            option.remove(option.size() - 1);
        }
    }
}

LeetCode 31. Next Permutation

Problem:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1

Solution:

public class Solution {
    public void nextPermutation(int[] nums) {
        int i = 0;
        for (; i < nums.length - 1; i++) {
            if (nums[i] < nums[i+1]) break;
        }
        if (i == nums.length - 1) {
            Arrays.sort(nums);
            return;
        }
        for (i = nums.length - 1; i > 0; i--) {
            if (nums[i-1] < nums[i]) break;
        }
        int pivot = i - 1;
        for (i = nums.length - 1; i > 0; i--)
            if (nums[i] > nums[pivot]) break;
        swap(nums, pivot, i);
        reverse(nums, pivot + 1, nums.length - 1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    private void reverse(int[] nums, int i, int j) {
        for (int k = i; k <= (i + j)/2; k++) {
            swap(nums, k, j + i - k);
        }
    }
}

LeetCode 148. Sort List

Problem:

Sort a linked list in O(n log n) time using constant space complexity.

Solution:

Three way quick sort

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        head = quicksort(head);
        return head;
    }
    
    private ListNode quicksort(ListNode pivot) {
        if (pivot == null || pivot.next == null)
            return pivot;
        ListNode prev1 = new ListNode(0), prev2 = new ListNode(0), prev = new ListNode(0);
        ListNode dummy1 = prev1, dummy2 = prev2, dummy = prev;
        ListNode current = pivot;
        while (current != null) {
            if (current.val < pivot.val) {
                prev1.next = current;
                prev1 = prev1.next;
            }
            else if (current.val > pivot.val) {
                prev2.next = current;
                prev2 = prev2.next;
            }
            else {
                prev.next = current;
                prev = prev.next;
            }
            current = current.next;
        }
        prev1.next = prev2.next = prev.next = null;
        dummy1.next = quicksort(dummy1.next);
        dummy2.next = quicksort(dummy2.next);
        current = dummy1;
        while (current.next != null) current = current.next;
        current.next = dummy.next;
        prev.next = dummy2.next;
        return dummy1.next;
    }
}