import java.util.ArrayList;

/**
 * Java約瑟夫問題： n個人（不同id）圍成一個圈，從startId(任意數)個開始報數m(任意數)個數，數m的人出列排成新隊列，m清零，
 * 然后又從下一個人開始數m個數開始，數到m就出列接在新隊列尾部，如此重復，知道所有人都出列為止。
 * 打印 出列后的新隊列
 *
 * eg
 * int n = 10;//總人數
 * int m = 3;   //報數個數
 * int startIndex = 1;  //起點位置
 * @author Hulk   2014  03 20
 *
 */
public class JosephListTest {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        JosephListTest test = new JosephListTest();
        int n = 10; //總人數
        int m = 3; //報數個數
        int startIndex = 12; //起點位置
        System.out.println("JosephListTest: n= " + n + ", m= " + m +
            ", startIndex= " + startIndex + "/n/nQUEUE RESULT:");

        ArrayList<Person> queueList = test.queuePreson(n, m, startIndex);

        for (Person person : queueList) {
            System.out.println("OUT person: " + person);
        }

        System.out.println("use time= " +
            (System.currentTimeMillis() - startTime));
    }

    private ArrayList<Person> queuePreson(int n, int m, int startIndex) {
        ArrayList<Person> queueList = null;
        PersonList list = createList(n);

        //list.search();
        if ((list != null) && (list.head != null)) {
            queueList = new ArrayList<JosephListTest.Person>();

            PNode pNode = list.head;

            if (startIndex > 0) {
                startIndex = startIndex % n;
                pNode = list.getNode(startIndex);
            } else {
                pNode = list.head;
            }

            int count = 1;

            while (list.size > 0) {
                Person outPerson = null;

                //find
                if (count == (m - 1)) {
                    //delete next node
                    Person prev = pNode.person;
                    outPerson = list.remove(prev);
                    queueList.add(outPerson);
                    //System.out.println("OUT person: " + outPerson + ", size= " + list.size);
                    count = 0;
                }

                pNode = pNode.next;
                count++;
            }
        }

        return queueList;
    }

    private PersonList createList(int n) {
        PersonList list = new PersonList();

        for (int i = 0; i < n; i++) {
            Person person = new Person(i, "name_" + (i + 1));
            list.add(i, person);
        }

        return list;
    }

    public class PersonList {
        PNode head = null;
        int size = 0;

        public PersonList() {
        }

        public PersonList(Person person) {
            head = new PNode(person, head);
            size++;
        }

        public PersonList(PNode head) {
            this.head = head;
            head.setNext(head);
            size++;
        }

        public PNode getHead() {
            return head;
        }

        public void setHead(PNode head) {
            this.head = head;
        }

        public int getSize() {
            return size;
        }

        public void setSize(int size) {
            this.size = size;
        }

        public void size(int size) {
            this.size = size;
        }

        public boolean isEmpty() {
            return this.size <= 0;
        }

        public void initHead(Person person) {
            if (size == 0) {
                head = new PNode(person, head);
            } else {
                PNode no = head;
                head = new PNode(person, no);
            }

            size++;
        }

        public void add(int index, Person person) {
            if (size == 0) {
                head = new PNode(person, head);
                head.setNext(head);

                //System.out.println("head: " + head);
            } else {
                if (index < 0) {
                    index = 0;
                }

                if (index > size) {
                    index = size;
                }

                PNode no = head;

                for (int i = 0; i < (index - 1); i++) {
                    no = no.next;
                }

                PNode newNode = new PNode(person, no.next);
                no.next = newNode;
            }

            size++;
        }

        public Person delete(int index) {
            PNode pNode = remove(index);

            if ((pNode != null) && (pNode.next != null)) {
                return pNode.next.person;
            }

            return null;
        }

        public PNode remove(int index) {
            if (size == 0) {
                return null;
            } else {
                if ((index < 0) || (index >= size)) {
                    return null;
                }
            }

            PNode no = head;

            for (int i = 0; i < (index - 1); i++) {
                no = no.next;
            }

            no.next = no.next.next;
            size--;

            if ((no != null) && (no.next != null)) {
                return no.next;
            }

            return null;
        }

        /**
        * remove next node of person node, and return the deleted person
        * @param prePerson
        * @return  removed Person
        */
        public Person remove(Person prePerson) {
            if (prePerson == null) {
                return null;
            }

            if (size == 0) {
                return null;
            }

            PNode preNode = head;
            int index = -1;

            for (int i = 0; i < size; i++) {
                if (preNode.person.id == prePerson.id) {
                    index = i;

                    break;
                } else {
                    preNode = preNode.next;
                }
            }

            Person remPerson = null;

            if (size <= 1) {
                //only one node, get its person and set it as null
                remPerson = preNode.person;
                preNode = null;
            } else {
                //preNode.next.person is dest one
                remPerson = preNode.next.person;
                preNode.next = preNode.next.next;
            }

            size--;

            //System.out.println("deleteing index= " + index + " :  " + remPerson + ", size= " + size);
            return remPerson;
        }

        public int update(Person src, Person dest) {
            if (src == null) {
                return -1;
            }

            int index = -1;
            PNode no = head;

            for (int i = 0; i < size; i++) {
                if (src.id == no.person.id) {
                    no.person = dest;

                    break;
                } else {
                    no = no.next;
                }
            }

            return index;
        }

        public boolean set(int index, Person person) {
            if (person == null) {
                return false;
            }

            if (size == 0) {
                return false;
            } else {
                if ((index < 0) || (index >= size)) {
                    return false;
                }
            }

            PNode no = head;

            for (int i = 0; i < index; i++) {
                no = no.next;
            }

            no.person = person;

            return true;
        }

        public Person get(int index) {
            PNode no = getNode(index);

            if (no != null) {
                return no.person;
            }

            return null;
        }

        public PNode getNode(int index) {
            if (size == 0) {
                return null;
            } else {
                if ((index < 0) || (index >= size)) {
                    return null;
                }
            }

            PNode no = head;

            for (int i = 0; i < index; i++) {
                no = no.next;
            }

            return no;
        }

        public void search() {
            int sizeLong = size;
            PNode no = head;

            for (int i = 0; i < sizeLong; i++) {
                System.out.println("search index= " + i + ",   " + no);
                no = no.next;
            }
        }
    }

    public class PNode {
        Person person;
        PNode next = null;

        public PNode() {
        }

        public PNode(Person person) {
            this.person = person;
        }

        public PNode(Person person, PNode next) {
            this.person = person;
            this.next = next;
        }

        @Override
        public String toString() {
            return "PNode [person=" + person.id + ", next=" + next.person.id +
            "]";
        }

        public Person getPerson() {
            return person;
        }

        public void setPerson(Person person) {
            this.person = person;
        }

        public PNode getNext() {
            return next;
        }

        public void setNext(PNode next) {
            this.next = next;
        }
    }

    public class Person {
        int id = 0;
        String name = "";

        public Person() {
        }

        public Person(int id, String name) {
            super();
            this.id = id;
            this.name = name;
        }

        @Override
        public String toString() {
            return "Person [id=" + id + ", name=" + name + "]";
        }
    }
}