func main() {
	l1, l2 := list.New(), list.New()

	l1_e1, l1_e2, l1_e3 := l1.PushBack(1), l1.PushBack(2), l1.PushBack(3)
	l2_e1, l2_e2, l2_e3 := l2.PushBack(1), l2.PushBack(2), l2.PushBack(3)

	fmt.Println("List 1")
	PrintList(l1)
	fmt.Printf("%d, %d, %d\n", l1_e1.Value, l1_e2.Value, l1_e3.Value)
	fmt.Println("List 2")
	PrintList(l2)
	fmt.Printf("%d, %d, %d\n", l2_e1.Value, l2_e2.Value, l2_e3.Value)

	// 从l1中删除l2_e2
	fmt.Println("Delete l2_e2 from l1")
	l1.Remove(l2_e2)
	fmt.Println("List 1")
	PrintList(l1)
	fmt.Println("List 2")
	PrintList(l2)

	// 在l2的l2_e2前插入一个值8，这个不会成功
	fmt.Println("Insert value 8 before l2_e2")
	l2.InsertBefore(8, l2_e2)
	fmt.Println("List 1")
	PrintList(l1)
	fmt.Println("List 2")
	PrintList(l2)
}

func NewTcpServer(addr string) *TcpServer {
	if len(addr) <= 0 {
		return &TcpServer{haddr: "0.0.0.0:9891", exitChan: make(chan int), clientlist: list.New()}
	} else {
		return &TcpServer{haddr: addr, exitChan: make(chan int), clientlist: list.New()}
	}
}

func main() {
	in := bufio.NewReader(os.Stdin)
	tags := make(map[string]*list.List)
	taglist := list.New()
	line, err := in.ReadSlice('\n')
	for err == nil {
		fields := strings.Fields(string(line))
		if len(fields) > 2 && fields[0] == "commit" {
			hash, tag := fields[1], fields[2]
			if tags[tag] == nil {
				tags[tag] = list.New()
				taglist.PushBack(tag)
			}
			tags[tag].PushBack(hash)
		}
		line, err = in.ReadSlice('\n')
	}

	i := 1
	for e := taglist.Front(); e != nil; e = e.Next() {
		k := e.Value.(string)
		v := tags[k]
		fmt.Printf("sh export-oldgit.sh %02d-%s ",
			i, k)
		for e := v.Front(); e != nil; e = e.Next() {
			fmt.Printf("%s ", e.Value.(string))
		}
		fmt.Println()
		i += 1
	}
}

func newConn(sock *net.UDPConn, peerIdentity, publicKey, privateKey []byte, domain string) *conn {
	if len(peerIdentity) != 32 || len(publicKey) != 32 || len(privateKey) != 32 {
		panic("wrong key size")
	}
	c := &conn{
		domain: domain,

		packetIn: make(chan packet),
		sock:     sock,

		readRequest:  make(chan []byte),
		writeRequest: make(chan []byte),
		ioResult:     make(chan opResult),

		toSend:   list.New(),
		sendFree: list.New(),

		received: ringbuf.New(recvBufferSize),
	}
	// Key setup.
	copy(c.peerIdentity[:], peerIdentity)
	var pub, priv [32]byte
	copy(pub[:], publicKey)
	copy(priv[:], privateKey)
	box.Precompute(&c.sharedKey, &pub, &priv)

	// Send blocks
	for i := 0; i < numSendBlocks; i++ {
		c.sendFree.PushBack(new(block))
	}

	go c.pump()
	return c
}

func (s *Surface) FindNeighborPixels(p Coord2D) (used, unUsed *list.List) {
	unUsed = list.New()
	used = list.New()
	if p.X > 0 {
		s.filterPixel(leftPixel(p), used, unUsed)
	}
	if p.X < s.Size-1 {
		s.filterPixel(rightPixel(p), used, unUsed)
	}
	if p.Y < s.Size-1 {
		s.filterPixel(upPixel(p), used, unUsed)
	}
	if p.Y > 0 {
		s.filterPixel(downPixel(p), used, unUsed)
	}
	if p.Y < s.Size-1 && p.X > 0 {
		s.filterPixel(upLeftPixel(p), used, unUsed)
	}
	if p.Y < s.Size-1 && p.X < s.Size-1 {
		s.filterPixel(upRightPixel(p), used, unUsed)
	}
	if p.Y > 0 && p.X > 0 {
		s.filterPixel(downLeftPixel(p), used, unUsed)
	}
	if p.Y > 0 && p.X < s.Size-1 {
		s.filterPixel(downRightPixel(p), used, unUsed)
	}
	return used, unUsed
}

// Helper functions
// set up all the structs needed for the program to run
func initialize() {
	fmt.Print("init")
	output += "init"

	// clear the global lists
	Ready_List.Init()
	Resource_List.Init()

	IO = &IO_RCB{list.New()}

	PIDs = make(map[string]*PCB)

	Init = &PCB{
		"init",
		list.New(),
		CT{nil, list.New()},
		Stat{"ready_s", Ready_List},
		0}
	Curr = Init
	PIDs["init"] = Init

	Ready_List.PushFront(list.New())
	Ready_List.PushFront(list.New())
	Ready_List.PushFront(list.New())

	listRLInsert(Init)

	Resource_List.PushFront(&RCB{"R1", "free", list.New()})
	Resource_List.PushFront(&RCB{"R2", "free", list.New()})
	Resource_List.PushFront(&RCB{"R3", "free", list.New()})
	Resource_List.PushFront(&RCB{"R4", "free", list.New()})

	fmt.Println(" ... done\nProcess init is running")
	output += " ... done\n\nProcess init is running\n"
}

func TestListToNodeSlice(t *testing.T) {
	//t.SkipNow()
	nodeA := search.GraphNode(NewWordNode("aardvark", 0))
	nodeB := search.GraphNode(NewWordNode("bonobo", 0))
	nodeC := search.GraphNode(NewWordNode("chipmunk", 0))
	cases := []struct {
		in   *list.List
		want []search.GraphNode
	}{
		{list.New(), []search.GraphNode{}},
		{list.New(), []search.GraphNode{nodeA, nodeB, nodeC}},
		//{list.New(), []search.GraphNode{nodeC, nodeB, nodeA},}, order matters
	}
	cases[1].in.PushBack(nodeA)
	cases[1].in.PushBack(nodeB)
	cases[1].in.PushBack(nodeC)
	// cases[2].in.PushBack(nodeA)
	// cases[2].in.PushBack(nodeB)
	// cases[2].in.PushBack(nodeC)
	for _, c := range cases {
		got := listToNodeSlice(c.in)
		if !reflect.DeepEqual(got, c.want) {
			t.Errorf("listToNodeSlice(%v), want=%v, got=%v", c.in, c.want, got)
		}
	}
}

func ParseSrtStream(source io.Reader) *list.List {
	reader := bufio.NewScanner(source)
	blocks := list.New()

	for {
		block_lines := list.New()

		for reader.Scan() {
			line := reader.Text()

			if line == "" {
				break
			}

			block_lines.PushBack(line)
		}

		if block_lines.Len() == 0 {
			break
		}

		srt_block := SrtBlockParse(ListToSlice(block_lines))
		blocks.PushBack(srt_block)
	}

	return blocks
}

// NewAroonWithoutStorage creates an Aroon (Aroon) without storage
func NewAroonWithoutStorage(timePeriod int, valueAvailableAction ValueAvailableActionAroon) (indicator *AroonWithoutStorage, err error) {

	// an indicator without storage MUST have a value available action
	if valueAvailableAction == nil {
		return nil, ErrValueAvailableActionIsNil
	}

	// the minimum timeperiod for an Aroon indicator is 2
	if timePeriod < 2 {
		return nil, errors.New("timePeriod is less than the minimum (2)")
	}

	// check the maximum timeperiod
	if timePeriod > MaximumLookbackPeriod {
		return nil, errors.New("timePeriod is greater than the maximum (100000)")
	}

	lookback := timePeriod
	ind := AroonWithoutStorage{
		baseIndicatorWithFloatBoundsAroon: newBaseIndicatorWithFloatBoundsAroon(lookback, valueAvailableAction),
		periodCounter:                     (timePeriod + 1) * -1,
		periodHighHistory:                 list.New(),
		periodLowHistory:                  list.New(),
		aroonFactor:                       100.0 / float64(timePeriod),
	}

	return &ind, nil
}

// NewServer creates, initiates, and returns a new server. This function should
// NOT block. Instead, it should spawn one or more goroutines (to handle things
// like accepting incoming client connections, triggering epoch events at
// fixed intervals, synchronizing events using a for-select loop like you saw in
// project 0, etc.) and immediately return. It should return a non-nil error if
// there was an error resolving or listening on the specified port number.
func NewServer(port int, params *Params) (Server, error) {
	s := &server{
		params:            params,
		requestc:          make(chan *request, 100),
		closeSignal:       make(chan struct{}),
		readBuffer:        make(map[int]*buffer),
		writeBuffer:       make(map[int]*buffer),
		unAckedMsgBuffer:  make(map[int]*buffer),
		latestAckBuffer:   make(map[int]*buffer),
		deferedRead:       list.New(),
		deferedClose:      list.New(),
		hostportConnIdMap: make(map[string]int),
		connIdHostportMap: make(map[int]*lspnet.UDPAddr),
		activeConn:        make(map[int]bool),
		expectedSeqNum:    make(map[int]int),
		seqNum:            make(map[int]int),
		latestActiveEpoch: make(map[int]int),
		currEpoch:         0,
		connId:            0,
		serverRunning:     true,
		connLostInClosing: false,
	}
	s.networkUtility = NewNetworkUtility(s.requestc)

	err := s.networkUtility.listen(":" + strconv.Itoa(port))
	if err != nil {
		return nil, err
	}

	go s.networkUtility.networkHandler()
	go s.eventHandler()
	go epochTimer(s.requestc, s.closeSignal, params.EpochMillis)

	return s, nil
}

// This function loops forever, handling the chat room pubsub
func chatroom() {
	archive := list.New()
	subscribers := list.New()

	for {
		select {
		case ch := <-subscribe:
			var events []Event
			for e := archive.Front(); e != nil; e = e.Next() {
				events = append(events, e.Value.(Event))
			}
			subscriber := make(chan Event, 10)
			subscribers.PushBack(subscriber)
			ch <- Subscription{events, subscriber}

		case event := <-publish:
			for ch := subscribers.Front(); ch != nil; ch = ch.Next() {
				ch.Value.(chan Event) <- event
			}

		case unsub := <-unsubscribe:
			for ch := subscribers.Front(); ch != nil; ch = ch.Next() {
				if ch.Value.(chan Event) == unsub {
					subscribers.Remove(ch)
					break
				}
			}
		}
	}
}

//////////////////////////////////////////////////////////////////////////////////////////////////
// Bot Initalization and Loading/Saving                                                        //
////////////////////////////////////////////////////////////////////////////////////////////////
func New() *TweetBot {
	return &TweetBot{
		commentSet:          mapset.NewSet(),
		potentialCommentSet: mapset.NewSet(),
		commentList:         list.New(),
		subRedditList:       list.New()}
}

func Manager(in chan ManagerRequest) {
	locations := map[string]Location{}
	waiters := list.New()
	for {
		req := <-in
		switch t := req.(type) {
		case *GetLocationsRequest:
			getLocReq := req.(*GetLocationsRequest)
			newLocations := map[string]Location{}
			CopyMap(locations, newLocations)
			getLocReq.out <- &newLocations
		case *UpdateLocationRequest:
			updateReq := req.(*UpdateLocationRequest)
			locations[updateReq.id] = *updateReq.location
			updateReq.out <- true
			newLocations := map[string]Location{}
			CopyMap(locations, newLocations)
			for e := waiters.Front(); e != nil; e = e.Next() {
				waiter := e.Value.(chan *map[string]Location)
				waiter <- &newLocations
			}
			waiters = list.New()
		case *WaitForUpdatesRequest:
			pollReq := req.(*WaitForUpdatesRequest)
			waiters.PushBack(pollReq.out)
		default:
			panic(fmt.Sprintf("Unknown request type %T", t))
		}
	}
}

// Returns all active values stored by the key. Also cleans expired
// Values. Values are considered expired if the current time is greater
// than or equal the value's end time.
func (s Store) Get(k Key) (activeValues *list.List, ok bool) {
	values, ok := s[k]

	if ok {
		activeValues = list.New()
		expiredValues := list.New()

		currentTime := CurrentTime()

		for element := values.Front(); element != nil; element = element.Next() {
			if value, ok := element.Value.(Value); ok {
				if value.IsActiveForTime(currentTime) {
					activeValues.PushBack(value.Data)
				} else if value.IsExpiredForTime(currentTime) {
					// Keep track of list elements to remove later. They cannot be removed
					// during iteration.
					expiredValues.PushBack(element)
				}
			}
		}

		// Go back and remove any elements that are expired. These can never become
		// active again so they are removed from storage
		for element := expiredValues.Front(); element != nil; element = element.Next() {
			expiredElement, ok := element.Value.(*list.Element)

			if ok {
				expiredValues.Remove(expiredElement)
			}
		}
	}

	return
}

func createBall1000(lball *ballon.All_ball, user *list.Element, base *db.Env) {
	lstmsg := createMessage1000()
	usr := user.Value.(*users.User)

	for i := 0; i < 1000; i++ {
		ball := new(ballon.Ball)

		ball.Id_ball = lball.Id_max
		lball.Id_max++
		ball.Edited = true
		ball.Title = "TEST" + strconv.Itoa(int(ball.Id_ball))
		ball.Messages = lstmsg
		ball.Coord = GetRandomCoord()
		ball.Itinerary = list.New()
		ball.Itinerary.PushBack(ball.Coord.Value.(*ballon.Checkpoint))
		ball.Followers = list.New()
		ball.Checkpoints = list.New()
		ball.Date = time.Now()
		ball.Possessed = nil
		ball.Followers = list.New()
		ball.Followers.PushFront(user)
		ball.Creator = user
		ball.Scoord = ball.Coord
		//	ball.InitCoord(ball.Coord.Value.(ballon.Checkpoint).Coord.Lon, ball.Coord.Value.(ballon.Checkpoint).Coord.Lat, int16(0), wd, true)
		eball := lball.Blist.PushBack(ball)
		usr.NbrBallSend++
		usr.Followed.PushBack(eball)
		lball.InsertBallon(ball, base)
	}

}

// AddRoom add a new room
func (c *Chat) AddRoom(name string, conf RoomConfig) (err error) {
	// room exists ?
	if c.RoomExists(name) {
		return errors.New("room " + name + " exists")
	}

	// Archive
	if conf.Archived {
		// check if bucket exist
		err = boltDB.Update(func(tx *bolt.Tx) error {
			_, err := tx.CreateBucketIfNotExists([]byte(name + "_arch"))
			return err
		})
		if err != nil {
			return err
		}
	}

	room := &Room{
		name:        name,
		subscribers: list.New(),
		archives:    list.New(),
		archiveLen:  conf.ArchivePushMessagesCount,
		heartrate:   conf.HeartRate,
	}

	if room.heartrate != 0 {
		room.Watch()
	}
	c.rooms[name] = room
	return nil
}

// This function loops forever, handling the chat room pubsub
func chatroom() {
	// subscribers := map[string]chan<-Event  // map user to channel
	archive := list.New()
	subscribers := list.New()

	for {
		select {
		case ch := <-subscribe:
			var events []Event
			for e := archive.Front(); e != nil; e = e.Next() {
				events = append(events, e.Value.(Event))
			}
			subscriber := make(chan Event)
			subscribers.PushBack(subscriber)
			ch <- Subscription{events, subscriber}

		case event := <-publish:
			for ch := subscribers.Front(); ch != nil; ch = ch.Next() {
				ch.Value.(chan Event) <- event
			}
			if archive.Len() >= archiveSize {
				archive.Remove(archive.Front())
			}
			archive.PushBack(event)

		case unsub := <-unsubscribe:
			for ch := subscribers.Front(); ch != nil; ch = ch.Next() {
				if ch.Value.(chan Event) == unsub {
					subscribers.Remove(ch)
				}
			}
		}
	}
}

// Lint reads the provided reader (with an optional associated path)
// and checks the markdown for basic errors. Any errors found are
// sent to the provided out channel
func Lint(reader *bufio.Reader, path string, out chan<- error) {
	brackets, parens := list.New(), list.New()
	line := 1
	column := 1
	enDashes := make(map[int]int)
	pos := int64(0)

	// Parse the file
	for {
		r, size, err := reader.ReadRune()
		pos += int64(size)

		if err != nil {
			if err != io.EOF {
				out <- fmt.Errorf("Error reading from %s - %s", path, err)
			}
			break
		}

		switch r {
		case '[':
			brackets.PushFront(syntaxError{line, column, pos})
		case ']':
			top := brackets.Front()
			if top == nil {
				basicError := fmt.Errorf(`Bad Markdown URL in %s:
	extra closing bracket at line %d, column %d`, path, line, column)
				out <- usefulError(path, pos, basicError)
			} else {
				brackets.Remove(top)
			}
		case '(':
			parens.PushFront(syntaxError{line, column, pos})
		case ')':
			top := parens.Front()
			if top == nil {
				basicError := fmt.Errorf(`Bad Markdown URL in %s:
	extra closing parenthesis at line %d, column %d`, path, line, column)
				out <- usefulError(path, pos, basicError)
			} else {
				parens.Remove(top)
			}
		case '–':
			enDashes[line]++
		case '\n':
			line++
			column = 0
		}

		column++
	}

	// Check the results and accumulate any problems
	checkHanging(brackets, "bracket", out, path)
	checkHanging(parens, "parenthesis", out, path)

	for line := range enDashes {
		out <- fmt.Errorf("literal en dash at %s:%d - please use -- instead", path, line)
	}
}

// the number of vars to test, their respective vals, and the number of bits needed to represent these vals; all these data are scattered in a hierarchical data structure (json)
// this function flattens these data into two lists for an easy, repetitive processing later
// the two returned lists should have the same length
// the length denotes the number of vars
// index i refers to var i (order established by the in order traversal of the json structure)
// list 1 stores for each var i its respective vals
// list 2 stores for each var i the number of bits needed to represent the number of vals
func Flatten(t Vars) (*list.List, *list.List) {
	if t == nil {
		return nil, nil
	}

	vals := list.New()
	numBits := list.New()

	for _, val := range t {
		if val.Vals == nil || len(val.Vals) == 0 {
			continue
		}

		switch val.Vals[0].(type) {
		case map[string]interface{}:
			sub_t := castInterfaceToVar(val.Vals)
			v, b := Flatten(sub_t)
			vals.PushBackList(v)
			numBits.PushBackList(b)
		default:
			vals.PushBack(val.Vals)
			v := uint(len(val.Vals))
			numBits.PushBack(bitutil.BitsPerVal(v))
		}
	}

	return vals, numBits
}

func (Svr *Solver) Solve_init(b *board.Board, Heur int) {
	Svr.nbrRow = b.Size
	fNode := new(Node)
	fNode.StateBoard = Get_StateBoard(Svr.nbrRow)
	fNode.relative = nil
	fNode.nbrMove = 0
	fNode.status = START
	Svr.openList = list.New()
	Svr.closeList = list.New()
	if Heur == MANHATTAN {
		Svr.Heuristic = manhattan_3.Get_manhattan_dis
	} else if Heur == MANHATTAN_CONFLICT {
		Svr.Heuristic = manhattan_3.Get_manhattan_dis_linear
	} else if Heur == MISSPLACEDTILES {
		Svr.Heuristic = missplacedtiles_3.Get_missplacedTiles
	} else {
		Svr.Heuristic = manhattan_3.Get_manhattan_dis
	}

	for i := 0; i < b.Size; i++ {
		for j := 0; j < b.Size; j++ {
			fNode.StateBoard[i][j] = b.Tiles[(i*b.Size)+j]
		}
	}
	Svr.openList.PushFront(fNode)
}