func (ls *libstore) deletelist() {
	now := time.Now()
	// ls.mutex.Lock()
	// // fmt.Println("deleteinvalid")
	// defer ls.mutex.Unlock()

	for key, list := range ls.keyValudhistory {
		ls.initiateKeyValueMutex(key)
		ls.keyValueMutex[key].Lock()
		for list.Len() > 0 {
			e := list.Front()
			if e.Value.(time.Time).Add(time.Duration(storagerpc.QueryCacheSeconds)*time.Second).After(now) && list.Len() <= storagerpc.QueryCacheThresh {
				break
			}
			list.Remove(list.Front())
		}
		ls.keyValueMutex[key].Unlock()
	}

	for key, list := range ls.keyListhistory {
		ls.initiateKeyListMutex(key)
		ls.keyListMutex[key].Lock()
		for list.Len() > 0 {
			e := list.Front()
			if e.Value.(time.Time).Add(time.Duration(storagerpc.QueryCacheSeconds)*time.Second).After(now) && list.Len() <= storagerpc.QueryCacheThresh {
				break
			}
			list.Remove(list.Front())
		}
		ls.keyListMutex[key].Unlock()
	}
}

func expandClass(regex []int) string {
	list := New()
	list.Init()
	nextEscape := false
	escaped := false
	var toDelete *Element
	for reg_index := 0; reg_index < len(regex); reg_index++ {
		escaped = nextEscape
		nextEscape = false
		switch regex[reg_index] {
		case '\\':
			if escaped {
				escaped = false
				list.PushBack(int('\\'))
				toDelete = nil
			} else {
				nextEscape = true
				toDelete = list.PushBack(int('\\'))
			}
			break
		case '-':
			if escaped {
				escaped = false
				list.PushBack(int('-'))
				toDelete.Value = Delete
			} else {
				if reg_index > 0 && reg_index < len(regex)-1 {
					start := regex[reg_index-1]
					end := uint8(regex[reg_index+1])
					for char := uint8(start + 1); char < end; char++ {
						list.PushBack(int(char))
					}
				} else {
					//ERROR
					fmt.Println("invalid character class")
				}
			}
			break
		default:
			list.PushBack(regex[reg_index])
			break
		}
	}
	for e := list.Front(); e != nil; e = e.Next() {
		if e.Value.(int) == Delete {
			list.Remove(e)
		}
	}
	out := string(list.Remove(list.Front()).(int))
	for e := list.Front(); e != nil; e = e.Next() {
		out += string('|')
		out += string(e.Value.(int))
	}
	return out
}

// Commit causes all requests that have been queued for the transaction
// to be sent to the request channel for processing. Calls the commit
// function (commitFunc) in order for each request that is part of the
// transaction.
func (txs *txStore) Commit(tx string, commitFunc func(f *frame.Frame) error) error {
	if list, ok := txs.transactions[tx]; ok {
		for element := list.Front(); element != nil; element = list.Front() {
			err := commitFunc(list.Remove(element).(*frame.Frame))
			if err != nil {
				return err
			}
		}
		delete(txs.transactions, tx)
		return nil
	}
	return txUnknown
}

func PrintDepartures(airport string, data *FlightData) {
	list := data.Departures[airport]
	for cursor := list.Front(); cursor != nil; cursor = cursor.Next() {
		f := cursor.Value.(Flight)
		fmt.Println(f.From, f.To, f.Cost)
	}
}

// Reads a list of ASN1Cert types from |r|
func readASN1CertList(r io.Reader, totalLenBytes int, elementLenBytes int) ([]ASN1Cert, error) {
	listBytes, err := readVarBytes(r, totalLenBytes)
	if err != nil {
		return []ASN1Cert{}, err
	}
	list := list.New()
	listReader := bytes.NewReader(listBytes)
	var entry []byte
	for err == nil {
		entry, err = readVarBytes(listReader, elementLenBytes)
		if err != nil {
			if err != io.EOF {
				return []ASN1Cert{}, err
			}
		} else {
			list.PushBack(entry)
		}
	}
	ret := make([]ASN1Cert, list.Len())
	i := 0
	for e := list.Front(); e != nil; e = e.Next() {
		ret[i] = e.Value.([]byte)
		i++
	}
	return ret, nil
}

// locate returns the node on which the item at the logical index should reside.
// If the index lands on a slice node, the offset is the physical index relative
// to the slice. If the index lands on a value node, then the offset is
// meaningless and set to 0.
func (s *GapSlice) locate(i int) (elem *list.Element, offset int) {
	if i < 0 || i >= s.size {
		return nil, 0
	}

	remaining := i
	list := s.list
	for e := list.Front(); e != nil; e = e.Next() {
		switch value := e.Value.(type) {
		case gapSliceChunk:
			if chunkSize := len(value); remaining < chunkSize {
				return e, remaining
			} else {
				remaining -= chunkSize
			}
		default:
			if remaining == 0 {
				return e, 0
			} else {
				remaining -= 1
			}
		}
	}

	panic(Errorf("could not find element for index %d in GapSlice", i))
}

func (ss *storageServer) GetList(args *storagerpc.GetArgs, reply *storagerpc.GetListReply) error {
	if !ss.isInServerRange(args.Key) {
		reply.Status = storagerpc.WrongServer
		return nil
	}

	//get the lock for current key
	ss.mutex.Lock()
	lock, exist := ss.lockMap[args.Key]
	if !exist {
		lock = new(sync.Mutex)
		ss.lockMap[args.Key] = lock
	}
	ss.mutex.Unlock()

	//Lock current key we are going to work on
	lock.Lock()

	//process lease request
	grantLease := false
	if args.WantLease {
		//add to lease map
		var libServerList *list.List
		libServerList, exist := ss.leaseMap[args.Key]
		if !exist {
			libServerList = new(list.List)
		}
		leaseRecord := LeaseRecord{args.HostPort, time.Now()}
		libServerList.PushBack(leaseRecord)
		ss.leaseMap[args.Key] = libServerList
		grantLease = true
	}
	reply.Lease = storagerpc.Lease{grantLease, storagerpc.LeaseSeconds}

	//retrieve list
	list, exist := ss.keyListMap[args.Key]
	if !exist {
		reply.Status = storagerpc.KeyNotFound
	} else {
		//convert list format from "map" to "[]string"
		listSize := list.Len()
		replyList := make([]string, listSize)

		i := 0
		for e := list.Front(); e != nil; e = e.Next() {
			val := (e.Value).(string)
			replyList[i] = val
			i = i + 1
		}

		reply.Value = replyList
		reply.Status = storagerpc.OK
	}

	lock.Unlock()
	return nil
}

func (stack *Stack) Top() []byte {
	list := (*list.List)(stack)
	el := list.Front()
	if el == nil {
		return nil
	}
	val, ok := el.Value.([]byte)
	if !ok {
		panic("Why is it not a byte array?")
	}
	return val
}

func (h *hashMap) Get(key Value) (Value, error) {
	index := h.getIndex(key)
	if h.data[index] == nil {
		return nil, fmt.Errorf("not found")
	}
	list := h.data[index]
	for e := list.Front(); e != nil; e = e.Next() {
		if i := e.Value.(*item); i.key.Get() == key.Get() {
			return i.value, nil
		}
	}
	return nil, fmt.Errorf("not found")
}

func IsBST(root *TreeNode) bool {
	list := list.New()
	createOrderedArray(root, list)

	prev := list.Front()
	for e := prev.Next(); e != nil; e = e.Next() {
		if prev.Value.(int) > e.Value.(int) {
			return false
		}
		prev = e
	}

	return true
}

func MatchAll(m *Matcher, text string) []Match {
	list := list.New()
	ch := m.Match(text)
	for n := range ch {
		list.PushBack(n)
	}
	all := make([]Match, list.Len())
	idx := 0
	for e := list.Front(); e != nil; e = e.Next() {
		all[idx] = e.Value.(Match)
		idx++
	}
	return all
}

// GoString formats this GapSlice as a space-separated list of nodes surrounded
// by parentheses. Value nodes are represented by the GoString format of the
// value itself, while slice nodes are presented as a space-separated list of
// values in GoString format surrounded by square brackets.
func (s *GapSlice) GoString() string {
	list := s.list
	b := bytes.NewBufferString("(")
	for e := list.Front(); e != nil; e = e.Next() {
		if chunk, isChunk := e.Value.(gapSliceChunk); isChunk {
			b.WriteString(fmt.Sprintf("%v", chunk))
		} else {
			b.WriteString(fmt.Sprintf("%#v", e.Value))
		}
		if e != list.Back() {
			b.WriteRune(' ')
		}
	}
	b.WriteRune(')')
	return b.String()
}

// Remove a service definition from the list. If a service has been removed,
// return true. Different connections cannot remove services they did not add.
func (l *serviceList) Remove(service *ServiceDef) bool {
	list := (*list.List)(l)
	for iter := list.Front(); iter != nil; iter = iter.Next() {
		e := iter.Value.(*ServiceDef)
		res := service.compare(e)
		if res > 0 {
			continue
		} else if res == 0 && e.connId == service.connId {
			list.Remove(iter)
			return true
		}
		// Did not find the service.
		break
	}
	return false
}

func daythirteen() {
	file, _ := os.Open("input-day13")
	list := list.New()
	scanner := bufio.NewScanner(file)
	for scanner.Scan() {
		text := scanner.Text()
		list.PushFront(text)
	}
	arr := make([]string, list.Len())
	count := 0
	for e := list.Front(); e != nil; e = e.Next() {
		arr[count] = e.Value.(string)
		count++
	}
	fmt.Printf("Best = %d\n", ProcSeatingArray(arr, 0))
	fmt.Printf("Best = %d\n", ProcSeatingArray(arr, 1))
}

func toArray(values interface{}) ([]interface{}, os.Error) {

	// vector to array
	if vector, ok := values.(*vector.Vector); ok {
		return toArray(*vector)
	}

	result := new(vector.Vector)

	// list to array
	if list, ok := values.(*list.List); ok {
		for e := list.Front(); e != nil; e = e.Next() {
			result.Push(e.Value)
		}
		return *result, nil
	}

	switch v := reflect.ValueOf(values); v.Kind() {

	// array to array (copy)
	case reflect.Array, reflect.Slice:
		arr := v
		for i := 0; i < arr.Len(); i++ {
			obj := arr.Index(i).Interface()
			result.Push(obj)
		}

	// channel to array
	case reflect.Chan:
		ch := v
		for {
			if x, ok := ch.Recv(); ok {
				obj := x.Interface()
				result.Push(obj)
			} else {
				break
			}
		}

	// unknown type
	default:
		return nil, Errorf("type error: expected a collection type, but was “%v” of type “%T”", values, values)
	}
	return *result, nil
}

// Walk iterates through this GapSlice, calling walkFn for each item visited by
// Walk.
//
// If walkFun returns an error, the iteration is immediately halted, and in turn,
// that error is returned by Walk.
func (s *GapSlice) Walk(walkFn GapSliceWalkFunc) error {
	list := s.list
	for e := list.Front(); e != nil; e = e.Next() {
		switch value := e.Value.(type) {
		case gapSliceChunk:
			for _, v := range value {
				if err := walkFn(v); err != nil {
					return err
				}
			}
		default:
			if err := walkFn(value); err != nil {
				return nil
			}
		}
	}
	return nil
}

func reconstructPath(came_from map[Coord]Coord, current_node Coord) []*Move {
	list := list.New()
	for present := true; present; _, present = came_from[current_node] {
		next_node := came_from[current_node]
		list.PushFront(findMove(current_node, next_node))

		current_node = next_node
	}

	// Convert to a list and return
	rtn := make([]*Move, list.Len())
	i := 0
	for e := list.Front(); e != nil; e = e.Next() {
		move := e.Value.(Move)
		rtn[i] = &move
		i++
	}
	return rtn
}

// Add a new service definition to the list. If the definition is added or
// updated, return true.
func (l *serviceList) Add(service *ServiceDef) bool {
	list := (*list.List)(l)
	for iter := list.Front(); iter != nil; iter = iter.Next() {
		e := iter.Value.(*ServiceDef)
		res := service.compare(e)
		if res > 0 {
			continue
		} else if res < 0 {
			list.InsertBefore(service, iter)
			return true
		} else if e.connId == service.connId {
			// Replace the definition if it is from the same connection.
			iter.Value = service
			return true
		}
		// Equal entries but from a different connection.
		return false
	}
	list.PushBack(service)
	return true
}

//查看某状态的任务
func taskView(w http.ResponseWriter, r *http.Request) {

	status := r.FormValue("status")

	reg := regexp.MustCompile(status_requ)
	if reg.MatchString(status) == false {
		io.WriteString(w, "need param status, status must be 0-new task ,1-success,2-can not get rdb,3-parse fatal, 4-get remote redis password error or 5-task is running!")
		return
	}

	int_stat, _ := strconv.ParseInt(status, 10, 32)

	mark, list := dbutil.FetchTask(int(int_stat))

	if mark == 1 {
		var listHtml string = "<body><ol>"
		for e := list.Front(); e != nil; e = e.Next() {
			task, ok := e.Value.(dbutil.Task)
			if ok {
				//获取task信息
				host := task.Host
				port := task.Port
				filterLength := task.FilterLength
				filterKey := task.FilterKey
				taskId := task.TaskId
				createTime := task.CreateTime
				listHtml += "<li>" + "host:" + host + ";port:" + port + ";filterLength:" + strconv.FormatInt(int64(filterLength), 10) + ";filterKey:" + filterKey + ";taskId:" + taskId + ";create_time:" + createTime + "</li>"
			} else {
				//task的类型不正确
				return
			}
		}
		listHtml = listHtml + "</ol></body>"
		io.WriteString(w, listHtml)
	} else {
		io.WriteString(w, "error occure !")
		logs.Log("error occure in taskView!")
	}
}

//根据taskId查看某一个task
func task(w http.ResponseWriter, r *http.Request) {

	taskId := r.FormValue("taskId")

	mark, list := dbutil.FetchTaskById(taskId)
	if list.Len() == 0 {
		io.WriteString(w, "without this task !")
		return
	}

	if mark == 1 {
		var listHtml string = "<body><ol>"
		for e := list.Front(); e != nil; e = e.Next() {
			task, ok := e.Value.(dbutil.Task)
			if ok {
				//获取task信息
				host := task.Host
				port := task.Port
				filterLength := task.FilterLength
				filterKey := task.FilterKey
				taskId := task.TaskId
				priority := task.Priority
				status := task.Status
				createTime := task.CreateTime
				listHtml += "<li>" + "host:" + host + ";port:" + port + ";filterLength:" + strconv.FormatInt(int64(filterLength), 10) + ";filter_key:" + filterKey + ";taskId:" + taskId +
					";priority:" + strconv.FormatInt(int64(priority), 10) + ";status:" + strconv.FormatInt(int64(status), 10) + ";create_time:" + createTime + "</li>"
			} else {
				//task的类型不正确
				return
			}
			listHtml = listHtml + "</ol></body>"
		}
		io.WriteString(w, listHtml)
	} else {
		io.WriteString(w, "error occure !")
		logs.Log("error occure in taskView!")
	}
}